#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
}
用0代表要填的数#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=0i<SIZEi++)
{
if(i%3==0)
{
for(j=0j<SIZE*2+4j++)
putchar('-')
putchar('\n')
}
for(j=0j<SIZEj++)
{
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=0i<SIZE*2+4i++)
putchar('-')
putchar('\n')
}
void sub(int i, int j, int bit)
{
int k, m
for(k=0k<SIZEk++)
{
board[k][j].left &= ~bit
board[i][k].left &= ~bit
}
for(k=i/3*3k<(i/3+1)*3k++)
for(m=j/3*3m<(j/3+1)*3m++)
board[k][m].left &= ~bit
}
void init()
{
int i, j
for(i=0i<SIZEi++)
for(j=0j<SIZEj++)
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=0k<SIZEk++)
{
board[k][j].left |= bit
board[i][k].left |= bit
}
for(k=i/3*3k<(i/3+1)*3k++)
for(m=j/3*3m<(j/3+1)*3m++)
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].leftleftleft&=(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=0i<SIZEi++)
for(j=0j<SIZEj++)
{
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
}
一、步骤：
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()
}
