문제 출처 : 한국 스도쿠 공식 카페 (http://cafe.daum.net/sudoku4u)

 

사실 요즘 햅틱2 에 내장되어 있는 스도쿠 월드 터치가 빠져 있다가 답을 찾아 주는 프로그램을 만들어 보았습니다.

프로그램 화면은 왼쪽 그림과 같습니다.

총 81개의 버튼이 있고, 버튼을 클릭한 후 숫자를 입력하면 됩니다.
스도쿠 문제를 모두 입력하면 Run 이라는 버튼을 누르면 빠른 속도로 답을 찾아 줍니다.

답은 아래와 같습니다.

위의 문제는 스도쿠 카페에서 5단계로 올라온 문제 중 하나입니다.
머리로 계산하면 머리 터집니다.
역시나 프로그램을 작성하여 돌리니 1초도 안 걸리는 군요.

작성 언어는 C#이고 .NET Framework 2.0을 사용하였습니다.

알고리즘은 N-queen Problem과 비슷한 Back Tracking인데, 속도 향상을 위해 Recursive function을 사용하지 않고,
적절한 후보(candidate)를 구한 후 stack을 이용해 Back tracking 하도록 하였습니다.

스도쿠를 빨리 풀기 위한 여러 가지 규칙이 존재하지만, 아주 기본적인 것만 사용하여도 답을 찾는 시간은 그리 걸리지 않았습니다.

2008. 12. 1 인스톨러 버전으로 배포합니다.
언인스톨은 제어판의 프로그램 추가/제거에서 하시면 됩니다.