P97. Scala로 풀어본 Sudoku(스도쿠)

P97 (**) Sudoku. (alternate solution)

Sudoku puzzles go like this:

주어진 스도쿠 퍼즐을 푸는 알고리즘을 작성하는 문제다.

스도쿠의 룰은 모두가 아는 것처럼 간단하다. 

9 x 9의 스도쿠 퍼즐 판이 있을 때 가로 방향으로 1에서 9까지의 숫자, 

세로 방향으로도 1에서 9까지의 숫자만을 포함하고 작은 섹션에서도 1에서 9까지의 숫자만을 가지면 된다.

N-Queens 알고리즘과 마찬가지로 스도쿠를 풀기 위한 알고리즘도 여러가지가 있다. 

가장 유명하고 단순한 방법인 백트래킹부터 제시된 풀이인 Dancing Links(알고리즘 X)와 같은 방법까지 있다. 

나는 N-Queens와 마찬가지로 재귀를 이용한 백트래킹으로 문제를 풀어 보려 한다.

이전 문제들과 마찬가지의 방법으로 풀이가 가능하다. 

숫자를 적어 넣은 보드를 인위적인 스택에 쌓아가면서 경우의 수를 만들고 검증해 나가면 된다.

스도쿠를 풀기 위해 중요한 점 두 가지가 있다. 

첫 번째는 좌표 (X, Y)에 대입 할 수 있는 숫자들을 찾는 것이고,

두 번째는 다음으로 숫자를 대입해야 하는 위치(좌표)를 찾는 것이다.

대입 할 수 있는 숫자들을 찾는 방법은 간단하다. 

1) 1부터 보드 사이즈만큼의 숫자의 Set을 준비한다. (보드에 들어갈 수 있는 수들) 2) 좌표의 행과 열에 포함된(가로, 세로 방향의) 숫자들을 구한다. 3) 좌표가 속한 섹션을 구한다.    섹션은 좌표에서 섹션 크기를 나누고 다시 섹션 크기를 곱하면 된다. (Int 타입의 소숫점 버림을 이용함) 4) 섹션에 속한 숫자들을 구한다. 5) 1에서 2와 4를 뺀다.

숫자를 대입해야 하는 위치를 찾는 방법은 조금 생각해 볼 필요가 있다.

간단하게 (0, 0)부터 (BS - 1, BS - 1)까지 찾아서 바로 대입 할 수도 있지만 

(0, 0) 부터 (BS - 1, BS - 1)까지 찾는 방법.

화살표 방향으로 진행하며 빈 좌표에 숫자를 대입해 본다.

행과 열, 섹션에 숫자가 더 많은, 다시 말해 대입 가능한 수의 개수가 더 적은 위치부터 수를 대입함으로써 

경우의 수를 줄이고 성능을 향상 시킬 수도 있다.

보드의 일부만 계산한 표. 붉은 중괄호에 적힌 숫자는 대입 가능한 수, 검은 대괄호에 적힌 숫자는 좌표.

대입 가능한 수의 개수가 적은 [0, 0] -> [1, 0] -> [1, 2] -> [2, 1] 순으로 대입한다.

사용할 리스트에 대해서도 생각해 볼 필요가 있다. 

리스트의 일정 지점을 선택해 채워나가는 방식이기 때문에 인덱스가 있는 리스트를 사용하는 것이 유리하다.

또, 보드를 스택으로 쌓는 방법을 택한다면 스택 내에서 보드가 수정 될 필요가 없기 때문에 immutable 콜렉션을 선택하는 것이 더 좋다.

스칼라로 구현한 코드는 아래와 같다.

/**
  * @since 2017-03-20
  */
class Sudoku {
  type Board = Vector[Vector[Short]]
  case class Frame(board: Board, points: List[(Int, Int)] = Nil)
  val BOARD_SIZE = 9
  val BOARD_GROUP_SIZE = 3
  val PROBLEM_BOARD: Board = Vector(Vector(0, 0, 4, 8, 0, 0, 0, 1, 7),
                                    Vector(6, 7, 0, 9, 0, 0, 0, 0, 0),
                                    Vector(5, 0, 8, 0, 3, 0, 0, 0, 4),
                                    Vector(3, 0, 0, 7, 4, 0, 1, 0, 0),
                                    Vector(0, 6, 9, 0, 0, 0, 7, 8, 0),
                                    Vector(0, 0, 1, 0, 6, 9, 0, 0, 5),
                                    Vector(1, 0, 0, 0, 8, 0, 3, 0, 6),
                                    Vector(0, 0, 0, 0, 0, 6, 0, 9, 1),
                                    Vector(2, 4, 0, 0, 0, 1, 5, 0, 0))

  // 문제 스도쿠 보드와 방문할 좌표의 순서를 적은 스택 첫 번째 값.
  val firstFrame = List(Frame(PROBLEM_BOARD, getEmptyPoints(PROBLEM_BOARD)))

