SUDOKU SOLVER

 SUDOKU SOLVER

1. What is Sudoku? 

Sudoku is a logic-based, combinatorial number-placement puzzle  also called as Number place. In classic sudoku, the objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that compose the grid (also called "boxes", "blocks", or "regions") contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.

Sudoku has many variations of grid sizes or region shapes and all. Also, it has many types in it some are mentioned below:

  • Killer Sudoku
  • Alphabetical Sudoku
  • Hyper Sudoku / Windoku
  • Twin Sudoku
These are the few mentioned sudokus. We are going to create one mathematical sudoku with 9*9 grid and 3*3 subgrids in it.


Fig 1. this is the 9*9 grid for our sudoku solver.

2. Algorithm Used for our Sudoku Solver.

We have many different algorithms to solve our sudoku like Stochastic search/optimization method, Constraint Programming, Exact cover and Backtracking etc. 
Here, we are using backtracking as our algorithm for our sudoku.

2.1 What is Backtracking?

Some hobbyists have developed computer programs that will solve Sudoku puzzles using a backtracking algorithm, which is a type of brute force search. Backtracking is a depth-first search (in contrast to a breadth-first search), because it will completely explore one branch to a possible solution before moving to another branch. Although it has been established that approximately 5.96 x 1126 final grids exist, a brute force algorithm can be a practical method to solve Sudoku puzzles.

A brute force algorithm visits the empty cells in some order, filling in digits sequentially, or backtracking when the number is found to be not valid. Briefly, a program would solve a puzzle by placing the digit "1" in the first cell and checking if it is allowed to be there. If there are no violations (checking row, column, and box constraints) then the algorithm advances to the next cell and places a "1" in that cell. When checking for violations, if it is discovered that the "1" is not allowed, the value is advanced to "2". If a cell is discovered where none of the 9 digits is allowed, then the algorithm leaves that cell blank and moves back to the previous cell. The value in that cell is then incremented by one. This is repeated until the allowed value in the last (81st) cell is discovered.

The animation shows how a Sudoku is solved with this method. The puzzle's clues (red numbers) remain fixed while the algorithm tests each unsolved cell with a possible solution. Notice that the algorithm may discard all the previously tested values if it finds the existing set does not fulfil the constraints of the Sudoku.



Fig 2. Animation of solving sudoku using backtracking


Advantages of this method are:

  • A solution is guaranteed (as long as the puzzle is valid).
  • Solving time is mostly unrelated to degree of difficulty.
  • The algorithm (and therefore the program code) is simpler than other algorithms, especially compared to strong algorithms that ensure a solution to the most difficult puzzles.

The disadvantage of this method is that the solving time may be slow compared to algorithms modeled after deductive methods. One programmer reported that such an algorithm may typically require as few as 15,000 cycles, or as many as 900,000 cycles to solve a Sudoku, each cycle being the change in position of a "pointer" as it moves through the cells of a Sudoku.

3. Code for solving Sudoku using Backtracking:

  # Solve using backtracking    
    def solve(self):
        # Find next empty cell
        findEmpty = self.emptyCell()
        
        if not findEmpty:
            return True   
        else:
            row, column = findEmpty
        
        for i in range(1,10):
            if self.isValid(i, (row, column)):
                filledBoard[row][column].set(i)

                if self.solve():
                    return True

                filledBoard[row][column].set(0)
        
        return False

    # Check row, column and subgrid(3x3 square) to see if number can be placed in cell          
    def isValid (self, num, pos):
        # Check Row
        for i in range(9):
            if filledBoard[pos[0]][i].get() == str(num):
                return False
        # Check Column 
        for i in range(9):
            if filledBoard[i][pos[1]].get() == str(num):
                return False

        # Check Sub Grid
        row = pos[0] // 3 
        column = pos[1] // 3 

        for i in range(row * 3, (row * 3) + 3):
            for j in range(column * 3, (column * 3) + 3):
                if filledBoard[i][j].get() == str(num):
                    return False 
        return True
This above given code is in Python. It's just a code for algorithm.

4. Complete code in Python for Sudoku Solver GUI:

from tkinter import *

root = Tk()
root.geometry('330x370')
  
