Sudoku solver: reduction + brute force

[Anton Vredegoor]

ago wrote:

> You can see my amended code in the link above.

Thanks, I will look into it sometime. At the moment I'm at a library
computer, which severely limits my Python options. Meanwhile I have
been thinking about the sudoku problem, maybe it will prompt you, me or
someone else to make some kind of other implementation which would
resemble what I am thinking about now.

Imagine a sudoku representation which is inside a 9x9x9 cube. The
values in the cubes' cells are just 1 or 0. The height of a '1' is
determined by the value in the original (flat) sudoku grid. There are
81 filled cells in the cube, just like in a sudoku solution. If one
would look at the cube from a side it would always be the case that a
filled cell at some depth inside the cube would block your line of
vision wichever column one would be looking at. In a way a sudoku is a
special case of a magic square, and a magic square can be transformed
to this view, and this way it can be seen as the solution to the
problem of making a cube not transparent by filling the minimum number
of cells.

Now such a cube can be mirrored in 48 ways and it would still be the
same 'kind' of solution. Also it would be possible to swap horizontal
layers at will and still have some kind of solution that is the 'same'
in some way. One could also swap vertical layers iff (and only if) one
would stay inside a 3-block group of layers. On the other hand it would
be possible to swap complete 3-block groups of layers (if I'm still
making sense) and maybe there are other symmetries that would leave the
original solution somewhat intact.

Suppose one would be able to generate all these possible symmetries and
only use the 'smallest' representation of the original position, this
'hash code' would consist of just letting Python sort  the possible
'same' cubes and selecting the smallest. It could be used to prevent us
from computing the same cube twice since we could check if we already
saw something with the same hash code.

Now to the optimization part. If we find empty cells in the cube where
there are only few positions in the same row, column, or depth
available, we can limit the search space considerably because cutting
off leaves early is most profitable. Maybe it would even pay off to
consider complete layers and selecting possible fillable cells that
have minimal fillable layers' sums.

Sorry, I guess I'm getting a little bit pataforical here, expect my
Python script any day now :-). It will be implemented as a sparse
matrix based on sets of triplets (3-tuples) where for example tuple
(0,0,0) will mean that the cell with x , y and z coordinate having
value '0', is filled (virtually has a '1' inside, the 'unfilled' cells
in the cube (the zeros) are not represented).

I wonder if I still make sense, it's hard to stay programming Python
without a computer to correct my thinking. Can someone write an
implementation to check my ideas?

Anton