:: The Journal of the Institute of Internet, Broadcasting and Communication ::, Vol.24 No.5 | (2024) pp.159~168
숫자 실마리 수지코 퍼즐에 관한 실마리 숫자 조합 교집합 알고리즘
Abstract
3×3의 9개 셀을 가진 격자 보드 판에서 4개 셀을 하나의 블록으로 하는 4개 합 실마리와 C개의 숫자 실마리를 가진 수지코 퍼즐은 다항시간으로 퍼즐을 풀 수 있는 방법이 알려져 있지 않은 NP-완전 문제이다. 이 퍼즐을 풀기 위해서는 (9-C)!의 가능한 모든 경우수를 대입해 보는 전수탐색 법을 적용해야 한다. 본 논문은 빈 셀들에 들어갈 수 있는 후보 숫자들을 축소시키는 방법으로 유일 숫자 셀의 실마리를 확정하였다. 유일 숫자 셀이 더 이상 존재하지 않으면 합 실마리 블록들 간의 교집합 숫자들을 선택하는 방법을 제안하였다. 제안된 알고리즘을 52개 벤치마킹 실험 데이터에 적용한 결과 모든 문제에 대해 퍼즐을 다항시간으로 풀 수 있음을 보였다.
In a grid board with 9 cells of 3X3, the Sujiko puzzle with 4 sum clues and C number clues as one block is an NP-complete problem with no known way to solve the puzzle in polynomial time. To solve this puzzle (9-C)! in all possible cases, a brute-force method should be applied to substitute the number. This paper confirmed the clue of the unique number cell by reducing the number of candidates that can enter empty cells. When the unique number cell no longer exists, a method of selecting the intersection combination numbers between the sum clue blocks has been proposed. Applying the proposed algorithm to 52 benchmarking experimental data showed that puzzles can be solved in polynomial time for all problems.
Sujiko puzzle,Sudoku puzzle,Number clue,Sum clue,Intersection
