编程之美1.15——构造数独

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

首先我们通过一个深度优先搜索来生成一个可行解，然后随机删除一定数量的数字，
以生成一个数独。
[cpp]
#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; 
    } 
}