In C, we have used pointers to change the value of the variables (row, col) passed to this function (pass by reference). 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.
#Pseudocode for solving sudoku 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. Else, we will come back and change the digit we used to fill the cell.Now, we will try to fill the next unallocated cell and if this happens successfully, then we will return true.Or else, we will fill an unallocated cell with a digit between 1 to 9 so that there are no conflicts in any of the rows, columns, or the 3x3 sub-matrices.If there are no unallocated cells, then the Sudoku is already solved.We are going to solve our Sudoku in a similar way. In backtracking, we first start with a sub-solution and if this sub-solution doesn't give us a correct final answer, then we just come back and change our sub-solution. Any 3x3 sub-matrix has the same number more than once.Any column contains the same number more than once.Any row contains the same number more than once.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. 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.
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.
0 kommentar(er)
