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);
}