问题陈述
编写一个程序来通过填充空细胞来解决Sudoku难题。
sudoku解决方案必须满足以下所有规则：
每个数字1-9必须在每一行中完全发生一次。
每个数字1-9必须在每列中完全发生一次。
每个数字1-9必须在网格的9个3x3子箱中的每个中完全出现一次。
这 '。'字符表示空细胞。
从：https://leetcode.com/problems/sudoku-solver。
提取的问题声明示例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:
约束：
- board.length == 9
- board[i].length == 9
- board[i][j] is a digit or '.'
- It is guaranteed that the input board has only one solution.
Sudoku求解器的解决方案
方法1：使用蛮力的sudoku
天真的方法是生成所有可能的数字1至9个配置以填充空单元格。我们一一尝试每一个组合，直到获得有效的sudoku。对于每个空单元，我们都会用1到9的数字填充位置。填充了Sudoku后，我们检查了Sudoku是否有效。如果Sudoku无效，我们会重复出现其他情况。
这种方法的C ++片段如下：
class Solution {
public:
bool isValid(vector<vector<char>>& board, int i, int j, char value){
// check for a valid row
for(int row = 0; row < 9; row++) {
if(board[row][j] == value) {
return false;
}
}
// check for a valid column
for(int col = 0; col < 9; col++) {
if(board[i][col] == value) {
return false;
}
}
// check for a valid 3 * 3 matrix
for(int k = 0; k < 9; k++) {
if(board[3 * (i / 3) + k % 3][3 * (j / 3) + k / 3] == value) {
return false;
}
}
return true;
}
bool solveSudokuHelper(vector<vector<char>>& board, int row, int column) {
// if we reached the last cell of the board
// we should avoid further backtracking
// return true in this case
if (row == 8 && column == 9)
return true;
// if the column value becomes 9,
// we move to the next row
if (column == 9) {
row++;
column = 0;
}
// if the current cell of the board already contains
// any value from 1-9, we iterate for the next column
if (board[row][column] != '.')
return solveSudokuHelper(board, row, column + 1);
for (int num = 1; num <= 9; num++) {
// Check if it is safe to place
// the num (1-9) in the
// given cell
if (isValid(board, row, column, num)) {
// assign the value to the corresponding cell
board[row][column] = char(num);
// fill in the values for the next column
if (solveSudokuHelper(board, row, column + 1))
return true;
}
// if, in the previous step, the sudoku was invalid
// update the cell to an empty value. In this case, '.'
board[row][column] = '.';
}
return false;
}
void solveSudoku(vector<vector<char>>& board) {
solveSudokuHelper(board, 0, 0);
}
};
这种方法的时间复杂性为 o（9 ^（n * n））。我们正在用所有9种可能的组合填充板的每个空单元。
空间复杂性是 o（1）。
方法2：使用回溯
sudoku是通过将数字逐一分配给空细胞来解决的。在这种方法中，我们首先检查为单元格分配一个数字是否安全。如果位置有效，我们将移至下一个列。要验证单元格值，我们检查当前行，列还是3 * 3子格里德中的数字是否不存在。验证单元格后，我们递归检查该分配是否导致解决方案。如果分配没有导致解决方案，我们将尝试下一个数字。
该方法的代码流如下：
- Create a HashMap for the row, column and 3 * 3 subgrid.
- Create a function that validates the assignment of the current cell of the grid.
- If any number from 1-9 has a value greater than 1 in the HashMap, return false else, return true.
- Create a recursive function that accepts the sudoku board as a param.
- Check for an empty cell ('.')
- if the cell is empty, assign a number from 1 to 9
- check if assigning the number to the current cell, makes the sudoku safe or not
- if the sudoku is valid, recursively call the function for all safe cases from 0 to 9.
- if any recursive call returns true, we end the loop.
这种方法的C ++片段如下：
class Solution {
public:
bool numPresentInRow(vector<vector<char>>& board, int row, int num) {
for (int column = 0; column < 9; column++)
if (grid[row][column] == num)
return true;
return false;
}
bool numPresentInColum(vector<vector<char>>& board, int column, int num) {
for (int row = 0; row < 9; row++)
if (grid[row][column] == num)
return true;
return false;
}
bool numPresentInSubGrid(vector<vector<char>>& board, int subGridRowStartIndex, int subGridColumnStartIndex, int num) {
for (int row = 0; row < 3; row++)
for (int col = 0; col < 3; col++)
if (grid[row + subGridRowStartIndex][col + subGridColumnStartIndex] == num)
return true;
return false;
}
bool isSafe(vector<vector<char>>& board, int row, int column, char num) {
return !numPresentInRow(board, row, num)
&& !numPresentInColum(board, column, num)
&& !numPresentInSubGrid(board, row - row % 3, column - column % 3, num)
&& board[row][column] == '.';
}
// function to check if there are any empty cells in the sudoku
// if yes, the row and column parameters (passed by reference)
// will be set to the location that is empty and true is returned
bool hasEmptyCell(vector<vector<char>>& board, int& row, int& column) {
for (row = 0; row < 9; i++)
for (column = 0; column < 9; column++)
if (grid[row][column] == '.')
return true;
return false;
}
bool solveSudokuHelper(vector<vector<char>>& board) {
int row, column;
// return true if there are no empty cells
if (!hasEmptyCell(board, row, column))
return true;
// loop from 1 to 9
for (int num = 1; num <= 9; num++) {
// check if the assignment of num is safe
if (isSafe(board, row, column, num)) {
// make a tentative assignment
board[row][column] = char(num);
// return true if the current assignment is valid
if (solveSudokuHelper(board))
return true;
// if the assignment is unsafe,
// assign the empty value
board[row][column] = '.';
}
}
// this triggers backtracking
return false;
}
void solveSudoku(vector<vector<char>>& board) {
solveSudokuHelper(board);
}
};
这种方法的最差时间复杂性与蛮力方法相同，即 o（9 ^（n * n））。但是，由于我们正在验证作业，因此我们避免了一些不必要的迭代；因此，平均案例时间复杂性会更好。
方法3：使用bitmask的sudoku
这种方法是对 BackTracing 解决方案的轻微优化。我们没有在每行上循环循环，而是列和子网格以检查数字是否已经存在，而是使用位掩码来验证相同的。
让我们先检查算法。
算法
// function solveSudoku(board)
- set vector<int> rows(9, 0), columns(9, 0), subgrids(9, 0)
// this will mask the bits in the row, columns and subgrids array
// for non-empty cells
- call setBits(board, rows, columns, subgrids)
// function to backtrack and generate the possible solutions
- backtrack(board, index, rows, columns, subgrids)
// function setBits(board, rows, columns, subgrids)
- loop for row = 0; row < 9; row++
- loop for column = 0; column < 9; column++
- if board[row][column] != '.'
- set bitMask = 1 << (board[row][column] - '1')
- set subgrid = (row / 3) * 3 + (column / 3)
// mask the values in the row, column and subgrid array
- rows[row] |= bitMask
- columns[column] |= bitMask
- subgrids[subgrid] |= bitMask
- end if
- end inner for loop
- end outer for loop
在 c ++ ， golang 和 javascript 中查看我们的解决方案。
。C ++解决方案
class Solution {
public:
void setBits(vector<vector<char>>& board, vector<int>& rows, vector<int>& columns, vector<int>& subgrids) {
for(int row = 0; row < 9; row++) {
for(int column = 0; column < 9; column++) {
if(board[row][column] != '.') {
int bitMask = 1 << (board[row][column] - '1');
int subgrid = (row / 3) * 3 + (column / 3);
rows[row] |= bitMask;
columns[column] |= bitMask;
subgrids[subgrid] |= bitMask;
}
}
}
}
bool backtrack(vector<vector<char>>& board, int index, vector<int>& rows, vector<int>& columns, vector<int>& subgrids) {
if (index > 80)
return true;
int row = index / 9;
int column = index % 9;
if (board[row][column] != '.')
return backtrack(board, index + 1, rows, columns, subgrids);
int subgrid = (row / 3) * 3 + (column / 3);
for (int i = 0; i < 9; ++i) {
int mask = 1 << i;
if (rows[row] & mask || columns[column] & mask || subgrids[subgrid] & mask)
continue;
board[row][column] = i + '1';
rows[row] |= mask;
columns[column] |= mask;
subgrids[subgrid] |= mask;
if (backtrack(board, index + 1, rows, columns, subgrids))
return true;
board[row][column] = '.';
rows[row] ^= mask;
columns[column] ^= mask;
subgrids[subgrid] ^= mask;
}
return false;
}
void solveSudoku(vector<vector<char>>& board) {
vector<int> rows(9, 0), columns(9, 0), subgrids(9, 0);
setBits(board, rows, columns, subgrids);
backtrack(board, 0, rows, columns, subgrids);
}
};
Golang解决方案
func setBits(board [][]byte, rows []int, columns []int, subgrids []int) {
for row := 0; row < 9; row++ {
for column := 0; column < 9; column++ {
if board[row][column] != '.' {
bitMask := 1 << (board[row][column] - '1')
subgrid := (row / 3) * 3 + (column / 3)
rows[row] |= bitMask
columns[column] |= bitMask
subgrids[subgrid] |= bitMask
}
}
}
}
func backtrack(board [][]byte, index int, rows []int, columns []int, subgrids []int) bool {
if index > 80 {
return true
}
row := index / 9
column := index % 9
if board[row][column] != '.' {
return backtrack(board, index + 1, rows, columns, subgrids)
}
subgrid := (row / 3) * 3 + (column / 3)
for i := 0; i < 9; i++ {
mask := 1 << i
if (rows[row] & mask != 0) || (columns[column] & mask != 0) || (subgrids[subgrid] & mask != 0) {
continue
}
board[row][column] = byte(i + 1 + '0')
rows[row] |= mask
columns[column] |= mask
subgrids[subgrid] |= mask
if backtrack(board, index + 1, rows, columns, subgrids) {
return true
}
board[row][column] = '.'
rows[row] ^= mask
columns[column] ^= mask
subgrids[subgrid] ^= mask
}
return false
}
func solveSudoku(board [][]byte) {
rows, columns, subgrids := make([]int, 9), make([]int, 9), make([]int, 9)
setBits(board, rows, columns, subgrids)
backtrack(board, 0, rows, columns, subgrids)
}
JavaScript解决方案
var setBits = function(board, rows, columns, subgrids) {
for(let row = 0; row < 9; row++) {
for(let column = 0; column < 9; column++) {
if(board[row][column] != '.') {
let bitMask = 1 << (parseInt(board[row][column]) - 1);
let subgrid = Math.floor(row / 3) * 3 + Math.floor(column / 3);
rows[row] |= bitMask;
columns[column] |= bitMask;
subgrids[subgrid] |= bitMask;
}
}
}
}
var backtrack = function(board, index, rows, columns, subgrids) {
if (index > 80)
return true;
let row = Math.floor(index / 9);
let column = Math.floor(index % 9);
if (board[row][column] != '.')
return backtrack(board, index + 1, rows, columns, subgrids);
let subgrid = Math.floor(row / 3) * 3 + Math.floor(column / 3);
for (let i = 0; i < 9; ++i) {
let mask = 1 << i;
if (rows[row] & mask || columns[column] & mask || subgrids[subgrid] & mask)
continue;
board[row][column] = (i + 1).toString();
rows[row] |= mask;
columns[column] |= mask;
subgrids[subgrid] |= mask;
if(backtrack(board, index + 1, rows, columns, subgrids))
return true;
board[row][column] = '.';
rows[row] ^= mask;
columns[column] ^= mask;
subgrids[subgrid] ^= mask;
}
return false;
}
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solveSudoku = function(board) {
let rows = Array(9).fill(0), columns = Array(9).fill(0), subgrids = Array(9).fill(0);
setBits(board, rows, columns, subgrids);
backtrack(board, 0, rows, columns, subgrids);
};