leetcode 37 数独问题答案

#include<iostream> #include<vector> using namespace std; class solvesudoku //建立一个专门解决此类问题的类 { public: bool Bactrack(vector<vector<char>>& board,int row,int col);//这是一个回溯函数 bool isValid(vector<vector<char>>& board, int row, int col,char ch);//判断这个数字在行，列以及每个小方格上是否重复 }; bool solvesudoku::Bactrack(vector<vector<char>>& board, int row, int col) { if (col == 9)//列为9，换到下一行 return Bactrack(board, row + 1, 0); if (row == 9)//行为9，说明已经结束，回溯成功，数独有解 return true; //从第0行第0列开始进行回溯 for (int i = row; i < 9; i++) { for (int j = col; j < 9; j++) { if (board[i][j] != ' ') //如果上面有数字，则跳到下一列 return Bactrack(board, i, j + 1); for (char ch = '1'; ch <='9'; ch++) //在这个方格当中对数字都进行一次尝试 { if (!isValid(board, i, j, ch))//每次填入一个数字就对这个数字进行判断 continue; board[i][j] = ch;//如果判断成功，那么就填入这个数字 if (Bactrack(board, i, j + 1))//判断成功的同时对这个位置的下一列进行判断，看看在这个数的基础上，这一行是否都成立 return true; board[i][j] = ' ';//如果不成立，回溯换数字 } return false;//如果这一行都回溯不成功，那么这个数独是无解的，返回错误 } } return false; } bool solvesudoku::isValid(vector<vector<char>>& board, int row, int col, char ch) { for (int i = 0 ; i < 9; i++) { if (board[row][i] == ch)//这一行上是否有相等的 return false; if (board[i][col] == ch)//这一列上是否有相等的 return false; if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == ch)//在分块的小方格上是否有相同的 return false; } return true; } int main() { vector<vector<char>> vec;//设一个二维的数组 solvesudoku Solution; vector<char>v;// 一维数组 char tem;//方便提取输入的字符 cout << "Input:" << endl; for (int i = 0; i < 9; i++) { v.clear();//进行一行的清除 for (int j = 0; j < 9; j++) { while (1) { tem = getchar(); if (tem >= '1' && tem <= '9' || tem == ' ') break; } v.push_back(tem);//压入一维数组 } vec.push_back(v);//把一维数组压入二维数组 } cout << endl; if (Solution.Bactrack(vec, 0, 0)) //带入函数当中，如果函数返回值为真，就输出这个结果 { cout << "Output:" << endl; cout << endl; cout << "["; for (int i = 0; i < 9; i++) { cout << "["; for (int j = 0; j < 9; j++) { if(j!=8) cout << "\"" << vec[i][j] << "\","; else cout << "\"" << vec[i][j] << "\" "; } cout << "],"; if(i!=8) cout << endl; } cout << "]"; } else //如果返回值假，就输出error表示这个数独无解 { cout << "error"; } system("pause"); }