스도쿠 문제 풀이 작성하기 (LiveScript)

user

8년 ago

스도쿠 문제를 풀어주는 프로그램을 만들어보자. 스도쿠 풀이 방법은 여러 접근법이 있지만, 여기서는 가장 간단하게 임의의 한 빈칸에서 출발해서 ‘쓸 수 있는 숫자 후보’들을 하나씩 넣으면서 다음 빈칸으로 이동하는 식으로 진행한다. 여기서 사용할 언어는 Livescript이다.

노드

스도쿠 문제풀이에 사용하고자 하는 방식은 일종의 깊이 우선 탐색이다. 각 칸에서 사용가능한 후보 숫자 중 하나를 적용하고 다른 칸으로 이동한다. 이 때 적용할 수 있는 후보 숫자가 없으면 어딘가 잘못된 것이므로 이전 노드에서 다른 후보 값을 사용하고 재탐색한다.
또한 노드는 1)처음부터 값이 주어진 칸, 2)공란, 3)문제를 푸는 과정에서 값을 쓴 칸으로 구분하게 되는데 이는 ‘색’이라는 속성으로 사용하도록 하겠다. 또 한가지 중요한 것은 노드는 자신의 위치(인덱스)도 저장해야 한다는 점이다. 이를 바탕으로 각 칸을 표현할 노드 클래스를 아래와 같이 정의한다.

class Node
    (@value, @order) ->
        @color = if @value == 0 then \white else \black

유틸리티 함수

스도쿠 문제를 푸는 과정에서의 핵심은 특정한 칸의 위치에서 사용할 수 있는 후보 숫자들을 뽑아내는 것인데 이는 1~9의 숫자에서 다음에 해당되는 숫자를 뺀 나머지가 된다.

같은 세로 줄에 있는 숫자
같은 가로 줄에 있는 숫자
같은 3X3 격자에 있는 숫자

따라서 다음과 같은 유틸리티 함수를 만들어야 한다.

인덱스로 좌표(x, y)를 산출하는 함수
인덱스로 zone 값을 구하는 함수
특정 zone 내의 칸의 인덱스들을 구하는 함수
특정 인덱스와 같은 열의 인덱스를 구하는 함수
특정 인덱스와 같은 행의 인덱스를 구하는 함수

인덱스를 좌표로 변환

인덱스를 좌표로 변환하는 것은 간단하다. 스도쿠는 9×9 영역에서 이루어지는 게임이므로 인덱스값 i를 9로 나눈 몫이 행이되고, 9로 나눈 나머지가 열이 된다.

i2c = (i) -> [i % 9, Math.floor i / 9]

인덱스를 zone으로 변환

인덱스를 좌표로 변환하고 나면, zone을 구하는 것도 간단하다. zone은 다음과 같이 위치한다고 할 때,

  0   1   2
  3   4   5
  6   7   8

y 값을 3으로 나눈 몫이 행의 위치가 되고, x 값을 3으로 나눈 나머지가 열의 위치가 된다. 따라서 아래와 같은 코드로 zone의 번호를 구할 수 있다.

zone = (i) ->
  [x, y] = i2c i
  (Math.floor y / 3) * 3 + (Math.floor x / 3)

인덱스와 동일한 zone에 속한 인덱스 구하기

반대로 zone의 번호를 가지고 해당 zone의 모든 인덱스를 구하는 방법을 생각해보자. 이는 각 zone의 가장 앞 인덱스를 구할 수 있다면 그 위치로부터 가로, 세로로 3개의 9개 인덱스 값을 얻으면 된다.
zone의 첫 칸의 위치는 zone 번호를 z라 할 때 다음과 같이 계산된다.

y : zone의 행 * 27
x : zone의 열 * 3

따라서 i 와 같은 zone에 위치한 인덱스들은 다음과 같이 계산한다.

in-zone = (i) ->
    z = zone i
    zi = (z % 3) * 3 + (Math.floor z / 3) * 27
    [za + m * 9 for m in [0 til 2]].map ->
        [it + n for n in [0 til 2]]
    .reduce (++), []

차집합 계산

그리고 후보숫자를 찾기 위해서 두 배열의 차집합을 구하는 함수를 하나 작성한다.

sub = (xs, ys) -> [x for x in xs when x not in ys]

이제, 필요한 유틸리티 함수들은 준비되었으니, 스도쿠 게임을 풀어보자.

스도쿠 게임 클래스

스도쿠 게임 클래스를 작성할 차례이다. 이 클래스는 크게 세가지 기능을 갖는데,

주어진 일련의 문자열로부터 81개의 숫자를 읽어들여서 스도쿠 판을 구성한다. 이 판은 Node들의 배열이다.
스도쿠 문제를 푼다.
결과를 출력한다.

