Difference between revisions of "Introduction to Artificial Intelligence (Fall 2007)/Assignment 3/Programming"
(→Assignment) 

Line 1:  Line 1:  
+  [[Category:Introduction to Artificial Intelligence]]  
+  [[Category:Assignments]]  
+  
You are to create a Prolog solver for a simplified (4 x 4) version of [http://en.wikipedia.org/wiki/Sudoku Sudoku].  You are to create a Prolog solver for a simplified (4 x 4) version of [http://en.wikipedia.org/wiki/Sudoku Sudoku].  
Latest revision as of 12:36, 9 November 2007
You are to create a Prolog solver for a simplified (4 x 4) version of Sudoku.
Contents 
The Sudoku Property
A 4x4 matrix is said to have the "Sudoku Property" iff neither the rows, columns, nor the 2x2 submatrices 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.