#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 i<SIZE i++)
{
if(i%3==0)
{
for(j=0 j<SIZE*2+4 j++)
putchar('-')
putchar('\n')
}
for(j=0 j<SIZE j++)
{
if(j%3==0)
putchar('|')
if(board[i][j].num > 0)
printf("\033[031m%2d\033[0m", board[i][j].num)
else
printf("%2d", board[i][j].try)
}
printf("|\n")
}
for(i=0 i<SIZE*2+4 i++)
putchar('-')
putchar('\n')
}
void sub(int i, int j, int bit)
{
int k, m
for(k=0 k<SIZE 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 i<SIZE i++)
for(j=0 j<SIZE 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 k<SIZE 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 i<SIZE i++)
for(j=0 j<SIZE 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
}
#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 = 0i <81i++)
{
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 = 0i <81i++)
{
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 = 1m <= 9m++)
{
bool mm = true
for (int n = 0n <9n++)
{
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()
}
前两天刚写完,还没优化,已运行通过了.晕，一维的好麻烦，这个也是碰巧前两天刚写好的，你看着自喊搭举己修改枝陵下
#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=0i<9i++)
{
for(j=0j<9j++)
{
if(!a[i][j])
{
b[k].line=i
b[k].row=j
b[k].num=0
k+=1
}
}
}
en=k
/*从b[0]开始试，若b[k].num>9,则k-1,否则k+1*/
for(k=0k<en)
{
++b[k].num
i=b[k].line
j=b[k].row
a[i][j]=b[k].num
n=0
while(n<9&&b[k].num<=9)
{
if(n==i)
{
for(y=0y<9y++)
{
if(y==j)
continue
if(a[n][y]==a[i][j])
flag=1
}
}
else if(n==j)
{
for(y=0y<9y++)
{
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(x<p+3x++)
{
for(y<q+3y++)
{
if(x==i&&y==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].num>9)
{
a[i][j]=b[k].num=0
k--
if(k<0)
{
printf("error!\r\n")
return -1
}
}
else
k++
}
for(i=0i<9i++)
{
for(j=0j<9j++)
{
printf("%d",a[i][j])
}
printf("\r\n")
}
return 1
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）