CSE 471/598 – Introduction to Artificial intelligence

Project I – Requirement Specifications

Problem Solving Agent for Sudoku

Deadline: TBA

 

 

In this project you will solve the popular Sudoku Puzzle using various search algorithms.

 

Related links: http://en.wikipedia.org/wiki/Sudoku

                        http://websudoku.com/

 

Sudoku  Puzzles

Sudoku puzzle is most frequently a 9×9 grid, made up of 3×3 subgrids called "regions" or “blocks” (like the figure above). Some cells already contain numerals, known as "givens" (or sometimes as "clues"). The goal is to fill in the empty cells, one numeral in each, so that each column, row, and region contains the numerals 1–9 exactly once.  

 

There is one variant like a 6×6 grid, made up of  six 3×2 subgrids. The goal is to fill in the empty cells, one numeral in each, so that each column, row, and region contains the numerals 1–6 exactly once.  The following is one example.

3

 

2

4

 

5

1

 

 

 

 

3

 

5

 

 

3

 

 

3

 

 

2

 

6

 

 

 

 

2

5

 

3

1

 

6

 

Usually, there is a unique solution to the Sudoku puzzle.

 

Task I: (75 pts)

This task is to solve a 6×6 sudoku. Your LISP program should contain a function named “sudoku” which should take two parameters, the input file as the 1st parameter and the name of the search method as the 2nd parameter. The function then should return two values: the 1st is the solution of the puzzle, and the 2nd value should be the time taken for the search. (You can use  “values” to return multiple values and “get-internal-real-time” for calculating cpu-time)

 

The format for the input file and the output values is given below.  

The search methods your program should support are:

  1. Depth First Search (function argument- DFS) (25 points)
  2. Breadth First Search (function argument- BFS) (25 points)
  3. Heuristic-based search (function argument- HEURISTIC) (25 points)

 

You should define your own heuristics for the heuristic-based search.

 

Input File Format

The corresponding input for the 6×6 sudoku above would be:

3 0 2 4 0 5

1 0 0 0 0 3

0 5 0 0 3 0

0 3 0 0 2 0

6 0 0 0 0 2

5 0 3 1 0 6

where 0 denotes an empty cell.  Basically, it is a 6×6 matrix with each entry separated by a white space and each line corresponding to one row.

 

The function “sudoku” will be called in the following format:

(sudoku “c:\\sudoku.txt” ‘DFS)

 

And the values returned should be like: 

#2A((3 6 2 4 1 5) (1 4 5 2 6 3) (2 5 1 6 3 4) (4 3 6 5 2 1) (6 1 4 3 5 2) (5 2 3 1 4 6)) 10
where the 1st value returned is a 2-dimentional array (actually a 6×6 matrix), the 2nd value 10 is the time taken for search.
 

 

Task II (Extra Credit 15pts):

This task is pretty similar to task I. Instead of solving a 6×6 sudoku, you need to solve a 9×9 sudoku. Your LISP program should contain a function named “sudoku-9” which should take two parameters, the input file as the 1st parameter, the name of the search method as the 2nd parameter. The function then should return two values like task I:  the 1st is the solution of the puzzle, and the 2nd value should be the time taken for the search.

 

The search methods your program should support are:

1.      Depth First Search (function argument- DFS-9) (5 points)

2.      Heuristic-based search (function argument- HEURISTIC-9) (10 points)

 

Again, heuristics plays a very important role here. You should define your own heuristics.

The input would be a txt file of a 9×9 matrix with each entry separated by a white space. The empty cell is denoted by 0.

 

The function “sudoku-9” should be called in the following format:

(sudoku-9 “c:\\sudoku-9.txt”, ‘DFS-9)

 

And the values returned should be like:

#2A ( ( 4 5 2 1 3 7 8 9) ….)   100

where the first value is a 2-dimentional array (actually a 9×9 matrix), and the 2nd value 100 is the time taken for search.

 

 

Project Submission Guidelines

  • You should submit "one" LISP file named {last name}-{first-name}.lisp
  • Submit the file through Assignment section in myASU.
  • Please make sure that the file is in simple text format and not in document (Microsoft Word or some other document) format.
  • The first line in the file should be your name. Please comment it.
  • If you want to label portions of your code as solution to part one, part two, etc., or you want to write the problem statement in the lisp file (it is not needed, you can do it if you feel it is convenient for you), please make sure that they are all commented properly.
  • There should be no syntax errors in the program (like forgotten closing brackets, misplaced semicolon unmatched double quotes, etc.,)
  • Please try to comment whatever code you have written for debugging purposes. The function execution calls like (sudoku “C:\\input.txt” 'DFS) should all be commented.
  • Make sure your program executes in Allegro lisp (ideally it should execute in clisp too).
  • Don't use #t it is something from Scheme and not part of Ansi Lisp. Allegro Lisp supports it but clisp doesn't.
  • Please don't change the package name or create functions in different package.
  • Please follow the lisp style guide available at http://www.lisp.org/table/style.html

Also, you are supposed to turn in a hardcopy report either in class or at the CSE department office. The report should be brief and contain the following:

  • Problem Statement
  • Design – Data Structure Design and Algorithm design
  • Discussion on any one aspect of the project of your interest. It could be anything like why your heuristic is admissible, its efficiency and efficacy or any other better search strategy for the problem.

 

Grading

 

The distribution of grades for the project:

Code – Task I    75 pts

Project Report – 25 pts

Extra Credit -     15 pts