CPSC 352 -- Artificial Intelligence -- Fall 2005
Sudoku Sidebar

The Fall 2005 CPSC 352 class did a case study of the 9 x 9 Sudoku puzzle. The original goal was to do a comparative study of various search techniques for solving Sudoku. Although we didn't accomplish as much as we had originally intended, this page presents what we did manage to accomplish. Student reports are linked at the bottom of this page.

Resources: Sudoku Techniques, Tools, and Puzzles

  • Sad Man Software
  • Random Sudoku
  • Sudoku Techniques with source code
  • Sudoku Satori
  • Sudoku.com Puzzles Site

    What We Learned

  • Sudoku puzzles can be solved efficiently without backtracking search by using a knowledge-based approach. This approach implements the various Sudoku solving techniques that we found on the Web. Like other knowledge-based approaches, this one will fail if it encounters a puzzle that requires knowledge that the solver does not possess. (See the results of testing below.)

    Source files: Load sudoku.pl into PROLOG and type "solve".

  • Sudoku puzzles can be solved efficiently using heuristic backtracking search. The only knowledge used in this approach were the basic rules of the Sudoku puzzle. These rules were used to repeatedly update the candidate lists associated with each square of the puzzle. The heuristic was to choose those squares with the shortest candidate lists and make a guess among the candidates, backtracking if necessary. This version solved all the puzzles that we tested it on. (See the results below.)

    Source files: Load heur_sudoku.pl into PROLOG and type "solve".

  • The Genetic Algorithm (GA) approach is not well suited for this type of problem. The Sudoku puzzle is a constraint satisfaction problem. However, unlike other such problems, the Sudoku puzzle allows for only one solution that is determined logically and exactly. It does not allow for approximate solutions.

  • We developed two different GAs using JGAP: Java Genetic Algorithms Package. In one, there are 81 genes on each chromosome, one for each square of the puzzle. The only constraint placed on the squares was that each could store a value from 1 to 9. We used standard single-point crossover and mutation involved picking squares at random and assigning them a random value.

    The source code for SudokuSolver is here. Instructions for using it are here.

  • In the other GA (developed by Ariel Isaacson), each chromosome had 9 genes, each of which consisted of a array containing a permutation of the values 1 through 9, representing one row of the Sudoku puzzle. Crossover swapped elements from each row, preserving the permutation. Mutation swapped random values in a single row or rows.

    The source code for SudokuSolver is here. Instructions for using it are here.

    Student Pages

  • Alexis Dekle ran tests on the simple JGAP GA Sudoku Solver and wrote this report on her results.

  • Emily Foster and Chris Klein ran tests on both PROLOG solvers, the knowledge based version and the heuristic version and wrote this report on their results.

  • Lisa Garvey ran tests on both PROLOG solvers, the knowledge based version and the heuristic version and wrote this report on her results.

  • Ariel Isaacson's report describes the basic elements of her permutation-based GA (in JGAP).

  • Todd Klasik wrote a Java GUI that generates PROLOG files that can be used to input Sudoku puzzles to the PROLOG programs.

  • Matt Corracio and Alec Schmidt provided an analysis of some of the complexities of the Sudoku puzzle and wrote this report.

  • Jay Piette and Shon Urbas wrote extensions to the knowledge-based PROLOG solver. A report describing their work is here.