原题地址：解数独
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。
空白格用 '.' 表示。
一个数独。
答案被标成红色。
Note:
- 给定的数独序列只包含数字 1-9 和字符 '.' 。
- 你可以假设给定的数独只有唯一解。
- 给定数独永远是 9x9 形式的。
回溯算法
利用回溯算法，将每个格子填上与现有格子不冲突的数字，然后继续处理下一个格子。如果发现这条路走不通，就回溯再尝试下一个数字。
具体的实现代码如下：
/**
* @param {string[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
const solveSudoku1 = function(board) {
// 对每一行、每一列及每一个小九宫格分别用一个Set来记录出现过的数字
let columnSets = new Array(board.length);
let rowSets = new Array(board.length);
let boxSets = new Array(board.length);
for (let i = 0; i < board.length; i ++) {
columnSets[i] = new Set();
rowSets[i] = new Set();
boxSets[i] = new Set();
}
let solved = false; // 记录是否已找到解
let array = []; // 记录未填过的格子，方便处理
// 获取小九宫的索引
const getBoxIndex = ([i, j]) => {
return Math.floor(i/3)*3+Math.floor(j/3);
};
// 将填过的数字保存到set中
const saveNumberToSet = ([i, j]) => {
rowSets[i].add(board[i][j]);
columnSets[j].add(board[i][j]);
boxSets[getBoxIndex([i, j])].add(board[i][j]);
};
// 已填过的数字不可行，从set中删除
const deleteNumberFromSet = ([i, j]) => {
rowSets[i].delete(board[i][j]);
columnSets[j].delete(board[i][j]);
boxSets[getBoxIndex([i, j])].delete(board[i][j]);
};
// 判断数字填在某个位置是否与已填过的冲突
const isOk = (number, place) => {
return !(columnSets[place[1]].has(number) ||
rowSets[place[0]].has(number) ||
boxSets[getBoxIndex(place)].has(number));
};
/**
* 将数字填到空白格子中
* @param index 空白格子在未填格子列表中的索引
* @param number 要填的数字
*/
const placeNumber = (index, number) => {
if (index === array.length) { // 所有的格子已填满，问题已解决
solved = true;
return;
}
if (solved) { // 已解决
return;
}
if (number === 10) { // 已不可行，返回
return;
}
if (isOk(`${number}`, array[index])) {
// 如果没有冲突就将该数字填到格子中
board[array[index][0]][array[index][1]] = `${number}`;
saveNumberToSet(array[index]);
// 然后处理下一个格子
placeNumber(index + 1, 1);
if (solved) { // 问题已解决就返回
return;
}
// 问题未解决，这条路走不通，将已填过数字要删掉
deleteNumberFromSet(array[index]);
board[array[index][0]][array[index][1]] = '.';
}
placeNumber(index, number + 1);
};
for (let i = 0; i < board.length; i ++) {
for (let j = 0; j < board.length; j ++) {
if (board[i][j] === '.') {
// 还没有填的格子保存到数组中
array.push([i, j])
} else {
// 已经填过的记录到对应的set中
saveNumberToSet([i, j])
}
}
}
// 从第一个未填过的格子开始处理
placeNumber(0, 1);
};
测试：
let start = new Date();
const test = solveSudoku1;
let 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"]
];
test(board);
/**
[
["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"]
]
*/
console.log(board);
board = [
[".","1","4",".",".","7",".","5","."],
[".","8",".","6","1",".",".",".","2"],
[".",".",".","8",".",".",".","9","."],
["3",".",".",".","2",".",".",".","7"],
[".",".","6",".","8","5","1",".","9"],
[".",".","8",".","7",".","5",".","6"],
[".","2",".",".",".","1",".","7","."],
["8",".","7",".","6",".",".",".","."],
[".","5",".",".",".",".",".","6","3"]
];
test(board);
/**
[
["9","1","4","2","3","7","6","5","8"],
["5","8","3","6","1","9","7","4","2"],
["7","6","2","8","5","4","3","9","1"],
["3","9","5","1","2","6","4","8","7"],
["2","7","6","4","8","5","1","3","9"],
["1","4","8","9","7","3","5","2","6"],
["6","2","9","3","4","1","8","7","5"],
["8","3","7","5","6","2","9","1","4"],
["4","5","1","7","9","8","2","6","3"]
]
*/
console.log(board);
console.log(new Date().getTime() - start.getTime()); // 34
时间复杂度： 由于格子大小确定，时间也是确定的，$O(1)$
空间复杂度： 空间复杂度为$O(1)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 7,2019