徐松亮算法教学-基于C语言的数独(九宫格)多种终盘生成方法（包含矩阵镜像旋转转置等相关算法）
生活随笔
收集整理的這篇文章主要介紹了
徐松亮算法教学-基于C语言的数独(九宫格)多种终盘生成方法（包含矩阵镜像旋转转置等相关算法）
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
版權聲明：本文為博主徐松亮的原創(chuàng)作品，未經(jīng)允許不得轉載，多謝支持！QQ：5387603
推薦點擊此鏈接：歡迎進入徐松亮博客一站式導航搜索(隨時更新)
?
目錄
一,前言
二,開發(fā)環(huán)境
電腦系統(tǒng)
編譯器
編程語言
編輯與工程環(huán)境
三,方法
方法概述
生成（或隨機選定）種子矩陣終盤
兩數(shù)交換法
非跨界行交換
非跨界列交換
塊行交換
塊列交換
矩陣旋轉
矩陣行鏡像
矩陣列鏡像
矩陣對角線鏡像
四,源碼
五,運行結果演示
運行結果---兩數(shù)交換法
運行結果---非跨界行交換
運行結果---非跨界列交換
運行結果---塊行交換
運行結果---塊列交換
運行結果---矩陣旋轉
運行結果---矩陣行鏡像
運行結果---矩陣列鏡像
運行結果---矩陣對角線鏡像
六,引用資料致謝
一,前言
- 昨天,發(fā)布了一篇數(shù)獨解題的文章，但是只有解題沒有出題，總是感覺差點意思。
- 相關鏈接如下：徐松亮算法教學-基于C語言的數(shù)獨(九宮格)求解（含多解和解數(shù)統(tǒng)計）
- 網(wǎng)上搜了一些相關資料，大多都是單一方式，流程基本上是填入部分隨機數(shù)---產生一個解盤---扣掉一些數(shù)。這個方案如果只是用于出題也是可行的，但是這么簡單的話，我真是懶得總結。
- 本文的矩陣轉換算法都為博主親自編寫調試，都是自身轉換，而不需要建立同樣大小的緩存，尤其是矩陣旋轉相關代碼，還真花費了我一些時間，很是推薦，比目前網(wǎng)上的要好很多，后續(xù)我會把矩陣轉換相關的代碼標準化后另建立學習文檔。
- 偶然在網(wǎng)上發(fā)現(xiàn)一篇文章，它講了多種數(shù)獨終盤生成辦法，主要是用的矩陣變換，還是那句話：雖然我對數(shù)獨本身這個游戲沒什么興趣，但是對它涉及到的計算機數(shù)學問題，還是頗有興趣。
- 做到這，我想到一個問題，接數(shù)獨是不是也可以用這篇文章講的矩陣變換方法，經(jīng)過各種行列兌換，生成一個解，原理有點像擰魔方似的，方法理論上應該是可行的，但不過這個方法不能統(tǒng)計出解的數(shù)量。
二,開發(fā)環(huán)境
-
電腦系統(tǒng)
- windows10
-
編譯器
- cygwin下的gcc
-
編程語言
- C語言
-
編輯與工程環(huán)境
- VSCode
- 不了解VSVode安裝配置的請看本人的原創(chuàng)文檔：
- 徐松亮軟件應用教學-基于Visual Studio Code的C語言開發(fā)環(huán)境搭建
?
- 徐松亮軟件應用教學-基于Visual Studio Code的C語言開發(fā)環(huán)境搭建
三,方法
-
方法概述
- 基于一個成型的終盤，經(jīng)過下列任意變換后，還是一個符合規(guī)則的終盤。
-
生成（或隨機選定）種子矩陣終盤
- 如果能真正的隨機生成一個終盤，那就不用下面的變換了，所以我們在此用選定的現(xiàn)有矩陣做種子。
- 真正做可以多做幾個，然后用隨機數(shù)來選。
-
兩數(shù)交換法
- 就是隨機選取兩個數(shù)，可以是1和9，也可以是3和5，全局交換后，仍是有效終盤。
- 下圖舉例，我們已2和8來做交換，如圖所示：
-
非跨界行交換
- 以宮為界，即1-3行為一組，4-6行為一組，7-9行為一組，組內可執(zhí)行行交換，組間不能。符合此規(guī)則執(zhí)行行交換后，終盤仍為符合規(guī)則的終盤。
- 下圖舉例，同色為界，我們執(zhí)行1與3行的數(shù)據(jù)交換。
-
非跨界列交換
- 以宮為界，即1-3列為一組，4-6列為一組，7-9列為一組，組內可執(zhí)行行交換，組間不能。符合此規(guī)則執(zhí)列列交換后，終盤仍為符合規(guī)則的終盤。
- 下圖舉例，我們執(zhí)列1與3列的數(shù)據(jù)交換。
-
塊行交換
- 以宮為界，即1-3行為一組，4-6行為一組，7-9行為一組，組與組交換在此我起名稱作塊行交換。符合此規(guī)則交換后，終盤仍為符合規(guī)則的終盤。
- 下圖舉例，我們組1與組2的數(shù)據(jù)交換。
-
塊列交換
- 以宮為界，即1-3列為一組，4-6列為一組，7-9列為一組，組與組交換在此我起名稱作塊列交換。符合此規(guī)則交換后，終盤仍為符合規(guī)則的終盤。
- 下圖舉例，我們組1與組2的數(shù)據(jù)交換。
-
矩陣旋轉
- 矩陣旋轉，就是相當于你轉著圈的去看數(shù)獨題，你從四個方向看，這個題都是成立的。
- 下圖舉例，如圖。
-
矩陣行鏡像
- 矩陣行鏡像，就好比你看完報紙正面，反過來看報紙背面一樣。符合此規(guī)則交換后，終盤仍為符合規(guī)則的終盤。
- 下圖舉例，如圖
-
矩陣列鏡像
- 矩陣列鏡像，原理同行鏡像其實是一樣的。符合此規(guī)則交換后，終盤仍為符合規(guī)則的終盤。
- 下圖舉例，如圖
-
矩陣對角線鏡像
- 矩陣對角線鏡像，原理相當于數(shù)學當中的矩陣轉置。
- 下圖舉例，如圖
四,源碼
/********************************************************************************* @file xsl_game_sudo.c* @author 徐松亮 許紅寧(5387603@qq.com)* @version V1.0.0* @date 2018/11/01******************************************************************************* @attention* 待解決* 1,數(shù)獨出題* GNU General Public License (GPL)** <h2><center>© COPYRIGHT 2017 XSLXHN</center></h2>*******************************************************************************//* Includes ------------------------------------------------------------------*/ #include <stdio.h> #include <stdint.h> // 用于計算耗時統(tǒng)計 #include <time.h> /* Private define ------------------------------------------------------------*/ #define XSLGAMESUDO_SUDOKU_LEVEL 9 #define OK 0 #define ERR 1 /* Private typedef -----------------------------------------------------------*/ typedef struct {// 輸入---計算前用戶設定uint8_t cells[XSLGAMESUDO_SUDOKU_LEVEL][XSLGAMESUDO_SUDOKU_LEVEL];//-----最大輸出答案數(shù)量(1,為了防止pOutBuf數(shù)據(jù)溢出;2,為了計算適可而止;)uint32_t MaxOutAnswersCount;// 輸入輸出//-----輸出緩存(NULL---無解輸出)uint8_t *pOutBuf;//-----解最大數(shù)量(NULL---不求此值則非全局搜索)uint32_t *pAnswersCount;// 輸出---計算后的統(tǒng)計結果uint32_t OutAnswersCount; } XSLGAMESUDO_S_SUDO; /* Private macro -------------------------------------------------------------*/ /* Private variables ---------------------------------------------------------*/ static const uint8_t XslGameSudo_SudoGenerateBuf[XSLGAMESUDO_SUDOKU_LEVEL][XSLGAMESUDO_SUDOKU_LEVEL] = {8, 1, 2, 7, 5, 3, 6, 4, 9,9, 4, 3, 6, 8, 2, 1, 7, 5,6, 7, 5, 4, 9, 1, 2, 8, 3,1, 5, 4, 2, 3, 7, 8, 9, 6,3, 6, 9, 8, 4, 5, 7, 2, 1,2, 8, 7, 1, 6, 9, 5, 3, 4,5, 2, 1, 9, 7, 4, 3, 6, 8,4, 3, 8, 5, 2, 6, 9, 1, 7,7, 9, 6, 3, 1, 8, 4, 5, 2}; // XSLGAMESUDO_S_SUDO XslGameSudo_s_Sudo; /* Extern variables ----------------------------------------------------------*/ /* Private function prototypes -----------------------------------------------*/ /* Private functions ---------------------------------------------------------*/ /*** @brief 格式化打印* @note 打印指定行列的數(shù)組* @param *pXslGameSudoS --- 數(shù)據(jù)指針* mode --- 0-打印問題 1-打印答案 2-只打印數(shù)獨不打印字符串* @return null*/ static void XslGameSudo_FormatPrint(XSLGAMESUDO_S_SUDO *pXslGameSudoS, uint8_t mode) {uint8_t i, j, k;uint8_t *pbuf;// 打印問題if ((mode == 0) || (mode == 2)){if (mode == 0){printf("Sudo Questions:\n");}pbuf = (uint8_t *)pXslGameSudoS->cells;for (i = 0; i < XSLGAMESUDO_SUDOKU_LEVEL; i++){for (j = 0; j < XSLGAMESUDO_SUDOKU_LEVEL; j++){printf("%2d", pbuf[i * XSLGAMESUDO_SUDOKU_LEVEL + j]);if (j == (XSLGAMESUDO_SUDOKU_LEVEL - 1))printf("\n");}}}// 打印答案else if (mode == 1){if (pXslGameSudoS->pAnswersCount == 0){printf("Sudo Processor : No Solution!\n");return;}//pbuf = pXslGameSudoS->pOutBuf;for (k = 0; k < pXslGameSudoS->OutAnswersCount; k++){printf("Sudo Answers(%d):\n", k + 1);for (i = 0; i < XSLGAMESUDO_SUDOKU_LEVEL; i++){for (j = 0; j < XSLGAMESUDO_SUDOKU_LEVEL; j++){printf("%2d", pbuf[(k * XSLGAMESUDO_SUDOKU_LEVEL * XSLGAMESUDO_SUDOKU_LEVEL) + (i * XSLGAMESUDO_SUDOKU_LEVEL + j)]);if (j == (XSLGAMESUDO_SUDOKU_LEVEL - 1))printf("\n");}}}if (pXslGameSudoS->pAnswersCount != NULL){printf("Sudo Answers Count: %d\n", *(pXslGameSudoS->pAnswersCount));}} }uint8_t XslGameSudo_Generate(XSLGAMESUDO_S_SUDO *pXslGameSudoS) {uint8_t num = 1;// 生成種子數(shù)獨memcpy((uint8_t *)(pXslGameSudoS->cells), (uint8_t *)&XslGameSudo_SudoGenerateBuf[0][0], XSLGAMESUDO_SUDOKU_LEVEL * XSLGAMESUDO_SUDOKU_LEVEL);printf("%d,----------Seeds sudoku:\n", num++);XslGameSudo_FormatPrint(pXslGameSudoS, 2);//----------memcpy((uint8_t *)(pXslGameSudoS->cells), (uint8_t *)&XslGameSudo_SudoGenerateBuf[0][0], XSLGAMESUDO_SUDOKU_LEVEL * XSLGAMESUDO_SUDOKU_LEVEL);// 兩數(shù)交換法{uint8_t commutation_data_1, commutation_data_2;uint8_t i;uint8_t *pbuf = pXslGameSudoS->cells;// 設定交換數(shù)commutation_data_1 = 2;commutation_data_2 = 8;// 執(zhí)行數(shù)據(jù)交換for (i = 0; i < XSLGAMESUDO_SUDOKU_LEVEL * XSLGAMESUDO_SUDOKU_LEVEL; i++){if (pbuf[i] == commutation_data_1){pbuf[i] = commutation_data_2;}else if (pbuf[i] == commutation_data_2){pbuf[i] = commutation_data_1;}else{;}}}printf("Point Exchange method sudoku(point:2,8):\n");XslGameSudo_FormatPrint(pXslGameSudoS, 2);//----------memcpy((uint8_t *)(pXslGameSudoS->cells), (uint8_t *)&XslGameSudo_SudoGenerateBuf[0][0], XSLGAMESUDO_SUDOKU_LEVEL * XSLGAMESUDO_SUDOKU_LEVEL);printf("%d,----------Seeds sudoku:\n", num++);XslGameSudo_FormatPrint(pXslGameSudoS, 2);// 非跨界行交換{uint8_t commutation_row_1, commutation_row_2;uint8_t i, temp;// 設定交換行(0-8有效)commutation_row_1 = 0;commutation_row_2 = 2;// 執(zhí)行交換行for (i = 0; i < XSLGAMESUDO_SUDOKU_LEVEL; i++){temp = pXslGameSudoS->cells[commutation_row_1][i];pXslGameSudoS->cells[commutation_row_1][i] = pXslGameSudoS->cells[commutation_row_2][i];pXslGameSudoS->cells[commutation_row_2][i] = temp;}}printf("Row Exchange method sudoku(row:1,3):\n");XslGameSudo_FormatPrint(pXslGameSudoS, 2);//----------memcpy((uint8_t *)(pXslGameSudoS->cells), (uint8_t *)&XslGameSudo_SudoGenerateBuf[0][0], XSLGAMESUDO_SUDOKU_LEVEL * XSLGAMESUDO_SUDOKU_LEVEL);printf("%d,----------Seeds sudoku:\n", num++);XslGameSudo_FormatPrint(pXslGameSudoS, 2);// 非跨界列交換{uint8_t commutation_col_1, commutation_col_2;uint8_t i, temp;// 設定交換行(0-8有效)commutation_col_1 = 0;commutation_col_2 = 2;// 執(zhí)行交換行for (i = 0; i < XSLGAMESUDO_SUDOKU_LEVEL; i++){temp = pXslGameSudoS->cells[i][commutation_col_1];pXslGameSudoS->cells[i][commutation_col_1] = pXslGameSudoS->cells[i][commutation_col_2];pXslGameSudoS->cells[i][commutation_col_2] = temp;}}printf("Col Exchange method sudoku(col:1,3):\n");XslGameSudo_FormatPrint(pXslGameSudoS, 2);//----------memcpy((uint8_t *)(pXslGameSudoS->cells), (uint8_t *)&XslGameSudo_SudoGenerateBuf[0][0], XSLGAMESUDO_SUDOKU_LEVEL * XSLGAMESUDO_SUDOKU_LEVEL);printf("%d,----------Seeds sudoku:\n", num++);XslGameSudo_FormatPrint(pXslGameSudoS, 2);// 塊行交換{uint8_t commutation_blockrow_1, commutation_blockrow_2;uint8_t i, j, temp;// 設定交換行(0-2有效)commutation_blockrow_1 = 0;commutation_blockrow_2 = 1;// 執(zhí)行交換行for (i = 0; i < XSLGAMESUDO_SUDOKU_LEVEL; i++){for (j = 0; j < 3; j++){temp = pXslGameSudoS->cells[commutation_blockrow_1 * 3 + j][i];pXslGameSudoS->cells[commutation_blockrow_1 * 3 + j][i] = pXslGameSudoS->cells[commutation_blockrow_2 * 3 + j][i];pXslGameSudoS->cells[commutation_blockrow_2 * 3 + j][i] = temp;}}}printf("Block Row Exchange method sudoku(Block Row:1,2):\n");XslGameSudo_FormatPrint(pXslGameSudoS, 2);//----------memcpy((uint8_t *)(pXslGameSudoS->cells), (uint8_t *)&XslGameSudo_SudoGenerateBuf[0][0], XSLGAMESUDO_SUDOKU_LEVEL * XSLGAMESUDO_SUDOKU_LEVEL);printf("%d,----------Seeds sudoku:\n", num++);XslGameSudo_FormatPrint(pXslGameSudoS, 2);// 塊列交換{uint8_t commutation_blockrow_1, commutation_blockrow_2;uint8_t i, j, temp;// 設定交換行(0-2有效)commutation_blockrow_1 = 0;commutation_blockrow_2 = 1;// 執(zhí)行交換行for (i = 0; i < XSLGAMESUDO_SUDOKU_LEVEL; i++){for (j = 0; j < 3; j++){temp = pXslGameSudoS->cells[i][commutation_blockrow_1 * 3 + j];pXslGameSudoS->cells[i][commutation_blockrow_1 * 3 + j] = pXslGameSudoS->cells[i][commutation_blockrow_2 * 3 + j];pXslGameSudoS->cells[i][commutation_blockrow_2 * 3 + j] = temp;}}}printf("Block Col Exchange method sudoku(Block Col:1,2):\n");XslGameSudo_FormatPrint(pXslGameSudoS, 2);//----------memcpy((uint8_t *)(pXslGameSudoS->cells), (uint8_t *)&XslGameSudo_SudoGenerateBuf[0][0], XSLGAMESUDO_SUDOKU_LEVEL * XSLGAMESUDO_SUDOKU_LEVEL);printf("%d,----------Seeds sudoku:\n", num++);XslGameSudo_FormatPrint(pXslGameSudoS, 2);// 矩陣旋轉(下面是方形矩陣的自旋轉程序(不用額外緩存)){uint8_t i, j, k, n, x;uint8_t temp1, temp2;//設置參數(shù)n = XSLGAMESUDO_SUDOKU_LEVEL;x = n / 2;// 一圈一圈處理k = n - 1;for (i = 0; i < x; i++){for (j = 0; j < k; j++){//右列temp1 = pXslGameSudoS->cells[i + j][n - 1 - i];pXslGameSudoS->cells[i + j][n - 1 - i] = pXslGameSudoS->cells[i][i + j];//下行temp2 = pXslGameSudoS->cells[n - 1 - i][n - 1 - i - j];pXslGameSudoS->cells[n - 1 - i][n - 1 - i - j] = temp1;//左列temp1 = pXslGameSudoS->cells[n - 1 - i - j][i];pXslGameSudoS->cells[n - 1 - i - j][i] = temp2;//左上pXslGameSudoS->cells[i][i + j] = temp1;}k -= 2;}}printf("Rotate method sudoku(90 degrees):\n");XslGameSudo_FormatPrint(pXslGameSudoS, 2);//----------memcpy((uint8_t *)(pXslGameSudoS->cells), (uint8_t *)&XslGameSudo_SudoGenerateBuf[0][0], XSLGAMESUDO_SUDOKU_LEVEL * XSLGAMESUDO_SUDOKU_LEVEL);printf("%d,----------Seeds sudoku:\n", num++);XslGameSudo_FormatPrint(pXslGameSudoS, 2);// 矩陣行鏡像{uint8_t i, j;uint8_t temp;//for (i = 0; i < XSLGAMESUDO_SUDOKU_LEVEL / 2; i++){for (j = 0; j < XSLGAMESUDO_SUDOKU_LEVEL; j++){temp = pXslGameSudoS->cells[j][XSLGAMESUDO_SUDOKU_LEVEL - 1 - i];pXslGameSudoS->cells[j][XSLGAMESUDO_SUDOKU_LEVEL - 1 - i] = pXslGameSudoS->cells[j][i];pXslGameSudoS->cells[j][i] = temp;}}}printf("X Mirror sudoku:\n");XslGameSudo_FormatPrint(pXslGameSudoS, 2);//----------memcpy((uint8_t *)(pXslGameSudoS->cells), (uint8_t *)&XslGameSudo_SudoGenerateBuf[0][0], XSLGAMESUDO_SUDOKU_LEVEL * XSLGAMESUDO_SUDOKU_LEVEL);printf("%d,----------Seeds sudoku:\n", num++);XslGameSudo_FormatPrint(pXslGameSudoS, 2);// 矩陣列鏡像{uint8_t i, j;uint8_t temp;//for (i = 0; i < XSLGAMESUDO_SUDOKU_LEVEL / 2; i++){for (j = 0; j < XSLGAMESUDO_SUDOKU_LEVEL; j++){temp = pXslGameSudoS->cells[XSLGAMESUDO_SUDOKU_LEVEL - 1 - i][j];pXslGameSudoS->cells[XSLGAMESUDO_SUDOKU_LEVEL - 1 - i][j] = pXslGameSudoS->cells[i][j];pXslGameSudoS->cells[i][j] = temp;}}}printf("Y Mirror sudoku:\n");XslGameSudo_FormatPrint(pXslGameSudoS, 2);//----------memcpy((uint8_t *)(pXslGameSudoS->cells), (uint8_t *)&XslGameSudo_SudoGenerateBuf[0][0], XSLGAMESUDO_SUDOKU_LEVEL * XSLGAMESUDO_SUDOKU_LEVEL);printf("%d,----------Seeds sudoku:\n", num++);XslGameSudo_FormatPrint(pXslGameSudoS, 2);// 矩陣對角線鏡像{uint8_t i, j;uint8_t temp;for (i = 0; i < XSLGAMESUDO_SUDOKU_LEVEL - 1; i++){for (j = 0; j < XSLGAMESUDO_SUDOKU_LEVEL - 1 - i; j++){temp = pXslGameSudoS->cells[i + j + 1][i];pXslGameSudoS->cells[i + j + 1][i] = pXslGameSudoS->cells[i][i + j + 1];pXslGameSudoS->cells[i][i + j + 1] = temp;}}}printf("Transpose sudoku:\n");XslGameSudo_FormatPrint(pXslGameSudoS, 2);//---------- } /*** @brief main函數(shù)* @note 主函數(shù)入口* @param null* @return null*/ uint8_t MemBuf[1024]; //81個字節(jié)存儲一組解,1024可以存儲大于10個解 uint32_t SudoCount; void main(int argc, char **argv) {uint8_t res;uint32_t time1, time2;printf("--------------------------------------------------\n");printf(" XSL Sudo Generate(Normal) \n");printf("--------------------------------------------------\n");XslGameSudo_Generate(&XslGameSudo_s_Sudo); while(1);printf("--------------------------------------------------\n");printf(" XSL Sudo Processor(Normal) \n");printf("--------------------------------------------------\n");// 數(shù)據(jù)載入memcpy((uint8_t *)(XslGameSudo_s_Sudo.cells), (uint8_t *)&XslGameSudo_SudoBuf[0][0], XSLGAMESUDO_SUDOKU_LEVEL * XSLGAMESUDO_SUDOKU_LEVEL);// 設置配置//---最多解析10個解XslGameSudo_s_Sudo.MaxOutAnswersCount = 5;XslGameSudo_s_Sudo.pOutBuf = MemBuf;XslGameSudo_s_Sudo.pAnswersCount = &SudoCount;// 打印原始數(shù)獨XslGameSudo_FormatPrint(&XslGameSudo_s_Sudo, 0);// 啟動數(shù)獨測試time1 = GetTickCount();XslGameSudo_Processor(&XslGameSudo_s_Sudo);time2 = GetTickCount();// 打印結果XslGameSudo_FormatPrint(&XslGameSudo_s_Sudo, 1);// 打印耗時printf("Time(ms):%ld\n", time2 - time1);// 定住頁面,否則程序結束直接閃退,延時10秒自動退出time1 = time2 = 0;time1 = GetTickCount();while (((time2 - time1) < 100000) || (time2 == 0)){time2 = GetTickCount();} }五,運行結果演示
-
運行結果---兩數(shù)交換法
-
運行結果---非跨界行交換
-
運行結果---非跨界列交換
-
運行結果---塊行交換
-
運行結果---塊列交換
-
運行結果---矩陣旋轉
-
運行結果---矩陣行鏡像
-
運行結果---矩陣列鏡像
-
運行結果---矩陣對角線鏡像
六,引用資料致謝
- 感謝如下連接給的思路：
- https://my.oschina.net/wangmengjun/blog/781984
總結
以上是生活随笔為你收集整理的徐松亮算法教学-基于C语言的数独(九宫格)多种终盘生成方法（包含矩阵镜像旋转转置等相关算法）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 做完c语言通讯录系统后的小结,c语言通讯
- 下一篇： c语言通讯录程序设计个人感言,C语言学习