P90. Scala로 풀어본 N-Queens Problem

P90 (**) Eight queens problem

This is a classical problem in computer science. The objective is to place eight queens on a chessboard so that no two queens are attacking each other; i.e., no two queens are in the same row, the same column, or on the same diagonal.

Hint: Represent the positions of the queens as a list of numbers 1..N. Example: List(4, 2, 7, 3, 6, 8, 5, 1) means that the queen in the first column is in row 4, the queen in the second column is in row 2, etc. Use the generate-and-test paradigm.

대학교 알고리즘 수업에서 꼭 푸는 문제 중 하나인 8 Queens problem이 일반화된 문제다. 

상하좌우, 대각선을 공격 할 수 있는 퀸을 서로 공격할 수 없게 배치하는 문제로 8x8의 체스판은 92개의 답이 존재한다. 

퀸의 이동 가능 범위

주로 백트래킹에 대한 문제로 제시되지만 위키백과를 보면 풀어내기 위한 많은 알고리즘들이 있다. 

나는 일반적인 재귀를 이용한 백트래킹으로 풀어보고자 한다.

책이나 검색으로 만날 수 있는 많은 풀이방법에선 2차원 배열을 이용해 푼다.

우리가 직접 체스판에 놓는 것처럼 배열을 변화시켜가며 푸는 방법인데, 사실 이 문제는 1차원 배열로 간단하게 풀어낼 수 있다.

문제를 풀기 위해 먼저 배경이 되는 생각을 해 보자.

8x8 체스판에서의 답 중 하나

a) 퀸이 놓인 행(왼쪽, 오른쪽 방향)에는 퀸이 놓일 수 없다.

=> 한 행에는 하나의 퀸만 놓일 수 있다. 그러므로 답은 퀸이 놓인 열들을 적은 하나의 리스트로 표현이 가능하다.

List(1, 5, 8, 6, 3, 7, 2, 4) = 각각의 요소는 (A, 1), (B, 5), (C, 8), (D, 6) ... 에 놓였다고 할 수 있음

b) 퀸이 놓인 열(위쪽, 아래쪽 방향)에도 퀸이 놓일 수 없다.

=> N x N의 체스판은 N개의 퀸 위치를 가진다. 그러므로 1 부터 N까지의 숫자들로 답을 나타낼 수 있다.

List(1, 5, 8, 6, 3, 7, 2, 4)에 포함된 수는 1부터 8이다.

c) 지금까지 퀸이 놓인 위치를 이용해 다음 퀸을 놓을 수 있는 위치를 알 수 있다.

예를 들어 파란 부분(C행)에 퀸을 놓아야 하는 차례일 때 

세번째 퀸을 놓아야 하는 상황

1) B행에 놓인 6의 대각선 방향인 5, 7은 이번에 놓을 수 없다. (6 - 1, 6 + 1)

2) A행에 놓인 4의 대각선 방향인 2, 6에도 이번에 놓을 수 없다. (4 - 2, 4 + 2)

C행에 놓을 수 있는 곳은 사용하지 않은 수 (1, 2, 3, 5, 7, 8)에서 이번에 놓을 수 없는 수 (5, 7, 2, 6)를 제외한 (1, 3, 8)이다.

=> 답을 행의 내림차순으로(H부터 A까지) 가지고 있다면 반복문으로 더하거나 뺄 수를 1씩 증가시켜 체크가 가능하다.

이런 생각들을 가지고 간단하게 정리하자면

A) 1부터 N까지 숫자의 리스트를 만든다. 이 수들을 Q라고 하자. B) Q와 지금까지 놓인 퀸의 위치를 비교해 이번에 놓을 수 있는 수들의 리스트인 R을 만든다.     R이 비었다면 이전 단계의 루프로 돌아간다. C) R에서 수 하나를 선택해 I라고 한다. (거기 놓았다고 친다).  D) Q에서 I를 제외한 리스트를 Q'라 한다. E) Q'가 비었다면 지금까지 선택한 수들이 답이 된다.     Q'가 비어있지 않다면 Q'로 B에 돌아가 반복한다.

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

/**
  * @param n 문제에서의 N. N x N 체스판에서의 답을 구한다.
  * @return 문제의 답들이 담긴 리스트
  */
def solve(n: Int): List[List[Int]] = {

  /** 해당 위치에 놓을 수 있는지 여부를 확인하기 위한 함수
    * @param value 체크하고자 하는 위치
    * @param log 지금까지 놓은 퀸들
    * @param offset 대각선 값을 계산하기 위해 사용되는 조정치
    * @return 놓을 수 있는지 여부
    */
  @tailrec
  def validate(value:Int, log:List[Int], offset:Int = 1):Boolean = log match {
    case h::t =>
      if(value == h - offset || value == h + offset) false
      else validate(value, t, offset + 1)
    case Nil => true // 더 이상 놓은 퀸의 위치가 없다면 true.
  }

  /** 답을 구하기 위해 재귀호출되는 함수
    * @param selectable 선택 가능한 수
    * @param log 지금까지 퀸을 놓은 열의 리스트
    * @return N개의 수를 모두 사용해 만든 답
    */
  def solveRec(selectable: List[Int], log: List[Int] = Nil): List[List[Int]] = {
    if(selectable.isEmpty) List(log) // N개의 수를 모두 사용했다면 답.
    else selectable.withFilter(validate(_, log)) // 이번에 놓을 수 있는 위치를 구함
                   .flatMap{i => solveRec(selectable.filterNot(_ == i), i::log)}
      // 선택 가능한 수 중 하나를 선택하고 재귀호출
  }

  solveRec((1 to n).toList) // 1부터 N까지의 값을 선택 가능한 수로 답을 구하기 시작함
}

문제를 풀어 답을 리턴하는 solve 함수에 '놓을 수 있는 위치인지를 리턴하는 validate 함수'와 

'답을 구하기 위해 재귀호출되는 solveRec 함수'를 Nested Function으로 구현했다. 

1부터 N까지의 수들은 Set을 사용하면 더 나쁜 성능을 보였다. Scala Collections Performance 문서를 보면 HashSet의 Lookup은 effectively constant time을 보장한다고 했는데, 들어간 수가 적어 Linear Time보다 더 좋지 못한 성능을 보인다고 생각한다.

예전 C로 풀었을 때는 100줄이 넘는 끔찍한 코드가 되었던 것 같은데 1/10의 코드라니. 참 묘한 일이다.