Review: Impuzzible - Monochromatic Rectangles Puzzle for iPhone and iPad

If you want to play hands-on with a complex mathematical problem, look no further than Impuzzible - Monochromatic Rectangles Puzzle.

The stated goal is pretty simple: change the color of the blocks (choosing among four colors) in such a way that there are no rectangles whose four corners have the same color. The grids get increasingly larger, so how far can you go before giving up?

Solving the first 2x2 grid is trivial, and initially everything looks fine and dandy. The game helpfully highlights the rectangles that don't respect the requirements, and you just need to fix them to proceed.

The game can even seem to be too easy, because it looks like you just need to randomly tap the corners of the wrong rectangles to quickly find a solution. Going up to 10x10 took me little effort.

Continuing to go up, however, becomes increasingly difficult. It starts to become common that every time you tap a corner to remove a rectangle, you create a new rectangle of a different color.

Simple logic isn't going to help you here. Finding a solution involves either random tinkering, or very advanced math.

This is a great way to experiment with a NP-complete problem, and see how much its difficulty is increased by each apparently small increase in the size of the grid.

The game description on the App Store is slightly incorrect. It states: "No one knows how far you can go, but the largest grid for which a solution is known is 18 by 18 (level 17)". It has actually been proven in this paper that no solution exists for 19x18, so 18x18 is the maximum.

Finding solutions for the larger grids took a long time. William Gasarch, one of the authors of the paper above, offered a prize in 2009 to whoever found a 17x17 solution. The solution was eventually found in 2012 by Bernd Steinbach and Christian Posthoff, after some very advanced research explained in this paper, and it wasn't just 17x17 but 18x18.

You can learn more about this problem here and here. All very interesting reads.

The challenge is open: how far can a human go, without the help of a computer?

Summary

Nontrivialness	★★★★★
Logical Reasoning	★☆☆☆☆
User Interface	★★★☆☆
Presentation	★★☆☆☆
Loading Time	★★★★★
Saves Partial Progress	✘
Status Bar	✘

©2014 Nicola Salmoria. Unauthorized use and/or duplication without express and written permission is strictly prohibited. Excerpts and links may be used, provided that full and clear credit is given to Nicola Salmoria and nontrivialgames.blogspot.com with appropriate and specific direction to the original content.