  /**
    * 체크할 스도쿠 보드의 좌표들을 찾는 첫 번째 방법.
    * (0, 0) 부터 (BS - 1, BS - 1) 순서로 찾는다.
    *
    * @param board 체크할 스도쿠 보드
    * @return 아직 값이 선택되지 않은 보드의 좌표들
    */
  def getSimpleEmptyPoints(board: Board): List[(Int, Int)] = {
    val lst = for{row <- 0 until BOARD_SIZE
                  col <- 0 until BOARD_SIZE
                  if board(col)(row) == 0} yield (row, col)
    lst.toList
  }

  /**
    * 체크 할 스도쿠 보드의 좌표들을 찾는 두 번째 방법.
    * 빈 곳의 좌표와 선택 할 수 있는 숫자의 갯수를 구한 후
    * 대입 할 수 있는 수의 갯수 오름차순으로 정렬한다.
    *
    * @param board 체크할 스도쿠 보드
    * @return 대입 할 수 있는 수의 갯수가 적은 순서로 정렬된,
    *         아직 값이 채워지지 않은 좌표들
    */
  def getEmptyPoints(board: Board): List[(Int, Int)] = {
    val lst = for{row <- 0 until BOARD_SIZE
                  col <- 0 until BOARD_SIZE
                  if board(col)(row) == 0
                  numCount = getNextNum(board, (row, col)).size } yield ((row, col), numCount)

    lst.sortBy(_._2).map(_._1).toList
  }

  /**
    * 보드의 좌표에서 선택 가능한 값의 목록을 얻는 메소드
    *
    * 소숫점을 버리는 Int 타입의 특성을 이용해
    * 그룹의 시작 위치를 구할 수 있다.
    *
    * @param board 체크할 스도쿠 보드
    * @param point 체크할 좌표. (row, col).
    * @return 다음으로 선택 가능한 값들
    */
  private def getNextNum(board: Board, point: (Int, Int)): Set[Short] = {
    val rowNums = board(point._2).toSet
    val colNums = board.map(_ (point._1)).toSet
    val groupNums = {
      val (groupRow, groupCol) = ((point._1 / BOARD_GROUP_SIZE) * BOARD_GROUP_SIZE,
        (point._2 / BOARD_GROUP_SIZE) * BOARD_GROUP_SIZE)
      for {row <- groupRow until groupRow + BOARD_GROUP_SIZE
           col <- groupCol until groupCol + BOARD_GROUP_SIZE} yield board(col)(row)
    }.toSet

    (1 to BOARD_SIZE).map(_.toShort).toSet -- rowNums -- colNums -- groupNums
  }


  /**
    * 스도쿠를 풀기 위한 메소드.
    * 지금까지 적은 보드를 이용해 다음 위치를 선택하고
    * 그 위치에 가능한 값 별로 스택을 만들어 쌓아가며 문제를 해결한다.
    *
    * @param stack 값을 하나씩 대입한 스도쿠 보드 스택
    * @return 찾은 정답이 적힌 스도쿠 보드
    */
  @tailrec
  final def solve(stack: List[Frame] = firstFrame): Option[String] = stack match {
    case Frame(board, points) :: frameTail =>
      if(points.isEmpty) Some(boardToString(board))
      else {
        val (row, col) = points.head
        val newStacks = getNextNum(board, points.head).map { num =>
          Frame(board.updated(col, board(col).updated(row, num)), points.tail)
        }.toList
        solve(newStacks ::: frameTail)
      }
    case Nil => None
  }

  /**
    * 스도쿠 보드를 출력 할 수 있는 문자열로 변환하는 메소드
    *
    * @param board 변환할 보드
    * @return 변환된 보드 문자열
    */
  private def boardToString(board: Board): String = {
    val sb = StringBuilder.newBuilder

    for(col <- 0 until BOARD_SIZE){
      if(col % BOARD_GROUP_SIZE == 0) sb.append("---------------------------------\n")

      for(row <- 0 until BOARD_SIZE){
        if(row != 0 && row % BOARD_GROUP_SIZE == 0) sb.append(" | ")
        if(board(col)(row) == 0) sb.append(" . ") else sb.append(s" ${board(col)(row)} ")
      }

      sb.append("\n")
    }
    sb.append("---------------------------------\n").toString()
  }

}

우리가 사용하는 좌표계, 그러니까 row - colum의 순서와 2차원 리스트의 좌표계가 다르다는 것을 염두해 둘 필요가 있다.

리스트 안에 리스트가 있기 때문에 첫 번째 값은 colum, 두 번째 값이 row의 index가 된다.

apply와 update에 effectively constant time이 소요된다는 immutable Vector를 사용했다.

스도쿠 보드의 크기가 작아 eC time의 Vector보다 Linear time의 리스트들을 사용하는게 성능이 더 좋을 수 있을 것이라 생각한다.

보드를 출력 가능한 문자열로 변환하는 boardToString 메소드는 굉장히 자바스럽게 느껴진다.

뭐, 이런 코드를 사용 할 수 있는 것도 스칼라의 장점으로 볼 수 있을 것 같다.(아마도)