Principles of Programming Languages - Programming Assignment 2

Due Thursday December 10th

Description

For this assignment you will be writing a Sudoku solver in Prolog. A Sudoku puzzle is a nine by nine grid of numbers (from 1 to 9) with some of the squares in the grid left empty. Additionally the grid is divided into nine three by three sub-grids (usually outlined with a thicker black line). To solve a Sudoku puzzle one must fill in the empty squares with numbers (again from 1 to 9) so that each row, each column, and each sub-grid contains all nine numbers (which means no row, column or sub-grid can contain two or more of the same number.)

Puzzle Representation

If we number each subgrid as if it were a button on a touch-tone telephone (the top three are 1, 2, and 3, the middle three are 4, 5, and 6, and the bottom three are 7, 8, and 9) And then number each of the squares in each subgrid in the same way, we can represent each square as a pair of numbers. We can then represent the numbers on the grid using a predicate called grid with an arity of three. The first argument is the "major" subgrid number, the second is the "minor" square number, and the third is the actual number in each square. Thus, the following puzzle:

could be represented as the following sequence of Prolog facts:

grid(1, 1, 5). grid(1, 2, 3). grid(1, 4, 6).
grid(1, 8, 9). grid(1, 9, 8). grid(2, 2, 7). 
grid(2, 4, 1). grid(2, 5, 9). grid(2, 6, 5).
grid(3, 8, 6). grid(4, 1, 8). grid(4, 4, 4). 
grid(4, 7, 7). grid(5, 2, 6). grid(5, 4, 8). 
grid(5, 6, 3). grid(5, 8, 2). grid(6, 3, 3). 
grid(6, 6, 1). grid(6, 9, 6). grid(7, 2, 6).
grid(8, 4, 4). grid(8, 5, 1). grid(8, 6, 9).
grid(8, 8, 8). grid(9, 1, 2). grid(9, 2, 8). 
grid(9, 6, 5). grid(9, 8, 7). grid(9, 9, 9).

Solving a Puzzle

A number of strategies may be employed to solve a Sudoku puzzle, but we will stick with the good old fashioned method of brute force. More specifically we can solve a puzzle by repeatedly guessing numbers to fill in the empty square, making sure to follow the rules about rows, columns, and sub-grids. Once we have a suitable guess for an empty square, we add the guess to our database and repeat the process. If we get to a point where every number will violate one of the rules for a given empty square, we must backtrack and try a different number for a previous empty square. Once our database has an entry for each square we are done.

In Prolog we can implement a solve predicate that makes a guess, inserts the guess into the puzzle, and recursively solves the result. To add an entry to our puzzle we can use the assert predicate to add a fact to our database:

assert(grid(1,3,1)).

To remove an entry to our puzzle we can use the retract predicate to remove a fact from our database:

retract(grid(1,3,1)).

If we want to clear the database entirely (which you may need to do directly in the Prolog interpreter) we can use the retractall predicate to remove all facts matching a given pattern from our database:

retractall(grid(X,Y,Z)).

The solve predicate must pick a major and minor number, make sure there isn't already an entry in our puzzle at that square, pick a number to write to that square that doesn't violate any of our rules, add that number to our database, and recursively call itself. If no number can be found for a given square we must backtrack and remove the last entry from our database. If no empty squares are left we can display the solution and exit. Here is my implementation of the solve predicate:

solve :-
        valid_number(Major), 
        valid_number(Minor), 
        not(grid(Major, Minor, _ )), !,
        pick_number(Major, Minor, Number),
        try_to_add(Major, Minor, Number).
solve :- print_grid( [[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[1, 2, 3], [4, 5, 6], [7, 8, 9]] ).

try_to_add(Major, Minor, Number) :-
        assert(grid(Major, Minor, Number)),
        solve.
try_to_add(Major, Minor, Number) :-
        retract(grid(Major, Minor, Number)), 
        fail.

Note the use of the cut predicate ! to commit to a location in the grid. The try_to_add predicate adds the entry to our puzzle using assert, then recursively calls the solve predicate to continue solving the puzzle. If the solve predicate fails, Prolog backtracks to the last try_to_add call, triggering the second rule which retracts the most recent assertion, and calls the fail predicate. This triggers a retry of the pick_number predicate. If pick_number runs out of numbers, the current call to solve fails and we retract the previous assertion. Once a solution is found, the second solve rule prints out the puzzle.

Your job for this assignment is to correctly implement the pick_number predicate. It must make sure that given major and minor coordinates, a number is chosen that does not violate any of the rules described above. When asked for another answer, it should choose another number if one exists, or fail if one does not.

Helper Predicates

I have implemented some helper predicates in this file that you may find useful for implementing the pick_number predicate.

valid_number: This predicate can be used in two ways. It can verify that a given number is an integer between 1 and 9, and it can also be used to iterate through the list of nine numbers. (try the query ?- one_to_nine(X). and see what happens if you keep typing semicolons after each response)
same_row: This predicate determines whether or not two major or minor coordinates correspond to the same row. For example, coordinates 1 and 3 are in the same row, but 1 and 4 are not (again think of a telephone keypad).
same_column: This predicate determines whether or not two major or minor coordinates correspond to the same column. For example, coordinates 1 and 4 are in the same column, but 1 and 3 are not.
print_grid, print_major_row, etc.: These predicates use the write and nl predicates to print the puzzle in a readable format.

Handing in Your Program

Please email your solution including my solve predicate and any helper predicates you used to ncolema2 at mix dot wvu dot edu. You do not need to hand in a printed copy.