Simple Soduku Solver

Here is some quick code for a simple Sudoku solver.

This python script will not work for a Sudoku puzzle where guessing is required; that functionality has not yet been worked in - but it will be.

The Puzzle is solved logically by working out what each cell of the grid could be, based on the well known rules of Sudoku. If there is only one possibility for a cell, you know that that has got to be the value. This process is repeated, after each modification has been made, until the grid is complete.

I tested it using http://www.websudoku.com, and it could solve any of the 'easy' puzzles. It could not get any higher than 'medium'.

The Python Script:

import time

##defs##

#find possibilities for rows
def rowPoss(row):
output = []
for i in range(9):
if not (i+1) in rows[row]:
output.append(i+1)
return output

#############################################

#find possibilitites for columns
def colPoss(col):
output = []
column = []
for i in range(9):
column.append(rows[i][col])
for i in range(9):
if not (i+1) in column:
output.append(i+1)
return output

#############################################

#find possibilities for each square
def squarePoss(square):

###########
#000#111#222#
#000#111#222#
#000#111#222#
###########
#333#444#555#
#333#444#555#
#333#444#555#
###########
#666#777#888#
#666#777#888#
#666#777#888#
###########

#set/get square values
temp = []
temp.append(rows[(square / 3)*3][(square % 3)*3])
temp.append(rows[(square / 3)*3][1+(square % 3)*3])
temp.append(rows[(square / 3)*3][2+(square % 3)*3])
temp.append(rows[1+(square / 3)*3][(square % 3)*3])
temp.append(rows[1+(square / 3)*3][1+(square % 3)*3])
temp.append(rows[1+(square / 3)*3][2+(square % 3)*3])
temp.append(rows[2+(square / 3)*3][(square % 3)*3])
temp.append(rows[2+(square / 3)*3][1+(square % 3)*3])
temp.append(rows[2+(square / 3)*3][2+(square % 3)*3])

#return a list of possible values
output = []
for i in range(9):
if not (i+1) in temp:
output.append(i+1)
return output

#############################################

#find all of the possibilities for a particular cell
def cellPoss(row, col):
output = []
for i in range(9):
if ((i+1) in rp[row]) and ((i+1) in cp[col]) and ((i+1) in sp[((row/3)*3)+(col/3)]):
output.append(i+1)
if len(output) == 1:
return output[0]
else:
return output

#############################################

#rows
r0 = [9,1,0,7,0,0,0,0,5]
r1 = [5,0,0,0,0,0,0,7,0]
r2 = [6,0,0,3,0,8,0,0,0]
r3 = [0,3,6,0,9,0,8,0,0]
r4 = [0,0,5,8,6,7,1,0,0]
r5 = [0,0,7,0,3,0,5,4,0]
r6 = [0,0,0,1,0,3,0,0,8]
r7 = [0,8,0,0,0,0,0,0,2]
r8 = [3,0,0,0,0,9,0,5,1]

rows = [r0,r1,r2,r3,r4,r5,r6,r7,r8]

#######################################
#OR, for user input - uncomment
#enter values row by row - just [ENTER] for blank

for i in range(9):
for j in range(9):
s = raw_input('::')
if s == '':
rows[i][j] = 0
else:
rows[i][j] = int(s)

########################################

cellPossibilities = rows
#now find each cell's possibilities
#cellPossibilities[row][column]

#get start time
startTime = time.time()

solved = 0
solvedPrev = -1

while solved < 81:

rp = []
for row in range(9):
rp.append(rowPoss(row))

cp = []
for column in range(9):
cp.append(colPoss(column))

sp = []
for square in range(9):
sp.append(squarePoss(square))

for row in range(9):
for col in range(9):
if (cellPossibilities[row][col] == 0) or (type(cellPossibilities[row][col]) == list):
cellPossibilities[row][col] = cellPoss(row, col)

solvedPrev = solved
solved = 0
for i in range(9):
for j in range(9):
if type(cellPossibilities[i][j]) == int:
solved += 1

if solved == solvedPrev:
print 'too difficult - guessing required'
solved = 81 #'trick it' into finishing


for i in range(9):
print cellPossibilities[i]

print 'It took ', round((time.time()-startTime), 3), ' seconds'



Improvements coming soon...

Thanks for reading,


Chris

EDIT: Appologies for the above code, the indentations seem to have been removed.