文档库 最新最全的文档下载
当前位置:文档库 › 独数运算

独数运算

// temp.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include
#include
#include
#include

//独数解析
#define X_B 0 //横向开始
#define Y_B 0 //纵向开始
#define X_E 8 //横向结束
#define Y_E 8 //纵向结束
#define D_B 1 //数据开始
#define D_E 9 //数据结束
#define I_S 3 //单元大小
#define D_S 9 //数据大小

int nStep = 0;
bool bShowStep = true;

char sMsg[300] = {0};
int nData[D_S][D_S] = {
{8,0,0,0,0,0,0,0,0},
{0,0,3,6,0,0,0,0,0},
{0,7,0,0,9,0,2,0,0},
{0,5,0,0,0,7,0,0,0},
{0,0,0,0,4,5,7,0,0},
{0,0,0,1,0,0,0,3,0},
{0,0,1,0,0,0,0,6,8},
{0,0,8,5,0,0,0,1,0},
{0,9,0,0,0,0,4,0,0}
}; //数据存储
int nValue[D_S][D_S] = {
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0}
}; //测试数据值

void showData(int nData[D_S][D_S])
{
memset(sMsg, 0, 300);

char ss[5] = {0};
for (int i = X_B; i <= X_E; i++)
{
for (int j = Y_B; j <= Y_E; j++)
{
sprintf(ss, "%d,", nData[i][j]);
strcat(sMsg, ss);
}

sMsg[strlen(sMsg) - 1] = 0;
strcat(sMsg, "\r\n");
}

strcat(sMsg, "\r\n");
printf(sMsg);
}

bool checkItemNum(int n, int x, int y, int nData[D_S][D_S])
{
//sprintf(sMsg, "check:%d(%d-%d)\r\n", n, x, y);
//printf(sMsg);

int i = 0;
int j = 0;

for (i = (x / I_S) * I_S; i < ((x / I_S) + 1) * I_S; i++)
{
for (j = (y / I_S) * I_S; j < ((y / I_S) + 1) * I_S; j++)
{
if (i != x && j != y && n == nData[i][j])
{
return false;
}
}
}

for (i = Y_B; i <= Y_E; i++)
{
if (i != y && n == nData[x][i])
{
return false;
}
}

for (j = X_B; j <= X_E; j++)
{
if (j != x && n == nData[j][y])
{
return false;
}
}

//sprintf(sMsg, "check:%d(%d-%d) true\r\n", n, x, y);
//printf(sMsg);

return true;
}

bool tryItemData(int x, int y, int xx, int yy, int nData[D_S][D_S])
{
nStep++;
if (x < X_B || x >= xx || y < Y_B || y > yy)
{
return true;
}

int n = 0;

if (nData[x][y] == 0)
{
for (n = D_B; n <= D_E; n++)
{
if (checkItemNum(n, x, y, nData))
{
nData[x][y] = n;

if (bShowStep)
{
sprintf(sMsg, "第%d步: %d(%d:%d)-----\r\n", nStep, n, x, y);
printf(sMsg);
showData(nData);
//getchar();
}

if (tryItemData(x, y, xx, yy, nData))
{
return true;
}

nData[x][y] = 0;
}
}

return n < D_E;
}
else if (x >= xx)
{
return tryItemData(X_B, y + 1, xx, yy, nData);
}
else if (y >= yy)
{
return tryItemData(x + 1, Y_B, xx, yy, nData);
}
else
{
return tryItemData(x, y + 1, xx, yy, nData);
}
}

bool findTryItem(int* x, int* y, int nData[D_S][D_S])
{
int i = 0;
int j = 0;

for (i = X_

B; i <= X_E; i++)
{
for (j = Y_B; j <= Y_E; j++)
{
if (nData[i][j] == 0)
{
*x = i;
*y = j;
return true;
}
}
}

return false;
}

bool findLastTryItem(int* x, int* y, int nValue[D_S][D_S])
{
int i = *x;
int j = *y;

for (; i >= X_B; i--)
{
for (; j >= Y_B; j--)
{
if (nValue[i][j] > 0)
{
*x = i;
*y = j;
return true;
}
}

j = Y_E;
}

return false;
}

bool tryItemValue(int n, int x, int y, int nData[D_S][D_S])
{
nStep++;

int i = 0;

for (i = n; i <= D_E; i++)
{
if (checkItemNum(i, x, y, nData))
{
nData[x][y] = i;

if (bShowStep)
{
sprintf(sMsg, "第%d步:%d(%d:%d)-----\r\n", nStep, i, x, y);
printf(sMsg);
showData(nData);
//getchar();
}

return true;
}
}

nData[x][y] = 0;

return false;
}

int ttt = 0;
bool tryAllData(int nData[D_S][D_S])
{
if (ttt)
{
int x = 0;
int y = 0;
bool b = true;

do
{
if (findTryItem(&x, &y, nData))
{
nValue[x][y]++;
if (!tryItemValue(nValue[x][y], x, y, nData))
{
nValue[x][y] = 0;
if (findLastTryItem(&x, &y, nValue))
{
nData[x][y] = 0;
}
else
{
b = false;
break;
}
}
}
else
{
break;
}
} while (true);

return b;
}
else
{
return tryItemData(X_B, Y_B, X_E, Y_E, nData) && tryItemData(X_E, Y_B, X_E + 1, Y_E, nData);
}
}

void jsDs()
{
printf("是否演示测试最难独数(芬兰数学家)(1:是;0:否)?");
if (getchar() == '1')
{
getchar();

nStep = 0;
printf("演算过程比较费时间,是否带演算过程(1:是;0:否)?");
bShowStep = (getchar() == '1');

getchar();
showData(nData);
printf("按任意键开始...");
getchar();
clock_t nStart = clock();
bool b = tryAllData(nData);

printf("共计%d步,共计用时: %d (ms)\r\n\r\n", nStep, (clock() - nStart));
if (b)
{
printf("计算结束,结果为:\r\n");
showData(nData);
}
else
{
printf("计算失败,可能没有正确答案!\r\n");
}

getchar();
}

do
{
do
{
system("cls");

nStep = 0;
printf("演算过程比较费时间,是否带演算过程(1:是;0:否)?");
bShowStep = (getchar() == '1');

getchar();
printf("请输入初始化值(整行输入,要填入数字用0代替):\r\n");
for (int i = 0; i < D_S; i++)
{
scanf("%d,%d,%d,%d,%d,%d,%d,%d,%d", &nData[i][0], &nData[i][1], &nData[i][2], &nData[i][3], &nData[i][4], &nData[i][5], &nData[i][6], &nData[i][7], &nData[i][8]);
}

printf("--------------------\r\n");
showData(nData);
printf("输入是否正确(1:正确;0错误)?");
getchar();
if (getchar() == '1')
{
break;
}
} while (true);

showData(nData);
printf("开始计算,请等待...\r\n");

clock_t nStart = clock();
bool b = tryAllData(nData);

p

rintf("共计%d步,共计用时: %d (ms)\r\n\r\n", nStep, (clock() - nStart));
if (b)
{
printf("计算结束,结果为:\r\n");
showData(nData);
}
else
{
printf("计算失败,可能没有正确答案!\r\n");
}

printf("是否继续计算(1:是;0:否)?");
getchar();
if (getchar() == '0')
{
break;
}
} while (true);
}

int main(int argc, char* argv[])
{
jsDs();
return 0;
}

相关文档
相关文档 最新文档