Sudoku Solver

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.

Evil Sudoku 666


# Python 2.7.7 Code
# Jonathan Frech 3rd of August, 2016
#         edited 5th of August, 2016

# import modules
import re, time

# 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 = [initialsudoku]
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

One thought on “Sudoku Solver

  1. Pingback: Web Sudoku Solver | J-Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s