CSC 421: Algorithm Design & Analysis
Spring 2015

HW5: Hidato and Recursive Backtracking

Hidato (sometimes referred to as Hidoku or Numbersnake) is a logic puzzle game that appears in many newspapers (e.g., Seattle Times), books (e.g., Hidato: 200 Pure Logic Puzzles, and Web sites (e.g., hidato.com). The goal of Hidato is to fill a grid with consecutive numbers that connect horizontally, vertically or diagonally. For example:

Note that grid need not be square and may even have holes. Some of the cells are filled in at the start, and it is up to the player to fill in the remaining cells so that the numbers from 1 to the maximum (here, 79) are connected.

For a person, solving a Hidato puzzle requires complex and careful logical reasoning. However, it turns out that even the most challenging Hidato puzzles can be easily solved by a computer using recursive backtracking. You are to write such a program. Your program should prompt the user for a file that contains the specifications for a puzzle. The first line of the puzzle file should specify the number of rows and columns in the grid. The contents of the grid should be specified next, with double-asterisks representing gaps in the grid and double-dashes representing blank cells. For example, the Hidato grid shown above would be represented as:

10 10 ** ** -- -- 69 -- -- 61 -- -- ** ** ** 68 -- -- -- -- 60 -- -- ** ** ** -- 63 -- 59 -- -- -- -- ** ** -- 1 -- 49 -- 79 15 -- -- 3 2 -- -- 47 -- -- -- -- 10 -- -- -- 43 46 51 -- 24 -- -- 8 -- -- ** ** 52 -- 19 -- 27 29 -- -- ** ** ** -- -- 22 -- 30 -- 35 -- ** ** ** ** -- -- -- 34 -- -- -- ** **

Assuming a solution exists, your program should display the solved grid, with the columns aligned and the correct numbers in place of the blanks. For example:

** ** 67 66 69 70 71 61 75 76 ** ** ** 68 65 72 62 74 60 77 13 ** ** ** 64 63 73 59 58 78 14 12 ** ** 4 1 48 49 57 79 15 16 11 3 2 5 45 47 50 56 17 25 10 9 6 44 43 46 51 55 24 18 26 8 7 42 ** ** 52 54 19 23 27 29 41 40 ** ** ** 53 20 22 28 30 33 35 39 ** ** ** ** 21 31 32 34 36 37 38 ** **

If there is no solution, your program should display a message to that effect.

FOR EXTRA CREDIT: Implement an additional feature that checks to make sure that the puzzle solution is unique. This will involve continuing the search after the first solution is found (i.e., pretending that solution doesn't exist) to see if another solution can be found. If so, your program should warn the user that the puzzle has multiple solutions.