Assignment 2B: Solving Sudoku

Assigned: October 5th, 2004
Due: October 19th, 2004, 11:59pm

Background

Sudoku, also known as "Number Place," is a logic game especially popular in Japan but gaining popularity throughout the world. The game is played on a square 9 by 9 grid, split up into 9 square 3 by 3 "sections".The goal of the game is to complete the grid so that each number appears exactly once in each row, column, and region. Further constraints are provided by "givens," fixed numbers that must remain unchanged in the grid.

Below is a sample grid (image taken from Wikipedia):

Sample sudoku puzzle

For more information on the game:

The Task

Since this is a course in artificial intelligence, your assignment is to implement a solver for sudoku games. You are free to use any programming language (within reason), and any applicable method from the class. Possible approaches include:

To make the problem more interesting, you must solve sudoku problems of varying size, not simply the classic 9x9 with 3x3 regions. In the general n^2 by n^2 sudoku problem, the grid is n^2 by n^2 and contains n^2 regions of size n by n. Instead of using the numbers 1-9, the generalized problem uses numbers 1-n^2. In all games, each number must appear exactly once in each row, column, and region.

To give a concrete example, n=3 is the classic sudoku game, n=3. For n=4, the task is to fill a 16 by 16 grid with the numbers 1 to 16, such that no row, column, or 4 by 4 region has the same number twice. For n=1, there exists only one possible game solution.

File Formats

Your program must input and output board description files in the following format:

You are free to make the problem size (n) a command line parameter. We provide you with 50 example problems in each of 3 sizes, at 5 levels of sparsity, along with solutions: sudoku_examples.zip.

Filenames in sudoku_examples.zip can be interpreted as follows:

[problem size]_[sparsity]_[index].[problem or solution]

Problem size:

Sparsity:

Index ranges from 000 to 050, corresponding to the 50 distinct problems at each size.

Files ending in .sol are solutions to the erase00 files. (More sparse versions may have multiple solutions. If multiple solutions exist, your solver should still find one of them.)

Optional Challenges

The possibilities below are wholly optional, but you may find doing them educational and fun. Extra work on assignments such as this one will be remembered when calculating final grades.

  1. Try running using your sudoku solver to generate new sudoku puzzles. What's the largest size puzzle your solver can create?
  2. Try several different solution methods and compare their speeds. What works fastest and why? Are the same methods fastest for small and large puzzles?
  3. websudoku.com offers puzzles of four difficulties: Easy, Medium, Hard, and Evil. Translate some of them into board files and time your solver on them. Is there a correlation between hardness for humans and hardness for your solver? (This may be hard to do if your solver solves them all too quickly. For the constraint satisfaction approaches, you can use the number of consistency checks as a metric. If using WalkSat, look at number of literal flips; for zChaff, look at number of decisions.)
  4. Does removing givens from a problem make it harder? Time your solver (as described in challenge #3) on the erase05, erase10, and erase20 examples, or remove givens yourself.
  5. Create a solver/generator for 3-dimensional sudoku. Or even k-dimensional sudoku.

What To Turn In

Please email to Daniel Lowd (lowd at cs) by Wednesday, October 19th at 11:59pm a zip file or tarball containing:

Last updated: October 5, 2005 11:57
CSE 573, Fall 2005