This program solves a given Sudoku.

It uses a simple strategy, looking at each box and determining those numbers that are not in its row, column and square. If that list has length 1, the box’s number is determined.

After going through each box, the program generates child Sudokus in which the first empty box get filled with one of the possible numbers for that box. Sudokus with an error get eliminated.

Using this simple but effective strategy this program can solve hard Sudokus in under a second.

As an example, I used Evil Puzzle 666 from Web Sudoku.

For more information on Sudokus, visit this Wikipedia entry.

```
# Python 2.7.7 Code
# Jonathan Frech 3rd of August , 2016
# edited 5th of August , 2016
# edited 2nd of December, 2017
# * Fixed a bug where the solved
# sudoku would be printed twice
# on easy sudokus.
```

```
```

```
# import modules
import re, time
import copy # Bugfix 2nd Dec 2017
# sudoku class
class Sudoku():
# init
def __init__(self, sudoku):
# sudoku's length must be 9**2
if len(sudoku) != 9**2:
print sudoku
raise Exception("Sudoku of wrong size (" + str(len(sudoku)) + ").")
# initialization
self.sudoku = sudoku
self.error = False
self.solved = False
self.children = []
# get the sudoku's row (0-8)
def row(self, n):
return self.sudoku[9*n:9*n+9]
# get the sudoku's column (0-8)
def column(self, n):
column = ""
for _ in range(0, 9):
column += self.row(_)[n]
return column
# get the sudoku's square (0-8)
def square(self, n):
square = ""
for _ in range((n/3)*3, (n/3)*3+3):
square += self.row(_)[(n%3)*3:(n%3)*3+3]
return square
# partially solve the sudoku
def partiallysolve(self):
# initialization
progress = False
self.solved = True
self.children = []
# loop through all 9**2 boxes
for _ in range(0, len(self.sudoku)):
# the box's number
box = self.sudoku[_]
# calculate box's coordinates
row = _/9
column = _%9
square = (_%9)/3 + ((_/9)/3)*3
# check if box is empty
if box == "0":
# not solved...
self.solved = False
# generate a list of all nine possible numbers for that box
numbers = []
for n in range(1, 10):
numbers.append(str(n))
# rule out any numbers that are found in the box's row, column or square
for c in [self.row(row), self.column(column), self.square(square)]:
for cc in c:
if cc in numbers:
numbers.remove(cc)
# if the list of possible numbers' length is 0, the sudoku has an error
if len(numbers) == 0:
self.error = True
self.solved = False
break
# if it is 1, that is the box's number
elif len(numbers) == 1:
self.sudoku = self.sudoku[0:_] + numbers[0] + self.sudoku[_+1:len(self.sudoku)]
# made progress!
progress = True
# get children
if not self.error and len(self.children) <= 0:
for n in numbers:
self.children.append(Sudoku(self.sudoku[0:_] + n + self.sudoku[_+1:len(self.sudoku)]))
# box is full, check for any errors
else:
r = self.row(row)
for c in [list(self.row(row)), list(self.column(column)), list(self.square(square))]:
c.remove(box)
if box in c:
self.error = True
break
# return if any progress was made
return progress
# solve the sudoku (as far as possible, check for errors and create child sudokus)
def solve(self):
# solve it as far as possible
while True:
if not self.partiallysolve():
break
# error in sudoku
if self.error:
return [], False
# return children and solved status
return self.children, self.solved
# print the sudoku
def __str__(self):
# upper strip
msg = "+" + ("-"*9) + "+"
# sudoku split in sets of nine
for _ in range(0, 9):
msg += "\n|" + re.sub("0", " ", self.row(_)) + "|"
# lower strip
msg += "\n+" + ("-"*9) + "+"
# retuurn message
return msg
# start timer
beg = time.time()
# header
print "==========================="
print " S U D O K U S O L V E R "
print "==========================="
print
# initialize the sudoku
initialsudoku = Sudoku("007600054000005800000140200000002068300418000000350900000270009010000000009504003")
#initialsudoku = Sudoku("000000000700008950901000004040780016003000070000012000070450069300900080010000000")
#initialsudoku = Sudoku("000005100006002009000037020350009600700201008001300072060910000400500800005700000")
#initialsudoku = Sudoku("280070400300900000600008000020060000094000870000050030000300005000006004001040082")
#initialsudoku = Sudoku("000000000000000000000000000000000000000000000000000000000000000000000000000000011")
#initialsudoku = Sudoku("650000000400270300000090708009003002060000070200500800901050000005041003000000081")
#initialsudoku = Sudoku("850070400070200000060009000900060000308000701000020005000800020000001090007030058")
# further initialization
sudokus = [copy.deepcopy(initialsudoku)] # Bugfix 2nd Dec 2017: added copy.deepcopy(...)
sudoku = None
solved = False
impossible = False
# solve it
while not solved and not impossible:
# initialization
newsudokus = []
# solve through sudokus
for s in sudokus:
# get children and solved status
children, solved = s.solve()
# solved!
if solved:
sudoku = s
break
# add children to new sudoku list
for _ in children:
newsudokus.append(_)
# use new sudokus as sudokus
sudokus = newsudokus[:]
# if there are no more sudokus to check and the sudoku is not solved, it is impossible
if len(sudokus) <= 0 and not solved:
impossible = True
# sudoku is impossible to solve
if impossible:
# split sudoku
initialsud = re.split("\n", str(initialsudoku))
# add arrow to middle part
initialsud[len(initialsud) / 2] += " -> /"
# print sudoku and error message
print "\n".join(initialsud)
print
print "This sudoku is impossible to solve."
# print solved sudoku
else:
# split sudokus
initialsud = re.split("\n", str(initialsudoku))
sud = re.split("\n", str(sudoku))
# add them line by line
s = ""
for _ in range(0, len(initialsud)):
s += initialsud[_] + [" ", " -> "][_ == len(initialsud) / 2] + sud[_] + "\n"
# print merged sudokus
print s
# stop timer
end = time.time()
# print time
t = abs(end - beg)
print "Took " + str(t) + " second" + ["s", ""][t == 1] + "."
# wait for user to terminate
raw_input()
```

Advertisements

Pingback: Web Sudoku Solver | J-Blog