编程之美1.15——构造数独

问题：

构造一个9*9的方格矩阵，玩家要在每个方格中，分别填上1至9的任意一个数字，
让整个棋盘每一列、每一行以及每一个3*3的小矩阵中的数字都不重复。

首先我们通过一个深度优先搜索来生成一个可行解，然后随机删除一定数量的数字，
以生成一个数独。

#include <iostream>#include <cstdlib>using namespace std;#define LEN 9#define CLEAR(a) memset((a), 0, sizeof(a))int level[] = {30, 37, 45};int grid[LEN+1][LEN+1];int value[LEN+1];void next(int &x, int &y){x++;if (x>9){x = 1;y++;}}// 选择下一个有效状态int pickNextValidValue(int x, int y, int cur){CLEAR(value);int i, j;for (i=1; i<y; i++)value[grid[i][x]] = 1;for (j=1; j<x; j++)value[grid[y][j]] = 1;int u = (x-1)/3*3 + 1;int v = (y-1)/3*3 + 1;for (i=v; i<v+3; i++)for (j=u; j<u+3; j++){value[grid[i][j]] = 1;}for (i=cur+1; i<=LEN && value[i]; i++);return i;}void pre(int &x, int &y){x--;if (x<1){x = 9;y--;}}int times = 0;int main(){int x, y, i, j;x = y = 1;// 深度搜索的迭代算法while (true){times++;// 满足成功结果if (y==LEN && x==LEN){for (i=1; i<=LEN; i++){for (j=1; j<=LEN; j++)cout << grid[i][j] << " ";cout << endl;}cout << times << endl;break;//pre(x, y);//times = 0;}// 满足失败结果if (y==0)break;// 改变状态grid[y][x] = pickNextValidValue(x, y, grid[y][x]);if (grid[y][x] > LEN){// 恢复状态grid[y][x] = 0;pre(x, y);}else// 进一步搜索next(x,y);}for (i=1; i<= level[2]; i++){int ind = rand()%(LEN*LEN);grid[ind/LEN+1][ind%LEN] = 0;}for (i=1; i<=LEN; i++){for (j=1; j<=LEN; j++)cout << grid[i][j] << " ";cout << endl;}}