Velocity Reviews > Brute force sudoku cracker

# Brute force sudoku cracker

poissonnier@gmail.com
Guest
Posts: n/a

 09-18-2005
Had the same reaction as everyone when I saw theses puzzles a month or
so ago, so here is my solution...
the solve function is recursive, so it can also solve the 'deadlock
set' (example3). find_cell looks for an empty cell with the most filled
cells in it's row and column, so the search tree doesn't grow too
'wide'.

-----------------------------------

example1 = """8 9 - - - - 3 - 4
- - 5 - 3 - - - -
- 7 - - 8 1 5 - -
- 4 - - - 7 - - 3
- - - 5 4 3 - - -
2 - - 1 - - - 5 -
- - 7 9 1 - - 4 -
- - - - 7 - 2 - -
9 - 8 - - - - 7 5"""

example2 = """- 5 2 - - - - - -
9 - - 1 - - - 5 -
- - 4 8 3 - - - 2
- 3 - - 9 - 1 - 5
- - - - - - - - -
5 - 7 - 6 - - 4 -
1 - - - 7 3 6 - -
- 7 - - - 9 - - 3
- - - - - - 2 7 -"""

example3 = """- 3 - 5 - - 8 1 -
1 - - 7 6 - - 9 -
4 - - - - - - - -
8 4 3 9 7 5 1 2 6
- 1 - 6 - - - 7 8
6 - - 8 - 1 9 3 -
- - - 1 5 7 - - 9
- 9 - - 8 6 - - 1
- 6 1 - 9 2 - 8 -"""

class ImpossibleException(Exception): pass

def field_from_string(field_str):
def mapper(x):
if x == '-': return None
else: return int(x)
return [map(mapper, line.split()) for line in
field_str.split('\n')]

def field_from_file(filename):
f = open(filename)
f.close()
return field

def print_field(field):
def mapper(x):
if x == None: return ' '
else: return str(x)+' '
str_rows = [map(mapper, x) for x in field]
str_rows = ['| ' + " ".join(str_row) + '|' for str_row in str_rows]
print 'x'+'-'*27+'x'
print "\n".join(x for x in str_rows)
print 'x'+'-'*27+'x'

def check_constraint(field, (x,y), num):
"""Checks if putting num at (x,y) is valid."""
#row constraint
occ = [elem for elem in field[x] if elem == num]
if occ:
return False
#column constraint
occ = [field[k][y] for k in range(9) if field[k][y] == num]
if occ:
return False
#subfield constraint
sub_x, sub_y = x//3, y//3
occ = [field[k+3*sub_x][l+3*sub_y] for k in range(3) for l in
range(3)
if field[k+3*sub_x][l+3*sub_y] == num]
if occ:
return False
return True

def find_cell(field):
"""Returns coords of an empty cell or None if all cells are filled.
Returns cells with most row and column 'neighbours' first."""
def count(row):
return len([x for x in row if x is not None])

#[(count, index), ... ]
x_counts = zip((count(row) for row in field), range(9))
sorted_x_counts = sorted(x_counts, reverse=True)
x_keys = [l for k,l in sorted_x_counts]

columns = [[field[k][y] for k in range(9)] for y in range(9)]
y_counts = zip((count(column) for column in columns), range(9))
sorted_y_counts = sorted(y_counts, reverse=True)
y_keys = [l for k,l in sorted_y_counts]

for x in x_keys:
for y in y_keys:
if field[x][y] == None:
return (x,y)
else:
return None

def set_value(field, (x,y), num):
"""Returns copy of field with cell (x,y) set to num."""
#new_field = copy.deepcopy(field)
new_field = [row[:] for row in field]
new_field[x][y] = num
return new_field

def solve(field):
xy = find_cell(field)
if not xy:
return field
poss = [e for e in range(1,10) if check_constraint(field, xy, e)]
for e in poss:
new_field = set_value(field, xy, e)
try:
return solve(new_field)
except ImpossibleException:
pass #try next possibility
raise ImpossibleException()

if __name__ == '__main__':
field = field_from_string(example3)
print 'initial field:'
print_field(field)
print 'solution:'
try:
print_field(solve(field))
except ImpossibleException:
print 'not solvable'

Anton Vredegoor
Guest
Posts: n/a

 09-18-2005
