*** UPDATE v2 ***
- .exe file working
- added backtrack counter
- added "stopwatch"
# SudokuSolver_solver.py
BACKTRACK_COUNTER = 0
def do_solve(sudoku):
status = wsolve(sudoku)
return status, sudoku, BACKTRACK_COUNTER
def consistent(matrix, row, col, value):
for i in range(9):
if matrix[row][i]==value: return False
if matrix[i][col]==value: return False
rowStart = row - row%3
colStart = col - col%3
for m in range(3):
for k in range(3):
if matrix[rowStart+k][colStart+m]==value: return False
return True
class SolutionFound(Exception):
pass
def wsolve(sudoku):
try:
solve(sudoku, 0)
except SolutionFound:
return True
except StopSolving:
return False
return False
def solve(sudoku, num):
global BACKTRACK_COUNTER
BACKTRACK_COUNTER += 1
if num==81:
raise SolutionFound
return True
else:
row = int(num / 9)
col = num % 9
if sudoku[row][col]!=' ':
solve(sudoku, num+1)
else:
for value in range(1,10):
if consistent(sudoku, row, col, str(value)):
sudoku[row][col] = str(value)
if solve(sudoku, num+1): return True
sudoku[row][col]=' '
return False
if __name__ == '__main__':
printSUDOKU(sudoku)
solve(sudoku, 0)
# SudokuSolver_class.py
import os
import SudokuSolver_solver as Solver
from random import randint
from tkinter import ttk
from tkinter import *
from tkcallasync import tk_call_async, MULTIPROCESSING
class SudokuSolver(Frame):
sudoku = [[" " for col in range(9)] for row in range(9)]
solution = [[" " for col in range(9)] for row in range(9)]
exampleSudoku = [[' ',' ',' ','2','1',' ',' ',' ',' '],
[' ',' ','7','3',' ',' ',' ',' ',' '],
[' ','5','8',' ',' ',' ',' ',' ',' '],
['4','3',' ',' ',' ',' ',' ',' ',' '],
['2',' ',' ',' ',' ',' ',' ',' ','8'],
[' ',' ',' ',' ',' ',' ',' ','7','6'],
[' ',' ',' ',' ',' ',' ','2','5',' '],
[' ',' ',' ',' ',' ','7','3',' ',' '],
[' ',' ',' ',' ','9','8',' ',' ',' ']]
def __init__(self, parent):
Frame.__init__(self, parent, name='frame')
self.parent = parent
self.initUI()
self.blankSUDOKU()
self.sudokudir = os.path.join(os.getcwd(), 'sudokus')
def initUI(self):
self.message_txt = StringVar()
self.time_txt = StringVar()
self.seconds = 0
self.minutes = 0
self.time_txt.set('0{}:0{}'.format(self.minutes, self.seconds))
self.timer_mode = 'stopped'
self.disabled = False
self.values = {}
self.parent.title('Sudoku Solver')
self.pack(fill=BOTH, expand=True)
self.message = Label(self, textvariable=self.message_txt)
self.message.grid(row=10,column=0,columnspan=8, sticky=E+W)
self.timer = Label(self,textvariable=self.time_txt)
self.timer.grid(row=10,column=8,sticky=E+W)
self.solveBtn = Button(self, text="solve",width=6,command=self.execute_solver)
self.solveBtn.grid(row=0,column=0)
self.newBtn = Button(self, text="new",width=6,command=self.blankSUDOKU)
self.newBtn.grid(row=0,column=1)
self.initBtn = Button(self, text="init",width=6,command=self.initSUDOKU)
self.initBtn.grid(row=0,column=2)
self.startBtn = Button(self, text="start",width=6,command=self.start_timer)
self.startBtn.grid(row=0,column=3)
self.checkBtn = Button(self, text="check",width=6,command=self.checkSOLUTION)
self.checkBtn.grid(row=0,column=6)
self.saveBtn = Button(self, text="save",width=6,command=self.saveSUDOKU)
self.saveBtn.grid(row=0,column=7)
self.printBtn = Button(self, text="print",width=6,command=self.printALL)
self.printBtn.grid(row=0,column=8)
self.pbar = ttk.Progressbar(self, mode='indeterminate')
self.pbar.grid(row=11,column=0, columnspan=9, sticky=W+E)
# --- clear all fields and delete all values in sudoku[][] and solution[][] --- #
def blankSUDOKU(self):
self.message_txt.set('')
self.reset_timer()
for row in range(9):
for col in range(9):
self.sudoku[row][col] = ' '
self.solution[row][col] = ' '
self.numEntry = Entry(self, width=5, justify=CENTER,
font="Helvetica 12 bold")
self.values[row,col] = self.numEntry
self.numEntry.grid(row=row+1,column=col, ipady=5)
# ----- get a random Sudoku from textfiles ----- #
def initSUDOKU(self):
self.blankSUDOKU()
self.message_txt.set('')
self.reset_timer()
Files = []
valid = True
for filename in os.listdir(self.sudokudir):
if filename.startswith('sudoku') and filename.endswith('.txt'):
Files.append(filename)
L = len(Files)
if L < 1:
self.message_txt.set('No Sudokus saved, yet! Try this one')
self.sudoku = self.copySUDOKU(self.exampleSudoku)
else:
# ----- fill sudoku array with values from textfile ----- #
R = randint(0, L-1)
sudokuFile = open(os.path.join(self.sudokudir,Files[R]))
row, col = 0, 0
for value in sudokuFile.read():
if value.isdigit() or value==' ':
if value=='0': value = ' ' # zeros can also be used as blanks
self.sudoku[row][col] = value
col += 1
if col==9:
if row==8: break
row += 1
col = 0
sudokuFile.close()
valid = self.checkSUDOKU(self.sudoku)[0]
if not valid:
self.message_txt.set('%s does not contain a valid sudoku' % Files[R])
else:
# ----- make values from random sudoku appear in the GUI ----- #
for row in range(9):
for col in range(9):
value = self.sudoku[row][col]
if value!=' ':
self.values[row,col].insert(0,value)
self.reset_message()
def printSUDOKU(self, matrix):
for row in range(9):
print("|-----------------------------------|")
for col in range(9):
print("| " + matrix[row][col] + " ",end='')
print("|")
print("|-----------------------------------|")
def printALL(self):
print('Sudoku:')
self.printSUDOKU(self.sudoku)
print('Solution:')
self.printSUDOKU(self.solution)
def saveSUDOKU(self):
CHECK = self.checkSUDOKU(self.solution)
if CHECK[0] and CHECK[1]: # check if Sudoku is valid and complete
filecount = 1 # variable for how many sudoku files are already existing
if not os.path.exists(self.sudokudir): os.makedirs(self.sudokudir)
while os.path.isfile(self.path_to("sudoku%s.txt" % filecount)):
filecount += 1
sudokuFile = open(self.path_to("sudoku%s.txt" % filecount), 'w')
solutionFile = open(self.path_to("solution%s.txt" % filecount), 'w')
# ----- create textfiles for sudoku and the solution ----- #
for row in range(9):
for col in range(9):
sudokuFile.write(self.sudoku[row][col])
solutionFile.write(self.solution[row][col])
sudokuFile.write('\n')
solutionFile.write('\n')
sudokuFile.close()
solutionFile.close()
self.message_txt.set('Files saved...')
else:
self.message_txt.set('Sudoku must be valid and complete!')
self.reset_message()
def copySUDOKU(self, matrix):
matrix_copy = [[" " for col in range(9)] for row in range(9)]
for row in range(9):
for col in range(9):
matrix_copy[row][col] = matrix[row][col]
return matrix_copy
# ----- check if user input makes sense -----#
def checkSUDOKU(self, matrix):
valid, complete, ctr = True, True, 0
for row in range(9):
for col in range(9):
value = matrix[row][col]
if value!=' ':
matrix[row][col]=' '
if not self.consistent(matrix, row, col, value):
valid, complete = False, True
return valid, complete, row, col
matrix[row][col] = value
ctr += 1
else: complete = False
if ctr<17: valid = False # Sudoku must include at least 17 clues
return valid, complete
# ----- check if solution is valid ----- #
def checkSOLUTION(self):
self.getinput(self.solution)
CHECK = self.checkSUDOKU(self.solution)
if CHECK[0] and CHECK[1]: self.message_txt.set("Solution correct!")
elif not CHECK[1]: self.message_txt.set("Sudoku is not complete!")
elif not CHECK[0]: self.message_txt.set("Mistake at row %s, col %s"
% (CHECK[2], CHECK[3]))
self.reset_message()
# ----- write user input into values{} ----- #
def getinput(self, matrix):
for row in range(9):
for col in range(9):
value = self.values[row,col].get()
if value=='': matrix[row][col] = ' '
elif len(value)!=1: matrix[row][col] = ' '
elif not value.isdigit(): matrix[row][col] = ' '
elif int(value)<1 or int(value)>9: matrix[row][col] = ' '
else : matrix[row][col] = value
# ----- check if this input leads to a valid solution ----- #
def consistent(self, matrix, row, col, value):
for i in range(9):
if matrix[row][i]==value: return False
if matrix[i][col]==value: return False
rowStart = row - row%3
colStart = col - col%3
for m in range(3):
for k in range(3):
if matrix[rowStart+k][colStart+m]==value: return False
return True
def path_to(self, name):
return os.path.join(self.sudokudir, name)
def execute_solver(self):
self.getinput(self.sudoku) # user input from GUI -> sudoku array
if not self.checkSUDOKU(self.sudoku)[0]: # check if user input makes sense
self.message_txt.set("This sudoku does not have a solution")
self.reset_message()
else:
if self.disabled:
self.message_txt.set("warning, It's still calculating...")
self.reset_message()
return
def callback(result):
self.disabled = False
status, self.solution, N = result
self.pbar.stop()
self.printSUDOKU(self.sudoku)
self.printSUDOKU(self.solution)
self.message_txt.set('Solution found! %s backtracks needed' % N if status else 'No Solution found!')
self.fill_solution()
self.reset_message(10000)
self.disabled = True
self.pbar.start(20)
tk_call_async(self, Solver.do_solve, args=(self.sudoku,),
callback=callback, method=MULTIPROCESSING)
def fill_solution(self):
for row in range(9):
for col in range(9):
self.values[row,col].delete(0,END)
self.values[row,col].insert(0,self.solution[row][col])
def start_timer(self):
if self.timer_mode == 'stopped':
self.startBtn.configure(text='stop')
self.timer_mode = 'running'
elif self.timer_mode == 'running':
self.startBtn.configure(text='start')
self.timer_mode = 'stopped'
def timer():
if self.timer_mode == 'stopped': return
if self.seconds == 60:
self.seconds = 0
self.minutes += 1
if self.seconds > 9 and self.minutes > 9:
self.time_txt.set('{}:{}'.format(self.minutes, self.seconds))
elif self.seconds > 9 and self.minutes <= 9:
self.time_txt.set('0{}:{}'.format(self.minutes, self.seconds))
elif self.seconds <= 9 and self.minutes <= 9:
self.time_txt.set('0{}:0{}'.format(self.minutes, self.seconds))
elif self.seconds <= 9 and self.minutes > 9:
self.time_txt.set('{}:0{}'.format(self.minutes, self.seconds))
self.seconds += 1
self.after(1000, timer)
timer()
def reset_timer(self):
self.startBtn.configure(text='start')
self.minutes = 0
self.seconds = 0
self.timer_mode = 'stopped'
self.time_txt.set('0{}:0{}'.format(self.minutes, self.seconds))
def reset_message(self,DELAY=5000):
def reset():
self.message_txt.set('')
self.after(DELAY, reset)
# SudokuSolver_main.py
from multiprocessing import freeze_support
if __name__ == '__main__':
freeze_support()
import SudokuSolver_class as Sudokuolver
from tkinter import Tk
def main():
root = Tk()
app = Sudokuolver.SudokuSolver(root)
root.mainloop()
main()
Next:
- Button that stops backtracking process. I have already tried a few things, but none auf them worked
- Timecounter (how long did backtracking take)