《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(58)七宝妙树破数独 - 数独求解(回溯剪枝)
《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(58)七宝妙树破数独 - 数独求解(回溯剪枝)
哪吒在数据修仙界中继续他的修炼之旅。这一次,他来到了一片神秘的七宝妙树阵,阵中有一棵巨大的七宝妙树,树身闪烁着神秘的光芒。阵的入口处有一块巨大的石碑,上面刻着一行文字:“欲破此阵,需以七宝妙树之力,破数独,回溯剪枝显真身。”
哪吒定睛一看,石碑上还有一行小字:“数独棋盘的部分格子已填有数字,需通过回溯与剪枝算法填充剩余格子,使每行、每列、每个3x3宫均为1-9的不重复数字。”哪吒心中一动,他知道这是一道关于数独求解的难题,需要通过回溯与剪枝的方法来解决。
暴力解法:七宝妙树的初次尝试
哪吒心想:“要解决数独,我可以逐个格子尝试。”他催动七宝妙树之力,从棋盘的左上角开始,逐个格子填充数字,试图找到合法的解。
bool solveSudoku(vector<vector<int>>& board) {
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] == 0) {
for (int num = 1; num <= 9; ++num) {
if (isValid(board, i, j, num)) {
board[i][j] = num;
if (solveSudoku(board)) {
return true;
}
board[i