Created
August 26, 2024 13:28
-
-
Save sujay1844/ed86ed0892ca5ed85fa7cce8af055f0c to your computer and use it in GitHub Desktop.
Sudoku Solver
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def solve_sudoku(puzzle): | |
| def find_empty(puzzle): | |
| for i in range(9): | |
| for j in range(9): | |
| if puzzle[i][j] == 0: | |
| return (i, j) | |
| return None | |
| def is_valid(puzzle, row, col, num): | |
| # check row | |
| for j in range(9): | |
| if puzzle[row][j] == num: | |
| return False | |
| # check column | |
| for i in range(9): | |
| if puzzle[i][col] == num: | |
| return False | |
| # check square | |
| square_row = (row // 3) * 3 | |
| square_col = (col // 3) * 3 | |
| for i in range(square_row, square_row + 3): | |
| for j in range(square_col, square_col + 3): | |
| if puzzle[i][j] == num: | |
| return False | |
| return True | |
| def solve(puzzle): | |
| empty_cell = find_empty(puzzle) | |
| if empty_cell is None: | |
| return True | |
| row, col = empty_cell | |
| for num in range(1, 10): | |
| if is_valid(puzzle, row, col, num): | |
| puzzle[row][col] = num | |
| if solve(puzzle): | |
| return True | |
| puzzle[row][col] = 0 | |
| return False | |
| # create a copy of the input puzzle to avoid modifying the original | |
| puzzle_copy = [row[:] for row in puzzle] | |
| # solve the puzzle | |
| solve(puzzle_copy) | |
| return puzzle_copy | |
| def test_solve_sudoku(): | |
| puzzle = [ | |
| [0, 0, 0, 2, 6, 0, 7, 0, 1], | |
| [6, 8, 0, 0, 7, 0, 0, 9, 0], | |
| [1, 9, 0, 0, 0, 4, 5, 0, 0], | |
| [8, 2, 0, 1, 0, 0, 0, 4, 0], | |
| [0, 0, 4, 6, 0, 2, 9, 0, 0], | |
| [0, 5, 0, 0, 0, 3, 0, 2, 8], | |
| [0, 0, 9, 3, 0, 0, 0, 7, 4], | |
| [0, 4, 0, 0, 5, 0, 0, 3, 6], | |
| [7, 0, 3, 0, 1, 8, 0, 0, 0] | |
| ] | |
| solution = solve_sudoku(puzzle) | |
| for row in solution: | |
| print(*row, sep=' ') | |
| test_solve_sudoku() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment