#!/usr/bin/python
# Stefan Huber
# 2. September 2006
#Changelog:
# - 01.09.2006: Initial sudoku code
# - 02.09.2006: Added two additional reducing strategies
# - if two equal states on the board are found which are in same row, column or block
# - if a state on board was found and this state doesn't occour in the same row, column or block
# Added bug fix for solving bigger-than-9 sudokus
import os
import sys
import copy
import math
import string
def load(filename):
"""Loading an sudoko state from file which is build like ksudoku files.
- The first line contains the size of the boad
- The following lines contain the sudoku board; a zero indicates unset
- The load also supports characters instead of numbers"""
try:
file = open(filename, 'r')
except IOError:
print "Can't read file " + filename
sys.exit()
try:
line = file.readline()
gamesize = string.atoi(line)
#Check if boardsize is a square-number
smallsize = int(math.sqrt(gamesize))
if smallsize**2 != gamesize:
raise Exception("Size of board is not a square-number")
game = []
for y in range(0,gamesize):
line = file.readline()
game.append([])
for x in range(0,gamesize):
#The character is a digit --> use it as a digit
if line[x].isdigit():
game[y] += [[ string.atoi(line[x]) ]]
#Otherwise de-offset it so that 'a' or 'A' is 1
else:
game[y] += [[ ord(line[x]) % 32 ]]
except IOError:
print "I/O error, invalid format of file"
sys.exit()
except ValueError:
print "Invalid character"
sys.exit()
return game
def printstate(gamestate, expanded=False):
"""Print the gamestate to stdout. If there is only one state
this state will be printed like [4]. If there are more
possible states, the number of states is printed. If there
is a state with a single zero, there is a '.' printed."""
for line in gamestate:
for entry in line:
if entry in [[0], []]:
print ' . ',
elif len(entry) >= 2 and not expanded:
print "%2d " % len(entry),
else:
if expanded:
if len(entry)<=3:
print "%10s" % entry,
else:
print " %5d" % len(entry),
else:
print entry,
print "\n"
print "\n"
def initstate(gamestate):
"""Expand a '0'-state to all possible states"""
length = len(gamestate)
for y in range(0,length):
for x in range(0,length):
if gamestate[y][x] == [0]:
gamestate[y][x] = range(1,length+1)
def findsamestate(gamestate, ry, rx):
"""Return the same gamestate at (rx,ry) at another position
which is right and buttom of (rx,ry) and in same row, column or block
return Truth-value of row, column and block; y, x of the buddy-position"""
length = len(gamestate)
smallsize = int(math.sqrt(length))
for y in range(ry,length):
for x in range(rx,length):
if gamestate[ry][rx] == gamestate[y][x] and [x,y] != [rx,ry]:
#Check if we are in the same row, column or block
srow = ( y==ry )
scol = ( x==rx )
sblock = ( rx/smallsize == x/smallsize and ry/smallsize == y/smallsize )
#If we are, return result
if srow or scol or sblock:
return srow, scol, sblock, y, x
return False, False, False, -1, -1
def reduceat(gamestate, ry, rx):
"""Analyse the state gamestate[ry][rx] and remove states from gamestate
by deterministic implications."""
length = len(gamestate)
smallsize = int(math.sqrt(length))
#The base positions of the block in the array
bx = smallsize*(rx / smallsize)
by = smallsize*(ry / smallsize)
#Try to find 2-touple [a,b] buddies at same row/column/block
# --> so we can remove all occurencies of a and b at the
#corresponding row/column/block
if len(gamestate[ry][rx]) == 2:
#Find a buddy of length 2
srow, scol, sblock, cy, cx = findsamestate(gamestate, ry, rx)
#Found buddy at same row
if srow:
#Remove all occurencies of these values in the row
for x in range(0,length):
if not x in [rx,cx]:
gamestate[ry][x] = filter( lambda v: not v in gamestate[ry][rx], gamestate[ry][x] )
#Found buddy at same col
if scol:
#Remove all occurencies of these values in the row
for y in range(0,length):
if not y in [ry,cy]:
gamestate[y][rx] = filter( lambda v: not v in gamestate[ry][rx], gamestate[y][rx] )
#Found buddy at same block
if sblock:
for dy in range(0,smallsize):
for dx in range(0,smallsize):
if not bx+dx in [rx,cx] or not by+dy in [ry,cy]:
gamestate[by+dy][bx+dx] = filter( lambda v: not v in gamestate[ry][rx], gamestate[by+dy][bx+dx] )
#Search for entries which do not appear in the full row, column or block
#Make sense, if there are at least two entries
if len(gamestate[ry][rx]) > 1:
for state in gamestate[ry][rx]:
#Default: They are not found in row, column or block
srow = scol = sblock = False
#Search for row
for x in range(0,length):
if state in gamestate[ry][x] and x!=rx:
srow = True
break
#Search for col
for y in range(0,length):
if state in gamestate[y][rx] and y!=ry:
scol = True
break
#Seach for block
for dy in range(0,smallsize):
for dx in range(0,smallsize):
if (bx+dx!=rx or by+dy!=ry) and state in gamestate[by+dy][bx+dx]:
sblock = True
break
#Reduce this state
if not srow or not scol or not sblock:
gamestate[ry][rx] = [state]
break
#There is only one state --> remove this one at all corresponding
if len(gamestate[ry][rx]) == 1:
rval = gamestate[ry][rx][0]
#Reduce all states in this row
for x in range(0,length):
if x != rx:
gamestate[ry][x] = filter( lambda v: v!=rval, gamestate[ry][x] )
#Reduce all states in this column
for y in range(0,length):
if y != ry:
gamestate[y][rx] = filter( lambda v: v!=rval, gamestate[y][rx] )
#Reduce all states in the corresponding sub-square
for dy in range(0,smallsize):
for dx in range(0,smallsize):
if bx+dx!=rx or by+dy!=ry:
gamestate[by+dy][bx+dx] = filter( lambda v: v!=rval, gamestate[by+dy][bx+dx] )
def reduceall(gamestate):
"""Call reduce(gamestate, y, x) for all possible (x,y)-pairs"""
length = len(gamestate)
for x in range(0,length):
for y in range(0,length):
reduceat(gamestate, y, x)
def isready(gamestate):
"""Check if the current gamestate is finished"""
length = len(gamestate)
for x in range(0,length):
for y in range(0,length):
# Not ready yet
if len(gamestate[y][x]) > 1:
return False
return True
def iscorrupt(gamestate):
"""Check if the current gamestate is corrupt"""
length = len(gamestate)
for x in range(0,length):
for y in range(0,length):
# Not ready yet
if len(gamestate[y][x]) ==0:
return True
return False
def expandstate(gamestate):
"""Select a state with minimal states but more than one and
make many gamestates by expanding this single state."""
length = len(gamestate)
minx, miny = 0,0
for y in range(0,length):
for x in range(0,length):
#The current stae contains only one state
if len(gamestate[miny][minx]) <= 1:
miny, minx = y,x
if len(gamestate[y][x]) < len(gamestate[miny][minx]) and len(gamestate[y][x]) > 1:
miny, minx = y,x
#array of expanded gamestates
expanded = []
#The states we want to expand
states = gamestate[miny][minx]
for s in states:
#Copy original gamestate and replace the state at (x,y)
ins = copy.deepcopy(gamestate)
ins[miny][minx] = [s]
expanded.append(ins)
return expanded
def solveit(initstate):
"""Solve the initial state, perhaps with guesses"""
#This is the stack where we remember the guesses we want
#to solve. But at initial state only the initstate is on the stack
gamequeue = [initstate]
#Number of reducing
run = 0
while True:
#Increment run number
run += 1
if len(gamequeue) == 0:
raise Exception(" The input file or the code is corrupt. ")
#Get gamestate
gamestate = gamequeue[0]
#Remember old state
oldstate = copy.deepcopy(gamestate)
if os.name == "posix":
os.system('clear')
printstate(gamestate)
else:
print ".",
#Reduce full sudoku
reduceall(gamestate)
#Nothing changed, so we have to guess
#We expand a state to many gamestates
if oldstate == gamestate:
#Fuck, we have to guess
print "[Guessing]"
#Expand the current game state to many others
gamequeue.extend( expandstate(gamestate) )
#Remove the current state, don't work with it again...
gamequeue.pop(0)
#The current state is corrupt, remove it
if iscorrupt(gamestate):
#The last guess was crappy
print "== dead end==="
gamequeue.pop(0)
#We have finished sudoku
if isready(gamestate):
break
print ""
#We have finished
return run, gamestate
if __name__ == "__main__":
if len(sys.argv) <= 1:
print "usage: sudoku.py \n"
sys.exit()
filename = sys.argv[1]
gamestate = load(filename)
print "Initial state"
printstate(gamestate)
initstate(gamestate)
print "Solving..."
run,state = solveit(gamestate)
print "End state:"
printstate(state)
print "Finished with %d reducing steps. " % run