This project aims to create and solve Sudoku as a Constraint Satisfaction Problem.
Sudoku is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that compose the grid (also called "boxes", "blocks", or "regions") contain all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.
- Install python Here
In this project, there are two different algorithms used to solve the Sudoku: Simple Backtracking and Backtracking with Forward-Checking.
Here's a breakdown of the code function by function:
generate_sudoku: This function generates a Sudoku puzzle. It first fills the diagonal boxes of the grid with random numbers, then solves the grid, and finally removes a random number of elements from the grid to create the puzzle. The sudoku is generated and ready to be solved.
fill_diagonal: This function fills the diagonal boxes of the Sudoku grid.
fill_box: This function fills a 3x3 box with random values.
is_safe: This function checks if it's safe to place a number in a particular position. It checks if the number is already used in the same row, column, or 3x3 box.
used_in_row: This function checks if a number is used in a row.
used_in_column: This function checks if a number is used in a column.
used_in_box: This function checks if a number is used in a 3x3 box.
find_unassigned_location: This function finds an unassigned location in the grid.
remove_elements: This function removes a certain number of elements from the grid.
solve_sudoku: This function solves the Sudoku puzzle using backtracking. It finds an unassigned location in the grid, then for each value from 1 to 9, it checks if it's safe to place the value at that location. If it is, it places the value and recursively tries to solve the rest of the grid. If it can't solve the grid with that value, it backtracks and tries the next value.
display_grid: This function displays the Sudoku grid.
solve_sudoku_forward_checking: This function solves the Sudoku puzzle using forward checking that is a common filtering. It first creates domains for each cell in the grid, which are the possible values that can be placed in that cell. Then it finds an unassigned location in the grid and for each value in the domain of that location, it checks if it's a valid assignment. If it is, it assigns the value and recursively tries to solve the rest of the grid. If it can't solve the grid with that value, it removes the value from the domain and tries the next value.
initializing_grid: This function generates and displays the initial Sudoku grid.
backtracking_answer: This function solves the Sudoku grid using backtracking and displays the result.
backtracking_forward_checking_answer: This function solves the Sudoku grid using backtracking with forward checking and displays the result.
Main: The main part of the script generates a Sudoku puzzle, makes two copies of it, and then solves it using both simple backtracking and backtracking with forward checking. It prints the initial Sudoku grid, the solved grid, and the number of steps taken to solve the grid for both methods.
Distributed under the MIT License.
This code is provided by ErfanXH and all rights are reserved.
Project Link: https://github.com/ErfanXH/Sudoku-AI