The Parks puzzle
The Parks puzzle is a Sudoku-like game that is played on a square grid containing different coloured regions known as parks. The objective is to place trees on some of the squares in such a way that each column contains c trees, each row contains r trees, and each park contains r trees. In addition, the trees must be placed so that no two trees are adjacent or diagonally adjacent, as if they were kings on a chessboard. The picture shows a solution to the puzzle in which c=r=2, meaning that each row, each column, and each park contains precisely two trees.
It only takes a few seconds to check whether the solution of the Parks puzzle given earlier is correct, but finding such a solution is a different story. Suppose for example that we are trying to solve the puzzle above, which has six rows, six columns, and six parks, with the parameters c=r=1. The objective in this case is to place the trees in nonadjacent squares in such a way that each row, each column, and each park has a single tree. The yellow park has a single square, so there must be a tree in F2 if a solution exists. Row 1 is entirely red, so the tree in row 1 must be the only tree in the red park. Similarly, column A is entirely red, so the tree in column A must be the only tree in the red park. It follows that the tree in the red park is in the square A1.
The tree in the green park cannot be in column F, because that column already contains a tree. The tree in the cyan park must be in E5 or E6, which means that the tree in the green park cannot be in column E, and also that the tree in the brown park cannot be at D5 or D6 (marked with a Y and a Z). Less obviously, the tree in the green park cannot be at D4 (marked with an X) because there would be nowhere to put a tree in row 5: there cannot be a tree at A5 or B5 because the red tree has already been placed, there cannot be a tree at C5, D5, or E5 because those squares are too close to X, and there cannot be a tree at F5 because there is already a tree in column F. The green tree is therefore at D3.
Continuing this argument shows that the tree in row 4 must be at B4, the brown tree must be at C6, and the tree in row 5 must be at E5. This shows that the puzzle has a solution, as shown above, and also that the solution is unique.
The recent paper Parks: A Doubly Infinite Family of NP-Complete Puzzles and Generalizations of A002464 by Igor Minevich, Gabe Cunningham, Aditya Karan, and Joshua V. Gyllinsky analyses the computational complexity of the Parks puzzle. The authors give the example of the 8 by 8 grid below with the parameters c=r=2, and leave it as an exercise to the reader to prove that this is the unique solution. (The picture at the top of the post shows the same example.)
As with the 6 by 6 example, checking the solution is easy, but finding the solution from scratch would likely need an argument even more complicated than the one from earlier. The main result of the paper is that the Parks puzzle is NP-complete, which roughly speaking means that the solution to the Parks puzzle is easy to check but hard to find. More precisely, a decision problem is in NP if its solution can be verified easily (meaning “in polynomial time”). The hardest problems in NP are called NP-complete. Any algorithm that can solve an NP-complete problem in polynomial time can also solve any problem in NP in polynomial time. Other games that have previously been proved to be NP-complete include Minesweeper, Sudoku, and Battleships.
Remarkably, the authors prove that the Parks puzzle is NP-complete by showing how to use parks and trees to build logic gates. The picture above and on the left shows how to build an IFF (“if and only if”) gate. The two green parks should be thought of as switches, representing TRUE if the tree is on the left, and FALSE if the tree is on the right. In the left-hand picture, placing the tree to the left in the dark green park forces the yellow tree to be at the top of the yellow park. In turn, this forces the cyan tree to be at the bottom, the purple tree to be on the left, and the light green tree to be on the left. A similar argument applied to the right-hand picture proves that if the dark green tree is placed on the right, then the light green tree also needs to be placed on the right. In this way, the two green switches are forced to synchronize by the rules of the Parks puzzle.
The picture above shows how to build an OR gate, using the green, cyan, and purple parks as switches. If all the switches are set to FALSE, then it is not possible to place a tree in row 7 and the puzzle has no solution. Less obviously, if at least one of the three switches is set to TRUE, then the yellow and brown parks ensure that there is a unique solution to the puzzle.
It is possible, as shown above, to use parks and trees to test more complicated formulae, such as (X∨Y∨Z)∧(¬X∨Y∨W); in other words, “(X OR Y OR Z) AND (NOT-X OR Y OR W)”. Again, the puzzle has a solution if and only if there is some assignment of the values TRUE and FALSE to the variables X, Y, Z, and W that makes the expression evaluate to TRUE. This is an example of the “3-Satisfiability problem”, which is known to be an example of an NP-complete problem.
Picture credits and relevant links
The first four graphics are my own work, and are based on pictures in the paper by Igor Minevich, Gabe Cunningham, Aditya Karan, and Joshua V. Gyllinsky. The tree icon comes from the TikZ package tikzsymbols by Ben Vitecek. The other pictures come directly from the paper.
It is a major open problem in theoretical computer science to decide whether or not the class P of problems that can be solved in polynomial time is equal to the class NP. This is called the P versus NP problem, and is one of the seven Millennium Prize Problems that were posed in 2000 by the Clay Institute. So far, only one of the problems (the Poincaré Conjecture) has been solved.
The A002464 in the title of the paper is a reference to the sequence in the On-Line Encyclopedia of Integer Sequences pertaining to Hertzsprung's problem. This asks for the number of ways to arrange n non-attacking kings on an n by n board, with one in each row and each column.
The Parks puzzle is not only theoretically interesting, but also fun to play. If you would like to try it, you can download the free app Parks Seasons by Andrea Sabbatini.
Substack management by Buzz & Hum.