earticle

영어

A puzzle that forms a block with the number of cells of each number without adjoining between the same number of blocks so that the sum of the number C of clue numbers c among k cells in rows and columns m × n is C ≤ k is called the Fillomino puzzle (FLP). FLP 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 obtain an accurate solution with the complexity of performing O(c). The proposed algorithm determines clue=1 as a block as an initial value and obtains an initial value that forms a sub-block combining neighboring same clue numbers. A method of forming a sub-block of a vector with a unique direction and size for the initial value was applied. The puzzle could be solved by forming such a unique vector block in a chain rule. Applying the proposed algorithm to 19 benchmarking experimental data showed that puzzles can be solved in polynomial time for all problems.

한국어

행과 열이 m × n인 k개 셀 보드 판에 주어진 단서 숫자 개수 c개의 합인 c에 대해 C ≤ k가 되도록 같은 숫자 블록 간에는 이웃하지 않으면서 각 숫자의 셀 수로 블록을 형성하는 퍼즐을 필로미노 퍼즐(FLP)이라 한다. FLP는 지수시 간이 필요한 NP-완전 문제로 다항시간의 정확한 해를 찾는 방법이 알려져 있지 않다. 본 논문은 O(c) 수행 복잡도로 정확한 해를 구하는 알고리즘을 제안하였다. 제안된 알고리즘은 초기 치로 단서=1을 블록으로 확정하고, 이웃하는 단서 숫자들을 결합한 부 블록을 형성한 초기 치를 얻는다. 초기 치에 대해 유일한 방향과 크기를 가진 벡터의 부 블록을 형성하는 방법을 적용하였다. 이와 같은 유일 벡터 블록 연쇄법칙으로 형성하여 퍼즐을 풀 수 있었다. 제안된 알고리즘을 19개 벤치마킹 실험 데이터에 적용한 결과 모든 문제에 대해 퍼즐을 빠르고 정확하게 풀 수 있음을 보였다.