그리고 문제를 푸는 과정에서 특정 위치에서 가용한 후보 숫자를 뽑아내는 메소드도 하나 있어야 한다.

입력값 파싱하여 스도쿠판 생성

먼저 주어진 문자열 데이터로 스도쿠 판을 구성하는 부분을 살펴보자.

class Sudoku
    (str-data) ->
        @data = str-data.split '' .map (c, i) ->
            new Node (parseInt c), i

특정 위치의 가용한 값 찾기

특정 위치 i에서 가용한 숫자를 찾는 메소드를 작성한다. 가용한 숫자는 아래 세 개 집합을 먼저 구해야 한다.

ar : i와 동일한 행에 있는 값들
ac : i와 동일한 열에 있는 값들
az : i와 동일한 zone에 있는 숫자들

이 세 배열을 합친 후 1~9에서 빼면 가용한 숫자가 나오게 된다. 이미 유틸리티 함수들을 작성해두었으므로 이 부분도 간단하다.

    avaiables: (i) ->
        [x, y] = i2c i
        ar = [0 til 9].map (e) ~> @data[9 * y + e].value
        ac = [0 til 9].map (e) ~> @data[9 * e + x].value
        az = in-zone i .map (e) ~> @data[e].value
        sub [1 to 9], ar++ac++az

문제 풀기

최종적으로 게임을 푸는 로직이다. 이는 재귀적으로 동작하는데

임의의 흰색 칸을 고른다. 만약 흰 칸이 남아있지 않다면 게임을 완료한 것이므로 true를 리턴한다.
만약 가용한 숫자가 없으면 false를 리턴한다.
가용한 숫자가 있다면 그 중 하나를 현재 칸에 쓰고 현재 칸의 색을 회색으로 바꾼다.
그리고 다음 흰 칸으로 넘어간다.
다음 칸이 false를 리턴했다면 다음 가용숫자를 사용해본다. 남은 가용숫자가 없다면 false를 리턴한다.

이런 식으로 돌아간다. 따라서 최종적으로 true가 리턴되면 게임이 풀린 것이고, false가 리턴된다면 문제가 잘못되어 풀 수 없다는 뜻이다.

    run: ->
        nv = @data.filter (.color == \white)
        if nv.length == 0 then return yes
        cv = nv[0]
        for a in @avaiables cv.order
            cv <<< color:\gray, value:a
            if @run! then return yes
        cv <<< color:\white, value:0
        no

결과 출력

최종적으로 결과를 9×9 격자모양으로 생성하는 메소드를 하나 추가한다. 한 행씩 구분자를 이용해서 문자열로 만든다음, 각 행을 역시 구분자로 엮어주면 된다.

    description: ->
        [0 til 9].map (r) ~>
            [0 til 9].map (c) ~>
                @data[c + r * 9].value.to-string!
            .join '|'
        .join '\n' + '-' * 17 + '\n'

테스트

오일러프로젝트에서 가져온 예시 데이터를 이용해서 한 번 실행해보도록 하자.

a = new Sudoku \003020600900305001001806400008102900700000008006708200002609500800203009005010300
a.run!
a.description! |> console.log

결과는 다음과 같다.

4|8|3|9|2|1|6|5|7
-----------------
9|6|7|3|4|5|8|2|1
-----------------
2|5|1|8|7|6|4|9|3
-----------------
5|4|8|1|3|2|9|7|6
-----------------
7|2|9|5|6|4|1|3|8
-----------------
1|3|6|7|9|8|2|4|5
-----------------
3|7|2|6|8|9|5|1|4
-----------------
8|1|4|2|5|3|7|6|9
-----------------
6|9|5|4|1|7|3|8|2

개선점

아무래도 첫 시작 부분에서 영 좋지 못한 선택을 하면 dead end를 확인하는데 까지 많은 비용이 소요된다. 그리고 스도쿠는 올바른 값을 채워나갈수록 문제가 점점 더 단순해지므로 다음 방법을 적용하면 문제를 푸는 속도를 개선할 수 있다.

문제가 항상 풀린다는 가정하에, 최초 주어진 값을 기준으로 가용한 숫자가 1개 밖에 없다면 이 노드들도 해당 값을 적용해서 검은칸으로 만든다. 그리고 새로 추가된 칸의 숫자 덕분에 답이 결정되는 다른 칸들이 나올 수 있다. 이렇게 제약조건을 계속 전파해나가면 빈칸의 수를 줄여서 속도가 개선된다.
흰색 칸 중에서 가용한 숫자의 개수가 적은 쪽을 먼저 선택하면 dead end든 올바른 정답이든 만날 수 있는 확룰이 커진다.

전체 소스코드는 다음과 같다.

노드