:: The Journal of the Institute of Internet, Broadcasting and Communication ::, Vol.17 No.4 | (2017) pp.155~161
스도쿠 퍼즐을 위한 이진역추적 알고리즘
Abstract
본 논문은 지금까지 NP-완전 문제로 다항시간 알고리즘이 존재하지 않는 스도쿠 퍼즐 문제의 해를 다항시간 으로 구하는 알고리즘을 제안하였다. 제안된 알고리즘은 빈칸들에 [1,2,⋯,9] 중에서 행, 열과 블록에 존재하는 실마 리 숫자를 제외한 후보 집합을 초기치로 설정하였다. 빈칸의 후보 집합에 대해 Stuart이 제시한 기본적인 규칙들과 더불 어 2개의 추가 규칙을 제시하고, 마지막으로 이진 역추적 기법(BBT)을 적용하였다. 다양한 부류의 해를 갖는 실험데이 터들에 대해 적용한 결과 제안된 BBT 알고리즘은 어떠한 부류의 해를 갖던지에 상관없이 주어진 스도쿠 퍼즐을 풀 수 있음을 보였다.
This paper suggests polynomial time solution algorithm for Sudoku puzzle problem. This problem has been known NP (non-deterministic polynomial time)-complete. The proposed algorithm set the initial value of blank cells to value range of [1,2,⋯,9]. Then the candidate set values in blank cells deleted by preassigned clue in row, column, and block. We apply the basic rules of Stuart, and proposes two additional rules. Finally we apply binary backtracking(BBT) technique. For the experimental Sudoku puzzle with various categories of solution, the BBT algorithm can be obtain all of given Sudoku puzzle regardless of any types of solution.
Sudoku,NP-Complete,Single value,Unique value,Common value