Diez B. Roggisch wrote:
> As everyone posts his, I'll do the same It uses some constraint based
> solving techniques - but not too complicated ones. When stuck, it
> backtracks. So far it never failed me, but I haven't tested it too
> thouroughly.

Thanks to all for sharing. I like to program sudoku and review such
code. So below here is my current file, I think it uses some techniques
not yet posted here. It also has a difficult 16x16 puzzle which I know
to be solvable (barring typing mistakes) but which my file can't solve
before I get tired of waiting, this might draw some heavyweights in the
ring

I have also read the sudoku wiki page:

http://en.wikipedia.org/wiki/Sudoku

paper about dancing links was nice, even though I think (but maybe
wrongly so) that we don't need dancing links now that we've got sets,
but it's still a very very interesting paper)

I think the first important step is to realize that some variations
have fewer values so that it is possible to reduce the search space
early. Currently I'm exploring ideas about contigengies as explained in
the wiki above which seems promising, but I haven't found a nice way to
implement them yet. Maybe an easy optimization would be to find values
that don't come up often and choose variations containing those. And
maybe I should switch to an approach that has possibility values inside
the cells instead of computing them on the fly each time, that could
make contigency elimination easier.

Anton

from __future__ import generators
from sets import Set as set

problem1 = ['063000700','000690008','900007002',
'002010080','050806090','090070200',
'600100003','700045000','009000140']

problem2 = ['030009007','010080000','000100090',
'004905006','020000010','500607400',
'050001000','000040020','700500030']

problem3 = ['030500810','000760090','400000000',
'043905006','010000070','600801930',
'000000009','090086000','061002080']

problem4 = ['004530080','060009000','900000005',
'000800350','000000000','027006000',
'800000007','000300040','090072600']

X =[' 1 0 0 0 0 12 0 10 11 7 6 0 0 4 0 0',
' 0 7 0 0 15 13 0 0 0 0 2 0 0 8 0 0',
' 3 0 0 0 4 0 0 0 0 5 0 12 0 16 0 0',
' 0 0 14 2 0 9 0 0 0 0 1 0 0 0 0 0',
'10 15 0 1 0 0 0 2 0 16 0 0 3 0 0 0',
'12 0 0 3 0 0 15 0 0 13 0 4 0 1 9 5',
' 5 0 11 0 7 0 8 0 0 0 0 0 0 15 0 0',
' 7 13 0 16 0 0 0 6 0 0 0 14 0 10 0 0',
' 0 0 13 0 11 0 0 0 10 0 0 0 1 0 12 0',
' 0 0 7 0 0 0 0 0 0 3 0 16 0 14 0 13',
'16 8 0 0 14 0 5 0 0 15 0 0 4 0 0 6',
' 0 0 0 9 0 0 4 0 1 0 0 0 2 0 0 7',
' 0 0 0 0 0 16 0 0 0 0 8 0 10 5 0 0',
' 0 0 4 0 12 0 6 0 0 0 16 7 0 0 0 14',
' 0 0 6 0 0 1 0 0 0 0 12 13 0 0 11 0',
' 0 0 15 0 0 8 11 3 2 0 9 0 0 0 0 1']

problem5 = [row.split() for row in X]

class State:

def __init__(self,solved,unsolved):
self.solved = solved
self.unsolved = unsolved
self.size = int((len(solved)+len(unsolved))**.25)

def choiceset(self,x,y):
"the set of possible choices for an empty cell"
sz = self.size
res = set(range(1,sz*sz+1))
r,c = x/sz*sz,y/sz*sz
for (i,j),v in self.solved.iteritems():
if x == i or y == j or (r<=i<r+sz and c<=j<c+sz):
return res

def celldict(self):
"""dictionary of (cellcoords,choiceset) for each empty cell
if *any* empty cell cannot be filled return an empty dict
to signal an illegal position
"""
res = {}
for x,y in self.unsolved:
c = self.choiceset(x,y)
if not c:
return {}
res[x,y] = c
return res

class Node:

def __init__(self,state):
self.state = state
self.issolved = not bool(state.unsolved)

