Number Chain

General description

This is a team assignment.

The "number chain" is a classic paper-and-pencil style puzzle. You are given a 9x9 grid, with some numbers running from 1 to 81 filled in. The goal of the problem is to create a chain of unique integers, running in sequence from 1 to 81, around the grid so that it intersects correctly the numbers that are already there. The chain may go horizontally or vertically, but not diagonally. For example, here is a puzzle and its solution:

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

Your goal is to write a Prolog program to print out a solution to a given puzzle. To get you started, I've created this program, which provides the row, column, and value for initial locations as shown in the above example. (I'm using an indexing system that starts at 1, not 0).

If you wish, you may stop reading here, and proceed on to the assignment. Alternatively, if you want some hints, keep on reading.

Note that the puzzle on the left actually shows you where the 1 is, which helps. It's easier to write a solution if you know where the 1 is. Here is another puzzle (with an an init file to go with it) where the 1 is not included. If you wish to go the easier route and base your solution on the location of the 1, you can earn 9 out of 10 points if you do all else correctly.

Hints and ideas

Here are a list of thoughts based on my own experiences when coding this up, and experimenting with alternatives. Of course, you may come up with a completely different approach, which is awesome! But I can share what I know regarding the approach that I took.

Viewing the above grid is cute, but I found it was much easier to think of the solution chain as a list of coordinates that grew to the left. For example, the above solution, starting with the final spot where the 81 is, would appear as:
```
[[1, 9], [2, 9], [3, 9], [3, 8], [2, 8], [1, 8], [1, 7], ...]]
```
I don't think it really matters which direction this list goes; whichever direction you choose just affects the directionality of other parts of your code. This approach seemed most natural to me because I started building the solution with just one spot (where the 1 went), and then I concatenated onto the left from there.

At any rate, I used this representation throughout my code, and merely wrote a separate predicate called show to display it in a prettier fashion. Here is the predicate I wrote for that:
```
show(Soln) :- reverse(Soln,Forwards), write('\n'),
              member(Row,[1,2,3,4,5,6,7,8,9]),
              write('\n'),
              member(Col,[1,2,3,4,5,6,7,8,9]),
              nth1(Value,Forwards,[Row,Col]),
              write(Value),write('\t'),
              fail.
```
I defined a predicate adjacent(I,J,X,Y) that takes a grid location (defined by a row I and column J), and fills in X and Y with the row and column for an adjacent location. This predicate has multiple ways of filling X and Y in.
The core of my code is a predicate called complete(Partial,Finished) (short for "complete the puzzle"). If I issue the query complete([[8,7],[8,6]],Finished), Prolog fills in for Finished the entire 81 coordinate chain that has the chain I provided in Partial as the starting point. For example, after issuing the above query, Prolog fills in for Finished a chain that looks like:
```
[[1, 9], [2, 9], [3, 9], [3, 8], [2, 8], [1, 8], [1, 7], ...,
 [9, 8], [9, 9], [8, 9], [8, 8], [8, 7], [8, 6]]
```
Alternatively, if I supply a partial sequence that does not lead to a solution, the query fails.

Figuring out how to make complete work was the key challenge. Here is some psuedocode that describes the thoughts I used. I had to handle two different cases, each of which is written as a separate version of the complete predicate. I also had some base cases.

Version A: "the next addition to the chain is in a location whose value was given in the initial setup"
- For the leftmost coordinate in the partial chain, find an adjacent position that is not already a member of the given partial list. That's your candidate for extending the chain.
- Continue only if that position is not already a member of the partial list. If it were a member, I don't want it, because I would be visiting the same spot twice.
- Determines if the puzzle had an initial value at that new position. Continue only if that's the case.
- Verify that the length of the given partial chain, plus 1, is equal to the initial value you found at the new location. This verifies that it is legal to extend the chain to that spot.
- Add the new position onto the left of the given partial list. Recursively try to complete that new list.
Version B: "the next addition to the chain is in a location where no value was provided in the initial puzzle"
- For the leftmost coordinate in the partial chain, find an adjacent position that is not already a member of the given partial list. That's your candidate for extending the chain.
- Continue only if that position is not already a member of the partial list. If it were a member, I don't want it, because I would be visiting the same spot twice.
- Verify that this new position does not have an initial value.
- Calculate the value that would go there as the length of the partial chain, plus 1.
- Verify that the new value that would go into this new position isn't already initialized somewhere else. (Note that this step is unnecessary for getting a correct answer, but was necessary to get my code to run fast enough to get an answer. It prunes large portions of the search tree.)
- Add the new position onto the left of the given partial list. Recursively try to complete that new list.
When debugging, I used the write predicate like crazy. Use it like you would use print statements while debugging in Python. I also used the built-in trace capabiliy. It was also found it critical to debug on very small boards. Create your own sample problem that's on a 2x2 grid, then a 3x3 grid, and so on. Starting right away on the 9x9 grid is madness.
To see if I could find a solution where the 1 is placed in row 4, col 6 (for the sake of argument), that query looks like:
```
complete([[4,6]],Final).
```
Therefore, since I assume that I do not know where the 1 goes, I created a predicated solve(Final) that fills in a solution chain for Final by repeatedly trying complete with different starting locations. Look above at my code for the predicate show for some ideas on how to "iterate" over a variety of combinations of values.
My solution runs nearly instantly on the main sample puzzle I've provided above. For this second sample puzzle, my program produces a solution in about 10 seconds.

Have fun with this! The program is not long. Focus on partial goals. Can you get it work with a chain of length two? Of length three? And again, remember to debug on small puzzles you make up yourself, and only try the big one after you have it working on small examples.

Submitting your work

Make it completely clear how the grader should run your code. Indicate with program comments exactly what the grader should type in order to see your code run and produce a solution.

If you haven't gotten the system completely working, indicate in program comments what does work. For example, if you got an adjacent predicate working directly, say so, and indicate how to test it. Likewise, if your solution works for only certain cases, indicate what those cases are.