vlambda博客
学习文章列表

C语言解数独(溯回法)




C语言解数独

It's a Title Here


01


效果如下


It's a Title



02


代码如下


It's a Title


#include<graphics.h>

#include<conio.h>

#include<stdio.h>

#define CHANG 600

#define KUAN  800

int juzheng[9][9] = { 0 };

int xinjuzheng[9][9] = { 0 };

void fangkuang();

void OUTTEXT(int x, int y, int i);

int shubiao(int *mx,int *my);

void chuti(int n, int x, int y);

void chucun(int n, int x, int y);

int panduan();

void qinping();

void tianshu(int x,int y, int n);

//void chubufengxi();

void xiangxichuli(int x, int y);

int check(int x, int y);

void print();

void tishifu();

int sum;

int cishu=0;

int main()

{


initgraph(600, 800);

fangkuang();

while (true)

{while (true)

{

while (true){

int m_x, m_y, num;

num = shubiao(&m_x, &m_y);

if (num == 11)

break;


chuti(num, m_x, m_y);

chucun(num, m_x, m_y);

}

if (panduan() == 0)//如果不符合条件,则清屏重新填入。

{

MessageBox(NULL, TEXT("你输入的数独题有误请重新填入!"), TEXT("来自数独的提示"), MB_OK);

juzheng[9][9] = { 0 };

qinping();//将填入的数据进行擦除

continue;

}

else

MessageBox(NULL, TEXT("初次判断题目无误,可以继续进行。"), TEXT("来自数独的提示"), MB_OK);

break;

}


//chubufengxi();//进行初步分析,解出个别的题目,


xiangxichuli(0,0);

if (cishu == 0)

MessageBox(NULL, TEXT("进一步判断您的题目有误,请重新输入。"), TEXT("来自数独的提示"), MB_OK);

qinping();

if (cishu > 0)

break;

}

MessageBox(NULL, TEXT("程序结束!感谢您的使用。"), TEXT("来自数独的提示"), MB_OK);



closegraph();


getch();

return 0;

}

void fangkuang()

{

setlinestyle(PS_SOLID | PS_ENDCAP_SQUARE,3);

for (int i = 0; i <= 9; i++)

{

if (i % 3 == 0)

setlinecolor(LIGHTGREEN);

else

   setlinecolor(BROWN);


line(48, 120 + i * 56, 552, 120 + i * 56);

line(48 + i * 56, 120, 48 + i * 56, 624);

}

settextcolor(LIGHTRED);

settextstyle(100, 0, _T("楷体"));

outtextxy(150,10,_T("数"));

outtextxy(350, 10, _T("独"));


fillrectangle(456,684,552,740);

setfillcolor(LIGHTGRAY);

setlinecolor(YELLOW);

settextcolor(BLACK);

//settextstyle(50, 0, _T("宋体"));

setbkmode(TRANSPARENT);

LOGFONT f;

gettextstyle(&f);                     // 获取当前字体设置

f.lfHeight = 45;                      // 设置字体高度为 48

_tcscpy(f.lfFaceName, _T("宋体"));    // 设置字体为“黑体”(高版本 VC 推荐使用 _tcscpy_s 函数)

f.lfQuality = ANTIALIASED_QUALITY;    // 设置输出效果为抗锯齿  

settextstyle(&f);                     // 设置字体样式

outtextxy(460, 689, _T("确定"));

settextcolor(WHITE);

settextstyle(25, 0, _T("宋体"));

outtextxy(48,670,_T("选择你需要填的数"));

line(48, 695, 444, 695);

line(48, 739, 444, 739);

for (int i = 0; i <= 9; i++)

line(48 + i * 44, 695, 48 + i * 44, 739);

settextstyle(41, 0, _T("宋体"));

for (int i = 0; i < 9; i++)

OUTTEXT(60 + i * 44, 697, i);

setlinecolor(RED);

setfillcolor(RED);

tishifu();

setlinecolor(YELLOW);


}

void OUTTEXT(int x,int y,int i)

{

if (i == -1)

{

i = 9;

}

switch (i)

{

case 0:  outtextxy(x, y, _T("1")); settextcolor(0xFFFFFF); break;

case 1:  outtextxy(x, y, _T("2")); settextcolor(0xEFFFFE); break;

case 2:  outtextxy(x, y, _T("3")); settextcolor(0xDFFFFD); break;

case 3:  outtextxy(x, y, _T("4")); settextcolor(0xCFFFFC); break;

case 4:  outtextxy(x, y, _T("5")); settextcolor(0xBFFFFB); break;

case 5:  outtextxy(x, y, _T("6")); settextcolor(0xAFFFFA); break;

case 6:  outtextxy(x, y, _T("7")); settextcolor(0x9FFFF9); break;

case 7:  outtextxy(x, y, _T("8")); settextcolor(0x8FFFF8); break;

case 8:  outtextxy(x, y, _T("9")); settextcolor(0x7FFFF7); break;

case 9: outtextxy(x, y, _T(" ")); break;

}

}

