rn false;
? ? }
?
? ? // check left upper diag
? ? for (i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
? ? {
? ? ? ? if (grid[i][j] == 1) return false;
? ? }
?
? ? // check left lower diag
? ? for (i = row + 1, j = col - 1; i < BOARD_SIZE && j >= 0; i++, j--)
? ? {
? ? ? ? if (grid[i][j] == 1) return false;
? ? }
?
? ? return true;
}
?
bool NQueue(Grid& grid, int curcol)
{
? ? // Base case
? ? if (curcol == BOARD_SIZE)
? ? {
? ? ? ? return true;
? ? }
?
? ? for (int i = 0; i < BOARD_SIZE;++i)
? ? {
? ? ? ? if (IsSafe(grid, i, curcol))
? ? ? ? {
? ? ? ? ? ? // try a choice
? ? ? ? ? ? PlaceQueue(grid, i, curcol);
? ? ? ? ? ? // if this choice lead a solution, return
? ? ? ? ? ? bool success = NQueue(grid, curcol + 1);
? ? ? ? ? ? if (success) return true;
? ? ? ? ? ? // else unmake this choice, try an alternative choice
? ? ? ? ? ? else RemoveQueue(grid, i, curcol);
? ? ? ? }
? ? }
?
? ? return false;
}
?
void PrintSolution(const Grid& grid)
{
? ? for (int i = 0; i < BOARD_SIZE; ++i)
? ? {
? ? ? ? for (int j = 0; j < BOARD_SIZE; ++j)
? ? ? ? {
? ? ? ? ? ? cout << grid[i][j] << " ";
? ? ? ? }
? ? ? ? cout << endl;
? ? }
? ? cout << endl;
}
复制代码
?【经典回溯问题2】数独问题
数独问题可以描述为在空格内填写1-9的数字，要求每一行每一列每一个3*3的子数独内的数字1-9出现一次且仅出现一次。一般数独问题会实现填写一些数字以保证解的唯一性，从而使得不需要暴力
破解，只是使用逻辑推理就可以完成。这一次让我们尝试用计算机暴力回溯来得到一个解。解决数独问题的伪代码及
C++代码如下：
?
复制代码
#include
#include
#include
#include
#include
using namespace std;
?
// Base Case: if cannot find any empty cell, return true
// Find an unsigned cell (x, y)
// for digit from 1 to 9
// ? ? ? ?if there is not conflict for digit at (x, y)
// ? ? assign (x, y) as digit and Recursively check if this lead to a solution
// ? ? if success, return true
// ? ? else remove the digit at (x, y) and try another digit
// if all digits have been tried and still have not worked out, return false to trigger backtracking
?
const int GRID_SIZE = 9;
const int SUB_GRID_SIZE = 3;
typedef vector > Grid;
?
bool IsSafe(const Grid& grid, int x, int y, int num);
bool FindEmptyCell(const Grid& grid, int& x, int& y);
bool Sudoku(Grid& grid);
void PrintSolution(const Grid& grid);
?
int main()
{
? ? freopen("sudoku.in", "r", stdin); ? ?
? ? vector > grid(GRID_SIZE, vector(GRID_SIZE, 0));
? ? for (int i = 0; i < GRID_SIZE; ++i)
? ? {
? ? ? ? for (int j = 0; j < GRID_SIZE; ++j)
? ? ? ? {
? ? ? ? ? ? cin >> grid[i][j];
? ? ? ? }
? ? }
?
? ? if (Sudoku(grid))
? ? {
? ? ? ? cout << "Find Solution " << endl;
? ? ? ? PrintSolution(grid);
? ? ? ? cout << endl;
? ? }
? ? else
? ? {
? ? ? ? cout << "Solution does not exist" << endl;
? ? }
? ? return 0;
}
?
bool Sudoku(Grid& grid)
{
? ? // base case
? ? int x = 0; int y = 0;
? ? if (!FindEmptyCell(grid, x, y)) return true;
? ??
? ? // for all the number?
? ? for (int num = 1; num <= 9; ++num)
? ? {
? ? ? ? if (IsSafe(grid, x, y, num))
? ? ? ? {
? ? ? ? ? ? // try one choice
? ? ? ? ? ? grid[x][y] = num;
? ? ? ? ? ? // if this choice lead to a solution
? ? ? ? ? ? if (Sudoku(grid)) return true;
? ? ? ? ? ? // otherwise, try an alternative choice
? ? ? ? ? ? else grid[x][y] = 0;
? ? ? ? }
? ? }
?
? ? return false;
}
?
bool IsSafe(const Grid& grid, int x, int y, int num)
{
? ? // check the current row
? ? for (int j = 0; j < grid[x].size(); ++j)
? ? {
? ? ? ? if (j != y && grid[x][j] == num) return false;
? ? }
?
? ? // check current col
? ? for (int i = 0; i < grid.size(); ++i)
? ? {
? ? ? ? if (i != x && grid[i][y] == num) return false;
? ? }
?
? ? // check the subgrid
? ? int ii = x / 3;
? ? int jj = y / 3;
? ? for (int i = ii * SUB_GRID_SIZE; i < (ii+1) * SUB_GRID_SIZE; ++i)
? ? {
? ? ? ? for (int j = jj * SUB_GRID_SIZE; ?j < (jj+1) * SUB_GRID_SIZE; ++j)
? ? ? ? {
? ? ? ? ? ? if (i != x || j != y)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if (grid[i][j] == num) return fa