earticle

영어

Kakuro puzzles are NP-complete problems where no way to solve puzzles in polynomial time is known. Until now, a brute-force search method or a linear programming method has been applied to substitute all possible cases. This paper finds a magic rule, a rule for box sizes and unfilled numbers according to sum clues. Based on the magic rule, numbers that cannot enter empty cells were deleted from the box for row and column sum clues. Next, numbers that cannot enter the box were deleted based on the sum clue value. Finally, cells with only a single number were confirmed as clues. As a result of applying the proposed algorithm to seven benchmarking experimental data, it was shown that solutions could be obtained for all problems.

한국어

가꾸로 퍼즐은 다항시간으로 퍼즐을 풀 수 있는 방법이 알려져 있지 않은 NP-완전 문제이다. 지금까지는 가능한 모든 경우수를 대입해 보는 전수탐색 법이나 선형계획법을 적용하고 있다. 본 논문은 박스 크기와 합 실마리에 따른 들어갈 수 없는 숫자들에 대한 규칙인 마법의 규칙을 찾아내었다. 마법의 규칙에 기반하여 빈 셀에 들어갈 수 없는 숫자 들을 행과 열 합 실마리에 대한 박스에서 삭제하였다. 다음으로 합 실마리 값에 기반하여 박스에 들어갈 수 없는 숫자들 을 삭제하였다. 최종적으로 단일 숫자만 존재하는 셀을 실마리로 확정하였다. 제안된 알고리즘을 7개의 벤치마킹 실험 데이터에 적용한 결과 모든 문제에 대해 해를 구할 수 있음을 보였다.