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.
-any ideas how to easily incorporate advanced solving strategies?
solve(problem1) and solve(problem2) give solutions, but solve(problem3)
gets stuck...
-any improvements possible for the current code? I didn't play a lot
with python yet, so I probably missed some typical python tricks, like
converting for-loops to list expressions.
TIA,
Bas
***********
from itertools import ifilterfalse
problem1 = [' 63 7 ',
' 69 8',
'9 7 2',
' 2 1 8 ',
' 5 8 6 9 ',
' 9 7 2 ',
'6 1 3',
'7 45 ',
' 9 14 ']
problem2 = [' 3 9 7',
' 1 8 ',
' 1 9 ',
' 49 5 6',
' 2 1 ',
'5 6 74 ',
' 5 1 ',
' 4 2 ',
'7 5 3 ']
problem3 = [' 3 5 81 ',
' 76 9 ',
'4 ',
' 439 5 6',
' 1 7 ',
'6 8 193 ',
' 9',
' 9 86 ',
' 61 2 8 ']
#define horizontal lines, vertical lines and 3x3 blocks
groups = [range(9*i,9*i+9) for i in range(9)] + \
[range(i,81,9) for i in range(9)] + \
[range(0+27*i+3*j,3+27*i+3*j) + range(9+27*i+3*j,12+27*i+3*j)
+ \
range(18+27*i+3*j,21+27*i+3*j) for i in range(3) for j in
range(3)]
def display(fields):
for i in range(9):
line = ''
for j in range(9):
if len(fields[9*i+j]) == 1:
line += ' ' + str(fields[9*i+j][0])
else:
line += ' '
print line
def all(seq, pred=bool):
"Returns True if pred(x) is True for every element in the iterable"
for elem in ifilterfalse(pred, seq):
return False
return True
def product(seq):
prod = 1
for item in seq:
prod *= item
return prod
def solve(problem):
fields = [range(1,10) for i in range(81)] #fill with all
posibilities for all fields
for i,line in enumerate(problem):
for j,letter in enumerate(line):
if letter != ' ':
fields[9*i+j]=[int(letter)] #seed with numbers from
problem
oldpos = 0
while True:
pos = product(len(field) for field in fields)
if pos == oldpos: #no new possibilities eliminated, so stop
break
display(fields)
print pos,'possibilities'
oldpos = pos
for group in groups:
for index in group:
field = fields[index]
if len(field) == 1: #if only number possible for field
remove it from other fields in group
for ind in group:
if ind != index:
try:
fields[ind].remove(field[0])
except ValueError:
pass
else: #check if field contains number that does not
exist in rest of group
for f in field:
if all(f not in fields[ind] \
for ind in group if ind!=index):
fields[index] = [f]
break
--
http://mail.python.org/mailman/listinfo/python-list
