Github項目地址

https://github.com/JackManTvO/sudoku

PSP表格

解題思路

生成數獨終局

??數獨的要求是在9×9的格子內，每一行和每一列和每一宮內都包含不重復的九個元素，但數獨終局的個數共有6,670,903,752,021,072,936,960（6.67×1021）種組合，盡管終局要求左上角第一個數字為固定值，其終局的種數也是巨大的。而程序設計對終局數量的需求僅在1,000,000個以內，因此，沒有必要窮舉找到前1,000,000種終局，而沒有合適的生成策略隨機生成則可能造成終局的重復。因此需制定合適的生成終局策略，而我的生成終局策略為對固定的終局模板進行數字交換以及行交換。這種策略共可以生成8!（除首數字外8個數字兩兩交換）×2（23行交換）×6（4～6行兩兩交換）×6（7～9行兩兩交換）=2,903,040種終局，大于要求的終局數。根據要求生成的終局個數對變換方式進行深度優(yōu)先搜索，第一層為數字交換，第二層為23行交換，第三層為4～6行交換，第四層為7～9行交換，以快速地遍歷第四層的葉子，以生成多個不重復的終局。
??具體步驟如下：

1. 生成一固定的有效終局作為模板。
2. 對模板進行數字交換。
3. 對進行數字交換后的終局進行行交換（2～3行交換、4～6行交換、7～9行交換）保證宮內不重復。
4. 若生成終局數滿足程序要求個數即返回，若不滿足，重復進行步驟2、步驟3。

求解數獨謎題

??對于給定的數獨謎題，按要求補充數獨的空缺，以完成數獨。因為填入的數需要滿足數獨的要求，所以每個固定位置的數值是有限制的，在剩余的可行值中選擇一個填入空白，接著填入下一個空白。若發(fā)現(xiàn)無可行解，則父節(jié)點選擇錯誤，采用回溯法，返回上一節(jié)點，填入另一可行解。直到生成樹的層數等于空缺數，則生成一可行的數獨終局，求解數獨謎題成功。
??具體步驟如下：

1. 掃描題目，將空白值坐標取出存入數組A。
2. 在數組A中選擇下一個坐標。
3. 查詢其所在行、列、宮的數值，填入可行解數組，在可行解數組中選取下一可行解填入。
4. 若填入成功，則返回步驟2，若無可行解，則在數組A中返回上一坐標，返回步驟3填入另一可行解。若A中無剩余，則返回，求解數獨成功。

設計實現(xiàn)過程

類

??我設計了三個類，分別為向量類、點類和數獨類（改進前）

Seed類（改進前）

Point類（改進前）

Sudoku類（改進前）

類圖（改進后）

Class Diagram.png

關鍵函數

元素交換函數

permutate.png

行交換函數

generate.png

解數獨函數

dfs.png

單元測試設計

??使用了代碼走讀，并對三個關鍵函數使用路徑測試法進行了單元測試：

元素交換函數

行交換函數

解數獨函數

改進

終局生成

??設置參數需要的棋盤數量為1,000,000，對該改進前代碼進行了10次性能分析，平均時間為138.251秒，最接近平均時間的一次為138.708秒。

性能1.png

??由性能分析可見，消耗最大的函數是Sudoku類的寫文件函數中的fputc函數，為了方便添加空格，我采用的是fputc函數逐個添加字符，且運行write函數后就關閉文件。這樣在1,000,000個終局生成中，會發(fā)生反復調用fputc函數和打開、關閉文件函數。因此我改動為在開始生成終局時打開文件，在寫入完成后關閉文件，將字符連接為字符串后，將一整個數獨終局以字符串寫入文件。且Point類的封裝性不強，我加強了Point類的封裝性（見類圖）。改進前在行交換時，回溯時需要置為交換前，浪費大量時間，我在行變換前，將數獨終局作為新變量保存以作為模板，方便進行二次行交換。
??改進后10次性能分析的平均時間為5.137秒，最接近平均時間的一次為5.368秒。

