How to check for a valid sudoku in Python
Hello friends, In this tutorial, we learn about Sudoku game, which is represented as 9 * 9 matrix. The following conditions are given below:
Check the sum on each line.
Check the amount on each column.
Amount checked on each box.
Check whether for duplicate numbers on each line.
Examine duplicate numbers on each column.
Check duplicate numbers on each box.
Note: An empty Sudoku game is also valid to play.
Important note
Sudoku is a logic-based number-placement puzzle, The objective of the puzzle is to fill n * n grid with digits so that:-
- All the column of the square contains each of the numbers from 1 to n only once.
- All the row of the square contains each of the numbers from 1 to n only once.
But the pseudo code is:
To solve the above sudoku game, we will follow these steps as given below:
- for i in range 1 to 9
- create some empty dictionary called row, col and block, row_cube := 3 * (i / 3), and col_cube := 3 * (i mod 3)
- for j in range 1 to 9
- If the board [i, j] is not empty and the board [i, j] is not in the row, it is incorrect
Line [board [i, j]]: = 1
If board [j, i] is not empty and col does not contain board [j, i], it is incorrect
col [board [j, i]]: = 1
r c: = row_cube + j / 3 and cc: = col_cube + j mod 3
If the board [r c, cc] is not blank in the block and the board [rc, cc] is false
Block [Board [RC, CC]]: = 1
- return true
Code implementation:
def valid_row(row, grid): temp = grid[row] # Removing 0's. temp = list(filter(lambda a: a != 0, temp)) # Checking for invalid values. if any(i < 0 and i > 9 for i in temp): print("Invalid value") return -1 # Checking for repeated values. elif len(temp) != len(set(temp)): return 0 else: return 1 def valid_col(col, grid): # Extracting the column. temp = [row[col] for row in grid] # Removing 0's. temp = list(filter(lambda a: a != 0, temp)) # Checking for invalid values. if any(i < 0 and i > 9 for i in temp): print("Invalid value") return -1 # Checking for repeated values. elif len(temp) != len(set(temp)): return 0 else: return 1 def valid_subsquares(grid): for row in range(0, 9, 3): for col in range(0,9,3): temp = [] for r in range(row,row+3): for c in range(col, col+3): if grid[r][c] != 0: temp.append(grid[r][c]) # Checking for invalid values. if any(i < 0 and i > 9 for i in temp): print("Invalid value") return -1 # Checking for repeated values. elif len(temp) != len(set(temp)): return 0 return 1 # Function to check if the board invalid. def valid_board(grid): for i in range(9): res1 = valid_row(i, grid) res2 = valid_col(i, grid) if (res1 < 1 or res2 < 1): print("The board is invalid") return res3 = valid_subsquares(grid) if (res3 < 1): print("The board is invalid") else: print("The board is valid") def print_board(grid): for row in grid: print(row) board = [[1, 4, 7, 0, 0, 0, 0, 0, 3], [2, 5, 0, 0, 0, 1, 0, 0, 0], [3, 0, 9, 0, 0, 0, 0, 0, 0], [0, 8, 0, 0, 2, 0, 0, 0, 4], [0, 0, 0, 4, 1, 0, 0, 2, 0], [9, 0, 0, 0, 0, 0, 6, 0, 0], [0, 0, 3, 0, 0, 0, 0, 0, 9], [4, 0, 0, 0, 0, 2, 0, 0, 0], [0, 0, 1, 0, 0, 8, 0, 0, 7]] print_board(board) valid_board(board) board2 = [[1, 4, 4, 0, 0, 0, 0, 0, 3], [2, 5, 0, 0, 0, 1, 0, 0, 0], [3, 0, 9, 0, 0, 0, 0, 0, 0], [0, 8, 0, 0, 2, 0, 0, 0, 4], [0, 0, 0, 4, 1, 0, 0, 2, 0], [9, 0, 0, 0, 0, 0, 6, 0, 0], [0, 0, 3, 0, 0, 0, 0, 0, 9], [4, 0, 0, 0, 0, 2, 0, 0, 0], [0, 0, 1, 0, 0, 8, 0, 0, 7]] print_board(board2) valid_board(board2)
Code Implementation:
correct = [[1,3,2], [2,1,3], [3,2,1]] incorrect = [[1,2,4,3], [2,3,1,3], [3,1,2,3], [4,2,2,4]] def check_sudoku(game): n = len(game) if n < 1: return False for i in range(0, n): horizontal = [] vertical = [] for k in range(0, n): #vertical check if game[k][i] in vertical: return False vertical.append(game[k][i]) if game[i][k] in horizontal: return False horizontal.append(game[i][k]) return True print (check_sudoku(correct)) print (check_sudoku(incorrect))
Output:
True False
Time complexity:
O(9^(n*n))
Space complexity:
O(n*n)
Leave a Reply