def children(self):
state = self.state
cd = state.celldict()
if cd: #position is still legal
ml = min([len(x) for x in cd.itervalues()])
#select empty cells which have the minimum number of
choices
items = [(k,v) for k,v in cd.iteritems() if len(v) == ml]
(x,y),S = min(items) #arbitrary choice of cell here
for v in S:
solved,unsolved =
dict(state.solved),dict(state.unsolved)
solved[x,y] = v
del unsolved[x,y]
yield Node(State(solved,unsolved))

def __repr__(self):
R = range(self.state.size**2)
res = [["__" for i in R] for j in R]+['']
for (i,j),v in self.state.solved.iteritems():
res[i][j] = "%02i" %v
return '\n'.join(map(' '.join,res))

def solutions(N):
if N.issolved:
yield N
else:
for child in N.children():
for g in solutions(child):
yield g

def todicts(P):
M = [map(int,row) for row in P]
solved = {}
unsolved = {}
for i,row in enumerate(M):
for j,x in enumerate(row):
if x:
solved[i,j] = x
else:
unsolved[i,j] = x
return solved,unsolved

def test():
solved,unsolved = todicts(problem4)
N = Node(State(solved,unsolved))
print N
for S in solutions(N):
print S

if __name__=='__main__':
test()

Gregory Bond
Guest
Posts: n/a

 09-19-2005

My current solver does 1 level of backtracking (i.e. constant space, and
bounded time) only, and it has been able to solve every puzzle I've
thrown at it. It's based on the usual logic and book-keeping for the
most part. (It also explains how it comes up with each answer step as
it goes, which is handy...)

Once it gets to the stage where it needs to guess, it arranges all the
unknowns then tries them in some arbitary order. It saves the state,
applies the guess (square x,y is N) and then re-applies all the logic
rules. There are 3 possible outcomes from here:

- We've solved it, which is good (this happens surprisingly often....)

- We can't solve it using this guess (so ignore this possibility,
restore the state & try the next guess)

- The Resulting puzzle is badly formed / inconsistant (represented by
a python exception, naturally!) In this case, we know the guessed
square/number is not valid, so we backtrack (restore the state before we
made this guess), remove that possibility (x,y is N) and then apply all
the logic rules again. Often times, this is enough to solve, but it
usually progreses things a little even if it doesn't solve it.

I've not yet found a (9x9) puzzle that this cannot solve. The downside
is that it cannot detect cases where there are multiple solutions.

Antoon Pardon
Guest
Posts: n/a

 09-19-2005
Op 2005-09-16, http://www.velocityreviews.com/forums/(E-Mail Removed) schreef <(E-Mail Removed)>:
>
> Bas ha escrito:
>
>> Hi group,
>>
>> I came across some of these online sudoku games and thought after
>> playing a game or two that I'd better waste my time writing a solver
>> than play the game itself any longer. I managed to write a pretty dumb
>> brute force solver that can at least solve the easy cases pretty fast.
>>
>> It basically works by listing all 9 possible numbers for all 81 fields
>> and keeps on striking out possibilities until it is done.
>> [snip]

>
> This problem is desperately begging for backtracking.

I don't think so. I regularly solve one and I never needed
to try something out, to see if it worked or not except
when there were muliple solutions.

I think it is a beautifull problem, to make people think of
how they could code some of their thought processes, which
would be a more fruitfull experience as programming this
with backtracking.

--
Antoon Pardon

Antoon Pardon
Guest
Posts: n/a

 09-19-2005
Op 2005-09-17, Tom Anderson schreef <(E-Mail Removed)>:
> On Fri, 16 Sep 2005, Bas wrote:
>
>> -any ideas how to easily incorporate advanced solving strategies?
>> solve(problem1) and solve(problem2) give solutions, but solve(problem3)
>> gets stuck...

>
> the only way to solve arbitrary sudoku problems is to guess.

That is strange, in al the puzzles that I have solved untill now,
I never needed to guess, unless the puzzle had multiple solutions,
which personnally I find inferior.

--
Antoon Pardon

Gerard Flanagan
Guest
Posts: n/a

 09-19-2005

Anton Vredegoor wrote:
> I like to program sudoku and review such
> code.

Some non-Python examples:

APL (The Horror! The Horror!...):

http://www.vector.org.uk/archive/v214/sudoku.htm

and my own effort with Excel/C# (very humble - needs work):

http://exmachinis.net/code/cs/2005/08/4.html