int shubiao(int *m_x,int*m_y)

{

int number=0;

MOUSEMSG m;// 定义鼠标消息

int xx = 1;

while (xx)

{

// 获取一条鼠标消息

m = GetMouseMsg();

setlinecolor(RED);

switch (m.uMsg)

{

//case WM_MOUSEMOVE:

//// 鼠标移动的时候画红色的小点

//putpixel(m.x, m.y, RED);

//break;


case WM_LBUTTONDOWN:

if (m.x >= 48 && m.x <= 444 && m.y >= 695 && m.y <= 739)

{

if (number > 0)

{

setlinecolor(YELLOW);

switch (number-1)

{

case 0:rectangle(48, 695, 92, 739);  break;

case 1: rectangle(48 + 44, 695, 92 + 44, 739); ; break;

case 2:rectangle(48 + 44 * 2, 695, 92 + 44 * 2, 739);  break;

case 3:rectangle(48 + 44 * 3, 695, 92 + 44 * 3, 739);   break;

case 4:rectangle(48 + 44 * 4, 695, 92 + 44 * 4, 739);   break;

case 5:rectangle(48 + 44 * 5, 695, 92 + 44 * 5, 739);   break;

case 6:rectangle(48 + 44 * 6, 695, 92 + 44 * 6, 739);   break;

case 7:rectangle(48 + 44 * 7, 695, 92 + 44 * 7, 739);   break;

case 8:rectangle(48 + 44 * 8, 695, 92 + 44 * 8, 739);  break;

}


}

setlinecolor(RED);

switch (int((m.x - 48.0) / 44))

{

case 0:rectangle(48, 695, 92, 739);   number = 1;  break;

case 1: rectangle(48 + 44, 695, 92 + 44, 739); number = 2; break;

case 2:rectangle(48 + 44 * 2, 695, 92 + 44 * 2, 739); number = 3; break;

case 3:rectangle(48 + 44 * 3, 695, 92 + 44 * 3, 739); number = 4; break;

case 4:rectangle(48 + 44 * 4, 695, 92 + 44 * 4, 739); number = 5; break;

case 5:rectangle(48 + 44 * 5, 695, 92 + 44 * 5, 739); number = 6; break;

case 6:rectangle(48 + 44 * 6, 695, 92 + 44 * 6, 739); number = 7; break;

case 7:rectangle(48 + 44 * 7, 695, 92 + 44 * 7, 739); number = 8; break;

case 8:rectangle(48 + 44 * 8, 695, 92 + 44 * 8, 739); number = 9; break;

}  } 

if (/*number > 0 &&*/ m.x >= 48 && m.x <= 552 && m.y >= 120 && m.y <= 624)

{

setlinecolor(YELLOW);

switch (number - 1)

{

case 0:rectangle(48, 695, 92, 739);  break;

case 1: rectangle(48 + 44, 695, 92 + 44, 739);; break;

case 2:rectangle(48 + 44 * 2, 695, 92 + 44 * 2, 739);  break;

case 3:rectangle(48 + 44 * 3, 695, 92 + 44 * 3, 739);   break;

case 4:rectangle(48 + 44 * 4, 695, 92 + 44 * 4, 739);   break;

case 5:rectangle(48 + 44 * 5, 695, 92 + 44 * 5, 739);   break;

case 6:rectangle(48 + 44 * 6, 695, 92 + 44 * 6, 739);   break;

case 7:rectangle(48 + 44 * 7, 695, 92 + 44 * 7, 739);   break;

case 8:rectangle(48 + 44 * 8, 695, 92 + 44 * 8, 739);  break;

}

xx = 0;

*m_x = m.x;

*m_y = m.y;


}

if (m.x >= 456 && m.x <= 552 && m.y >= 684 && m.y <= 740)

{

setlinecolor(RED);

rectangle(456, 684, 552, 740);

break;

}

if (m.x>=556&&m.x<=600&&m.y>=0&&m.y<=44)

{

setfillcolor(YELLOW);

setlinecolor(YELLOW);

tishifu();

setfillcolor(RED);

setlinecolor(RED);

break;

}


case WM_LBUTTONUP://左键抬起

if (m.x >= 456 && m.x <= 552 && m.y >= 684 && m.y <= 740)

{

  setlinecolor(YELLOW);

  rectangle(456, 684, 552, 740);

  number = 11;

  return number;

}

if (m.x >= 556 && m.x <= 600 && m.y >= 0 && m.y <= 44)

{

tishifu();

MessageBox(NULL, wPROGRAMINFO, _T("关于"), MB_OK | MB_ICONASTERISK);

}


}

}


return number;

}

void chuti(int n, int x, int y)

