This program can solve and create sudoku puzzles
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 | #!/usr/bin/python
# TODO: Make solve function faster!!! Have it check for singles, doubles,
# triples, and quads both naked and hidden
from random import random
def rand(lst):
"returns a random element in list or integer"
if type(lst)==type([]):
return lst[int(random()*len(lst))]
elif type(lst)==type(0):
return int(random()*lst)
else:
raise Exception,"don't know what do do with type %s!!!"%type(lst)
def reorder(lst):
"reorders a list to a random order"
ret=[]
for item in lst:
ret.insert(rand(len(ret)),item)
return ret
def row(row,puzzle):
return puzzle[row*9:row*9+9]
def col(col,puzzle):
ret=[]
for i in range(9):
ret.append(row(i,puzzle)[col])
return ret
def box(box,puzzle):
x=box%3
if box<3:
y=0
elif box<6:
y=1
else:
y=2
ret=[]
for i in range(3):
ret.extend(row(y*3+i,puzzle)[x*3:x*3+3])
return ret
def remaining(wcb):
ret=[]
for i in range(1,10):
if not i in wcb:
ret.append(i)
return reorder(ret) # does not significantly slow program
# and allows for generation of random puzzles
def coordToBox(x,y):
box=0
if x<3:
pass
elif x<6:
box+=1
else:
box+=2
if y<3:
pass
elif y<6:
box+=3
else:
box+=6
return box
def coordToLinear(x,y):
return y*9+x
def linearToCoord(index):
y=8
for i in range(9):
if index<i*9:
y-=1
x=index%9
return x,y
def possible(x,y,puzzle):
if not puzzle[coordToLinear(x,y)]==0:
return [puzzle[coordToLinear(x,y)]]
imp=[]
imp.extend(row(y,puzzle))
imp.extend(col(x,puzzle))
imp.extend(box(coordToBox(x,y),puzzle))
return remaining(imp)
def printPuzzle(puzzle):
string=((((("%s "*3)+"| ")*2+("%s "*3)+"\n")*3+"------|-------|------\n")*3)[:-22]+"\n"
text=(string%tuple(puzzle)).replace("0","_")
print text,
return text
def check(x,y,puzzle):
for i in range(9):
if not i==y and len(possible(x,i,puzzle))==0:
return False
if not i==x and len(possible(i,y,puzzle))==0:
return False
box_x,box_y=linearToCoord(coordToBox(x,y))
for i in range(box_x,box_x+3):
if i==x:
break
for j in range(box_y,box_y+3):
if j==y:
break
if len(possible(i,j,puzzle))==0:
return False
return True
def solve(puzzle,start=0): # TODO: Make this function faster!!!
if start==81:
return [puzzle[:]]
ret=[]
x,y=linearToCoord(start)
possibilities=possible(x,y,puzzle)
if len(possibilities)==0:
return
for possibility in possibilities:
p=puzzle[:]
p[coordToLinear(x,y)]=possibility
x,y=linearToCoord(start)
if not check(x,y,puzzle):
continue
solved=solve(p,start+1)
if solved:
ret.extend(solved)
if 1<len(ret): # there is more than one puzzle
return ret # enough already!!!
return ret
def solve_no_check_for_dups(puzzle,start=0):
"This solver function does not check for multiple solutions."
if start==81:
return puzzle[:]
x,y=linearToCoord(start)
possibilities=possible(x,y,puzzle)
if len(possibilities)==0:
return
for possibility in possibilities:
p=puzzle[:]
p[coordToLinear(x,y)]=possibility
x,y=linearToCoord(start)
if not check(x,y,puzzle):
continue
solved=solve_no_check_for_dups(p,start+1)
if solved:
return solved
return []
def generate(sym=True,goodness=0): # goodness=0 means evil
if sym:
RANGE=41
else:
RANGE=81
puzzle=[0]*81
soln=solve_no_check_for_dups(puzzle)
puzzle=soln[:]
spaces=range(RANGE)
for i in range(RANGE-goodness):
space=spaces.pop(rand(len(spaces)))
puzzle[space]=0
if sym:
puzzle[80-space]=0
if 1<len(solve(puzzle)):
puzzle[space]=soln[space]
if sym:
puzzle[80-space]=soln[80-space]
return puzzle
#puzzle=[]
#for i in range(9):
# puzzle.extend(map(int,raw_input().split()))
try:
import psyco
psyco.full()
except ImportError:
print "You do not have psyco installed. The program will run slower."
if __name__=="__main__":
#puzzle=generate()
#printPuzzle(puzzle)
#soln=solve(puzzle)
#printPuzzle(soln[0])
#if 1<len(soln):
# print "More than one solution!!!"
#puzzle=generate(sym=False)
#printPuzzle(puzzle)
#soln=solve(puzzle)
#printPuzzle(soln[0])
#if 1<len(soln):
# print "More than one solution!!!"
from time import sleep
while True:
puzzle=generate(sym=False)
text=printPuzzle(puzzle)
f=open("./sudoku","a")
f.write(text)
f.close()
sleep(180)
|
This program is somewhat unfinished, so I left my comments in there (including debugging ones) for anybody who wants to improve it. It does, however, work, so feel free to use it. The "TODO:" at the top refers to implementing a few different methods of solving sudoku puzzles in order to reduce the brute force used by the program.
or better random.shuffle(lst)
try lst = random.sample(lst, len(lst)) instead of def reorder(lst): ... ... ...
Thank you for the helpful comment. However, I have moved on to bigger and better things, and seeing as this project was "just for fun", I really cannot be bothered changing anything about it. Feel free to start an open source project around it if you so desire.