P91. Scala로 풀어본 Knight's Tour(기사의 여행)

P91 (**) Knight's tour.

Another famous problem is this one: How can a knight jump on an N×N chessboard in such a way that it visits every square exactly once?

Hints: Represent the squares by pairs of their coordinates of the form (X, Y), where both X and Y are integers between 1 and N. (Alternately, define a Point class for the same purpose.) Write a function jumps(N, (X, Y)) to list the squares that a knight can jump to from (X, Y) on a N×N chessboard. And finally, represent the solution of our problem as a list of knight positions (the knight's tour).

It might be nice to find more than one tour, but a computer will take a long time trying to find them all at once. Can you make a lazy list that only calculates the tours as needed?

Can you find only "closed tours", where the knight can jump from its final position back to its starting position?

기사의 여행 문제는 체스에서의 '나이트'가 이동 가능한 방향으로 움직여가며 체스판 전체를 빈틈없이 방문하는 경로를 찾는 문제다.

나이트의 이동 가능 범위

괄호 안의 좌표는 왼쪽 위를 (0, 0)으로 보았을 때.

체스판 전체를 방문한 후 시작 위치로 다시 이동할 수 있는 경로를 '닫힌 여행(Closed tour)',

다시 이동할 수 없는 경로를 '열린 여행(Open tour)' 라고 한다.

위키백과에 따르면 8 x 8 체스판에서 가능한 닫힌 여행의 갯수는 26,534,728,821,064개라고 한다.

따라서 한번에 모든 답을 구할 수는 없다. 

8-퀸즈 문제와 마찬가지로 이 문제를 풀기 위한 많은 알고리즘이 있지만 나는 스칼라의 지연 콜렉션 Stream을 이용, 재귀를 이용한 백트래킹으로 풀어보고자 한다. 

이전 포스트에 적었던 것처럼 이 문제는 

이전 계산까지의 결과를 파라미터로 재귀호출하는 방법으로 Stream을 이용할 수 있다.

한 위치에 나이트를 이동하고 그 위치에서 이동할 수 있는 다음 위치로 이동했을 때를 인위적인 '스택'에 쌓아올려 나가는 것이다.

당연하게도 방문했던 위치로는 다시 이동할 수 없기 때문에 방문하지 않았던 위치로 이동해 나가면 된다. 

나이트의 이동 방향이 특이할 뿐 이전 위치를 다시 방문하지만 않으면 되니 오히려 8퀸즈보다 간단하게 접근할 수 있는 문제다.

하지만 그 전에 생각해보아야 할 점들이 있다.

1. 나이트의 이동 순서

나이트가 이동 가능한 범위는 알고 있다. 하지만 그 중 어떤 위치를 우선적으로 가야 할까?

간단하게 생각해 보자. 

체스판을 칠할 때 지그재그로 칠하는 것과 시계-혹은 반시계 방향으로 칠해 나가는 것이 빠를까?

당연히 시계/반시계 방향으로 칠하는 것이 빠를 것이다.

닫힌 여행의 경우는 조금 다르겠지만 상관없이 답을 빠르게 찾고자 한다면 시계/반시계 방향으로 방문해 나가야 한다.

2. Warnsdorf's rule

Warnsdorf의 규칙은 나이트가 이동 할 때

이동 가능한 위치 중 그 곳으로 이동했을 때 그 다음 이동 가능한 위치가 더 적은 곳을 우선하라는 것이다.

숫자가 적힌 곳은 이동 가능한 곳.

숫자는 그곳에서 그 다음 이동할 수 있는 곳의 갯수

위의 그림으로 더 쉽게 이해할 수 있다. 흰 나이트가 이동 가능한 위치는 6개,

각각의 '다음 이동 가능한 위치'의 갯수는 3, 7, 7, 7, 5, 2개이다.

저 중에서는 다음 이동 가능한 갯수가 가장 적은, 2가 적힌 곳으로의 이동을 우선하라는 것이다.

위키백과에서 좀 더 자세한 설명을 볼 수 있다.

스칼라 코드로 구현하면 아래와 같다.

/**
  * @since 2017-01-26
  */
class KnightTour(n: Int = 8) {

  // 나이트의 '위치'를 위한 튜플
  type Point = (Int, Int)

  /**
    * 나이트가 이동한 경로를 저장해두는 단위로 사용되는 케이스 클래스
    *
    * @param point  현재 위치
    * @param step   이동 횟수
    * @param logSet 지금까지 지나갔던 포인트들의 Set (중복 검사를 위해 사용됨)
    * @param logLst 지금까지 지나간 포인트들의 리스트 (이동 경로)
    */
  case class Log(point: Point = (1, 1), step: Int = 1, logSet: Set[Point] = Set.empty, logLst: List[Point] = Nil)

  // 나이트가 이동할 수 있는 위치들. 왼쪽 위부터 시계 방향으로 적음
  val knightMovePoint = //List((1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2))
                         List((-2, -1), (-1, -2), (1, 2), (2, 1), (1, -2), (2, -1), (-1, 2), (-2, 1))

  /**
    * 파라미터로 입력받은 포인트로부터 이동할 수 있는 위치들의 리스트를 리턴하는 메소드
    * Warnsdorf's rule을 이용해 갈수있는 곳이 더 적은 곳 부터 가기 시작함
    *
    * @param point 현재 위치
    * @return 갈 수 있는 다음 위치
    */
  def getNextPoint(point: Point, logSet: Set[Point] = Set.empty): List[Point] = {

    /**
      * 위치가 체스판 안에 있는지 체크하는 메소드
      *
      * @param point 위치
      * @return 이동 가능한 위치인지 여부
      */
    def pointValidate(point: Point): Boolean = 0 < point._1 && point._1 <= n &&
                                               0 < point._2 && point._2 <= n

    /**
      * 입력받은 위치로부터 이동 가능한 위치들을 리턴하는 메소드
      *
      * @param point 위치
      * @return 이동 가능한 위치의 리스트
      */
    def getPureNextPoint(point: Point): List[Point] = knightMovePoint.map(t => (t._1 + point._1, t._2 + point._2))
      .filter(e => pointValidate(e) && !logSet.contains(e))

    // Warndorf's rule에 따라 그 다음 이동 가능한 위치의 갯수별로 정렬
    getPureNextPoint(point).sortWith(getPureNextPoint(_).length < getPureNextPoint(_).length)
  }


  /**
    * 이동해야 할 곳을 스택으로 쌓아올림.
    * 스택의 가장 윗부분으로는 이동할 수 있는 포인트를 얻을 수 있고
    * 그 포인트들은 다시 스택에 쌓이게 됨.
    *
    * @param moveStack 이동 할 수 있는 포인트들
    * @return 첫번째 결과 #:: 나머지 스택을 이용한 재귀
    */
  def solve(moveStack: List[Log] = List(Log())): Stream[List[Point]] = moveStack match {
    case Log(point, step, logSet, logLst) :: tailStack =>
      if (step == n * n) logLst #:: solve(tailStack) // n * n 회 순회한 경우는 답
      else {
        // 현재 위치에서 다음 이동할 수 있는 위치로 이동한 경우들을 스택의 나머지와 합침
        val newMoveStack = getNextPoint(point, logSet)
          .map(p => Log(p, step + 1, logSet + p, p :: logLst))
        solve(newMoveStack ::: tailStack) // 새로 만들어진 스택을 이용해 재귀
      }

    case _ => Stream.empty
  }
}

방문했던 위치를 기록하기 위해 List와 Set을 모두 사용했는데

List는 경로를 위해 사용했고 Set은 방문했는지 여부를 확인하기 위해 사용했다.

Set을 사용하지 않고 List에서 방문 여부를 확인해도 된다. 단지 Linear한 시간이 소요될 것이다.(둘 중 어느 것이 더 빠른지는 확인해보지 않았다)

스택에 쌓이는 메모리를 생각하면 List만을 사용하는 것이 더 나을지도 모르겠다.

닫힌 여행만을 구해내고자 한다면 결과에 filter를 사용해 결과의 head가(마지막 위치가) 이동 가능한 위치에 시작 위치가 있는지를 확인하면 된다. 하지만 기본 메모리 설정으로 1, 1에서 시작하면 첫 답을 찾기 전에 StackOverFlow가 발생했다.