C语言数独求解
#include
/*数字0表示该位置为空，待填入数字
{0,0,4,6,0,2,0,9,1},
{2,1,0,9,8,4,0,5,6},
{9,0,0,0,7,1,4,2,0},
{1,2,5,0,6,0,3,4,7},
{4,7,6,0,0,0,9,8,5},
{8,3,9,0,4,0,1,6,2},
{0,9,1,2,5,0,0,0,4},
{5,8,0,4,1,6,0,3,9},
{6,4,0,3,0,7,5,0,0}};
*/
int data[9][9] = {
{0,7,0,2,6,0,9,0,0},
{3,0,0,0,0,8,0,0,7},
{0,9,0,0,5,7,0,0,0},
{5,0,0,0,0,0,0,7,0},
{0,4,7,3,1,2,8,5,0},
{0,8,0,0,0,0,0,0,1},
{0,0,0,8,2,0,0,4,0},
{7,0,0,6,0,0,0,0,2},
{0,0,4,0,3,9,0,8,0}};
void input()
{
int i,j;
for(i = 0;i 9;i++)
for(j = 0;j 9;j++)
scanf(“%d”,data[i][j]);
}
void output()
{
int i,j;
for(i = 0;i 9;i++)
{
for(j = 0;j 9;j++)
printf(“%d “,data[i][j]);
printf(“\n”);
}
printf(“\n”);
}
/*检查num是否可放置在3*3区域是否有冲突*/
int CheckSquare(int line,int col,int num)
{
int i = (line / 3) * 3;
int j = (col / 3) * 3;
int m,n;
for(m = i;m i + 3;m++)
for(n = j;n j + 3;n++)
if((data[m][n] == num) !(m == line n == col))
return 0;
return 1;
}
/*检查行冲突*/
int CheckLine(int line,int col,int num)
{
int i = 9;
while(i–)
if((data[line][i] == num) (i != col))
return 0;
return 1;
}
/*检查列冲突*/
int CheckColumn(int line,int col,int num)
{
int i = 9;
while(i–)
if((data[i][col] == num) (i != line))
return 0;
return 1;
}
/*检查i行j列是否可放置num*/
int Check(int i,int j,int num)
{
return CheckSquare(i,j,num) CheckLine(i,j,num) CheckColumn(i,j,num);
}
/*检查是否完成*/
int IsDone()
{
int i,j;
for(i = 0;i 9;i++)
for(j = 0;j 9;j++)
if(!Check(i,j,data[i][j]) || (data[i][j] == 0))
return 0;
return 1;
}
void Calc()
{
int i,j,x;
if(IsDone())
{
output();
return;
}
for(i = 0;i 9;i++)
{
for(j = 0;j 9;j++)
{
if(data[i][j] == 0)
{
for(x = 1; x = 9;x++)
{
if(Check(i,j,x))
{
data[i][j] = x;
Calc();
}
}
if(x == 10)
{
data[i][j] = 0;
return ;
}
}
}
}
}
int main()
{
// input();
Calc();
output();
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;
}
求解数独题，用C语言实现
回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
#includestdio.h
int map[9][9];
bool isPlace(int count){
int row = count #47; 9;
int col = count % 9;
int j;
#47;#47;同一行
for(j = 0; j 9; ++j){
if(map[row][j] == map[row][col] j != col){
return false;
}
}
#47;#47;同一列
for(j = 0; j 9; ++j){
if(map[j][col] == map[row][col] j != row){
return false;
}
}
#47;#47;同一小格
int tempRow = row #47; 3 * 3;
int tempCol = col #47; 3 * 3;
for(j = tempRow; j tempRow + 3;++j){
for(int k = tempCol; k tempCol + 3; ++k){
if(map[j][k] == map[row][col] j != row k != col){
return false;
}
}
}
return true;
}
void backtrace(int count){
if(count == 81){
for(int i = 0; i 9; ++i){
for(int j = 0; j 9; ++j){
printf(“%d “,map[i][j]);
}
printf(“#92;n”);
}
return;
}
int row = count #47; 9;
int col = count % 9;
if(map[row][col] == 0){
for(int i = 1; i = 9; ++i){
map[row][col] = i;#47;#47;赋值
if(isPlace(count)){#47;#47;可以放
backtrace(count+1);#47;#47;进入下一层
}
}
map[row][col] = 0;#47;#47;回溯
}else{
backtrace(count+1);
}
}
int main()
{
char c;
for(int i=0;i9;i++)
{
for(int j=0;j9;j++)
{
scanf(“%c”,c);
if(c==’.’)map[i][j]=0;
else map[i][j]=c-‘0’;
}
scanf(“%c”,c);#47;#47;接收换行符
}
backtrace(0);
return 0;
}
基于SAT的数独游戏求解程序，求C语言代码
用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 16:
case 256:
return 9;
基础解法
排除法（摒除法）
摒除法：用数字去找单元内唯一可填空格，称为摒除法，数字可填唯一空格称为排除法 (Hidden Single)。
根据不同的作用范围，摒余解可分为下述三种：
数字可填唯一空格在「宫」单元称为宫排除（Hidden Single in Box），也称宫摒除法。
数字可填唯一空格在「行」单元称为行排除法（Hidden Single in Row），也称行摒除法。
急！C语言递归解数独
我从网上随便找个一个帮你改了改。首先把你要解的数独放入一个文件sudo_input里，和你编译后的exe文件在同一目录。内容为：
1 0 0 0
0 0 0 2
0 0 4 0
0 3 0 0
代码如下（备注：基本上这个也可以做9路甚至更多的，只需改动LENGTH和SUBLEN值即可）：
#include stdlib.h
#include stdio.h
#define LENGTH 4
#define SUBLEN 2
int answer = 0;
void printSudo(int array[][LENGTH]) {
printf(“\n\n”);
int i, j;
for (i = 0; i LENGTH; i++) {
if ((i + 1) % SUBLEN == 0)
printf(“\n\n”);
for (j = 0; j LENGTH; j++) {
if ((j + 1) % SUBLEN == 0)
printf(“\t”);
printf(“%d “, array[i][j]);
}
printf(“\n”);
}
exit(0);
}
void initSudoArray(int array[][LENGTH]) {
int i, j;
FILE *fp;
if ((fp = fopen(“sudo_input”, “r”)) == NULL) {
printf(“File open failed !\n”);
exit(-1);
}
for (i = 0; i LENGTH; i++) {
for (j = 0; j LENGTH; j++) {
fscanf(fp, “%d”, array[i][j]);
}
}
fclose(fp);
}
int checkSudo(int array[][LENGTH], int i, int j, int testVal) {
int row, col;
printf(“checkSudo for [%d][%d] testVal = %d\n”, i, j, testVal);
// fixed to col j, check for the rows
for (row = 0; row LENGTH; row++) {
printf(“check for rows! [%d][%d] = %d\n”, row, j, array[row][j]);
if (array[row][j] == testVal)
return 0;
}
// fixed to row i, check for cols
for (col = 0; col LENGTH; col++) {
printf(“check for cols! [%d][%d] = %d\n”, i, col, array[i][col]);
if (array[i][col] == testVal)
return 0;
}
//check for the sub-square
int row_subSquare = (i / SUBLEN) * SUBLEN;
int col_subSquare = (j / SUBLEN) * SUBLEN;
printf(“[%d][%d]\n”, row, col);
for (row = row_subSquare; row row_subSquare + SUBLEN; row++) {
for (col = col_subSquare; col col_subSquare + SUBLEN; col++) {
printf(“check for sub-square! [%d][%d] = %d\n”, row, col, array[row][col]);
if (array[row][col] == testVal)
return 0;
}
}
return 1;
}
// length is the plane index of the sudo array
void sudo_solve(int array[][LENGTH], int length) {
// i for rows, j for cols
int i, j;
int testVal;
int tempArray[LENGTH][LENGTH];
//dump the array to tempArray
for (i = 0; i LENGTH; i++) {
for (j = 0; j LENGTH; j++)
tempArray[i][j] = array[i][j];
}
i = length / LENGTH;
j = length % LENGTH;
printf(“array[%d][%d] = %d”, i, j, array[i][j]);
if (array[i][j] != 0) {
// there is a val in the slot array[i][j]
if (length == 80)
printSudo(tempArray);
else
sudo_solve(tempArray, length + 1);
} else {
// there is no val in the slot array[i][j]
for (testVal = 1; testVal = LENGTH; testVal++) {
if (checkSudo(tempArray, i, j, testVal) != 0) {
tempArray[i][j] = testVal;
if (length == LENGTH * LENGTH – 1)
printSudo(tempArray);
else
sudo_solve(tempArray, length + 1);
tempArray[i][j] = 0;
}
}
}
}
int main(void) {
int array[LENGTH][LENGTH];
initSudoArray(array);
sudo_solve(array, 0);
if (answer == 0)
printf(“There is no answer for this sudo!”);
return 0;
}
数独 算法 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();
}
微信扫一扫 
支付宝扫一扫 
