By Alexander Radu
My smarter algorithm explained below aims to cut down on the run time and solve much more difficult sudoku puzzles in a reasonable amount of time.
import sys
f = open(sys.argv[1], 'r')
#f = open('SudokuBoards.txt', 'r')
reading = f.read().strip().split('\n')
boardName = sys.argv[3]
#boardName = 'name,Easy-NYTimes,unsolved'
f.close()
Cliques
Each sublist in cliques dictates the indices of nine squares where each digit must be unique within its respective sublist. The first set of sublists denotes the rows of the sudoku board. The second set of sublists denotes the columns of the sudoku board. The third set of sublists denotes the subgrids of the sudoku board.
cliques = [[0, 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], \
[0, 9, 18, 27, 36, 45, 54, 63, 72], \
[1, 10, 19, 28, 37, 46, 55, 64, 73], \
[2, 11, 20, 29, 38, 47, 56, 65, 74], \
[3, 12, 21, 30, 39, 48, 57, 66, 75], \
[4, 13, 22, 31, 40, 49, 58, 67, 76], \
[5, 14, 23, 32, 41, 50, 59, 68, 77], \
[6, 15, 24, 33, 42, 51, 60, 69, 78], \
[7, 16, 25, 34, 43, 52, 61, 70, 79], \
[8, 17, 26, 35, 44, 53, 62, 71, 80], \
[0, 1, 2, 9, 10, 11, 18, 19, 20], \
[3, 4, 5, 12, 13, 14, 21, 22, 23], \
[6, 7, 8, 15, 16, 17, 24, 25, 26], \
[27, 28, 29, 36, 37, 38, 45, 46, 47], \
[30, 31, 32, 39, 40, 41, 48, 49, 50], \
[33, 34, 35, 42, 43, 44, 51, 52, 53], \
[54, 55, 56, 63, 64, 65, 72, 73, 74], \
[57, 58, 59, 66, 67, 68, 75, 76, 77], \
[60, 61, 62, 69, 70, 71, 78, 79, 80]]
Reading the File
The desired sudoku board was isolated and then interpreted into a list of length 81. Each blank was replaced with a zero, and each given number was kept as it was given. The list of integers was then stored in the variable, board.
for number in range(len(reading)):
if reading[number].strip() == boardName:
reading = reading[number + 1: number + 10]
break
reading = ','.join(reading).replace('_', '0')
reading = reading.split(',')
board = [int(element) for element in reading]
print('The Processed Sudoku Board: ' + str(board))
print('The Length of the List: ' + str(len(board)))
Grouping the Neighbors
Each square of the sudoku board must contain a number that is different from those of its neighbors. The neighbors of each square can be accessed from the neighbors dictionary with the key being the index of the square and the value being a set with the indices of each neighbor.
neighbors = {}
for index in range(len(board)):
if board[index] == 0:
unique = set()
for cluster in cliques:
for number in cluster:
if index == number:
unique.update(cluster)
neighbors[index] = unique
print('The Neighbors for Each Square: ' + str(neighbors))
print('Number of Blanks: ' + str(len(neighbors)))
Finding Valid Numbers
The vaidMoves() method updates the possible dictionary with numbers that could be placed in each square of the sudoku board.
possible = {}
digits = {1, 2, 3, 4, 5, 6, 7, 8, 9}
def validMoves():
for key in neighbors:
used = set()
for location in neighbors[key]:
used.add(board[location])
possible[key] = digits.difference(used)
validMoves()
print('Possible Numbers: ' + str(possible))
Next Logical Step
The step() method modifies the inputted sudoku board to replace empty squares with only one valid number possibility with that number possibility.
def step():
for key in possible:
if len(possible[key]) == 1:
board[key] = possible[key].pop()
del neighbors[key]
step()
print('Number of Blanks: ' + str(len(neighbors)))
Algorithm Descprition
For easier puzzles, using the next logical step may solve the entire board. On the other hand, for harder puzzles, this method may be done at first to optimize the solution, but a different algorithm needs to be used to completely solve the sudoku board.
while board.count(0):
validMoves()
step()
print('Solved: ' + str(board))
Presenting the Answer
The answer variable will contain the solved sudoku board in the string format.
column = 0
answer = ''
for item in board:
answer += str(item)
if column == 8:
column = 0
answer += '\n'
else:
answer += ','
column += 1
print(answer)
Writing the File
The solved version of the sudoku board is written in the output file in a manner that is fairly appealing to the user's eye. The numbers are organized in a nine by nine square that closely resembles the structure of an actual sudoku board.
g = open(sys.argv[2], 'w')
#g = open('TestOutput.txt', 'w')
g.write(response.strip())
g.close()
Conclusion
Overall, writing the smarter sudoku algorithm directed me to explore a variety of methods that Python has for sets and the usefulness of this data structure.
Naive Algorithm Backtracks / Smart Algorithm Backtracks
The calculated ratios comparing my naive sudoku algorithm to my smarter sudoku algorithm are the following:
My smarter algorithm tends to take half as many backtracks as my naive algorithm.