TITLE

Sudoku - A sudoku solver

OVERVIEW

This program implements scanning and blocked rows or columns invalidation. It does not consider all effects of multiple number blocking, where a combination of invalid numbers blocks a row or column. In such cases a simple backtracking algorithm continues to solve the sudoku.

SYNOPSIS

  parrot -Ot sudoku.pir [--options] [file]

If no file is given a builtin game is run.

Valid options are:

--version

Print version information and exit.

--help

Print help hint and exit.

--debug

Print debug output and game progress to stdout.

--inv=n..

Print additionally invalid state of given number(s).

--pairs

Print additionally fields with uniqe pairs of numbers.

--builtin=name

Run builtin game. If no name is given a list of builtins is printed.

--nc

Use ncurses for display and single step through progress. Press any key for next display.

DESCRIPTION

The game state is held in multiple views which share one Integer PMC per common position. Thus updating a row sets also the column or square information. These three views are list of lists.

GAME FILES

Game files may contain comments (hash sign in the first column) digits, and dots for empty fields. E.g:

  # std020.sud
  # der standard 020 - leicht
  2.1..678.
  ...2...36
  8.9.3...5
  .7...4..2
  ..6.9.5..
  9..5...6.
  5...4.9.7
  71...3...
  .987..2.3

PARROT

Parrot features used

Parrot OO

The solver is an object as well as the display.

Freeze/thaw

For deep copying the game state for backtracking.

Multi Method Dispatch

The display classes define multiple methods with the name print, which take different types and amounts of arguments.

Libraries

The program uses Getopt/Obj and the ncurses library.

Exception handling

To turn off ncurses just in case.

Variable indices

Column, rows, and sqares have zero-based indices. Squares are numbered from top left to bottom right.

Sudoku Class attributes

rows, cols, sqrs

LoL of 0 = free, 1..9 = number

i_rows, i_cols, i_sqrs

LoL of a bitmask of invalid numbers per field. Bits are starting at bit one not zero.

all

Hash referencing these 6 items - used for backtracking.

opt

The option hash.

disp

Holds an instance of the display class (Dummy, NCurses) to use.

AUTHOR

Leopold Toetsch

COPYRIGHT

Same as parrot.

Advanced checks

Double blocked rows/columns

Consider this one:

  # daily sudoku 16-nov-2005 very hard
  .5..3.9..
  .394.....
  .....964.
  .6...84..
  5.......8
  ..19...2.
  .826.....
  .....576.
  ..5.9..8.

It got solved until here, then backtracking began (and succeeded).

  +---------+---------+---------+
  | 4  5  6 | 8  3  . | 9  .  . |    777 77. 7..
  | .  3  9 | 4  .  . | 8  .  . |    .77 7.. 7..
  | .  .  8 | .  .  9 | 6  4  3 |    ..7 ..7 777
  +---------+---------+---------+
  | .  6  . | .  .  8 | 4  .  . |    .7. ..7 7..
  | 5  .  . | .  .  . | .  .  8 |    7.. ... 7.7
  | 8  .  1 | 9  .  . | .  2  6 |    7.7 7.. 777  <<<<<<<<<<
  +---------+---------+---------+
  | .  8  2 | 6  .  . | .  .  . |    .77 7.. 777
  | .  .  . | 2  8  5 | 7  6  . |    777 777 777
  | 6  .  5 | .  9  . | 2  8  . |    7.7 .7. 777
  +---------+---------+---------+

Have a look at the marked row 5. '3' and '5' can't be in col 1. So '3' and '5' have to be at the right side of the row.

Now take a look at the '7' - invalid positions are shown above already (dumped with the --inv=7 option).

In both squares 0 and 6 the '7' can only be in columns 0 or 1. This implies that a '7' has to be in col 2, row 3 or 4. Looking at square 5, the '7' is also in row 3 or 4. Therefore the '7' in the middle square (4) has to be too in row 5.

Voila we have 3 numbers (3,5,7) which are somewhere on the right side of row 5 and we get a unique number in row 5, col 1 - the '4'.

And then it's easy.

One part (the '7') is implemented in scan_dbl, which boils down this case to the other one below.

Blocking due to multiple others

Given this sudoku:

  # daily sudoku 16-nov-2005 very hard
  .5..3.9..
  .394.....
  .....964.
  .6...84..
  5.......8
  ..19...2.
  .826.....
  .....576.
  ..5.9..8.

Earlier sudoku.pir started backtracking at:

  +---------+---------+---------+
  | .  .  1 | 3  8  5 | .  .  . |
  | 6  8  7 | .  1  . | .  9  . |
  | 2  3  5 | 6  9  7 | .  .  1 |
  +---------+---------+---------+
  | 1  .  . | 9  7  3 | .  5  . |
  | .  7  6 | 5  .  8 | 1  3  . |
  | .  5  . | .  6  1 | .  .  . |
  +---------+---------+---------+
  | 7  1  . | 8  .  . | .  .  4 |
  | .  .  . | 7  .  . | .  1  8 |
  | .  .  . | 1  .  9 | 7  .  . |
  +---------+---------+---------+

In columns 7 the digits (9,5,3) are blocking this column in square 8 so that the digits (2,6) have to be in column 7 too. Which implies that in square 2 we have a unique '7' at row 0, col 7:

  +---------+---------+---------+
  | .  .  1 | 3  8  5 | x  7  y |   (x,y) = (2|6)
  | 6  8  7 | .  1  . | .  9  . |
  | 2  3  5 | 6  9  7 | .  .  1 |
  +---------+---------+---------+
  | 1  .  . | 9  7  3 | .  5  . |
  | .  7  6 | 5  .  8 | 1  3  . |
  | .  5  . | .  6  1 | .  .  . |
  +---------+---------+---------+
  | 7  1  . | 8  .  . | a  .  4 |  (a,b,c) = (3|5|9)
  | .  .  . | 7  .  . | b  1  8 |
  | .  .  . | 1  .  9 | 7  .  c |
  +---------+---------+---------+