# Sudoku solver class
class SudokuSolver():

    def __init__(self):
        self.setZero()
        self.solve()
        
    # Set the empty cells to 0 (i.e. the cells you have not filled in)
    def setZero(self):
        for i in range(9):
            for j in range(9):
                if filledBoard[i][j].get() not in ['1','2','3','4','5','6','7','8','9']:
                    filledBoard[i][j].set(0)

    # Solve using backtracking    
    def solve(self):
        # Find next empty cell
        findEmpty = self.emptyCell()
        
        if not findEmpty:
            return True   
        else:
            row, column = findEmpty
        
        for i in range(1,10):
            if self.isValid(i, (row, column)):
                filledBoard[row][column].set(i)

                if self.solve():
                    return True

                filledBoard[row][column].set(0)
        
        return False

    # Check row, column and subgrid(3x3 square) to see if number can be placed in cell          
    def isValid (self, num, pos):
        # Check Row
        for i in range(9):
            if filledBoard[pos[0]][i].get() == str(num):
                return False
        # Check Column 
        for i in range(9):
            if filledBoard[i][pos[1]].get() == str(num):
                return False

        # Check Sub Grid
        row = pos[0] // 3 
        column = pos[1] // 3 

        for i in range(row * 3, (row * 3) + 3):
            for j in range(column * 3, (column * 3) + 3):
                if filledBoard[i][j].get() == str(num):
                    return False 
        return True

    # Find empty cells, defined as cells filled with a zero
    def emptyCell(self):
        for row in range(9):
            for column in range(9):
                if filledBoard[row][column].get() == '0':
                    return (row,column)
        return None

# GUI class
class Interface():
    def __init__(self, window):
        self.window = window
        window.title("Sudoku Solver")

        font = ('Arial', 20)
        color = 'white'

        # Create solve and clear button and link them to Solve and Clear methods
        solve = Button(window, text = 'Solve', command = self.Solve)
        solve.grid(column=3,row=20)
        clear = Button(window, text = 'Clear', command = self.Clear)
        clear.grid(column = 5,row=20)

        # Initialise empty 2D list
        self.board  = []
        for row in range(9):
            self.board += [["","","","","","","","",""]]

        for row in range(9):
            for col in range(9):
                # Change color of cells depending on position in grid
                if (row < 3 or row > 5) and (col < 3 or col > 5):
                    color = 'white' 
                elif (row >= 3 and row < 6) and (col >=3 and col < 6):
                    color = 'white'
                else:
                    color = 'grey'
                
                # Make each cell of grid a entry box and store each user entry into the filledBoard 2D list
                self.board[row][col] = Entry(window, width = 2, font = font, bg = color, cursor = 'arrow', borderwidth = 2,
                                          highlightcolor = 'yellow', highlightthickness = 0, highlightbackground = 'black', 
                                          textvariable = filledBoard[row][col]) 
                self.board[row][col].bind('<FocusIn>', self.gridChecker) 
                self.board[row][col].bind('<Motion>', self.gridChecker)                        
                self.board[row][col].grid(row = row, column = col)

    # Function to check if user enters a value which is not an int between 1 and 9 (valid numbers in Sudoku game).
    # If entry is not valid, clear value
    def gridChecker(self, event):
        for row in range(9):
            for col in range(9):
                if filledBoard[row][col].get() not in ['1','2','3','4','5','6','7','8','9']:
                    filledBoard[row][col].set('')

    # Call Sudoku solver class (called by solve button)
    def Solve(self):
        SudokuSolver()

    # Function to clear board (called by clear button) 
    def Clear(self):
        for row in range(9):
            for col in range(9):
                filledBoard[row][col].set('')

# Global 2D list which saved in the values the user enters on the GUI
# Each value in the 2D list is set as a StringVar(), a class in Tkinter
# which allows you to save values users enter into the Entry widget
filledBoard = []
for row in range(9): 
    filledBoard += [["","","","","","","","",""]]
for row in range(9):
    for col in range(9):
        filledBoard[row][col] = StringVar(root)    

# Main Loop
Interface(root)
root.mainloop()





This is complete python code for Sudoku Solver GUI.

Output of above program is :


Fig 3. Output of Sudoku solver.

Here, we can type the numbers for solving the sudoku and we get the desired output i.e. solution for our sudoku.

5. Conclusion :

Here, above we learnt about the sudoku and about the algorithms to solve the sudoku. Also, we learnt about the how to solve sudoku in Python. Code and output for solving Sudoku in Python is given above. 

6. References:

  • https://en.wikipedia.org/wiki/Sudoku 
  • https://en.wikipedia.org/wiki/Backtracking
  • https://en.wikipedia.org/wiki/Sudoku_solving_algorithms


Comments

Post a Comment