Python Forum

Hi,

I am new to Python and programming in general. What I want to do is build a kind of "sudoku-solver" which is capable of doing the following tasks:
- let the user enter a random sudoku
- solve the sudoku via backtracking if it has a solution
- save sudoku and solution to a .txt file
- import sudokus from .txt file
...

This is how it looks like:


When pressing the solve button, this function is called:

    def solveSUDOKU(self):

        self.getinput(self.sudoku)  # get user input from GUI and write it into sudoku arrey
        if not self.checkSUDOKU(self.sudoku)[0]:    # check if user input makes sense
            self.message_txt.set("This sudoku does not have a solution")
        # ----- save time how long the solving took ----- #
        else:
            start = time.time()
            solve(0)    # start backtracking
            end = time.time()
            self.message_txt.set("%s seconds, %s backtracks"%(round((end-start),3)
                                                              ,self.backtrack_ctr))
            self.backtrack_ctr = 0      # reset backtrack counter

            # ----- fill all fields with the solution ----- #
            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])

solve(0) is calling this recursive function:

def solve(num):
    SudokuSolver.backtrack_ctr += 1
    if num==81:
        print("Solution found!")
        SudokuSolver.solution = SudokuSolver.copy(SudokuSolver,SudokuSolver.sudoku)
        return True
    else:
        row = int(num / 9)
        col = num % 9
        if SudokuSolver.sudoku[row][col]!=' ':
            solve(num+1)
        else:
            for value in range(1,10):
                if SudokuSolver.consistent(SudokuSolver,SudokuSolver.sudoku,
                                           row,col,str(value)):
                    SudokuSolver.sudoku[row][col]=str(value)
                    if solve(num+1): return True
                SudokuSolver.sudoku[row][col]=' '
            return False

This backtracking can take some time (depending on the sudoku). After a few seconds tkinter freezes and you cant do anything. Is there any possibility to not "crash" the GUI while waiting for the solution? I have looked into multiprocessing and multithreading but I didnt really understand how to do it.

Searching 'long running task in tkinter' in a search engine yields many related links. Here is a full example from zetcode, and here is an active state recipe that should adapt readily to your case.

I have rearranged my program according to "full example from zetcode":

function called when "solve" is pressed

    def solveSUDOKU(self):

        self.getinput(self.sudoku)  # get user input from GUI and write it into sudoku arrey
        if not self.checkSUDOKU(self.sudoku)[0]:    # check if user input makes sense
            self.message_txt.set("This sudoku does not have a solution")
        # ----- save time how long the solving took ----- #
        else:
            self.solveBtn.config(state=DISABLED)
            self.start = time.time()
            self.p = Process(target=solve, args=(0, q, self.sudoku))
            self.p.start()
            self.after(80, self.writeSUDOKU)

backtracking algorythm:

def solve(num, q, sudoku):
    SudokuSolver.backtrack_ctr += 1
    print(SudokuSolver.backtrack_ctr)
    if num==81:
        print("Solution found!")
        q.put(sudoku)
        return True
    else:
        row = int(num / 9)
        col = num % 9
        if sudoku[row][col]!=' ':
            solve(num+1,q,sudoku)
        else:
            for value in range(1,10):
                if SudokuSolver.consistent(SudokuSolver,sudoku,
                                           row,col,str(value)):
                    sudoku[row][col]=str(value)
                    if solve(num+1,q,sudoku): return True
                sudoku[row][col]=' '
            return False

q = Queue()

function that is supposed to be called after the backtracking process has finished:

    def writeSUDOKU(self):

        if(self.p.is_alive()):
            self.after(80, self.writeSUDOKU)
            return
        else:
            self.end = time.time()
            self.message_txt.set("%s seconds, %s backtracks"%(round((self.end-self.start),3)
                                                              ,self.backtrack_ctr))
            self.backtrack_ctr = 0      # reset backtrack counter
            self.solveBtn.config(state=NORMAL)
            # ----- fill all fields with the solution ----- #
            for row in range(9):
                for col in range(9):
                    self.values[row,col].delete(0,END)
                    self.values[row,col].insert(0,q.get()[row][col])

Now my program crashes instantly when I press "solve". I used that "print(SudokuSolver.backtrack_ctr)" statement to find out where the error might occur, but the number does not show up even once in python shell. So this might indicate that my program crashes as soon as the process "p" is started and the solve() backtracking-function is not called at all.