Caleb Hattingh
Guest
Posts: n/a

 09-19-2005
Very interesting that sudoku solving appears on the python group - there
is a programming competition at mathschallenge.net (euler) where one of
the puzzles is developing a sudoku solving algorithm...

Actually the python entrants are giving the C guys a good run!

On Mon, 19 Sep 2005 09:12:54 +0200, Antoon Pardon
<(E-Mail Removed)> wrote:

> Op 2005-09-16, (E-Mail Removed) schreef
> <(E-Mail Removed)>:
>>
>> Bas ha escrito:
>>
>>> Hi group,
>>>
>>> I came across some of these online sudoku games and thought after
>>> playing a game or two that I'd better waste my time writing a solver
>>> than play the game itself any longer. I managed to write a pretty dumb
>>> brute force solver that can at least solve the easy cases pretty fast.
>>>
>>> It basically works by listing all 9 possible numbers for all 81 fields
>>> and keeps on striking out possibilities until it is done.
>>> [snip]

>>
>> This problem is desperately begging for backtracking.

>
> I don't think so. I regularly solve one and I never needed
> to try something out, to see if it worked or not except
> when there were muliple solutions.
>
> I think it is a beautifull problem, to make people think of
> how they could code some of their thought processes, which
> would be a more fruitfull experience as programming this
> with backtracking.
>

david.blume@gmail.com
Guest
Posts: n/a

 09-21-2005
Bas, you and I are both a little late to the sudoku python experience.
Here's my feeble attempt:

Excellent strategies are provided by Dan Rice's blog:

You won't find any better solver than this:
http://sudoku.sourceforge.net/

Tom Anderson
Guest
Posts: n/a

 09-21-2005
On Wed, 21 Sep 2005 (E-Mail Removed) wrote:

> Excellent strategies are provided by Dan Rice's blog:

There's an interesting remark in this post:

"Some Sudoku generators skip the step of generating a board altogether.
It's enough to place some random numbers in the board and see if it has a
solution. For a backtracking solver, which can solve puzzles very quickly,
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^
the time wasted analyzing impossible sets of clues will be minor. For a
human-style solver, it seems reasonable to exclude the possibility of
self-contradictory clues by first generating a consistent underlying
board."

He seems to think that backtrackers are faster than reasoners. That's
somewhat counter-intuitive; i wonder if it's really true. It would
certainly be rather sad if it was.

> You won't find any better solver than this:
> http://sudoku.sourceforge.net/

That's a fairly straightforward backtracker. In fact, it's the solver
which inspired me to write mine - which i believe has a more sophisticated
heuristic (i haven't compared them formally, but my heuristic
sophistication estimation heuristic - which is itself, of course, fairly
sophisticated - suggests that it is). Clearly, what we need is a sudoku
solver shootout.

tom

--
everything from live chats and the Web, to the COOLEST DISGUSTING PORNOGRAPHY AND RADICAL MADNESS!!

Tom Anderson
Guest
Posts: n/a

 09-21-2005
On Mon, 19 Sep 2005, Antoon Pardon wrote:

> Op 2005-09-17, Tom Anderson schreef <(E-Mail Removed)>:
>> On Fri, 16 Sep 2005, Bas wrote:
>>
>>> -any ideas how to easily incorporate advanced solving strategies?
>>> solve(problem1) and solve(problem2) give solutions, but
>>> solve(problem3) gets stuck...

>>
>> the only way to solve arbitrary sudoku problems is to guess.

>
> That is strange, in al the puzzles that I have solved untill now, I
> never needed to guess, unless the puzzle had multiple solutions, which
> personnally I find inferior.

Well, if we are to believe Lance Fortnow, a fairly expert comptational
complexionist, that's probably not generally true:

http://weblog.fortnow.com/2005/08/sudoku-revisited.html

It's this bit:

"Since we don't believe that NP has fast probabilistic algorithms, we
expect that there are no efficient procedures to completing a generalized
Sudoku grid"

That makes me think that there probably isn't a non-backtracking method,
since that would almost certainly be polynomial-time.

The thing is, the puzzles you encounter in the wild have been designed to
be solved by humans, using non-backtracking methods; they're much easier
to solve than the general class of Sudoku.

tom

--
everything from live chats and the Web, to the COOLEST DISGUSTING