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개 벤치마킹 실험 데이터에 적용한 결과 모든 문제에 대해 퍼즐을 빠르고 정확하게 풀 수 있음을 보였다.

목차

요약
Abstract
Ⅰ. 서론
Ⅱ. 관련 연구와 문제점
Ⅲ. 유일 벡터 파급효과 알고리즘
Ⅳ. 실험 결과 및 분석
Ⅴ. 결론
References

키워드

저자

• 이상운 [ Sang-Un Lee | 정회원, 강릉원주대학교 과학기술대학 멀티미디어공학과 ] Corresponding Author

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국인터넷방송통신학회 논문지 [The Journal of the Institute of Internet, Broadcasting and Communication]

• 간기

  격월간

• pISSN

  2289-0238

• eISSN

  2289-0246

• 수록기간

  2001~2025

• 십진분류

  KDC 326 DDC 380