From 935681b3ddd0cd9c2dc0a8b7a220969e270f3829 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Sat, 30 Aug 2025 19:52:37 -0600 Subject: 37. sudoku solver --- sudoku_solver.py | 66 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 66 insertions(+) create mode 100644 sudoku_solver.py (limited to 'sudoku_solver.py') diff --git a/sudoku_solver.py b/sudoku_solver.py new file mode 100644 index 0000000..7a395e7 --- /dev/null +++ b/sudoku_solver.py @@ -0,0 +1,66 @@ +# 37. Sudoku Solver + +""" +write a program to solve a sudoku puzzle by filling the empty cells. a sudoku +solution must satisfy all of the following rules. each of the digits '1-9' +must occur exactly once in each row, each of the digits '1-9', must occur +exactly once in each column, and each of the digits '1-9' must occur exactly +once in each of the 9 3x3 sub-boxes of the grid. the '.' character indicates +empty cells. +""" + + +class Solution(object): + def solveSudoku(self, board): + """ + :type board: List[List[str]] + :rtype: None Do not return anything, modify board in-place instead. + """ + n = 9 + + def valid(row, col, idx): + row, col = int(row), int(col) + for i in range(9): + if board[i][col] == idx: + return False + if board[row][i] == idx: + return False + if board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == idx: + return False + return True + + def solve(row, col): + if row == n: + return True + if col == n: + return solve(row + 1, 0) + if board[row][col] == ".": + for i in range(1, 10): + if valid(row, col, str(i)): + board[row][col] = str(i) + if solve(row, col + 1): + return True + else: + board[row][col] = "." + return False + else: + return solve(row, col + 1) + + solve(0, 0) + + +if __name__ == "__main__": + obj = Solution() + board = [ + ["5", "3", ".", ".", "7", ".", ".", ".", "."], + ["6", ".", ".", "1", "9", "5", ".", ".", "."], + [".", "9", "8", ".", ".", ".", ".", "6", "."], + ["8", ".", ".", ".", "6", ".", ".", ".", "3"], + ["4", ".", ".", "8", ".", "3", ".", ".", "1"], + ["7", ".", ".", ".", "2", ".", ".", ".", "6"], + [".", "6", ".", ".", ".", ".", "2", "8", "."], + [".", ".", ".", "4", "1", "9", ".", ".", "5"], + [".", ".", ".", ".", "8", ".", ".", "7", "9"], + ] + obj.solveSudoku(board) + print(board) -- cgit v1.2.3