How to check for a valid sudoku in Python

By Suyash pratap Singh

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)