求解数独题，用C语言实现
6.78..4..
.2.1.7.5.
..4...28.
....3....
.19...3..
.7.4.1.9.
..8..36.7
.5.......
点号表示需要求解的数字。
答案是
581346972
697825431
423197856
734619285
865234719
219578364
372461598
148953627
956782143
求大神用C 语言实现解题。 展开
回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
#include<stdio.h>
int map[9][9];
bool isPlace(int count){
int row = count / 9;
int col = count % 9;
int j;
//同一行
for(j = 0; j < 9; ++j){
if(map[row][j] == map[row][col] && j != col){
return false;
}
}
//同一列
for(j = 0; j < 9; ++j){
if(map[j][col] == map[row][col] && j != row){
return false;
}
}
//同一小格
int tempRow = row / 3 * 3;
int tempCol = col / 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("\n");
}
return;
}
int row = count / 9;
int col = count % 9;
if(map[row][col] == 0){
for(int i = 1; i <= 9; ++i){
map[row][col] = i;//赋值
if(isPlace(count)){//可以放
backtrace(count+1);//进入下一层
}
}
map[row][col] = 0;//回溯
}else{
backtrace(count+1);
}
}
int main()
{
char c;
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
scanf("%c",&c);
if(c=='.')map[i][j]=0;
else map[i][j]=c-'0';
}
scanf("%c",&c);//接收换行符
}
backtrace(0);
return 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=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[0;31m%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;
}
这个怎么觉得没有什么规则呢？你最好再用些语言说明一下。
|
广告 您可能关注的内容 |
