Parks Puzzle is a popular puzzle game that is played on a square grid. A Parks Puzzle consists of an nxn grid with contiguous regions known as parks. The aim of the puzzle is to place trees within parks such that every row, column, and park contains one tree, and no two trees are on squares that border one another. My senior proposal is to show that the associated problem of deciding whether a given configuration of a Parks puzzle is consistent with a solution or not, dubbed PARKS, is NP-Complete. This result lets us meaningfully state that the Parks Puzzle in general is an NP-Complete problem, and that it is highly unlikely that there exist any polynomial time algorithms for the problem. Since I have already found a proof, I am currently working on the kPARKS problem, which is the analogous problem of placing k trees in each row, column and park.<\/p>\n","protected":false},"excerpt":{"rendered":"