earticle

영어

There is no known systematic way to solve the Shikaku(partitions) puzzle(PP), which partitions numbers into squares of numerical size on m×n grid cell boards marked on specific cells with number. Conventionally, only a method of first determining the corner or a number with the only square is uniquely. This paper proposes an algorithm that treats numbers as vectors of direction and magnitude and prioritizes the unique vector of magnitude and direction to determine squares. Once the unique vector is determined, it can be changed to a vector with the unique vector among the numbers that ununique vector in the neighborhood, and the rectangle of this unique vector can be determined in a chain rule. This was called the unique vector ripple effect algorithm. Applying the proposed algorithm to 41 benchmarking experimental data showed that puzzles can be solved in polynomial time for all problems.

한국어

특정 셀에 숫자들이 표기된 m×n 격자 셀 보드 판에서 숫자의 크기를 가진 사각형으로 분할하는 시카쿠(분할) 퍼즐을 풀 수 있는 체계적인 방법은 알려져 있지 않다. 기존에는 모서리 부분 우선 결정법 또는 유일한 사각형을 갖는 숫자부터 시작하는 방법만이 알려져 있다. 본 논문에서는 숫자를 방향과 크기를 가진 벡터로 취급하여 유일한 크기와 방향을 가진 유일벡터를 우선하여 사각형을 결정하는 알고리즘을 제안하였다. 유일 벡터가 결정되면 이웃하는 유일 벡터 를 갖지 않던 숫자들 중에서 유일 벡터를 갖는 벡터로 변경되어 이 유일 벡터의 사각형을 연쇄적으로 결정할 수 있다. 이를 유일 벡터 파급효과 알고리즘이라 칭하였다. 제안된 알고리즘을 41개 벤치마킹 실험 데이터에 적용한 결과 모든 문제에 대해 퍼즐을 빠르고 정확하게 풀 수 있음을 보였다.