earticle

영어

A puzzle in which a number bulb of a given black cell is placed on a r × c grid cell board with rows and columns, and the bulb is placed to illuminate the white cells without missing, is called an Arkari(light up) puzzle (LUP). LUP is an NP-complete problem that requires exponential time, and it is not known how to find the exact solution of polynomial time. This paper proposed an algorithm to find the exact solution of polynomial time. This paper proposed a rule that places all possible bulbs as initial values and prioritizes the essential required bulbs. In addition, if this rule does not exist, the rule for placing light bulbs in cells that cover the maximum white cells in rows and columns, or in cells that uniquely cover rows and columns was applied. Applying the proposed algorithm to 22 benchmarking experimental data showed that puzzles can be solved in polynomial time for all problems.

한국어

행과 열이 r × c인 격자 셀 보드 판에 주어진 검정 색 셀의 숫자 전구를 배치하여 백색 셀들을 빠짐없이 비추도록 전구를 배치하는 퍼즐을 아카리(전등 밝히기) 퍼즐(LUP)이라 한다. LUP는 지수시간이 필요한 NP-완전 문제로 다항시간 의 정확한 해를 찾는 방법이 알려져 있지 않다. 본 논문은 다항시간의 정확한 해를 구하는 알고리즘을 제안하였다. 제안 된 알고리즘은 초기치로 가능한 모든 전구를 배치하고, 필수적으로 요구되는 전구를 우선적으로 선택하는 규칙을 제안하 였다. 또한 이 규칙이 존재하지 않으면 행과 열의 최대 백색 셀을 커버하는 셀 또는 행과 열을 유일하게 커버하는 셀에 전구를 배치하는 규칙을 적용하였다. 제안된 알고리즘을 22개 벤치마킹 실험 데이터에 적용한 결과 모든 문제에 대해 퍼즐을 빠르고 정확하게 풀 수 있음을 보였다.