{

int myx, myy;

myx = ((x - 48) / 56) * 56 + 48+15;

myy = ((y - 120) / 56) * 56 + 120+2;

settextstyle(52, 0, _T("宋体"));

setbkmode(OPAQUE);

OUTTEXT(myx, myy, n-1);

setbkmode(TRANSPARENT);

}

void chucun(int n, int x, int y)

{

int mx, my;

mx = (x - 48) / 56;

my = (y - 120) / 56;

juzheng[mx][my] = n;

}

int panduan()

{

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] = juzheng[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 0;

}

}

}

}

}}//行的判断;

{for (int i = 0; i < 9; i++)

for (int j = 0; j < 9; j++)

{

b[j] = juzheng[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 0;

}

}

}

}

}}//列的判断;

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] = juzheng[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 0;

}

}

}

}

ns = 0;

}

};

return 1;

}

void qinping()

{

settextstyle(52, 0, _T("宋体"));

setbkmode(OPAQUE);

for (int i = 0; i < 9;i++)

for (int j = 0; j < 9; j++)

{

outtextxy(j * 56 + 48 + 15, i * 56 + 120 + 2, _T(" "));

juzheng[i][j] = 0;

xinjuzheng[i][j] = 0;

}


}

void tianshu(int i, int j, int n)

{

int myx, myy;

myx = i * 56 + 48 + 15;

myy = j * 56 + 120 + 2;

settextstyle(52, 0, _T("宋体"));

setbkmode(OPAQUE);

OUTTEXT(myx, myy, n - 1);

setbkmode(TRANSPARENT);

}

//void chubufengxi()

//{

//while (true)//对矩阵中的数组进行循环判断,找出有唯一解的填入,直至矩阵中没有唯一解,跳出循环

//{

//int OK = 0;

//{for (int i = 0; i < 9; i++)

//for (int j = 0; j < 9; j++)

//{

//xinjuzheng[j][i] = juzheng[j][i];//先将以前的矩阵储存到新的矩阵中

//}};

//for (int i = 0; i < 9; i++)

//{

//for (int j = 0; j < 9; j++)//每找到一数值;就结束循环;重新判断;直到找不到任何一个值;结束大循环;

//{

//int shiyan = 9, bj = 0, shuju = 0;

//if (juzheng[j][i] == 0)

//{

//

//while (shiyan){

//juzheng[j][i] = shiyan;

//tianshu(j, i, shiyan);

//Sleep(10);

//tianshu(j, i, 10);

//

//if (panduan() == 1)

//{

//bj++;

//

//shuju = shiyan;

//shiyan--;

//

//}

//else

//shiyan--;

//

//}

//juzheng[j][i] = 0;

//

//}

//if (bj == 1)

//{

//juzheng[j][i] = shuju;

//tianshu(j, i, shuju);

//OK = 2;

//break;

//}

//

//

//

//if (i == 8 && j == 8)

//{

//OK = 1;

//break;

//}

//

//

//}

//if (OK == 2)

//break;

//

//

//if (OK == 1)

//break;

//}

//if (OK == 1)

//break;

//

//

//}

//}

void xiangxichuli(int x,int y)

{

if (x == 9)

{

if (cishu>0)

MessageBox(NULL, TEXT("您的数独有多解是否查看下一个?"), TEXT("来自数独的提示"), MB_OK);

print();

cishu++;

sum++;

}


if (juzheng[x][y] == 0)

{

for (int j = 1; j <= 9; j++)

{

juzheng[x][y] = j;

if (check(x, y))

{

xiangxichuli(x + (y + 1) / 9, (y + 1) % 9);


}

juzheng[x][y] = 0;

}

}

else

{

xiangxichuli(x + (y + 1) / 9, (y + 1) % 9);

}



}

int check(int x, int y)//检查一行一列中的数,和九宫格中

{

int flag = 1;

for (int i = 0; i<9; i++)

{

if (juzheng[x][i] == juzheng[x][y] && i != y)

{


flag = 0;

}

if (juzheng[i][y] == juzheng[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&&juzheng[i][j] == juzheng[x][y])

{

flag = 0;

}



}

}


return flag;



}

void print()

{

for (int i = 0; i<9; i++)

{

for (int j = 0; j<9; j++)

{

if (juzheng[j][i] == xinjuzheng[j][i])

continue;

for (int n = 1; n <= 9;n++)

if (n <= juzheng[j][i])

{

tianshu(j, i, n);

Sleep(10);

}

else continue;

}


}

}

void tishifu()

{

setlinestyle(PS_SOLID | PS_ENDCAP_FLAT, 2);

circle(578, 22, 21);

setlinestyle(PS_SOLID | PS_ENDCAP_SQUARE, 9);

line(578, 26, 578, 34);

setlinestyle(PS_SOLID | PS_ENDCAP_FLAT, 1);

fillcircle(578, 13, 5);

setlinestyle(PS_SOLID | PS_ENDCAP_SQUARE, 3);

}


C语言解数独(溯回法)