It is difficult to help without the whole code. I'd like to try and run the program. Can you write a working program without GUI that finds the solution of the sudoku? You need to separate completely the GUI part and the solving part.

Yes, sure...

sudoku = [[' ',' ',' ','2','1',' ',' ',' ',' '],
          [' ',' ','7','3',' ',' ',' ',' ',' '],
          [' ','5','8',' ',' ',' ',' ',' ',' '],
          ['4','3',' ',' ',' ',' ',' ',' ',' '],
          ['2',' ',' ',' ',' ',' ',' ',' ','8'],
          [' ',' ',' ',' ',' ',' ',' ','7','6'],
          [' ',' ',' ',' ',' ',' ','2','5',' '],
          [' ',' ',' ',' ',' ','7','3',' ',' '],
          [' ',' ',' ',' ','9','8',' ',' ',' ']]

def printSUDOKU(matrix):
    for row in range(9):
        print("|-----------------------------------|")
        for col in range(9):
            print("| " + matrix[row][col] + " ",end='')
        print("|")
    print("|-----------------------------------|")

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

def solve(num):
    if num==81:
        print("Solution found!")
        printSUDOKU(sudoku)
        return True
    else:
        row = int(num / 9)
        col = num % 9
        if sudoku[row][col]!=' ':
            solve(num+1)
        else:
            for value in range(1,10):
                if consistent(sudoku, row, col, str(value)):
                    sudoku[row][col] = str(value)
                    if solve(num+1): return True
                sudoku[row][col]=' '
            return False

printSUDOKU(sudoku)
solve(0)

I don't see any tkinter in your code, other than the title. If you are using tkinter then use after() with a small time out to schedule a new task, which will not cause the program to hang.

        if sudoku[row][col]!=' ':
            root.after(100, solve, num+1)  ## waits 1/10 of a second 

If you are not using tkinter, post back and I will add a multiprocessing Process to do this.

I made it work by using the active state recipe, which I saved verbatim as a file tkcallasync.py. Then I changed your code a little in a file solvesudo.py

# solvesudo.py
sudoku = [[' ',' ',' ','2','1',' ',' ',' ',' '],
          [' ',' ','7','3',' ',' ',' ',' ',' '],
          [' ','5','8',' ',' ',' ',' ',' ',' '],
          ['4','3',' ',' ',' ',' ',' ',' ',' '],
          ['2',' ',' ',' ',' ',' ',' ',' ','8'],
          [' ',' ',' ',' ',' ',' ',' ','7','6'],
          [' ',' ',' ',' ',' ',' ','2','5',' '],
          [' ',' ',' ',' ',' ','7','3',' ',' '],
          [' ',' ',' ',' ','9','8',' ',' ',' ']]
 
def printSUDOKU(matrix):
    for row in range(9):
        print("|-----------------------------------|")
        for col in range(9):
            print("| " + matrix[row][col] + " ",end='')
        print("|")
    print("|-----------------------------------|")
 
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
    return False

def solve(sudoku, num):
    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)

Finally, I wrote a small tkinter code, tksudo.py, similar to the example in the active state recipe

# tksudo.py
from tkinter import Tk, Frame, Entry, Label, Button, IntVar, StringVar, LEFT
from tkinter import messagebox
from tkcallasync import tk_call_async, MULTIPROCESSING
import solvesudo

def do_solve(sudoku):
    status = solvesudo.wsolve(sudoku)
    return status, sudoku

disabled = False

def execute_solver():
    global disabled
    if disabled:
        messagebox.showinfo("warning", "It's still calculating...")
        return

    def callback(result):
        global disabled
        disabled = False
        status, sudoku = result
        solvesudo.printSUDOKU(sudoku)
        result_var.set('Found!' if status else 'Not Found!')

    disabled = True
    tk_call_async(root, do_solve, args=(solvesudo.sudoku,), callback=callback, method=MULTIPROCESSING)

root = Tk()

row = Frame(root)
row.pack()
Button(row, text="Solve Sudoku", command =execute_solver).pack(side=LEFT)
Button(row, text="It's responsive", command= lambda: messagebox.showinfo("info", "it's responsive")).pack(side=LEFT)

result_var = StringVar()
Label(root, textvariable=result_var).pack()

