Jump to content

Shikaku

From Wikipedia, the free encyclopedia

Shikaku (四角に切れ, shikaku ni kire) (also anglicised as Divide by Box[1] or Rectangles[2]) is a logic puzzle published by Nikoli.

History

[edit]

The game was invented by Yoshiano Anpuku, a math student at the University of Kyoto, in 1989 and published by Japanese games magazine Nikoli under the name "Shikaku". The puzzle later spread to other publications and has been adapted into video games.[3]

Rules

[edit]
An initial configuration.
A solution.

Shikaku is played on a rectangular grid. Some of the squares in the grid are numbered. The objective is to divide the grid into rectangular and square pieces such that each piece contains exactly one number, and that number represents the area of the rectangle.[4]

Computational complexity

[edit]

Determining whether a given instance of Shikaku has a valid solution has been proven to be NP-complete.[5]

See also

[edit]

References

[edit]
  1. ^ "Shikaku (Divide by Box)". Nikoli. 20 September 2021. Retrieved 2024-05-21.
  2. ^ Milner, Susan. "Chapter 1: Rectangles". Mathematical Logic Puzzles on a Grid (PDF). A Taste Of Mathematics / Aime-T-On Les Mathématiques. Vol. 17. Canadian Mathematical Society. pp. 1–7. ISBN 978-0-919558-30-4.
  3. ^ Bellos, Alex (May 23, 2022). "Inside Japan's Cult-Favorite Puzzle Laboratory". Atlas Obscura. Retrieved May 14, 2024.
  4. ^ Wanko, Jeffrey J. (November 2009). "Japanese logic puzzles and proof". The Mathematics Teacher. 103 (4). National Council of Teachers of Mathematics: 266–271. doi:10.5951/mt.103.4.0266. JSTOR 20876604.
  5. ^ Takenaga, Yasuhiko; Aoyagi, Shintaro; Iwata, Shigeki; Kasai, Takumi (2013). "Shikaku and ripple effect are NP-complete". Congressus Numerantium. 216: 119–127. MR 3220078.