Number_unassigned → This function finds a vacant cell and makes the variables ‘row’ and ‘col’ equal to indices of that cell. Print_sudoku() → This is just a function to print the matrix. Thus, the matrix contains the Sudoku problem and the cells with value 0 are vacant cells. Initially, we are just making a matrix for Sudoku and filling its unallocated cells with 0.
#Sudoku generator algorithm code#
SIZE = 9 #sudoku problem #cells with value 0 are vacant cells matrix =, ,, ,, ,, , ] #function to print sudoku def print_sudoku (): for i in matrix : print ( i ) #function to check if all cells are assigned or not #if there is any unassigned cell #then this function will change the values of #row and col accordingly def number_unassigned ( row, col ): num_unassign = 0 for i in range ( 0, SIZE ): for j in range ( 0, SIZE ): #cell is unassigned if matrix = 0 : row = i col = j num_unassign = 1 a = return a a = return a #function to check if we can put a #value in a paticular cell or not def is_safe ( n, r, c ): #checking in row for i in range ( 0, SIZE ): #there is a cell with same value if matrix = n : return False #checking in column for i in range ( 0, SIZE ): #there is a cell with same value if matrix = n : return False row_start = ( r // 3 ) * 3 col_start = ( c // 3 ) * 3 #checking submatrix for i in range ( row_start, row_start + 3 ): for j in range ( col_start, col_start + 3 ): if matrix = n : return False return True #function to check if we can put a #value in a paticular cell or not def solve_sudoku (): row = 0 col = 0 #if all cells are assigned then the sudoku is already solved #pass by reference because number_unassigned will change the values of row and col a = number_unassigned ( row, col ) if a = 0 : return True row = a col = a #number between 1 to 9 for i in range ( 1, 10 ): #if we can assign i to the cell or not #the cell is matrix if is_safe ( i, row, col ): matrix = i #backtracking if solve_sudoku (): return True #f we can't proceed with this solution #reassign the cell matrix = 0 return False if solve_sudoku (): print_sudoku () else : print ( "No solution" ) Explanation of the code #include #define SIZE 9 //sudoku problem int matrix = Python If there is no digit which fulfills the need, then we will just return false as there is no solution of this Sudoku.
![sudoku generator algorithm sudoku generator algorithm](https://img.itch.zone/aW1hZ2UvNDgxMzYvMjA5NTc4LnBuZw==/original/CAmmHd.png)
Thus, we can also conclude that a Sudoku is considered wrongly filled if it satisfies any of these criteria: You can see that every row, column, and sub-matrix (3x3) contains each digit from 1 to 9.
![sudoku generator algorithm sudoku generator algorithm](http://toms-cafe.de/vdr/sudoku/srcdoc/classSudoku_1_1Generator__inherit__graph.png)
For example, a Sudoku problem is given below. We are provided with a partially filled 9x9 matrix and have to fill every remaining cell in it. Sudoku is a 9x9 matrix filled with numbers 1 to 9 in such a way that every row, column and sub-matrix (3x3) has each of the digits from 1 to 9.
![sudoku generator algorithm sudoku generator algorithm](https://www.codeproject.com/KB/game/SudokuGen/AlgorithmTree.jpg)
If you don't know about backtracking, then just brush through the previous post. In this post, I will introduce a Sudoku-solving algorithm using backtracking.