스도쿠 퍼즐 풀기
예전에 어디선가 Scala 코드 15줄로 스도쿠 퍼즐을 풀 수 있다는 글을 본 생각이 났다. 어떤 놀라운 알고리즘이 있나 봤는데 알고보니 CSP(Constraint Satisfaction Problem) 라이브러리를 사용한 것이었다. Clojure에서는 core.logic을 사용해 Scala 풀이와 비슷하게 문제를 풀 수 있다.
자세한 내용은 모르지만, 간만히 말하자면 코드에 조건을 기술하고 실행하면 CSP 엔진이 가능한 답을 찾아준다는 것이다. 풀이 코드 대부분은 텍스트 파일을 읽고 보드를 초기화하고 루프를 돌면서 스도쿠 퍼즐을 푸는 것이라 여기서 따로 설명하지 않는다. 핵심은 다음 코드 블록이라 할 수 있겠다.
...
(run* [q]
(== q board)
(everyg #(fd/in % sdnum) board)
(init-board board puzzle)
(everyg fd/distinct rows)
(everyg fd/distinct cols)
(everyg fd/distinct squares))
...
각 행 숫자가 모두 달라야 하고, 각 열 숫자가 모두 달라야 하고, 격자 안의 숫자가 모두 달라야 한다는 조건을 기술했다. 이렇게 조건을 기술하고 돌리면 엔진이 답을 찾아준다. 50개의 스도쿠 퍼즐을 풀었으면 각 해답지에서 맨 왼쪽 위 숫자를 이어붙인 수를 구해 모두 더하면 된다.
실행 결과는 다음과 같다.
p096=> (time (solve)) "Elapsed time: 2904.611072 msecs" 24?02
이건 내가 문제를 푼 게 아니라 core.logic이 푼 것이다. 스도쿠 퍼즐을 푸는 알고리즘은 아직도 모른다.