SUDOKU: Sudoku Puzzle Solver/Generator

  1. Introduction
  2. Using SUDOKU
  3. Output

Introduction

Sudoku is a logic-based number-placement puzzle. The objective is to fill a 9×9 grid so that each column, each row, and each of the nine 3×3 boxes (also called blocks or regions) contains the digits from 1 to 9 only one time each. The puzzle provides a partially completed grid (http://en.wikipedia.org/wiki/Sudoku). The following is an example of a Sudoku puzzle:

Its solution given by SODOKU is given below:

SUDOKU is a Gendex module for solving/generating Sudoku puzzle. It uses an unpublished exchange algorithm of its author and can solve Sudoku puzzles of different grid sizes: 4x4, 6x6, 8x8 and 9x9 (see http://www.menneske.no/sudoku/eng/). The box sizes which correspond to each mentioned grid size are 2x2, 2x3, 2x4 and 3x3 respectively.

For a given Sudoku puzzle of grid size nxn, the mentioned exchange algorithm minimizes the objective function f* where f*=f-n2 and f is the sum of the number of times each digit occur with itself and other digits having the same values in each row and in each column. Users who are familiar with design theory can see that f is sum of the trace of NN' (concurrence matrix of column components of the grid) and trace of MM' (concurrence matrix of row components of the grid). The 2-exchange algorithm swaps the positions of two digits in a replicate. The 3-exchange algorithm swaps the positions of three digits in a replicate. When f becomes 0, the solution is obtained.

Note: SUDOKU is designed to solve a Sudoku puzzle of any size. However, it is much more successful with puzzle of size 9x9 or less.

Using SUDOKU

Let's assume all Gendex class files are in the directory c:\gendex and suppose you want to find the solution for Sudoku puzzle in the previous Section. At the working directory, create a file say s9x9.txt with missing cells replaced by 0's. 

 5   3   0   0   7   0   0   0   0
 6   0   0   1   9   5   0   0   0
 0   9   8   0   0   0   0   6   0
 8   0   0   0   6   0   0   0   3
 4   0   0   8   0   3   0   0   1
 7   0   0   0   2   0   0   0   6
 0   6   0   0   0   0   2   8   0
 0   0   0   4   1   9   0   0   5
 0   0   0   0   8   0   0   7   9

At the working directory, type the following command at the command prompt (case is important): 

java -cp c:\gendex sudoku

The SUDOKU window will pop up. Enter s9x9.txt in the File field, the random seed in the Seed field and the number of tries in the No. of tries field. Note that the default random seed is the one obtained from the system clock and the default number of tries is 100000. You can change these default values if you wish to. The default algorithm is 3-exchange (which includes both 2- and 3-exchange). Again, you can change this default setting. Now, click START and SUDOKU starts searching for the solution of the puzzle. The following is an example of a Sudoku puzzle with grid size 8x8: 

 8   0   5   0   2   0   1   0
 4   0   1   0   0   0   0   7
 2   0   0   0   0   0   4   0
 0   0   0   1   5   0   0   0
 0   0   0   4   6   0   0   0
 0   6   0   0   0   0   0   8
 1   0   0   0   0   4   0   5
 0   3   0   2   0   6   0   1

Its solution given by SODOKU is given below:

To generate a Sudoku puzzle, you have to leave the File field blank and specify (i) the grid size (either 9x9, 8x8, 6x6 or 4x4) and the number of empty cells. Below is a generated Sudoku puzzle for the gird size 8x8 with 30 missing cells.

Output

When SUDOKU is used to solve a Sudoku puzzle, the SUDOKU output screen contains the result of the best try at a particular point of time. Information for this try includes:

  1. Try number;
  2. Try grid size;
  3. The random seed used;
  4. The number of iterations;
  5. f, the objective function. The program automatically stops when f=0.
  6. The Sudoku solution;
  7. The time in seconds SUDOKU used to construct the above design.

©2009 Design Computing