Welcome to Subscribe On Youtube
37. Sudoku Solver
Description
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-9must occur exactly once in each row. - Each of the digits
1-9must occur exactly once in each column. - Each of the digits
1-9must occur exactly once in each of the 93x3sub-boxes of the grid.
The '.' character indicates empty cells.
Example 1:
Input: 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"]] Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]] Explanation: The input board is shown above and the only valid solution is shown below:
Constraints:
board.length == 9board[i].length == 9board[i][j]is a digit or'.'.- It is guaranteed that the input board has only one solution.
Solutions
Solution 1: Backtracking
We use arrays row, col, and box to record whether a number has appeared in each row, each column, and each 3x3 grid respectively. If the number i has appeared in the rth row, the cth column, and the bth 3x3 grid, then row[r][i], col[c][i], and box[b][i] are all true.
We traverse each empty space in board, enumerate the numbers v that it can fill in. If v has not appeared in the current row, the current column, and the current 3x3 grid, then we can try to fill in the number v and continue to search for the next empty space. If we search to the end and all spaces are filled, it means that a feasible solution has been found.
The time complexity is $O(9^{81})$, and the space complexity is $O(9^2)$.
-
class Solution { private boolean ok; private char[][] board; private List<Integer> t = new ArrayList<>(); private boolean[][] row = new boolean[9][9]; private boolean[][] col = new boolean[9][9]; private boolean[][][] block = new boolean[3][3][9]; public void solveSudoku(char[][] board) { this.board = board; for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { if (board[i][j] == '.') { t.add(i * 9 + j); } else { int v = board[i][j] - '1'; row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true; } } } dfs(0); } private void dfs(int k) { if (k == t.size()) { ok = true; return; } int i = t.get(k) / 9, j = t.get(k) % 9; for (int v = 0; v < 9; ++v) { if (!row[i][v] && !col[j][v] && !block[i / 3][j / 3][v]) { row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true; board[i][j] = (char) (v + '1'); dfs(k + 1); row[i][v] = col[j][v] = block[i / 3][j / 3][v] = false; } if (ok) { return; } } } } -
using pii = pair<int, int>; class Solution { public: void solveSudoku(vector<vector<char>>& board) { bool row[9][9] = {false}; bool col[9][9] = {false}; bool block[3][3][9] = {false}; bool ok = false; vector<pii> t; for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { if (board[i][j] == '.') { t.push_back({i, j}); } else { int v = board[i][j] - '1'; row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true; } } } function<void(int k)> dfs = [&](int k) { if (k == t.size()) { ok = true; return; } int i = t[k].first, j = t[k].second; for (int v = 0; v < 9; ++v) { if (!row[i][v] && !col[j][v] && !block[i / 3][j / 3][v]) { row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true; board[i][j] = v + '1'; dfs(k + 1); row[i][v] = col[j][v] = block[i / 3][j / 3][v] = false; } if (ok) { return; } } }; dfs(0); } }; -
class Solution: def solveSudoku(self, board: List[List[str]]) -> None: def dfs(k): nonlocal ok if k == len(t): ok = True return i, j = t[k] for v in range(9): if row[i][v] == col[j][v] == block[i // 3][j // 3][v] == False: row[i][v] = col[j][v] = block[i // 3][j // 3][v] = True board[i][j] = str(v + 1) dfs(k + 1) row[i][v] = col[j][v] = block[i // 3][j // 3][v] = False if ok: return row = [[False] * 9 for _ in range(9)] col = [[False] * 9 for _ in range(9)] block = [[[False] * 9 for _ in range(3)] for _ in range(3)] t = [] ok = False for i in range(9): for j in range(9): if board[i][j] == '.': t.append((i, j)) else: v = int(board[i][j]) - 1 row[i][v] = col[j][v] = block[i // 3][j // 3][v] = True dfs(0) -
func solveSudoku(board [][]byte) { var row, col [9][9]bool var block [3][3][9]bool var t [][2]int ok := false for i := 0; i < 9; i++ { for j := 0; j < 9; j++ { if board[i][j] == '.' { t = append(t, [2]int{i, j}) } else { v := int(board[i][j] - '1') row[i][v], col[j][v], block[i/3][j/3][v] = true, true, true } } } var dfs func(int) dfs = func(k int) { if k == len(t) { ok = true return } i, j := t[k][0], t[k][1] for v := 0; v < 9; v++ { if !row[i][v] && !col[j][v] && !block[i/3][j/3][v] { row[i][v], col[j][v], block[i/3][j/3][v] = true, true, true board[i][j] = byte(v + '1') dfs(k + 1) row[i][v], col[j][v], block[i/3][j/3][v] = false, false, false } if ok { return } } } dfs(0) } -
public class Solution { public void SolveSudoku(char[][] board) { this.board = new ushort?[9,9]; for (var i = 0; i < 9; ++i) { for (var j = 0; j < 9; ++j) { if (board[i][j] != '.') { this.board[i, j] = (ushort) (1 << (board[i][j] - '0' - 1)); } } } if (SolveSudoku(0, 0)) { for (var i = 0; i < 9; ++i) { for (var j = 0; j < 9; ++j) { if (board[i][j] == '.') { board[i][j] = '0'; while (this.board[i, j].Value != 0) { board[i][j] = (char)(board[i][j] + 1); this.board[i, j] >>= 1; } } } } } } private ushort?[,] board; private bool ValidateHorizontalRule(int row) { ushort temp = 0; for (var i = 0; i < 9; ++i) { if (board[row, i].HasValue) { if ((temp | board[row, i].Value) == temp) { return false; } temp |= board[row, i].Value; } } return true; } private bool ValidateVerticalRule(int column) { ushort temp = 0; for (var i = 0; i < 9; ++i) { if (board[i, column].HasValue) { if ((temp | board[i, column].Value) == temp) { return false; } temp |= board[i, column].Value; } } return true; } private bool ValidateBlockRule(int row, int column) { var startRow = row / 3 * 3; var startColumn = column / 3 * 3; ushort temp = 0; for (var i = startRow; i < startRow + 3; ++i) { for (var j = startColumn; j < startColumn + 3; ++j) { if (board[i, j].HasValue) { if ((temp | board[i, j].Value) == temp) { return false; } temp |= board[i, j].Value; } } } return true; } private bool SolveSudoku(int i, int j) { while (true) { if (j == 9) { ++i; j = 0; } if (i == 9) { return true; } if (board[i, j].HasValue) { ++j; } else { break; } } ushort stop = 1 << 9; for (ushort t = 1; t != stop; t <<= 1) { board[i, j] = t; if (ValidateHorizontalRule(i) && ValidateVerticalRule(j) && ValidateBlockRule(i, j)) { if (SolveSudoku(i, j + 1)) { return true; } } } board[i, j] = null; return false; } } -
class Solution { /** * @param string[][] $board * @return bool */ public function solveSudoku(&$board) { if (isSolved($board)) { return true; } $emptyCell = findEmptyCell($board); $row = $emptyCell[0]; $col = $emptyCell[1]; for ($num = 1; $num <= 9; $num++) { if (isValid($board, $row, $col, $num)) { $board[$row][$col] = (string) $num; if ($this->solveSudoku($board)) { return true; } $board[$row][$col] = '.'; } } return false; } } function isSolved($board) { foreach ($board as $row) { if (in_array('.', $row)) { return false; } } return true; } function findEmptyCell($board) { for ($row = 0; $row < 9; $row++) { for ($col = 0; $col < 9; $col++) { if ($board[$row][$col] === '.') { return [$row, $col]; } } } return null; } function isValid($board, $row, $col, $num) { for ($i = 0; $i < 9; $i++) { if ($board[$row][$i] == $num) { return false; } } for ($i = 0; $i < 9; $i++) { if ($board[$i][$col] == $num) { return false; } } $startRow = floor($row / 3) * 3; $endCol = floor($col / 3) * 3; for ($i = 0; $i < 3; $i++) { for ($j = 0; $j < 3; $j++) { if ($board[$startRow + $i][$endCol + $j] == $num) { return false; } } } return true; }