本文目录一览:
- 1、求用C语言编一个解九宫格数独的程序
- 2、数独 算法 C语言 代码
- 3、用c语言写一个简易数独的思路。要代码
- 4、C语言编写一个3*3数独,保证每行每列的和都相等!!求求各位大神了
- 5、用C语言怎么解数独
求用C语言编一个解九宫格数独的程序
前两天刚写完,还没优化,已运行通过了.
晕,一维的好麻烦,这个也是碰巧前两天刚写好的,你看着自己修改下
#include stdio.h
typedef struct
{
int line;
int row;
int num;
}Node;
int main()
{
/*
int a[9][9]={
{4,0,3,6,0,0,0,0,0},
{0,0,0,0,0,1,0,2,4},
{0,1,0,0,4,0,5,0,0},
{0,0,0,9,0,4,0,6,0},
{3,0,2,0,0,0,4,0,9},
{0,7,4,1,0,3,0,0,0},
{0,0,1,0,9,0,0,4,0},
{2,4,0,3,0,0,0,0,0},
{0,0,0,4,0,8,2,0,7}};
*/
int a[9][9]={
{0,0,0,8,0,0,0,6,0},
{8,7,0,0,0,0,0,0,0},
{2,9,0,0,4,1,0,0,5},
{0,0,5,7,0,0,0,0,9},
{0,2,0,0,0,0,0,1,0},
{9,0,0,0,0,4,3,0,0},
{7,0,0,6,1,0,0,9,8},
{0,0,0,0,0,0,0,5,2},
{0,6,0,0,0,9,0,0,0}};
/*
int a[9][9]={
{0,2,0,0,6,0,0,0,0},
{0,9,0,4,0,5,1,3,0},
{0,0,8,7,0,0,0,0,5},
{6,0,0,3,0,0,4,0,0},
{0,0,0,9,0,6,0,0,0},
{0,0,7,0,0,1,0,0,3},
{4,0,0,0,0,7,3,0,0},
{0,8,5,2,0,4,0,7,0},
{0,0,0,0,9,0,0,1,0}};
*/
/*
int a[9][9]={
{0,0,3,0,2,0,0,0,6},
{0,0,2,0,9,0,0,0,4},
{7,0,0,8,0,0,2,0,3},
{0,8,0,0,7,0,5,0,0},
{0,7,0,1,0,6,0,3,0},
{0,0,0,2,0,0,0,9,0},
{4,0,6,0,0,8,0,0,5},
{6,0,0,0,4,0,3,0,0},
{9,0,0,0,1,0,7,0,0}};
*/
int i,j,n,en,flag,y,k=0,x,qu,p,q;
Node b[70];
for(i=0;i9;i++)
{
for(j=0;j9;j++)
{
if(!a[i][j])
{
b[k].line=i;
b[k].row=j;
b[k].num=0;
k+=1;
}
}
}
en=k;
/*从b[0]开始试,若b[k].num9,则k-1,否则k+1*/
for(k=0;ken;)
{
++b[k].num;
i=b[k].line;
j=b[k].row;
a[i][j]=b[k].num;
n=0;
while(n9b[k].num=9)
{
if(n==i)
{
for(y=0;y9;y++)
{
if(y==j)
continue;
if(a[n][y]==a[i][j])
flag=1;
}
}
else if(n==j)
{
for(y=0;y9;y++)
{
if(y==i)
continue;
if(a[y][n]==a[i][j])
flag=1;
}
}
/*判断同一块中有没有相同值*/
qu=3*(i/3)+j/3;
switch(qu)
{
case 0:x=0;
y=0;
break;
case 1:x=0;
y=3;
break;
case 2:x=0;
y=6;
break;
case 3:x=3;
y=0;
break;
case 4:x=3;
y=3;
break;
case 5:x=3;
y=6;
break;
case 6:x=6;
y=0;
break;
case 7:x=6;
y=3;
break;
default :x=6;
y=6;
break;
}
p=x;
q=y;
for(;xp+3;x++)
{
for(;yq+3;y++)
{
if(x==iy==j)
continue;
if(a[x][y]==a[i][j])
{
flag=1;
break;
}
}
if(flag==1)
break;
}
if(flag==1)
{
a[i][j]=++b[k].num;
flag=0;
n=0;
continue;
}
n++;
}
if(b[k].num9)
{
a[i][j]=b[k].num=0;
k--;
if(k0)
{
printf("error!\r\n");
return -1;
}
}
else
k++;
}
for(i=0;i9;i++)
{
for(j=0;j9;j++)
{
printf("%d",a[i][j]);
}
printf("\r\n");
}
return 1;
}
数独 算法 C语言 代码
一、步骤:
1.对每一个空格,根据规则推断它可能填入的数字,并存储它的所有可能值;
2.根据可能值的个数,确定填写的顺序。比如说,有些空格只有一种可能,那必然是正确的结果,首先填入。
3.将所有只有一种可能的空格填写完毕以后,回到步骤1,重新确定剩下空格的可能值;
4.当没有只有一种可能的空格时(即每个空格都有两种以上可能),按照可能值个数从小到大的顺序,使用深度(广度)优先搜索,完成剩下空格。
二、例程:
#include windows.h
#include stdio.h
#include time.h
char sd[81];
bool isok = false;
//显示数独
void show()
{
if (isok) puts("求解完成");
else puts("初始化完成");
for (int i = 0; i 81; i++)
{
putchar(sd[i] + '0');
if ((i + 1) % 9 == 0) putchar('\n');
}
putchar('\n');
}
//读取数独
bool Init()
{
FILE *fp = fopen("in.txt", "rb");
if (fp == NULL) return false;
fread(sd, 81, 1, fp);
fclose(fp);
for (int i = 0; i 81; i++)
{
if (sd[i] = '1' sd[i] = '9') sd[i] -= '0';
else sd[i] = 0;
}
show();
return true;
}
//递归解决数独
void force(int k)
{
if (isok) return;
if (!sd[k])
{
for (int m = 1; m = 9; m++)
{
bool mm = true;
for (int n = 0; n 9; n++)
{
if ((m == sd[k/27*27+(k%9/3)*3+n+n/3*6]) || (m == sd[9*n+k%9]) || (m == sd[k/9*9+n]))
{
mm = false;
break;
}
}
if (mm)
{
sd[k] = m;
if (k == 80)
{
isok = true;
show();
return;
}
force(k + 1);
}
}
sd[k] = 0;
}
else
{
if (k == 80)
{
isok = true;
show();
return;
}
force(k + 1);
}
}
int main()
{
system("CLS");
if (Init())
{
double start = clock();
force(0);
printf("耗时%.0fms", clock() - start);
}
else puts("初始化错误");
getchar();
}
用c语言写一个简易数独的思路。要代码
#includestdio.h
int num[9][9], xy[9][9];
int check(int x, int y) {
int i, m, n;
for(i = 0; i 9; i++)
if ((xy[x][y] == xy[i][y]i != x)||(xy[x][y] == xy[x][i]i != y))
return 0;
for(i = 0, m = x / 3 * 3, n = y / 3 * 3; i 9; i++)
if (xy[x][y] == xy[m + i / 3][n + i % 3]m + i / 3 != xn + i % 3 != y)
return 0;
return 1;
}
void search(int x, int y) {
if (x == 9)
for(x = 0; x 9; x++) {
for(y = 0; y 9; y++)
printf("%d ", xy[x][y]);
printf("\n");
}
else if (num[x][y])
search(x + (y + 1) / 9, (y + 1) % 9);
else
for(xy[x][y] = 1; xy[x][y] = 9; xy[x][y]++)
if (check(x, y))
search(x + (y + 1) / 9, (y + 1) % 9);
return;
}
int main() {
int i, j;
for(i = 0; i 9; i++)
for(j = 0; j 9; j++) {
scanf("%d", num[i][j]);
xy[i][j] = num[i][j];
}
search(0, 0);
return 0;
}
输入为9行9列整数,已知的整数填写对应的数字,尚待计算的未知数字填写0。
该代码的思路很简单,就是从第一行第一列开始依次填入数字,检查是否是在同一行、同一列、同一宫有没有填入重复数字,如果没有就继续填入下一个数字,如果有就返回。
虽然效率稍低,但原理简单、表述直白、易于理解,更有效率的代码是使用十字链表完成,如有兴趣可继续深入
C语言编写一个3*3数独,保证每行每列的和都相等!!求求各位大神了
/*
因为你说是数独 可是你只表述了行列相等,如果是数独应该对角线相加也相等,所以我写了两个判断函数,judge1为对角线也相等的情况,judge为你描述的行列和相等(情况太多了)
结题方案只需要做一次dfs就可以了,还需要配合一个栈来存储dfs的路径,将每个符合条件的路径做一次行列和是否相等的判断 然后输出就是要的结果!
*/
#includestdio.h
#includememory.h
#includestdbool.h
//stack
int a[9]={0};//a[0]--a[0][0] a[1]--a[0][1] and so on simulate stack
int len=0;
//dfs
int visited[10]={0};
bool judge()//行列相等
{
int i,j;
int tmp[6]={0};
for(i=0;i3;i++)
for(j=0;j3;j++)
tmp[i]+=a[3*i+j];
for(i=0;i3;i++)
for(j=0;j3;j++)
tmp[3+i]+=a[i+3*j];
int jud=tmp[0];
for(i=1;i6;i++)
{
if(jud!=tmp[i])
return false;
}
return true;
}
bool judge1()//行列相等 对角线也相等
{
int i,j;
int tmp[8]={0};
for(i=0;i3;i++)
for(j=0;j3;j++)
tmp[i]+=a[3*i+j];
for(i=0;i3;i++)
for(j=0;j3;j++)
tmp[3+i]+=a[i+3*j];
tmp[7]=a[0]+a[4]+a[8];
tmp[6]=a[2]+a[4]+a[6];
int jud=tmp[0];
for(i=1;i8;i++)
{
if(jud!=tmp[i])
return false;
}
return true;
}
void printa()
{
int t,p;
for(t=0;t3;t++)
{
for(p=0;p3;p++)
{
printf("%d ",a[3*t+p]);
}
printf("\n");
}
}
void dfs(int i,int v[])
{
if(i==10)//find one solution
{
if(judge1())//给你写了两个判断函数 如果对角线也相等那么用judge1()即可判断
printa();
return;
}
int j;
for(j=1;j=9;j++)
{
int tmp[10];
memcpy(tmp,v,10*sizeof(int));
if(tmp[j]==0)
{
tmp[j]=1;
a[len++]=j;
//printf("%d %d\n",len-1,a[len-1]);
dfs(i+1,tmp);
len--;
}
}
}
int main(void)
{
dfs(1,visited);
return 0;
}
用C语言怎么解数独
#include stdio.h
#include stdlib.h
#define SIZE 9
#define get_low_bit(x) ((~x(x-1))+1)
struct{
int left;
char num;
char try;
}board[SIZE][SIZE];
int bit2num(int bit)
{
switch(bit){
case 1:case 2:
return bit;
case 4:
return 3;
case 8:
return 4;
case 16:
return 5;
case 32:
return 6;
case 64:
return 7;
case 128:
return 8;
case 256:
return 9;
}
}
void printf_res()
{
int i, j, k;
for(i=0; iSIZE; i++)
{
if(i%3==0)
{
for(j=0; jSIZE*2+4; j++)
putchar('-');
putchar('\n');
}
for(j=0; jSIZE; j++)
{
if(j%3==0)
putchar('|');
if(board[i][j].num 0)
printf("\033[0;31m%2d\033[0m", board[i][j].num);
else
printf("%2d", board[i][j].try);
}
printf("|\n");
}
for(i=0; iSIZE*2+4; i++)
putchar('-');
putchar('\n');
}
void sub(int i, int j, int bit)
{
int k, m;
for(k=0; kSIZE; k++)
{
board[k][j].left = ~bit;
board[i][k].left = ~bit;
}
for(k=i/3*3; k(i/3+1)*3; k++)
for(m=j/3*3; m(j/3+1)*3; m++)
board[k][m].left = ~bit;
}
void init()
{
int i, j;
for(i=0; iSIZE; i++)
for(j=0; jSIZE; j++)
if(board[i][j].num 0)
sub(i, j, 1(board[i][j].num-1));
else if(board[i][j].try 0)
sub(i, j, 1(board[i][j].try-1));
}
void add(int i, int j, int bit)
{
int k, m;
for(k=0; kSIZE; k++)
{
board[k][j].left |= bit;
board[i][k].left |= bit;
}
for(k=i/3*3; k(i/3+1)*3; k++)
for(m=j/3*3; m(j/3+1)*3; m++)
board[k][m].left |= bit;
}
void solve(int pos)
{
int i=pos/SIZE;
int j=pos%SIZE;
int bit, left;
if(pos == SIZE*SIZE)
{
printf_res();
exit(0);
}
if(board[i][j].num 0)
solve(pos+1);
else
for(left=board[i][j].left; left; left=(left-1))
{
bit = get_low_bit(left);
sub(i, j, bit);
board[i][j].try = bit2num(bit);
solve(pos+1);
add(i, j, bit);
board[i][j].try=0;
init();
}
}
int main()
{
int i, j, c;
for(i=0; iSIZE; i++)
for(j=0; jSIZE; j++)
{
while((c=getchar())'0' || c'9')
;
board[i][j].num = c-'0';
board[i][j].try = 0;
board[i][j].left = 0x0001FF;
}
init();
solve(0);
return 0;
}