性能2.png

數獨求解

??為了方便進行數獨求解，我添加了Pset類已保存空白點（見類圖），且封裝性良好。為了優(yōu)化性能，我采用了隨機的策略選取下一空白點的解，并記錄空白點處理的順序以方便回溯。這個算法的時間復雜度明顯優(yōu)于全圖遍歷。且為了減少數據的冗余，在讀入數獨時完成空白點集的添加。

代碼說明

元素交換函數

void Sudoku::permutate (int level) {
    if (level == side - 2) {        //全排列結束
        mod ();     //生成模板
        generate ();        //行交換
        return;
    }
    for (int i = level; i < side; i++) {
        if (i != level)
            seed.swapi (level, i);      //交換元素
        permutate (level + 1);      //遞歸
        if (nsudoku == 0)
            return;
        if (i != level)
            seed.swapi (level, i);
    }
    return;
}

行交換函數

void Sudoku::generate () {      //生成終局
        /*行變換*/
    Sudoku ans;
    for (int i = 0; i < 2 && nsudoku>0; i++)        //第一階段
        for (int j = 0; j < 6 && nsudoku>0; j++)        //第二階段
            for (int k = 0; k < 6 && nsudoku>0; k++) {      //第三階段
                ans.cpy(this);
                switch (i) {
                case 0:
                    break;
                case 1:
                    ans.swapRow (1, 2); break;
                }
                switch (j) {
                case 0:
                    break;
                case 1:
                    ans.swapRow (4, 5); break;
                case 2:
                    ans.swapRow (3, 4); break;
                case 3:
                    ans.swapRow (3, 5); ans.swapRow (3, 4); break;
                case 4:
                    ans.swapRow (3, 4); ans.swapRow (3, 5); break;
                case 5:
                    ans.swapRow (3, 5); break;
                }
                switch (k) {
                case 0:
                    break;
                case 1:
                    ans.swapRow (7, 8); break;
                case 2:
                    ans.swapRow (6, 7); break;
                case 3:
                    ans.swapRow (6, 8); ans.swapRow (6, 7); break;
                case 4:
                    ans.swapRow (6, 7); ans.swapRow (6, 8); break;
                case 5:
                    ans.swapRow (6, 8); break;
                }
                ans.write (fpw);
                nsudoku--;      //生成數+1
                if (nsudoku == 0) {
                    if (fpw != NULL)
                        fclose (fpw);
                    return;
                }
                if (fpw != NULL)
                    fprintf (fpw, "\n\n");
            }
    return;
}

解數獨函數

int Sudoku::dfs () {
    int iz = pset.geti();
    Point p (this->pset.getVal(iz));
    /*初始化占有標識數組*/
    for (int i = 0; i < 9; i++) {
        if (val[p.getx ()][i] != 0 && p.getpos (val[p.getx ()][i]) == 0)
            p.setpos (val[p.getx ()][i], 1);
        if (val[i][p.gety ()] != 0 && p.getpos (val[p.getx ()][i]) == 0)
            p.setpos (val[i][p.gety ()], 1);
    }
    for (int i = (p.getx () / 3) * 3; i < (p.getx () / 3) * 3 + 3; i++)
        for (int j = (p.gety () / 3) * 3; j < (p.gety () / 3) * 3 + 3; j++)
            if (val[i][j] != 0 && p.getpos (val[p.getx ()][i]) == 0)
                p.setpos (val[i][j], 1);
    /*尋找可行解*/
    int found = 0;
    for (int i = 1; i < 10; i++)
        if (p.getpos(i) == 0) {     //找到一可行解
            found = 1;
            val[p.getx ()][p.gety ()] = i;
            p.setpos (i, 1);
            pset.del (iz);
            if (pset.isEmpty()) {
                write (fpw);
                return 1;
            }
            if (dfs ())     //找下一個空位的可行解
                return 1;
            p.setpos (i, 0);
        }
    return 0;
}

附加題