root.mainloop()

The result is that it works very well (in linux), and the small GUI remains responsive while the peer process computes the solution.

Output:
λ python3 tksudo.py
|-----------------------------------|
| 6 | 4 | 3 | 2 | 1 | 5 | 8 | 9 | 7 |
|-----------------------------------|
| 1 | 2 | 7 | 3 | 8 | 9 | 6 | 4 | 5 |
|-----------------------------------|
| 9 | 5 | 8 | 7 | 6 | 4 | 1 | 2 | 3 |
|-----------------------------------|
| 4 | 3 | 5 | 8 | 7 | 6 | 9 | 1 | 2 |
|-----------------------------------|
| 2 | 7 | 6 | 9 | 5 | 1 | 4 | 3 | 8 |
|-----------------------------------|
| 8 | 9 | 1 | 4 | 3 | 2 | 5 | 7 | 6 |
|-----------------------------------|
| 7 | 8 | 9 | 6 | 4 | 3 | 2 | 5 | 1 |
|-----------------------------------|
| 5 | 6 | 4 | 1 | 2 | 7 | 3 | 8 | 9 |
|-----------------------------------|
| 3 | 1 | 2 | 5 | 9 | 8 | 7 | 6 | 4 |
|-----------------------------------|

Hi, thanks for your help. Unfortunately the code doesnt seem to work on windows. When I press "Solve Sudoku" another instance of tkinter shows up. By pressing it again he says that its still calculating but even after waiting for 10 minutes there is no solution printed in python shell.



@woooee
I am using tkinter but I left out that part of the code because it is a lot and quite messy. Here is the whole code if you are interested:

import time
import os
from random import randint
from tkinter import *


class SudokuSolver(Frame):

    backtrack_ctr = 0
    sudoku = [[" " for col in range(9)] for row in range(9)]
    solution = [[" " for col in range(9)] for row in range(9)]

    def __init__(self, parent):

        Frame.__init__(self, parent, name='frame')
        self.parent = parent
        self.initUI()
        self.newSUDOKU()


    def initUI(self):

        self.message_txt = StringVar()
        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.solveBtn = Button(self, text="solve",width=6,command=self.solveSUDOKU)
        self.solveBtn.grid(row=0,column=0)

        self.newBtn = Button(self, text="new",width=6,command=self.newSUDOKU)
        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.printBtn = Button(self, text="print",width=6,command=self.printSUDOKU)
        self.printBtn.grid(row=0,column=8)

        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)


    # ----- make all fields empty ----- #
    def newSUDOKU(self):

        self.message_txt.set('')
        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 random Sudoku from textfiles ----- #
    def initSUDOKU(self):

        self.newSUDOKU()
        self.message_txt.set('')
        L = len(os.listdir(os.getcwd() + "\sudokus")) / 2
        sudokuFile = open(os.getcwd() + "\sudokus\Sudoku%s.txt" % (randint(1, L)))

        # ----- fill sudoku_original array with values from textfile ----- #
        row, col = 0, 0
        for value in sudokuFile.read():
            if value.isdigit() or value==' ':
                self.sudoku[row][col]=value
                col += 1
                if col==9:
                    if row==8: break
                    row += 1
                    col = 0

        sudokuFile.close()
        self.sudoku_original = self.copy(self.sudoku)

        for row in range(9):
            for col in range(9):
                value = self.sudoku[row][col]
                if value!=' ':
                    self.values[row,col].insert(0,value)


    # ----- 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


    # ----- print matrix ----- #

    def printMATRIX(self, matrix):

        for row in range(9):
            print("|-----------------------------------|")
            for col in range(9):
                print("| " + matrix[row][col] + " ",end='')
            print("|")
        print("|-----------------------------------|")


    # ----- save sudoku ----- #

    def saveSUDOKU(self):

       CHECK = self.checkSUDOKU(self.solution)
       if CHECK[0] and CHECK[1]:
           num = 1
           while os.path.isfile(os.getcwd() + "\sudokus\sudoku%s.txt" % num): num += 1
           sudokuFile = open(os.getcwd() + "\sudokus\sudoku%s.txt" %num, 'w')
           solutionFile = open(os.getcwd() + "\sudokus\solution%s.txt" %num, 'w')

           for row in range(9):
               for col in range(9):
                   sudokuFile.write(self.sudoku_original[row][col])
                   solutionFile.write(self.solution[row][col])
               sudokuFile.write('\n')
               solutionFile.write('\n')
           sudokuFile.close()
           solutionFile.close()
           print("FILES SAVED!")
           self.message_txt.set("Files saved...")



    # ----- print sudoku_original, sudoku, solution ----- #

    def printSUDOKU(self):

        print("Original : ")
        self.printMATRIX(self.sudoku_original)
        print("Sudoku : ")
        self.printMATRIX(self.sudoku)
        print("Solution : ")
        self.printMATRIX(self.solution)
        if  not self.checkSUDOKU(self.sudoku)[0]:
            print("sudoku is not valid")



    # ----- 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


    # ----- check if user input makes sense -----#

    def checkSUDOKU(self, matrix):
        valid, complete, rowM, colM, ctr = True, True, 0, 0, 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
                        rowM, colM = row+1, col+1
                        print("MISTAKE AT row=%s ,col=%s" % (row+1, col+1))
                        return valid, complete, rowM, colM
                    matrix[row][col] = value
                    ctr += 1
                else: complete = False
        if ctr<17: valid = False
        return valid, complete, rowM, colM



    # ----- check if solution is valid ----- #

    def checkSOLUTION(self):

        self.getinput(self.sudoku)
        CHECK = self.checkSUDOKU(self.sudoku)
        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]))



    # ----- returns an exact copy of 2dim array ----- #

    def copy(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



    # ----- solve current sudoku ----- #

    def solveSUDOKU(self):

        self.getinput(self.sudoku)  # get user input from GUI and write it into sudoku arrey
        if not self.checkSUDOKU(self.sudoku)[0]:    # check if user input makes sense
            self.message_txt.set("This sudoku does not have a solution")
        # ----- save time how long the solving took ----- #
        else:
            start = time.time()
            solve(0)    # start backtracking
            end = time.time()
            self.message_txt.set("%s seconds, %s backtracks"%(round((end-start),3)
                                                              ,self.backtrack_ctr))
            self.backtrack_ctr = 0      # reset backtrack counter

            # ----- fill all fields with the solution ----- #
            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])




