본 논문은 지금까지 NP-완전 문제로 다항시간 알고리즘이 존재하지 않는 스도쿠 퍼즐 문제의 해를 다항시간으로 구하는 알고리즘을 제안하였다. 제안된 알고리즘은 빈칸들에 [$1,2,{\cdots},9$] 중에서 행, 열과 블록에 존재하는 실마리 숫자를 제외한 후보 집합을 초기치로 설정하였다. 빈칸의 후보 집합에 대해 Stuart이 제시한 기본적인 규칙들과 더불어 2개의 추가 규칙을 제시하고, 마지막으로 이진 역추적 기법(BBT)을 적용하였다. 다양한 부류의 해를 갖는 실험데이터들에 대해 적용한 결과 제안된 BBT 알고리즘은 어떠한 부류의 해를 갖던지에 상관없이 주어진 스도쿠 퍼즐을 풀 수 있음을 보였다.
본 논문은 지금까지 NP-완전 문제로 다항시간 알고리즘이 존재하지 않는 스도쿠 퍼즐 문제의 해를 다항시간으로 구하는 알고리즘을 제안하였다. 제안된 알고리즘은 빈칸들에 [$1,2,{\cdots},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,{\cdots},9$]. Then the candidate set values in...
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,{\cdots},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.
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,{\cdots},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.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 장에서는 어떠한 종류의 해를 갖는 스도쿠 퍼즐에 대해서도 해를 구할 수 있는 알고리즘을 제안한다. 제안된 알고리즘은 SS1과 SS2에서 적용된 기본적인 규칙인 성공 열쇠와 성공적 감소 열쇠 범주에 속한 규칙들을 적용하고, 추가적으로 매우 성공적 감소 열쇠와 50% 성공 열쇠의 범주를 적용하여 빠르게 해를 구할 수 있도록 하였다.
한국에서도 수많은 스도쿠 서적이 나오고, 네이버에서 매일 하나씩 스도쿠 문제를 제공할 정도로 스도쿠는 두터운 매니아층을 가지고 있으며, 2010년 3월 애플 선정 ‘새롭고 주목할 만한 어플’, 한국 애플 앱스토어 1위, 미국 애플 앱소토어 퍼즐 20위 등을 차지하고 있다. 이와 같이 방송통신의 발전에 따른 퍼즐 등의 앱들이 점차 수요가 증대되는 사회적 현상에 발맞추어 본 논문에서는 스도쿠 퍼즐을 푸는데 있어서 규칙(법칙)이 존재함을 밝히고, 이 법칙에 따라 퍼즐을 보다 쉽게 풀 수 있는 방법을 제안한다.
제안 방법
본 논문에서는 SS1과 SS2의 기본 규칙인 NS/NP/NT/NQd/NQt,HS/HP/HT/HQd/HQt,PP/PT에 추가로 2가지 규칙을 제안하고, 마지막으로 이진 역추적(binary backtracking, BBT)을 추가한 방법으로 O(n2)의 다항시간으로 스도쿠 퍼즐을 푸는 알고리즘을 제안한다.
제안된 BBT 알고리즘은 범주 1을 최우선적으로 적용하며, 범주 1이 없으면 범주 2를 적용한다. 이와 같이 차례로 적용하고 마지막으로 부득이하게 적용할 규칙이 없을 경우 범주 4의 BBT를 적용한다.
제안된 알고리즘은 SS1[13]과 같이 각 빈칸에 [1,2,…,9]의 숫자 중에서 행, 열과 블록에 사전에 배정된 실마리 숫자들을 삭제한 후보 집합(candidate set)을 적용한다.
본 장에서는 어떠한 종류의 해를 갖는 스도쿠 퍼즐에 대해서도 해를 구할 수 있는 알고리즘을 제안한다. 제안된 알고리즘은 SS1과 SS2에서 적용된 기본적인 규칙인 성공 열쇠와 성공적 감소 열쇠 범주에 속한 규칙들을 적용하고, 추가적으로 매우 성공적 감소 열쇠와 50% 성공 열쇠의 범주를 적용하여 빠르게 해를 구할 수 있도록 하였다.
제안된 알고리즘은 n2-k개 빈칸의 후보집합에 대해 다음의 4개 범주 열쇠들을 적용한다.
대상 데이터
본장에서 제안하는 이진 역추적 알고리즘(BBT)은 다음의 후보 집합 이론과 4개의 범주를 가진 열쇠에 기반하고 있다. 4개의 열쇠 범주는 성공 열쇠(success key), 성공적 감소 열쇠(success reducing key), 매우 성공적 감소 열쇠(very high success reducing key)와 50% 성공 열쇠(half success key)이다.
본 논문은 빈 칸들에 [1,2,…,9]의 숫자들 중 행, 열과 블록에 존재하는 실마리 숫자들을 제외한 후보 집합을 이용하였다.
이론/모형
본 장에서는 스도쿠 퍼즐들 중 난해한 그림 4의 실험 데이터들에 대해 BBT 알고리즘을 적용하여 본다.
본 논문은 빈 칸들에 [1,2,…,9]의 숫자들 중 행, 열과 블록에 존재하는 실마리 숫자들을 제외한 후보 집합을 이용하였다. 후보 집합에 대해 Stuart[13]의 기본 규칙들을 적용하고, 추가적으로 2개의 규칙과 이진 역추적 기법을 적용하였다.
성능/효과
본 논문에서는 다양한 부류의 스도쿠 퍼즐 문제들에 대해 실험을 수행한 결과, 제안된 BBT 알고리즘은 유일해, 회피 불가능 해, 다중 해의 어떠한 해 유형을 갖는 스도쿠 문제 뿐 아니라 실마리가[1,2,…,9] 중 7개 숫자만 포함된 경우에 대해서도 해를 구할 수 있음을 보였다.
질의응답
핵심어
질문
논문에서 추출한 답변
스도쿠 퍼즐은 무엇을 생성하고자 하는가?
스도쿠 퍼즐은 유일 해(unique solution)를 갖도록 유효한(valid) k-실마리 스도쿠 퍼즐을 생성하고자 한다[2]. 그러나 문제를 풀면 유일 해를 갖는 경우는 극소수에 불과하고, 대부분은 회피 불가능 집합(unavoidable set)이 존재하는 다중 해(multiple solution)를 갖는 경우[1]와 회피 불가능 집합은 존재하지 않지만 별개의(distinct) 다중 해를 갖는 경우[3]도 발생할 수 있다.
전형적인 스도쿠 퍼즐은 어떤 형태인가?
전형적인 스도쿠 퍼즐(Sudoku puzzle)은 n×n(n=9)개의 정방행렬 형태를 취하고 있으며, 행렬 내에 3×3의 9개의 블록으로 분할되어 있다. 스도쿠 문제는 문제를 풀 수 있도록 사전에 주어진 숫자를 실마리 (clue)라 하며, 스도쿠 퍼즐은 k개의 실마리가 주어진 상황에서 m2-k개의 빈칸(blank cells)의 각 행, 열과 블록에 [1,2,…,9]의 숫자가 중복되지 않도록 배정하는 문제이다[1].
스도쿠 퍼즐 게임에서 어떤 경우도 발생할 수 있는가?
스도쿠 퍼즐은 유일 해(unique solution)를 갖도록 유효한(valid) k-실마리 스도쿠 퍼즐을 생성하고자 한다[2]. 그러나 문제를 풀면 유일 해를 갖는 경우는 극소수에 불과하고, 대부분은 회피 불가능 집합(unavoidable set)이 존재하는 다중 해(multiple solution)를 갖는 경우[1]와 회피 불가능 집합은 존재하지 않지만 별개의(distinct) 다중 해를 갖는 경우[3]도 발생할 수 있다.
참고문헌 (16)
G. McGuire, B. Tugemann, and G. Givario, "There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem," School of Mathematical Sciences, University College Dublin, Ireland, pp. 1-36, Jan, 2012. arXiv: 1201.0749
The Physics arXiv Blog, "Mathematicians Solve Minimum Sudoku Problem," http://www.technologyreview.com/view/509091/best-of-2012-mathematicians-solve-minimum-sudoku-problem/, MIT Technology Review, Jan. 2012.
J. P. Delahaye, "The Science Behind Sudoku," Scientific American, Vol. 294, No. 6, pp. 80-87 Jun. 2006, doi:10.1038/scientificamerican0606-80
H. H. Lin, and I. C. Wu, "Solving the Minimum Sudoku Problem," International Conference on Technologies and Applications of Artificial Intelligence (TAAI), pp. 456-461, Nov. 2010, doi:10.1109/TAAI.2010.77
A. M. Herzberg and M. R. Murty, "Sudoku Squares and Chromatic Polynomials," Notices of the American Mathematical Society (AMS), Vol. 54, No. 6, pp. 708-717, Jun. 2007.
B. Felgenhauer and F. Jarvis, "Enumerating Possible Sudoku Grids," http://www.afjarvis.staff.shef.ac.uk/sudoku.pdf, 2005.
T. Yato and T. Seta, "Complexity and Completeness of Finding Another Solution and Its Application to Puzzles," IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol .E86-A, No. 5, pp. 1052-1060, May 2003, ISSN: 0916-8508
E. R. Maria and Z. Toroczkai, "The Chaos Within Sudoku," Scientific Reports, Vol. 2, pp. 1-8, Oct. 2012, doi:10.1038/srep00725.
E. S. Reich, "Mathematician Clams Breakthrough in Sudoku Puzzle," Nature News, Jan. 2012, doi:10.10.1038/nature.2012.9751
Wikipedia, "Algorithmics of Sudoku," http://en.wikipedia.org/wiki/Algorithmics_of_Sudoku, Wikipedia Foundation Ltd., 2015.
J. F. Crook, "A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles," Notices of the American Mathematical Society (AMS), Vol. 56, No. 4, pp. 460-468, Apr. 2009.
A. Stuart, "Sudoku Solver for Android and iPhone: Sudoku Solver for Mobile Devices. Ver. 1.97," http://www.sudokuwi ki.or g/sudoku.htm, Syndicated Puzzles Inc, Jul. 2013.
M. Swain, "World's Hardest Sudoku Puzzle: It's the Most Baffling Brainteaser Ever Devised... Can You Solve it?," http://www.mirror.co.uk/news/weired-news/worlds-hardest-sudoku-puzzle-ever-942299, Jun. 2012.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.