編寫一個程序通過填充空單元格來解決數獨謎題。
數獨的解決方案必須滿足以下所有規則：每個數字 1-9 必須在每一行中恰好出現一次。
每個數字 1-9 必須在每一列中恰好出現一次。
每個數字 1-9 必須在網格的每一個 9 個 3x3 子框中恰好出現一次。
字符 '.' 表示空單元格。
Python
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
def is_valid(board, row, col, num):
# Check row
for c in range(9):
if board[row][c] == num:
return False
# Check column
for r in range(9):
if board[r][col] == num:
return False
# Check 3x3 sub-box
startRow, startCol = 3 * (row // 3), 3 * (col // 3)
for r in range(startRow, startRow + 3):
for c in range(startCol, startCol + 3):
if board[r][c] == num:
return False
return True
def solve(board):
for row in range(9):
for col in range(9):
if board[row][col] == '.':
for num in map(str, range(1, 10)):
if is_valid(board, row, col, num):
board[row][col] = num
if solve(board):
return True
board[row][col] = '.'
return False
return True
solve(board)
16.54MB, 103ms
C++
#include <vector>
using namespace std;
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
solve(board);
}
private:
bool isValid(vector<vector<char>>& board, int row, int col, char num) {
// Check row
for (int c = 0; c < 9; c++) {
if (board[row][c] == num) {
return false;
}
}
// Check column
for (int r = 0; r < 9; r++) {
if (board[r][col] == num) {
return false;
}
}
// Check 3x3 sub-box
int startRow = 3 * (row / 3), startCol = 3 * (col / 3);
for (int r = startRow; r < startRow + 3; r++) {
for (int c = startCol; c < startCol + 3; c++) {
if (board[r][c] == num) {
return false;
}
}
}
return true;
}
bool solve(vector<vector<char>>& board) {
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
if (board[row][col] == '.') {
for (char num = '1'; num <= '9'; num++) {
if (isValid(board, row, col, num)) {
board[row][col] = num;
if (solve(board)) {
return true;
}
board[row][col] = '.';
}
}
return false;
}
}
}
return true;
}
};
7.76MB, 7ms
Javascript
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solveSudoku = function(board) {
solve(board);
};
function solve(board) {
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
if (board[i][j] === '.') {
for (let num = 1; num <= 9; num++) {
if (isValid(board, i, j, num.toString())) {
board[i][j] = num.toString();
if (solve(board)) {
return true;
} else {
board[i][j] = '.';
}
}
}
return false;
}
}
}
return true;
}
function isValid(board, row, col, num) {
// Check row
for (let j = 0; j < 9; j++) {
if (board[row][j] === num) return false;
}
// Check column
for (let i = 0; i < 9; i++) {
if (board[i][col] === num) return false;
}
// Check 3x3 sub-box
let boxRow = Math.floor(row / 3) * 3;
let boxCol = Math.floor(col / 3) * 3;
for (let i = boxRow; i < boxRow + 3; i++) {
for (let j = boxCol; j < boxCol + 3; j++) {
if (board[i][j] === num) return false;
}
}
return true;
}
50.37MB, 79ms
