Sudoku

Doing Sudoku puzzles manually has some entertainment value, but not nearly as much as writing something to automate the process. And once you've done that you start wondering about algorithms for constructing puzzles too.

Here's my own effort (Python code).

In the tarball, the sudoku9x9 module provides functions to solve and create puzzles (MIT Licensed). The solve and create executables are simple examples of how to use it. There's no nice GUI front end; if you've got a puzzle to solve then you'll have to set up some code as in the solve example.

Example output from a fairly difficult puzzle. Surprisingly few puzzles require any sort of guessing and possible backtracking, but this one did.

Solving:
  2 . .   . . .   . . 4
  . 8 .   . 2 9   . 3 .
  . . 3   . . 7   6 . .

  . 6 2   3 . 8   . . .
  . 4 .   . . .   . 2 .
  . . .   4 . 2   7 1 .

  . . 8   5 . .   3 . .
  . 1 .   2 8 .   . 5 .
  6 . .   . . .   . . 8
Solving puzzle with (53, 424) (unknown cells,excess values)
Eliminated using known cells  : (53, 131)
Eliminated using unknown cells: (47, 115)
Eliminated using known cells  : (47, 104)
Eliminated using unknown cells: (44, 98)
Eliminated using known cells  : (43, 93)
Eliminated using known cells  : (43, 91)
Eliminated using unknown cells: (42, 88)
Eliminated using known cells  : (42, 86)
Eliminated using unknown cells: (38, 75)
Eliminated using known cells  : (38, 73)
Guessing:
Guessing cell (1, 3) : trying 1 from possibilities [1, 6]
  Solving puzzle with (37, 72)
  Eliminated using known cells  : (21, 40)
  Unsolvable
Guessing cell (1, 3) : trying 6 from possibilities [1, 6]
  Solving puzzle with (37, 72)
  Eliminated using known cells  : (37, 68)
  Eliminated using unknown cells: (35, 60)
  Guessing:
  Guessing cell (0, 3) : trying 8 from possibilities [8, 1]
    Solving puzzle with (34, 59)
    Eliminated using known cells  : (33, 52)
    Eliminated using unknown cells: (26, 42)
    Eliminated using known cells  : (22, 30)
    Eliminated using known cells  : (16, 21)
    Eliminated using known cells  : (11, 12)
    Eliminated using known cells  : (0, 0)
    Solved
Solution is:
  2 7 6   8 5 3   1 9 4
  4 8 1   6 2 9   5 3 7
  5 9 3   1 4 7   6 8 2

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

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