Introduction to Artificial Intelligence (Fall 2007)/Assignment 3/Programming

Latest revision as of 13:36, 9 November 2007

You are to create a Prolog solver for a simplified (4 x 4) version of Sudoku.

The Sudoku Property

A 4x4 matrix is said to have the "Sudoku Property" iff neither the rows, columns, nor the 2x2 sub-matrices have any duplicate elements. For example, the following matrix satisfies the Sudoku property:

Assignment

You are given a 4x4 matrix that is partially complete; for example:

The object is to fill in the empty elements such that the resulting matrix satisfies the Sudoku Property. Your task is to write a Prolog program that, when given a partial matrix, will fill in the missing elements or&emdash;if no valid assignment of the missing elements is possible&emdash;then it will say so. You may implement this within Prolog however you like.

Example output

Here is an example of what your implementation should be able to do:

?- consult('EvanSultanikSudokuSolver.pl').
% EvanSultanikSudokuSolver.pl compiled 0.00 sec, 7,836 bytes

Yes
?- sudoku([[1,_,3,_],
           [_,_,_,2],
           [4,_,_,_],
           [_,3,_,1]]).

[1, 2, 3, 4]
[3, 4, 1, 2]
[4, 1, 2, 3]
[2, 3, 4, 1]

Yes
?-

Submission

You are to submit your assignment through BbVista. You must include a README file describing how to run your code.

Extra credit

Extend your Sudoku solver to work on "regular" 9x9 Sudoku grids. Depending on your implementation and the nature of the given input, your 9x9 solver may take an inordinate amount of time to solve the problem; this is okay, but more credit will be given to those that have efficient implementations.