SOLVED: Implement the constraints satisfaction problem which can solve Odd/Even/Prime Sudoku puzzle.

Implement the constraints satisfaction problem which can solve Odd/Even/Prime Sudoku puzzle.  You have to define the constrains, find domains, variables and non empty domain of possible values of each variable. After defining constrain use backtracking algorithm to solve the puzzle. Please read following instruction carefully for the development of program.

 

   To solve the puzzle, player has to fill 9x9 grids with single digit numbers (1 to 9). Out of 81 cells 9 cells are green color cells and their position is fixed. Remaining 72 cells are either gray or white colored. Gray and white colors are randomly allocated to the cells at the beginning of the game. Within the rows and columns are 9 “squares” (made up of 3 x 3 spaces). Each 3x3 space must have one green color cell at the center. Each row, column and square (9 spaces each) needs to be filled out without repeating any numbers within the row, column or square. Green colored cells must be filled with prime numbers (2, 3, 5, and 7). Gray color cells must be filled with odd numbers (1,3,5,7,9) and white color cell must be filled with even number(2,4,6,8). At the beginning of the game 25% random location must be filled with numbers.

Solution

 class soduku_solver:

# A Utility Function to print the Grid 

  def print_grid(self, arr): 

      for i in range(9): 

          for j in range(9): 

            print(arr[i][j],end=' ')

          print('n') 

  

          

# Function to Find the entry in the Grid that is still  not used 

# Searches the grid to find an entry that is still unassigned. If 

# found, the reference parameters row, col will be set the location 

# that is unassigned, and true is returned. If no unassigned entries 

# remains, false is returned. 

# 'l' is a list  variable that has been passed from the solve_sudoku function 

# to keep track of incrementation of Rows and Columns 

  def find_empty_location(self, arr, l): 

      for row in range(9): 

          for col in range(9): 

              if(arr[row][col]== 0): 

                  l[0]= row 

                  l[1]= col 

                  return True

      return False

  

# Returns a boolean which indicates whether any assigned entry 

# in the specified row matches the given number. 

  def used_in_row(self, arr, row, num): 

      for i in range(9): 

          if(arr[row][i] == num): 

              return True

      return False

  

# Returns a boolean which indicates whether any assigned entry 

# in the specified column matches the given number. 

  def used_in_col(self, arr, col, num): 

      for i in range(9): 

          if(arr[i][col] == num): 

              return True

      return False

  

# Returns a boolean which indicates whether any assigned entry 

# within the specified 3x3 box matches the given number 

  def used_in_box(self, arr, row, col, num): 

      for i in range(3): 

          for j in range(3): 

              if(arr[i + row][j + col] == num): 

                  return True

      return False

  

# Checks whether it will be legal to assign num to the given row, col 

# Returns a boolean which indicates whether it will be legal to assign 

# num to the given row, col location. 

  def check_location_is_safe(self, arr, row, col, num): 

        

      # Check if 'num' is not already placed in current row, 

      # current column and current 3x3 box 

      return not soduku_solver.used_in_row(self,arr, row, num) and not soduku_solver.used_in_col(self,arr, col, num) and not soduku_solver.used_in_box(self,arr, row - row % 3, col - col % 3, num) 

  

# Takes a partially filled-in grid and attempts to assign values to 

# all unassigned locations in such a way to meet the requirements 

# for Sudoku solution (non-duplication across rows, columns, and boxes) 

  def solve_sudoku(self,arr): 

        

      # 'l' is a list variable that keeps the record of row and col in find_empty_location Function     

      l =[0, 0] 

        

      # If there is no unassigned location, we are done     

      if(not soduku_solver.find_empty_location(self,arr, l)): 

        return True

        

      # Assigning list values to row and col that we got from the above Function  

      row = l[0] 

      col = l[1] 

        

      # consider digits 1 to 9 

      for num in range(1, 10): 

            

          # if looks promising 

          if(soduku_solver.check_location_is_safe(self,arr, row, col, num)): 

                

              # make tentative assignment 

              arr[row][col]= num 

    

              if(self.solve_sudoku(arr)): 

                return True

    

              # failure, unmake & try again 

              arr[row][col] = 0

                

      

      # this triggers backtracking         

      return False 

    

# Driver main function to test above functions 

if __name__=="__main__": 

      

    # creating a 2D array for the grid 

    grid =[[0 for x in range(9)]for y in range(9)] 

      

    # assigning values to the grid 

    grid =[[3, 0, 6, 5, 0, 8, 4, 0, 0], 

          [5, 2, 0, 0, 0, 0, 0, 0, 0], 

          [0, 8, 7, 0, 0, 0, 0, 3, 1], 

          [0, 0, 3, 0, 1, 0, 0, 8, 0], 

          [9, 0, 0, 8, 6, 3, 0, 0, 5], 

          [0, 5, 0, 0, 9, 0, 6, 0, 0], 

          [1, 3, 0, 0, 0, 0, 2, 5, 0], 

          [0, 0, 0, 0, 0, 0, 0, 7, 4], 

          [0, 0, 5, 2, 0, 6, 3, 0, 0]] 

      

    # if success print the grid 

    solver=soduku_solver()

    

    if(solver.solve_sudoku(grid)): 

        solver. print_grid(grid) 

    else: 

        print("No solution exists")