Now the tests in "create_inv_n" invalidate illegal positions due to multiple-blocking and other tests are likely to proceed.

Y-WING

(This is partially still TODO)

Given this suduku:

# "unsolvable" 3 - Y-Wing . . . 8 . . . . 6 . . 1 6 2 . 4 3 . 4 . . . 7 1 . . 2 . . 7 2 . . . 8 . . . . . 1 . . . . . 1 . . . 6 2 . . 1 . . 7 3 . . . 4 . 2 6 . 4 8 1 . . 3 . . . . 5 . . .

It started backtracking at:

  +---------+---------+---------+
  | .  3  . | 8  5  4 | .  1  6 |      .. .. 29    .. .. ..    79 .. ..
  | .  .  1 | 6  2  9 | 4  3  . |      .. .. ..    .. .. ..    .. .. ..
  | 4  6  . | 3  7  1 | .  .  2 |      .. .. ..    .. .. ..    .. 59 ..
  +---------+---------+---------+
  | .  4  7 | 2  9  3 | .  8  1 |      56 .. ..    .. .. ..    56 .. ..
  | .  .  . | .  1  7 | 3  .  . |      .. .. ..    45 .. ..    .. .. 59
  | .  1  3 | .  8  6 | 2  .  . |      59 .. ..    45 .. ..    .. .. ..
  +---------+---------+---------+
  | 1  .  . | 7  3  2 | .  .  4 |      .. .. ..    .. .. ..    .. .. ..
  | .  2  6 | 9  4  8 | 1  .  3 |      57 .. ..    .. .. ..    .. 57 ..
  | 3  .  4 | 1  6  5 | .  2  . |      .. .. ..    .. .. ..    .. .. ..
  +---------+---------+---------+

The numbers on the right side are showing squares with unique pairs. Having a look at the columns 7 and 8, we see these pairs (79, 59, and 57)

Let's label these numbers as A, B, and C:

  +---------+---------+---------+
  | .  3  . | 8  5  4 | AC 1  6 |
  | .  .  1 | 6  2  9 | 4  3  . |
  | 4  6  . | 3  7  1 | .  AB 2 |
  +---------+---------+---------+
  | .  4  7 | 2  9  3 | .  8  1 |
  | .  .  . | .  1  7 | 3  .  . |
  | .  1  3 | .  8  6 | 2  .  . |
  +---------+---------+---------+
  | 1  .  . | 7  3  2 | X  .  4 |
  | .  2  6 | 9  4  8 | 1  BC 3 |
  | 3  .  4 | 1  6  5 | X  2  . |
  +---------+---------+---------+

When we now try to fill row 2, column 7 with A or B, we see that at positions X, a C can't be valid. Either it's blocked via the column or directly via the last square. Thus we can eliminate digit 7 from positions X.

TODO

  # daily sudoku wed 28-dec-2005, very hard
  # backtracking
  ...52.63.
  .5.....7.
  9....8..2
  .17..4...
  .9.....6.
  ...8..31.
  1..6....5
  .4.....9.
  .86.95...

This one starts backtracking early. The '6' is an 'X-Wing' like configuration (col 1 and row 2 with a common corner have just 2 possible positions, just one is valid, when you try both). The same happens a bit later with '9'.

  +---------+---------+---------+
  | .  7  . | 5  2  . | 6  3  . |    666 666 666
  | .  5  . | .  .  . | .  7  . |    .66 6.. 666
  | 9  .  . | .  .  8 | .  .  2 |    6.6 6.6 666
  +---------+---------+---------+
  | .  1  7 | .  .  4 | .  .  . |    .66 6.6 666
  | .  9  . | .  .  . | .  6  . |    666 666 666
  | .  .  . | 8  .  . | 3  1  . |    ..6 6.. 666
  +---------+---------+---------+
  | 1  .  9 | 6  .  . | .  .  5 |    666 666 666
  | .  4  . | .  .  . | .  9  6 |    666 666 666
  | .  8  6 | .  9  5 | .  .  3 |    666 666 666
  +---------+---------+---------+

Here is starts backtracking. A possible improvement would be:

  - detect such digit configuration
  - only backtrack try this digit ('6') above

TODO deadly square

See also std331.sud

TODO Generalization

A Sudoku has 2 dimensions and 3 connected views (row, column, and square). There are 1-dim tests, which work for all views. 2-dim tests are a bit more tricky to generalize and not yet done properly.

Basically: as only 2 views are independant, all these tests can work on 2 of 3 views:

  square, row
  square, column
  row, columm

Now the problem is, how to generalize the possible other direction. Let's call it the 'neighbour'. A neighbour is always 'towards' the second view. A row has 9 column neighbours and 3 square neighbours. A square has 3 row and 3 column neighbours. (Maybe neighbour is a bad term as it does contain itself).

scan_dbl can now easily be reviewed and generalized:

For all neighbours (n): If in the view (v0) a digit is valid in only one of (n)'s views: giving (v1), this digit is invalid in the complement of the intersection (v0 & v1).

NB: it seems to be simpler to just hack the code as to utter the idea in $human_lang.

This is trivial if these views are (row, column) as the intersection is just one point, but it is the generalization of the 'inv_1' code.

Another example of a 2-dim test is of course Y-Wing.

Copyright © 2002-2009, Parrot Foundation.