[Algorithms]N-queens (Chess Puzzle)

 

알고리즘, 연습 또 연습

 알고리즘적 사고를 한다는건 정말 어려운 일이다. 인간은 컴퓨터와는 다르게 생각하기 때문이다. 일련의 모든 과정들을 일일이 명령하고 알려줘야만 컴퓨터는 사고할 수 있다. 이번에 다룰 알고리즘 또한 만만치 않은 퍼즐이다.

 지난 세기의 대결, 이세돌과 알파고와의 대결은 엄청났다. 알파고는 어떻게 바둑을 뒀을까? 물론 딥러닝과 같은 컴퓨터 기술을 구현하는건 아니지만 체스보드를 활용해서 꽤 유명한 알고리즘 퍼즐을 풀어봤다. 

 

 우리는 체스의 규칙을 알지만 컴퓨터는 모른다. 그렇기 때문에 각각의 경우마다 어떻게 체스를 둬야할 지 하나하나 길을 알려주어야 하는 것이다. 그 중, 체스의 가장 강력한 말인 퀸을 구현해본다. 여기서 말하는 N은 체스보드의 크기이며, 어떠한 보드의 사이즈(NxN)가 오더라도 퀸의 공격범위에 다른 퀸이 들어갈 수 없다. 그렇게 퀸이 몇개가 들어갈 수 있는지, 또 그 경우의 수는 무엇인지 알아보자.

 

 문제는 전략, 뭘 어떻게?

let ChessBoard =
[
[0, 0, 1, 0],
[0, 0, 0, 0],
[0, 1, 0, 0],
[0, 0, 0, 0]
]

위 코드처럼 체스보드에 하나하나 그려가면서 각 행렬의 좌표를 구해서 퀸의 갯수를 찾아낼 수도 있다. 이번에 우리가 풀어낸 방법은 2차 배열이 아닌 트리구조를 이용해서 풀어보았다. 갑자기 왜 트리구조인가? 싶을 수 있겠지만 전략은 이렇다.

 

가장 먼저 루트를 만들어주고, 이제 그 루트는 (행row, 열column)의 좌표를 가진 자식을 포함하게 된다. 그렇게 모든 자식들 또한 보드의 가장 아래부분까지 N의 숫자만큼 자식을 갖게 된다. 트리구조에서 알수 있듯이 level은 각 행을 말하고 자식은 각각의 열을 말하게 된다.

let queensTree = {
  coordinate: [0, 0],
  children: [
              {
                coordinate: [1, 0],
                children: []
              },
              {
                coordinate: [1, 1],
                children: []
              },
              {
                coordinate: [1, 2],
                children: []
              }
            ]
}

이런 식의 구조를 생각할 수 있다. 쉽게말해서, 체스판에 들어갈 수 있는 모든 경우의 수를 구하는 것이다. 하지만 문제는 만약 N이 8이라면, 8의 8승에 해당하는 경우의 수가 나오게 된다. 천 육백 칠십 칠만 칠천 이백 십 육개가 나오니 사람은 절대로 구할 수가 없다. 중요한점은, 이렇게 무수히 많은 경우의 수를 담는 트리는 만드는 것이 아니라, 퀸이 첫번째 자식에 들어가면 그 퀸의 공격범위를 제외하고 다음 퀸이 들어 갈 수 있는 자리를 찾아서 자식으로 담게 된다. 퀸의 공격범위에 들어오지 않는 조건을 통해서 트리구조가 생성되는 과정에서 퀸이 들어올 수 없는 데이터는 자동으로 걸러지게 되는 것이다. 그리고 자연스럽게 트리구조를 읽어가면서 보드에 표시만 해주면 NxN의 보드에 퀸이 어디에 몇개가 들어갈 수 있는지 알아낼 수 있다.

 

코드로 구현하다

 이틀 동안이나 시간을 들여서 알고리즘을 완성했다. 결코 쉽지 않은 도전이였다. 전략을 짜면서 생각했던 것 보다 괜찮겠는데? 라고 말했는데 작은 경우의 수를 트리구조로 구현하는 것부터 쉽지 않았다. 자식을 더하는 과정에서 원하는 자식의 수가 채워지면 첫번째 자식을 시작으로 반복적으로 채워나가는 것이다. 분명 재귀를 사용해서 해결할 수 있는 부분이였지만 처음에는 자식의 자식으로 들어가지 않고 루트의 자식으로만 모든 경우의 수가 붙어버리는 것이였다. 바이너리 트리에서 노드를 더하는 식으로 자식의 갯수에 제한을 두고, 제한을 넘어가면 첫번째 자식으로 돌아가 그의 자식을 더했다. 그러자 우리가 원하던 모든 경우의 수를 가진 트리가 완성됐다. 한가지 주의해야할 점은 8이상으로 넘어가면 몇시간이 걸리지 모른다. 또는 브라우져의 콜스택이 폭발해버리는 일을 경험하게 될 것이다. 9x9는 1억개가 넘으니까...

 

 정말 어려웠던 부분은 어떻게해야 행과 열에 들어가면 안된다는 조건과 함께 대각선 라인도 비워둬야 한다는 조건을 만족시키냐는 것이였다.  행의 값은 자식으로 들어갈수록 레벨에 따라서 증가하기 때문에(내려간다는 뜻) 부모의 열 값과 겹치지 않는 좌표를 찾으면 행과 열에 겹치지 않는 배열을 찾을 수가 있다. 곰곰히 생각해보니까 대각선도 사실은 그렇게 어려운 조건은 아니였다. 다음 행에서 부모 열 값에 +1 과 -1 을 해주면 바로 오른쪽 아래와 왼쪽 아래쪽에는 다른 퀸을 배치할 수 없다는걸 알수 있다. 그래서 자식들의 열과 부모 열 값에 1을 더하고 뺀 값을 비교하면 어디에 퀸을 둘 수 있을지 알 수 있었다.

 

언젠가는...

이번 알고리즘 퍼즐을 통해서 깊이는 아니지만 실제로 플레이어와 컴퓨터의 대결을 하는 게임이나 여러 앱에서 어떻게 동작하고 반응하는지 알 수 있었다. 언젠가 한번 두 플레이어가 정식으로 체스를 둘 수 있는 게임을 만들어 보고 싶다. 컴퓨터가 수를 자동으로 읽고 말을 배치하고 플레이를 하는 것 까지는 아니어도 사이드 프로젝트처럼 체스게임을 구현해보면 훨씬 많은 것들을 배울 수 있을 것 같다.