解数独,我们都可能玩过或者了解知道,就是数独游戏。数独是一种运用纸、笔进行演算的逻辑游戏。玩法:在空格里填入数字1到9,使得每一行、每一列和每一个用粗线围起来的3×3的九个单元格里,填数都包含1到9各一个。
而利用电脑怎样实现呢?怎样将我们的数字解题思路用到代码的实现上呢?其实最简单的方法就是搜所,对每一个要填的空尝试填入1到9,再检查能不能实现。
我遇到的这道题与数独游戏的规则有区别,如下图:
其实,都是一样的思路,先尝试,就如“暴力枚举法”,对要填的每一个空进行尝试,再看看有没有什么规律可循,就如,这个空填完了,就进行下一个空。与回溯法也类似,把要填的空分为多个问题,再看看每一步要满足什么条件,有什么约束条件,再注意一下什么时候或者到哪一步问题就解决了,还有就是剪枝的条件。
对于解数独问题的大致思路就是:遍历整个棋盘,对于每个空格,尝试填充,从[1 - 9][1−9]每个数字进行尝试,如果合法,此格子位置就填入该数字,然后递归去填充下一个空格。递归之后要回溯,即把该格子位置还原为空格。
部分代码:
for (int row = 0; row < n; row++) { // 遍历整个棋盘,对于每一个空格,都尝试填充,看看满不满足条件
for (int col = 0; col < n; col++) {// 已填好数字直接跳过
if (board[row][col] != '.') {
continue;
}
// [1 - 9]数字逐一进行尝试
for (char d = '1'; d <= '9'; d++) {
if (valid(row, col, d)) {
// 此位置可填充这个数字
board[row][col] = d;
// 递归去填充下一个空格
if (doSolveSudoku()) {
return true;
}
// 回溯,还原为空格
board[row][col] = '.';
}
}
// 这个空格,9个数字都不行,说明没有一个符合条件的解
return false;
}
以上就是对自己遇到的一道题的总结,总结一下方法!