編程之美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; 
    } 
}