def instantiateCases () :
# Correctly Formulated Sudoku
global h
h =[[0,0,0, 0,0,0, 0,3,0],
[6,0,5, 0,0,0, 0,0,0],
[0,3,0, 0,1,0, 9,0,0],
[5,7,0, 6,0,0, 0,0,0],
[0,9,0, 0,0,0, 0,1,0],
[0,0,0, 0,0,8, 0,2,4],
[0,0,1, 0,7,0, 0,4,0],
[0,0,0, 0,0,0, 5,0,8],
[0,2,0, 0,0,0, 0,0,0]]
instantiateCases ()
solved(s) returns True if the puzzle is solved and False if it is not solved.
def solved(s) :
for row in s:
if 0 in row:
return False
return True
horizontalCheck(x,val,s) which, given a row number x, a value to check val, and a sudoku puzzle s, returns False if the given value has already been used in the indicated row, and True if the number is still available.
def horizontalCheck(x, val, s) :
if val in s[x]:
return False
else:
return True
verticalCheck(y,val,s) which, given a column number y, a value to check val, and a sudoku puzzle s, returns False if the given value has already been used in the indicated column, and True if the number is still available.
def verticalCheck(y, val, s) :
for row in s:
if row[y] == val:
return False
return True
The function whichSquare(pos) that given a position value (0-8), returns which square that box is located in, and return the range of said box. The function does not distinguish between row and column, as it can be applied either way.
The function subSquareCheck(x,y,val,s) that, given the x and y position of the cell we are checking ('x' and 'y' respectively), a value to check val, and a sudoku puzzle s, returns False if the given value has already been used in the indicated sub-square, and True if the number is still available.
def whichSquare(pos):
a = (0,1,2)
b = (3,4,5)
c = (6,7,8)
if pos in a:
return a
elif pos in b:
return b
else:
return c
def subSquareCheck(x,y,val,s) :
for i in whichSquare(x):
for j in whichSquare(y):
if s[j][i] == val:
return False
return True
class SudokuInvalid(Exception):
pass
class SudokuUnsolvable(Exception):
pass
The function applyStrategy(strategy, s) which, given a strategy (in this case, a function with the input/output properties described earlier), and a puzzle s, applies that strategy to each cell in the puzzle. Have the function return True if the strategy worked, and False if it didnt
from itertools import combinations
import copy
import random
def applyStrategy(strategy, s, sbar) :
counter = 0
sbarChange = copy.deepcopy(sbar)
try:
#For elimination and Hidden singles strategies
for row in range(9):
for col in range(9):
if (s[row][col] == 0):
#For eliminiation and hidden Singles
if strategy(col, row, s) > 0:
s[row][col] = strategy(col, row, s)
counter +=1
except:
#For all other strategies
strategy(s)
for row in range(9):
for col in range(9):
if sbarChange[row][col] != sbar[row][col]:
counter +=1
if counter == 0:
return False
else:
return True
An algorithm that will attempt to solve a puzzle, given the puzzle and a list of strategy functions.
def possibilities(s):
global sbar
sbar = [x[:] for x in s]
for row in range(9):
for col in range(9):
sbar[row][col] = [sbar[row][col]]
if (sbar[row][col] == [0]):
sbar[row][col] = []
for val in (1,2,3,4,5,6,7,8,9):
if (subSquareCheck(col,row,val,s) and verticalCheck(col, val, s) and horizontalCheck(row, val, s)):
sbar[row][col].append(val)
pass
def sudokuSolver (s, strategies) :
possibilities(s)
while not solved(s):
changed = []
for strategy in strategies:
changed.append(applyStrategy(strategy, s, sbar))
if (True not in changed) :
break
#Last ditch attempt to see if solved puzzle lies in sbar
for row in range(9):
for col in range(9):
if len(sbar[row][col])!=1:
#Does not lie in sbar
break
else:
s[row][col] = sbar[row][col][0]
if not solved(s):
#Gosh diddly darnit we gotta pull out the big guns
brutus = bruteForce(s,sbar,strategies)
if not solved(brutus):
#Big guns couldnt do it... so sad
raise SudokuUnsolvable
else:
#Hoorah! no need for strategies, the big guns have dunnit
return brutus
else:
return s
def updateSbar(row,col,val,s):
#Set Sbar to value found
sbar[row][col] = [val]
#Remove value from its row and column
for i in range(9):
if (i != col and (val in sbar[row][i])):
sbar[row][i].remove(val)
if (i != row and (val in sbar[i][col])):
sbar[i][col].remove(val)
#Remove value from its block
for i in whichSquare(row):
for j in whichSquare(col):
if (sbar[i][j] != [val] and (val in sbar[i][j])):
sbar[i][j].remove(val)
return val
A youtube video which outlines nine sudoku strategies coded below: https://www.youtube.com/watch?v=b123EURtu3I`possibilities(s)`
def elimination (col, row, s) :
counter = 0
ans = 0
for val in (1,2,3,4,5,6,7,8,9):
if (subSquareCheck(col,row,val,s) and verticalCheck(col, val, s) and horizontalCheck(row, val, s)):
counter += 1
ans = val
if (counter == 0):
raise SudokuInvalid
elif (counter == 1):
return updateSbar(row,col,ans,s)
else:
return 0
def hiddenSingles(col, row, s) :
for val in (1,2,3,4,5,6,7,8,9):
if (subSquareCheck(col,row,val,s) and verticalCheck(col, val, s) and horizontalCheck(row, val, s)):
#Single in row case
checkrow = 0
for i in range(9):
if verticalCheck(i, val, s):
checkrow +=1
if checkrow == 1:
return updateSbar(row,col,val,s)
#Single in column case
checkcol = 0
for j in range(9):
if horizontalCheck(row, val, s):
checkcol +=1
if checkcol == 1:
return updateSbar(row,col,val,s)
#Single in block case
checkblock = 0
for i in whichSquare(col):
for j in whichSquare(row):
if (verticalCheck(i, val, s) and horizontalCheck(j, val, s) and s[j][i] == 0):
checkblock +=1
if checkblock == 1:
return updateSbar(row,col,val,s)
return 0
def nakedPair(s):
#two cells in a row a column or a block
#having only the same pair of candidates
#are called a naked pair all other
#appearances of the two candidates in the
#same row column or block can be
#eliminated
for row in sbar:
a = []
for col in row:
if (row.count(col) == 2 and len(col)==2 and (col not in a)):
a.append(col)
for col in row:
if len(a) > 0 :
for pair in a:
if (col != pair):
if pair[0] in col:
col.remove(pair[0])
if pair[1] in col:
col.remove(pair[1])
# #Pair in column
for col in range(9):
c = []
d = []
for row in sbar:
c.append(row[col])
#Find a pair & add to list c
for i in c:
if (c.count(i)==2 and len(i)==2 and (i not in d)):
d.append(i)
for row in sbar:
if len(d) >0:
for pair in d:
if (row[col] != pair):
if pair[0] in row[col]:
row[col].remove(pair[0])
if pair[1] in row[col]:
row[col].remove(pair[1])
#Pair in block
for i in (1,4,7):
for j in (1,4,7):
e = []
t = []
#In each block, check all positions
for v in (-1,0,1):
for h in (-1,0,1):
e.append(sbar[i+v][j+h])
for k in e:
if (e.count(k)==2 and len(k)==2 and (k not in t)):
t.append(k)
for v in (-1,0,1):
for h in (-1,0,1):
if (len(t)>0):
for pair in t:
if (sbar[i+v][j+h] != pair):
if pair[0] in sbar[i+v][j+h]:
sbar[i+v][j+h].remove(pair[0])
if pair[1] in sbar[i+v][j+h]:
sbar[i+v][j+h].remove(pair[1])
#Change s as we go
for row in range(9):
for col in range(9):
if (len(sbar[row][col])==1):
s[row][col] = sbar[row][col][0]
updateSbar(row,col,sbar[row][col][0],s)
pass
def pointingPair(s):
#when a certain candidate appears only in
#two or three cells in a block and the
#cells are aligned in a column or a row
#they are called a pointing pair or
#triples all other appearances of the
#candidate outside the block in the same
#column or row can be eliminated
for val in (1,2,3,4,5,6,7,8,9):
for i in (1,4,7):
for j in (1,4,7):
#Find where we can put val in block
drows = [[0,0,0],[0,0,0],[0,0,0]]
dcols = [[0,0,0],[0,0,0],[0,0,0]]
for v in (-1,0,1):
for h in (-1,0,1):
if (val in sbar[i+v][j+h]) and len(sbar[i+v][j+h])>1:
drows[v+1][h+1]=1
dcols[h+1][v+1]=1
#To catch unupdated sbars
elif (val in sbar[i+v][j+h]) and len(sbar[i+v][j+h])==1:
drows = [[0,0,0],[0,0,0],[0,0,0]]
break
yeet = [0,0,0]
yote = [0,0,0]
rowSingle = False
colSingle = False
for k in range(3):
if drows[k].count(1) > 1:
yeet[k] = 1
elif drows[k].count(1) == 1:
rowSingle = True
if dcols[k].count(1) > 1:
yote[k] = 1
elif dcols[k].count(1) == 1:
colSingle = True
#remove from row if cond are met
if (yeet.count(1) == 1 and not rowSingle):
specialrow = yeet.index(1) - 1
for rep in range(9):
if horizontalCheck(i+specialrow, val, s):
if ((rep!=j-1) and (rep!=j) and (rep!=j+1) and len(sbar[i+specialrow][rep]) != 1 and (val in sbar[i+specialrow][rep])):
sbar[i+specialrow][rep].remove(val)
else:
#update sbars
if ((val in sbar[i+specialrow][rep]) and len(sbar[i+specialrow][rep]) != 1):
sbar[i+specialrow][rep].remove(val)
#Change s as we go
for row in range(9):
for col in range(9):
if (len(sbar[row][col])==1):
s[row][col] = sbar[row][col][0]
updateSbar(row,col,sbar[row][col][0],s)
pass
def claimingPair(s):
#when a certain candidate appears in only
#two or three cells in a row or a column
#and the cells are also in a block they
#are called a claiming pair or triple all
#other appearances of the candidate in
#the same block the family can be
#eliminated
for val in (1,2,3,4,5,6,7,8,9):
for row in range(9):
counter = []
for col in sbar[row]:
if val in col:
counter.append(1)
else:
counter.append(0)
if (counter.count(1) == 2 and counter[0:3].count(1) == 2) or (counter.count(1) == 3 and counter[0:3].count(1) == 3):
for i in whichSquare(row):
for j in (0,1,2):
if i != row and len(sbar[i][j]) > 1 and ((val in sbar[i][j])):
sbar[i][j].remove(val)
if (counter.count(1) == 2 and counter[3:6].count(1) == 2) or (counter.count(1) == 3 and counter[3:6].count(1) == 3):
for i in whichSquare(row):
for j in (3,4,5):
if i != row and len(sbar[i][j]) > 1 and ((val in sbar[i][j])):
sbar[i][j].remove(val)
if (counter.count(1) == 2 and counter[6:9].count(1) == 2) or (counter.count(1) == 3 and counter[6:9].count(1) == 3):
for i in whichSquare(row):
for j in (6,7,8):
if i != row and len(sbar[i][j]) > 1 and ((val in sbar[i][j])):
sbar[i][j].remove(val)
for col in range(9):
counter = []
for row in range(9):
if val in sbar[row][col]:
counter.append(1)
else:
counter.append(0)
if (counter.count(1) == 2 and counter[0:3].count(1) == 2) or (counter.count(1) == 3 and counter[0:3].count(1) == 3):
for j in whichSquare(col):
for i in (0,1,2):
if j != col and len(sbar[i][j]) > 1 and ((val in sbar[i][j])):
sbar[i][j].remove(val)
if (counter.count(1) == 2 and counter[3:6].count(1) == 2) or (counter.count(1) == 3 and counter[3:6].count(1) == 3):
for j in whichSquare(col):
for i in (3,4,5):
if j != col and len(sbar[i][j]) > 1 and ((val in sbar[i][j])):
sbar[i][j].remove(val)
if (counter.count(1) == 2 and counter[6:9].count(1) == 2) or (counter.count(1) == 3 and counter[6:9].count(1) == 3):
for j in whichSquare(col):
for i in (6,7,8):
if j != col and len(sbar[i][j]) > 1 and ((val in sbar[i][j])):
sbar[i][j].remove(val)
#Change s as we go
for row in range(9):
for col in range(9):
if (len(sbar[row][col])==1):
s[row][col] = sbar[row][col][0]
updateSbar(row,col,sbar[row][col][0],s)
pass
def nakedTriple(s):
#three cells in a row, a column, or a block
#having only the same three candidates or
#their subsets are called naked triple
#all other appearances of the same
#candidates can be eliminated if they are
#in the same row column or block
for row in range(9):
#remove cases in row that are already solved
combvals = [1,2,3,4,5,6,7,8,9]
for i in s[row]:
if i != 0:
combvals.remove(i)
combos = combinations(combvals, 3)
for comb in combos:
counter = 0
for col in range(9):
if set(sbar[row][col]).issubset(set(comb)):
counter += 1
if counter == 3:
for k in sbar[row]:
for q in comb:
if ((q in k) and not set(k).issubset(set(comb))):
k.remove(q)
for col in range(9):
combvals = [1,2,3,4,5,6,7,8,9]
for i in [item[col] for item in s]:
if i != 0:
combvals.remove(i)
combos = combinations(combvals, 3)
for comb in combos:
counter = 0
for row in range(9):
if set(sbar[row][col]).issubset(set(comb)):
counter += 1
if counter == 3:
for k in sbar:
for q in comb:
if ((q in k[col]) and not set(k[col]).issubset(set(comb))):
k[col].remove(q)
for i in (1,4,7):
for j in (1,4,7):
combvals = [1,2,3,4,5,6,7,8,9]
for v in (-1,0,1):
for h in (-1,0,1):
if s[i+v][j+h] != 0:
combvals.remove(s[i+v][j+h])
combos = combinations(combvals, 3)
for comb in combos:
counter = 0
for v in (-1,0,1):
for h in (-1,0,1):
if set(sbar[i+v][j+h]).issubset(set(comb)):
counter += 1
if counter == 3:
for v in (-1,0,1):
for h in (-1,0,1):
for q in comb:
if ((q in sbar[i+v][j+h]) and not set(sbar[i+v][j+h]).issubset(set(comb))):
sbar[i+v][j+h].remove(q)
#Change s as we go
for row in range(9):
for col in range(9):
if (len(sbar[row][col])==1):
s[row][col] = sbar[row][col][0]
updateSbar(row,col,sbar[row][col][0],s)
pass
def nakedQuad(s):
#four cells in a row a column or a block
#having only the same four candidates or
#their subset are called a naked quad all
#other appearances of the same candidates
#can be eliminated if they are in the
#same row column or block
for row in range(9):
#remove cases in row that are already solved
combvals = [1,2,3,4,5,6,7,8,9]
for i in s[row]:
if i != 0:
combvals.remove(i)
combos = combinations(combvals, 4)
for comb in combos:
counter = 0
for col in range(9):
if set(sbar[row][col]).issubset(set(comb)):
counter += 1
if counter == 4:
for k in sbar[row]:
for q in comb:
if ((q in k) and not set(k).issubset(set(comb))):
k.remove(q)
for col in range(9):
combvals = [1,2,3,4,5,6,7,8,9]
for i in [item[col] for item in s]:
if i != 0:
combvals.remove(i)
combos = combinations(combvals, 4)
for comb in combos:
counter = 0
for row in range(9):
if set(sbar[row][col]).issubset(set(comb)):
counter += 1
if counter == 4:
for k in sbar:
for q in comb:
if ((q in k[col]) and not set(k[col]).issubset(set(comb))):
k[col].remove(q)
for i in (1,4,7):
for j in (1,4,7):
combvals = [1,2,3,4,5,6,7,8,9]
for v in (-1,0,1):
for h in (-1,0,1):
if s[i+v][j+h] != 0:
combvals.remove(s[i+v][j+h])
combos = combinations(combvals, 4)
for comb in combos:
counter = 0
for v in (-1,0,1):
for h in (-1,0,1):
if set(sbar[i+v][j+h]).issubset(set(comb)):
counter += 1
if counter == 4:
for v in (-1,0,1):
for h in (-1,0,1):
for q in comb:
if ((q in sbar[i+v][j+h]) and not set(sbar[i+v][j+h]).issubset(set(comb))):
sbar[i+v][j+h].remove(q)
#Change s as we go
for row in range(9):
for col in range(9):
if (len(sbar[row][col])==1):
s[row][col] = sbar[row][col][0]
updateSbar(row,col,sbar[row][col][0],s)
pass
def hiddenPair(s):
#when a pair of candidates appears in
#only two cells in a row a column or a
#block but they are the only candidates
#in the cells they are called the hidden
#pair all candidates other than the pair
#in the cells can be eliminated yielding a naked pair
for row in sbar:
d = {1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
pair = []
for col in row:
for poss in col:
d[poss] +=1
for i in d:
if d[i] == 2:
pair.append(i)
if len(pair) > 1:
comb = combinations(pair, 2)
for combo in comb:
counter = 0
for col in row:
if set(combo).issubset(col):
counter += 1
if (counter == 2):
#yay! Hidden pair
for col in row:
if set(combo).issubset(col):
#change sbar to just the pair
col = list(combo)
for col in range(9):
d = {1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
pair = []
for row in range(9):
for poss in sbar[row][col]:
d[poss] +=1
for i in d:
if d[i] == 2:
pair.append(i)
if len(pair) > 1:
comb = combinations(pair, 2)
for combo in comb:
counter = 0
for row in range(9):
if set(combo).issubset(sbar[row][col]):
counter += 1
if (counter == 2):
#yay! Hidden pair
for row in range(9):
if set(combo).issubset(sbar[row][col]):
#change sbar to just the pair
sbar[row][col] = list(combo)
#Pair in block
for i in (1,4,7):
for j in (1,4,7):
e = []
pair = []
d = {1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
#In each block, check all positions
for v in (-1,0,1):
for h in (-1,0,1):
for poss in sbar[i+v][j+h]:
d[poss] +=1
for egg in d:
if d[egg] == 2:
pair.append(egg)
if len(pair) > 1:
comb = combinations(pair, 2)
for combo in comb:
counter = 0
for v in (-1,0,1):
for h in (-1,0,1):
if set(combo).issubset(sbar[i+v][j+h]):
counter += 1
if (counter == 2):
#yay! Hidden pair
for v in (-1,0,1):
for h in (-1,0,1):
if set(combo).issubset(sbar[i+v][j+h]):
#change sbar to just the pair
sbar[i+v][j+h] = list(combo)
#Change s as we go
for row in range(9):
for col in range(9):
if (len(sbar[row][col])==1):
s[row][col] = sbar[row][col][0]
updateSbar(row,col,sbar[row][col][0],s)
pass
def Xwing(s):
#when a candidate appears in four cells
#that form the corners of a rectangle or
#a square and it appears only in the two
#cells in both rows all other appearances
#of the candidate in the two columns a
#family can be eliminated it also works
#if rows and columns are switched around
for val in (1,2,3,4,5,6,7,8,9):
#FOR ROWS
counter = []
for row in range(9):
counter.append([])
for col in range(9):
if val in sbar[row][col]:
counter[row].append(1)
else:
counter[row].append(0)
edges = []
for row in range(9):
if counter[row].count(1) == 2:
edges.append([row, counter[row]])
colLoc = []
numXwingperVal = 0
if len(edges) > 1:
comb = combinations(edges, 2)
for i in comb:
if i[0][1] == i[1][1]:
#print("XWING",val,i, sbar)
colLoc.append([])
#SUCCESS
for colEdge in range(9):
if i[0][1][colEdge] == 1:
colLoc[numXwingperVal].append([i[0][0],i[1][0],colEdge])
numXwingperVal += 1
#print(colLoc)
#[[[1, 4, 4], [1, 4, 5]], [[5, 7, 0], [5, 7, 2]]]
for amt in colLoc:
for row in range(9):
for col in amt:
#specify rows to not delete
if (row != col[0] and row != col[1]):
if val in sbar[row][col[2]]:
print(val,col[2])
sbar[row][col[2]].remove(val)
#FOR COLUMNS
counter = []
for col in range(9):
counter.append([])
for row in range(9):
if val in sbar[row][col]:
counter[col].append(1)
else:
counter[col].append(0)
edges = []
for col in range(9):
if counter[col].count(1) == 2:
edges.append([col, counter[col]])
rowLoc = []
numXwingperVal = 0
if len(edges) > 1:
comb = combinations(edges, 2)
for i in comb:
if i[0][1] == i[1][1]:
#print("XWING",val,i, sbar)
rowLoc.append([])
#SUCCESS
for rowEdge in range(9):
if i[0][1][rowEdge] == 1:
rowLoc[numXwingperVal].append([i[0][0],i[1][0],rowEdge])
numXwingperVal += 1
#print(colLoc)
#[[[1, 4, 4], [1, 4, 5]], [[5, 7, 0], [5, 7, 2]]]
for amt in rowLoc:
for col in range(9):
for row in amt:
#specify rows to not delete
if (col != row[0] and col != row[1]):
if val in sbar[row[2]][col]:
print(val,row[2])
sbar[row[2]][col].remove(val)
for row in range(9):
for col in range(9):
if (len(sbar[row][col])==1):
s[row][col] = sbar[row][col][0]
updateSbar(row,col,sbar[row][col][0],s)
pass
def bruteForce(s,sbar,strategies):
#When all else fails
sTry = copy.deepcopy(s)
for i in range(5):
a = random.choice(range(9))
b = random.choice(range(9))
sTry[a][b] = random.choice(sbar[a][b])
try:
return sudokuSolver(sTry, strategies)
except SudokuInvalid:
return bruteForce(s,sbar)
except SudokuUnsolvable:
return bruteForce(sTry,sbar)
except:
return bruteForce(s,sbar)
Below the code will attempt to solve the puzzle outlined at the start.
def printSudoku(puzzle):
for i in range(9):
if i in (3,6):
print("=========================================")
print(puzzle[i][0], " ", puzzle[i][1], " ",puzzle[i][2], " || ",puzzle[i][3], " ",puzzle[i][4], " ",puzzle[i][5], " || ",puzzle[i][6], " ",puzzle[i][7], " ",puzzle[i][8])
instantiateCases ()
try:
solution = sudokuSolver(h, [elimination, hiddenSingles, nakedPair, pointingPair, claimingPair, nakedTriple , Xwing, nakedQuad, hiddenPair]) # <== add your strategies to the list here
print("The puzzle was solvable! Congrats! See solution below:")
printSudoku(solution)
except SudokuUnsolvable:
print("Sudoku Puzzle Unsolvable, here is as much as could be done:", h)