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.
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?
|Saves Partial Progress||✘|
©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.