2014
12-24

# 数独求解-回溯

### 回溯法求解

#include
#define UNASSIGNED 0

// NxN 的大小
#define N 9

// 是否还有未放置的位置
bool FindUnassignedLocation(int grid[N][N], int &row, int &col);

// 在位置 grid[row][col]处，是否可以放置num
bool isSafe(int grid[N][N], int row, int col, int num);

/* 回溯法求解 */
bool SolveSudoku(int grid[N][N])
{
int row, col;

// 都已经放置完，则返回true
if (!FindUnassignedLocation(grid, row, col))
return true; // success!

for (int num = 1; num <= 9; num++)
{
if (isSafe(grid, row, col, num))
{
// 放置棋子
grid[row][col] = num;

// return, if success, yay!
if (SolveSudoku(grid))
return true;

// 失败, 设置为　未放置的 & 再一次尝试
grid[row][col] = UNASSIGNED;
}
}
return false;
}

bool FindUnassignedLocation(int grid[N][N], int &row, int &col)
{
for (row = 0; row < N; row++)
for (col = 0; col < N; col++)
if (grid[row][col] == UNASSIGNED)
return true;
return false;
}

bool UsedInRow(int grid[N][N], int row, int num)
{
for (int col = 0; col < N; col++)
if (grid[row][col] == num)
return true;
return false;
}

bool UsedInCol(int grid[N][N], int col, int num)
{
for (int row = 0; row < N; row++)
if (grid[row][col] == num)
return true;
return false;
}

bool UsedInBox(int grid[N][N], int boxStartRow, int boxStartCol, int num)
{
for (int row = 0; row < 3; row++)
for (int col = 0; col < 3; col++)
if (grid[row+boxStartRow][col+boxStartCol] == num)
return true;
return false;
}

bool isSafe(int grid[N][N], int row, int col, int num)
{
return !UsedInRow(grid, row, num) &&
!UsedInCol(grid, col, num) &&
!UsedInBox(grid, row - row%3 , col - col%3, num);
}

void printGrid(int grid[N][N])
{
for (int row = 0; row < N; row++)
{
for (int col = 0; col < N; col++)
printf("%2d", grid[row][col]);
printf("\n");
}
}

/* 测试 */
int main()
{
int grid[N][N] = {{3, 0, 6, 5, 0, 8, 4, 0, 0},
{5, 2, 0, 0, 0, 0, 0, 0, 0},
{0, 8, 7, 0, 0, 0, 0, 3, 1},
{0, 0, 3, 0, 1, 0, 0, 8, 0},
{9, 0, 0, 8, 6, 3, 0, 0, 5},
{0, 5, 0, 0, 9, 0, 6, 0, 0},
{1, 3, 0, 0, 0, 0, 2, 5, 0},
{0, 0, 0, 0, 0, 0, 0, 7, 4},
{0, 0, 5, 2, 0, 6, 3, 0, 0}};
if (SolveSudoku(grid) == true)
printGrid(grid);
else
printf("No solution exists");

return 0;
}


1. 博主您好，这是一个内容十分优秀的博客，而且界面也非常漂亮。但是为什么博客的响应速度这么慢，虽然博客的主机在国外，但是我开启VPN还是经常响应很久，再者打开某些页面经常会出现数据库连接出错的提示