# ----- backtracking algorithm ----- #

def solve(num):
    SudokuSolver.backtrack_ctr += 1
    if num==81:
        print("Solution found!")
        SudokuSolver.solution = SudokuSolver.copy(SudokuSolver,SudokuSolver.sudoku)
        return True
    else:
        row = int(num / 9)
        col = num % 9
        if SudokuSolver.sudoku[row][col]!=' ':
            solve(num+1)
        else:
            for value in range(1,10):
                if SudokuSolver.consistent(SudokuSolver,SudokuSolver.sudoku,
                                           row,col,str(value)):
                    SudokuSolver.sudoku[row][col]=str(value)
                    if solve(num+1): return True
                SudokuSolver.sudoku[row][col]=' '
            return False



def main():

    root = Tk()
    app = SudokuSolver(root)
    root.mainloop()

if __name__== '__main__':
    main()

if you want the init function to work you have to create a folder called "sudokus" and save it to your working directory. Within that folder you create a .txt file called "sudoku1.txt" with the following content:

   21    
  73     
 58      
43       
2       8
       76
      25 
     73  
    98   

all spaces needed

I have not tried using after() method, yet but I suspect that it would slow down the program substantially because it is called in every backtracking step. For example if there are 10k backtracks needed for a certain sudoku, the program would need 1000s longer than normal and 10k backtracks are not even a lot.

(Mar-31-2018, 08:46 AM)Zatox11 Wrote: [ -> ]When I press "Solve Sudoku" another instance of tkinter shows up. By pressing it again he says that its still calculating but even after waiting for 10 minutes there is no solution printed in python shell.

There is some error in your logic, especially the screenshot shows two instances of the root window. It means that you didn't connect the GUI and the solver the way it should be. Without the whole failing code, it is impossible to debug.

I have 3 files:
1. solvesudo.py - your code
2. tksudo.py - your code
3. tkcallasync.py - code from active state recipe

When I run tksudo.py the root window shows up. Then I click on "Solve Sudoku" and another instance of the root window shows up. When I click "Solve Sudoku" again (does not matter which of the instances) I get the message that it is still calculating, but even after waiting for several minutes nothing happens.