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.

## Monday, 25 August 2008

Subscribe to:
Post Comments (Atom)

## No comments:

Post a Comment