C語言實現數獨輔助器(附源碼)
數獨遊戲介紹
數獨是源自瑞士的一種數學遊戲。是一種運用紙、筆進行演算的邏輯遊戲。玩傢需要根據 9×9 盤面上的已知數字，推理出所有剩餘空格的數字，並滿足每一行、每一列、每一個粗線宮（3*3）內的數字均含 1-9，不重復 。
數獨盤面是個九宮，每一宮又分為九個小格。在這八十一格中給出一定的已知數字和解題條件，利用邏輯和推理，在其他的空格上填入1-9的數字。使1-9每個數字在每一行、每一列和每一宮中都隻出現一次，所以又稱“九宮格”。
數獨輔助器編寫思路
首先，肯定是畫九宮格，做好這個程序的界面。然後給這個界面的相應位置賦予對應相應的數，用鼠標給這個數獨九宮格進行填數。當然做好前面的這些隻是表面的，最主要的是如何用電腦來解這個數獨呢？我一直在思考，程序其實就是一個工具，而我們就是要學會應用這個工具去做一些我們很難做到的事，編寫程序就是一個解決問題的好辦法。我記得我曾經花瞭一周的時間去解一個數獨，雖然數獨最終解出來瞭，但假如我又遇到別的數獨呢？這就是我們需去考慮的問題。我們不是為瞭去解決一個數獨，而是要解決所有的數獨，當然，我們不僅僅隻是為瞭解決所有數獨，而是要用程序解決所以需要耗時耗力的問題。
要解決掉所有的數獨，需要懂數獨的規則，編寫一個程序一定要要思路，有想法。首先數獨，有它的唯一性，每一行，每一列，每一宮中都隻能出現一次，那麼我們就可以用循環從左上角來對這個數獨進行填寫，根據它的唯一性，假如不符合，我們就換一個數，再判斷是否符合，假如都不符合則返回上一步，判斷上一步的下一個數是否符合，如果還是都不符合，則返回上上步，直至所有的都符合數獨的唯一性。（我們解數獨的時候是進行推理，邏輯思考。電腦解數獨的時候是窮舉，嘗試所有的可能性，這裡用到的方法是回溯法，我們也可以用這種方法解，但人的速度太慢瞭，肯定沒有電腦速度快，這就是電腦的優勢）
效果圖
源碼
///
//
// 程序名稱：數獨解題器
// 編譯環境：Mictosoft Visual Studio 2013, EasyX_20200315(beta)
//
#include <graphics.h>
#define WIDTH 480
#define HEIGHT 640
const wchar_t wPROGRAMINFO[] = _T("\n操作說明：\n1.鼠標左擊下方不同的數字進行選取 \n2.再左擊九宮格相應位置進行填入 \n3.選擇後可重復填入 \n4.點擊求解鍵後開始處理數獨 \n4.點擊清空將清除掉九宮格內的數\n");
int matrix[9][9] = { 0 }; // 定義一個二維數組儲存數獨
void drawframe(); // 繪制九宮格及修飾的相關圖形
void grain(); // 紋路
void Prompt(); // 繪制提示符
void Solution(); // 求解按鈕
void ClearButton(); // 清空按鈕
void OUTTEXT(int i,int x,int y); // 繪制輸出數字
int MouseMessage(int *m_x, int *m_y); // 處理鼠標消息，返回數與鼠標的坐標
void retrace(int number, COLORREF color); // 重新復原邊框顏色等
void save(int n, int x,int y); // 儲存和輸出
void ClearScreen(); // 清空九宮格
bool FirstCheck(); // 初次判斷檢查
void Output(); // 輸出答案
int MouseNumber = 0;
int sum = 0; // 數獨多解的記錄
int trace(int x, int y); // 算法的核心回溯法
int check(int x, int y); // 每次判斷
bool newmatrix[9][9];
void Tofalse(); // 將數組全部置為 false
int CheckNumber(int n); // 判斷裡面有沒有這個數
int Totrue(int n);
bool SecondCheck(); // 第二次判斷
bool Point[3][3];
int main()
{
initgraph(WIDTH, HEIGHT);
drawframe(); // 繪制表格框架
while (true)
{
while (true)
{
int m_x, m_y, number;
number = MouseMessage(&m_x, &m_y); // 鼠標消息
if (number == 10)
{
MouseNumber = 0;
if (FirstCheck() == false)
continue;
else
break;
}
save(number, m_x, m_y);
if (FirstCheck() == false)
{
settextstyle(20, 0, _T("楷體"));
settextcolor(0xf4b1a4);
outtextxy(120, 99, _T("輸入有誤，請檢查！"));
}
if (FirstCheck() == true)
{
settextstyle(20, 0, _T("楷體"));
outtextxy(120, 99, _T(" "));
}
}
settextcolor(0xf4b1a4);
settextstyle(20, 0, _T("楷體"));
outtextxy(120, 99, _T("求解中......"));
if (SecondCheck() == true) // 第二次檢查，防止不必要的死循環
{
trace(0, 0); // 溯回法判斷
}
else sum = 0;
if (sum == 0)
{
setbkmode(OPAQUE);
settextcolor(0xf4b1a4);
settextstyle(20, 0, _T("楷體"));
outtextxy(120, 99, _T(" "));
outtextxy(120, 99, _T("該數獨無解！"));
continue;
}
if (sum == 1)
{
setbkmode(OPAQUE);
settextcolor(0xf4b1a4);
settextstyle(20, 0, _T("楷體"));
outtextxy(120, 99, _T(" "));
outtextxy(120, 99, _T("該數獨隻有一個解"));
sum = 0;
continue;
}
if (sum > 1)
{
setbkmode(OPAQUE);
settextcolor(0xf4b1a4);
settextstyle(20, 0, _T("楷體"));
outtextxy(120, 99, _T(" "));
outtextxy(120, 99, _T("該數獨有多個解"));
sum = 0;
continue;
}
}
closegraph();
return 0;
}
// 繪制數獨框架，可以進一步美化
void drawframe()
{
setbkcolor(0x3a0a0a);
cleardevice();
grain();
setlinestyle(PS_SOLID | PS_ENDCAP_SQUARE, 0);
setlinecolor(0x5555FF);
int x = 60;
int y = 120;
// 繪制九宮格，左上角坐標為（x ，y）每隔40畫一條橫線，並畫一條豎線
for (int i = 0; i <= 9; i++)
{
line(x, y + i * 40, 420, y + i * 40);
line(x + i * 40, y, x + i * 40, 480);
}
setlinestyle(PS_SOLID | PS_ENDCAP_SQUARE, 3);
setlinecolor(0xFF5555);
// 分割為九份，左上角坐標為（x , y）每隔120畫一條橫線，並畫一條豎線
for (int i = 0; i < 4; i++)
{
line(x, y + i * 120, 420, y + i * 120);
line(x + i * 120, y, x + i * 120, 480);
}
// 繪制漢字修飾符
settextcolor(0xf4b1a4);
setbkmode(TRANSPARENT);
settextstyle(76, 0, _T("楷體"));
outtextxy(60, 22, _T("數獨輔助器"));
settextstyle(20, 0, _T("楷體"));
outtextxy(40, 490, _T("請選擇你需要填入的數："));
// 繪制下邊的框格
line(40, 520, 440, 520);
line(40, 560, 440, 560);
for (int i = 0; i <= 10; i++)
{
line(40 + 40 * i, 520, 40 + 40 * i, 560);
}
// 給框格內填入數字
for (int i = 0; i <= 9; i++)
{
setbkmode(TRANSPARENT);
OUTTEXT(i, 40 + 40 * i + 12, 522);
}
settextcolor(0xf4b1a4);
// 繪制求解鍵
Solution();
// 繪制提示說明符
Prompt();
// 繪制清屏按鈕
ClearButton();
settextstyle(20, 0, _T("楷體"));
outtextxy(60, 99, _T("提示："));
}
// 繪制提示說明符
void Prompt()
{
setbkmode(TRANSPARENT);
setlinestyle(PS_SOLID | PS_ENDCAP_FLAT, 2);
settextstyle(42, 0, L"Webdings");
wchar_t c = 0x69;
outtextxy(438, 0, c);
}
// 求解按鈕
void Solution()
{
setbkmode(TRANSPARENT);
rectangle(360, 580, 440, 620);
setbkmode(TRANSPARENT);
settextstyle(36, 0, _T("楷體"));
outtextxy(364, 582, _T("求解"));
}
// 清空按鈕
void ClearButton()
{
setbkmode(TRANSPARENT);
setlinestyle(PS_SOLID | PS_ENDCAP_FLAT, 3);
rectangle(280, 580, 360, 620);
settextstyle(36, 0, _T("楷體"));
outtextxy(284,582,_T("清空"));
}
// 紋路
void grain()
{
setlinestyle(PS_SOLID | PS_ENDCAP_FLAT, 2);
setlinecolor(0xb82727);
line(61, 486, 0, 547);
line(94, 486, 0, 580);
line(140, 486, 7, 619);
line(158, 486, 15, 629);
line(170, 491, 24, 638);
line(170, 491, 212, 491);
line(212, 491, 280, 560);
line(280, 560, 400, 560);
line(400, 560, 480, 480);
line(228, 486, 271, 530);
line(271, 530, 352, 530);
line(352, 530, 396, 486);
line(40, 640, 105, 575);
line(105, 575, 114, 575);
line(114, 575, 168, 520);
line(168, 520, 220, 520);
line(220, 520, 300, 600);
line(300, 600, 360, 600);
setfillcolor(WHITE);
solidcircle(360, 600, 4);
line(60, 640, 110, 590);
line(110, 590, 119, 590);
line(119, 590, 177, 530);
line(177,530,211,530);
line(211, 530, 290, 608);
line(290, 608, 290, 632);
solidcircle(290, 632, 4);
circle(137, 593, 3);
line(139, 591, 179, 551);
line(179, 551, 213, 551);
line(213, 551, 242, 582);
line(242, 582, 242, 605);
solidcircle(242, 605, 4);
circle(159, 592, 3);
line(161, 589, 171, 579);
line(171, 579, 213, 579);
line(213, 579, 220, 585);
line(220, 585, 220, 592);
circle(220, 595, 3);
circle(110 ,600, 3);
line(113, 604, 128, 619);
line(128, 619, 260, 619);
line(260, 619, 280, 639);
line(280, 639, 339, 639);
line(339, 639, 379, 600);
line(379, 600, 379, 576);
circle(379, 573, 3);
circle(77, 637, 3);
line(80, 633, 95, 619);
line(95, 619, 117, 619);
line(117, 619, 125, 626);
line(125, 626, 210, 626);
line(210, 626, 222, 640);
line(88, 640, 93, 634);
line(93, 634, 199, 634);
line(199, 634, 202, 640);
line(358, 639, 397, 599);
line(397, 599, 438, 599);
line(438, 599, 470, 568);
circle(472, 565, 3);
line(379, 639, 398, 619);
line(398, 619, 420, 619);
circle(423, 619, 3);
circle(426, 568, 3);
line(429, 565, 480, 516);
line(458, 638, 467, 630);
line(467, 630, 480, 630);
line(0, 184, 26, 210);
line(26, 210, 26, 369);
line(26, 369, 0, 393);
line(0, 205, 7, 211);
line(7, 211, 7, 270);
circle(7, 273, 3);
line(0, 463, 5, 457);
line(5, 457, 5, 430);
line(5, 430, 51, 383);
line(51, 174, 40, 163);
line(40, 163, 40, 16);
circle(40, 13, 3);
line(52, 0, 69, 18);
line(69, 18, 69, 52);
circle(69, 55, 3);
line(257, 0, 144, 111);
line(144, 111, 144, 120);
line(310, 0, 190, 120);
line(238, 120, 263, 94);
line(263, 94, 329, 94);
line(329, 94, 424, 0);
line(423, 461, 423, 421);
line(423, 421, 445, 397);
circle(451, 392, 3);
line(420, 358, 480, 358);
line(420, 136, 480, 74);
line(420, 186, 443, 186);
line(443, 186, 480, 147);
line(420, 207, 450, 206);
line(450, 206, 480, 179);
line(420, 254, 480, 254);
line(420, 261, 480, 261);
// 粗白線
setlinestyle(PS_SOLID | PS_JOIN_BEVEL, 4);
line(70, 120, 70, 107);
line(70, 107, 138, 40);
line(138, 40, 138, 0);
line(133, 120, 133, 95);
line(212, 120, 331, 0);
line(420, 168, 429, 168);
line(429, 168, 480, 117);
line(420, 227, 462, 227);
line(462, 227, 480, 208);
line(0, 145, 45, 190);
line(45, 190, 45, 368);
line(45, 368, 0, 412);
line(133, 95, 227, 0);
line(344, 120, 460, 0);
line(119, 486, 0, 605);
setlinecolor(0xf4b1a4);
line(420, 268, 480, 268);
line(48, 471, 0, 520);
circle(464, 612, 3);
line(467, 609, 480, 597);
}
// 輸出相應位置對應的相應的數
void OUTTEXT(int i, int x, int y)
{
settextstyle(36, 0, _T("consolas"));
switch (i)
{
case 0: settextcolor(0xFFFFFF); outtextxy(x, y, _T(" ")); break;
case 1: settextcolor(0xEFFFFE); outtextxy(x, y, _T("1")); break;
case 2: settextcolor(0xDFFFFD); outtextxy(x, y, _T("2")); break;
case 3: settextcolor(0xCFFFFC); outtextxy(x, y, _T("3")); break;
case 4: settextcolor(0xBFFFFB); outtextxy(x, y, _T("4")); break;
case 5: settextcolor(0xAFFFFA); outtextxy(x, y, _T("5")); break;
case 6: settextcolor(0x9FFFF9); outtextxy(x, y, _T("6")); break;
case 7: settextcolor(0x8FFFF8); outtextxy(x, y, _T("7")); break;
case 8: settextcolor(0x7FFFF7); outtextxy(x, y, _T("8")); break;
case 9: settextcolor(0x6FFFF6); outtextxy(x, y, _T("9")); break;
}
}
// 有鼠標獲取相應位置相應的數
int MouseMessage(int *myx, int *myy)
{
MOUSEMSG m; // 定義鼠標消息
bool T = true;
while (T)
{
m = GetMouseMsg(); // 獲取一個鼠標消息
setlinecolor(RED);
switch (m.uMsg)
{
case WM_LBUTTONDOWN:
if (m.x >= 40 && m.x <= 440 && m.y >= 520 && m.y <= 560) // 如果左鍵按下的范圍在下方選擇的范圍內
{
if (MouseNumber >= 0) // 如果這個鼠標已經過數，繼續點擊，需要使得畫過的顏色復原
{
retrace(MouseNumber, 0xFF5555);
}
retrace((m.x - 40) / 40, RED);
MouseNumber = (m.x - 40) / 40;
}
if (m.x >= 60 && m.x <= 420 && m.y >= 120 && m.y <= 480) // 坐標點在九宮格內就將給點坐標按地址值傳出
{
*myx = m.x;
*myy = m.y;
T = false;
}
if (m.x >= 360 && m.x <= 440 && m.y >= 580 && m.y <= 620) // 確定鍵按按下
{
setlinecolor(RED);
settextcolor(RED);
Solution();
retrace(MouseNumber, 0xFF5555);
settextstyle(20, 0, _T("楷體"));
outtextxy(120, 99, _T(" "));
break;
}
if (m.x >= 436 && m.x <= 480 && m.y >= 0 && m.y <= 44) // 提示符按下
{
settextcolor(RED);
setlinecolor(RED);
Prompt();
break;
}
if (m.x >= 280 && m.x <= 360 && m.y >= 580 && m.y <= 620) // 清屏按下
{
setlinecolor(RED);
settextcolor(RED);
ClearButton();
retrace(MouseNumber, 0xFF5555);
setbkmode(OPAQUE);
settextstyle(20, 0, _T("楷體"));
outtextxy(120, 99, _T(" "));
break;
}
case WM_LBUTTONUP: // 左鍵抬起
if (m.x >= 360 && m.x <= 440 && m.y >= 580 && m.y <= 620) // 確定鍵抬起
{
setlinecolor(0xFF5555);
settextcolor(0xf4b1a4);
Solution();
MouseNumber = 10;
return MouseNumber;
}
if (m.x >= 436 && m.x <= 480 && m.y >= 0 && m.y <= 44) // 提示符抬起彈出操作說明
{
settextcolor(0xFF5555);
setlinecolor(0xFF5555);
Prompt();
MessageBox(NULL, wPROGRAMINFO, _T("關於"), MB_OK | MB_ICONASTERISK);
}
if (m.x >= 280 && m.x <= 360 && m.y >= 580 && m.y <= 620) // 清屏抬起
{
settextcolor(0xf4b1a4);
setlinecolor(0xFF5555);
ClearButton();
ClearScreen();
sum=0;
break;
}
}
}
return MouseNumber;
}
// 重新描矩形，給人按鈕的感覺
void retrace(int number, COLORREF color)
{
setlinestyle(PS_SOLID | PS_ENDCAP_FLAT, 3);
setlinecolor(color);
switch (number)
{
case 0: rectangle(40 + 40 * 0, 520, 80 + 40 * 0, 560); break;
case 1: rectangle(40 + 40 * 1, 520, 80 + 40 * 1, 560); break;
case 2: rectangle(40 + 40 * 2, 520, 80 + 40 * 2, 560); break;
case 3: rectangle(40 + 40 * 3, 520, 80 + 40 * 3, 560); break;
case 4: rectangle(40 + 40 * 4, 520, 80 + 40 * 4, 560); break;
case 5: rectangle(40 + 40 * 5, 520, 80 + 40 * 5, 560); break;
case 6: rectangle(40 + 40 * 6, 520, 80 + 40 * 6, 560); break;
case 7: rectangle(40 + 40 * 7, 520, 80 + 40 * 7, 560); break;
case 8: rectangle(40 + 40 * 8, 520, 80 + 40 * 8, 560); break;
case 9: rectangle(40 + 40 * 9, 520, 80 + 40 * 9, 560); break;
}
}
// 對相應數的填入和儲存
void save(int n, int x, int y)
{
int myx, myy;
myx = ((x - 60) / 40) * 40 + 60 + 12;
myy = ((y - 120) / 40) * 40 + 120 + 2;
setbkmode(OPAQUE);
OUTTEXT(n, myx, myy);
int mx, my;
mx = (x - 60) / 40;
my = (y - 120) / 40;
matrix[mx][my] = n;
}
// 將九宮格內的數清空
void ClearScreen()
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
setbkmode(OPAQUE);
OUTTEXT(0,i * 40 + 60 + 12, j * 40 + 120 + 2);
matrix[i][j] = 0;
}
}
MouseNumber = 0;
}
// 將答案輸出
void Output()
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
setbkmode(OPAQUE);
OUTTEXT(matrix[i][j], 60 + i * 40 + 12, 120 + j * 40 + 2);
}
}
}
// 檢查一行一列中的數，和九宮格中
int check(int x, int y)
{
int flag = 1;
for (int i = 0; i<9; i++)
{
if (matrix[x][i] == matrix[x][y] && i != y)
{
flag = 0;
}
if (matrix[i][y] == matrix[x][y] && i != x)
{
flag = 0;
}
}
int xi = x / 3, yi = y / 3;
for (int i = xi * 3; i<(xi + 1) * 3; i++)
{
for (int j = yi * 3; j<(yi + 1) * 3; j++)
{
if (i != x && j != y && matrix[i][j] == matrix[x][y])
{
flag = 0;
}
}
}
return flag;
}
// 核心算法，回溯法
int trace(int x, int y)
{
if (x == 9)
{
Output();
sum++;
}
if (sum > 1)
return 0;
if (matrix[x][y] == 0)
{
for (int j = 1; j <= 9; j++)
{
matrix[x][y] = j;
if (check(x, y))
{
trace(x + (y + 1) / 9, (y + 1) % 9);
}
matrix[x][y] = 0;
}
}
else
{
trace(x + (y + 1) / 9, (y + 1) % 9);
}
return 0;
}
// 初步進行判斷數獨的正確性
bool FirstCheck()
{
int a[9]; // 行
int b[9]; // 列
int c[9]; // 塊
// 判斷每一行是否符合條件
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
a[j] = matrix[i][j];
if (j == 8)
{
for (int q = 0; q < 9; q++)
{
for (int p = q + 1; p < 9; p++)
{
if (p < 9)
{
if (a[q] != 0 && a[p] != 0)
{
if (a[q] == a[p])
return false;
}
}
}
}
}
}
}
// 判斷每一列是否符合條件
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
b[j] = matrix[j][i];
if (j == 8)
{
for (int q = 0; q < 9; q++)
{
for (int p = q + 1; p < 9; p++)
{
if (p < 9)
{
if (b[q] != 0 && b[p] != 0)
{
if (b[q] == b[p])
return false;
}
}
}
}
}
}
}
// 用於判斷九宮格中每一個塊中有無重復的
int ns = 0;
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
for (int p = 0; p < 3; p++)
{
for (int q = 0; q < 3; q++)
{
c[ns] = matrix[i * 3 + p][j * 3 + q];
ns++;
if (ns == 9)
{
for (int w = 0; w < 9; w++)
{
for (int z = w + 1; z < 9; z++)
{
if (z < 9)
{
if (c[w] != 0 && c[z] != 0)
{
if (c[w] == c[z])
return false;
}
}
}
}
ns = 0;
}
}
}
}
}
// 如果依次判斷後，無重復，則返回正確
return true;
}
// 將數組全部置為 false
void Tofalse()
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
newmatrix[i][j] = false;
}
}
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
Point[i][j] = false;
}
}
}
// 判斷九宮格裡面有沒有這個數
int CheckNumber(int n)
{
int c[9];
int ns = 0;
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
for (int p = 0; p < 3; p++)
{
for (int q = 0; q < 3; q++)
{
c[ns] = matrix[i * 3 + p][j * 3 + q];
ns++;
if (ns == 9) //將每一宮中的數存儲到一個一維數組中進行判斷
{
for (int w = 0; w < 9; w++)
{
if (c[w] == n)
Point[i][j] = true;
}
ns = 0;
}
}
}
}
}
return 0;
}
// 對行列進行賦值
int Totrue(int number)
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (matrix[i][j] == number)
{
for (int p = 0; p < 9; p++)
{
newmatrix[i][p] = true;
newmatrix[p][j] = true;
}
}
if (matrix[i][j] != 0)
{
newmatrix[i][j] = true;
}
}
}
return 0;
}
// 第二次判斷
bool SecondCheck()
{
for (int number = 1; number < 10; number++)
{
Tofalse(); // 將數組初始化為假
CheckNumber(number); // 將有這個數的宮格進行賦值
Totrue(number); // 將含有這個數的行列都賦為真
// 開始判斷第一個宮格是否存在這個數，如果存在，則判斷下一個，如果存在，判斷它裡面是否為假
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (Point[i][j] == false)
{
int nums = 0;
for (int p = 0; p < 3; p++)
{
for (int q = 0; q < 3; q++)
{
if (newmatrix[i * 3 + p][j * 3 + q] == false)
{
nums++;
}
}
}
if (nums>0)
{
nums = 0;
}
else
return false;
}
}
}
}
return true;
}
以上就是C語言實現數獨輔助器(附源碼)的詳細內容，更多關於C語言數獨輔助器的資料請關註WalkonNet其它相關文章！