数独游戏的一种解法

最近在北京青年报偶然看到了一个数独游戏的题，具体来说就是按规矩进行填书。自己想了想，觉得还是有点费脑子的。于是就编写了一个程序，可以搜索数独游戏的所有答案。算法很简单，就是使用了回溯+剪枝，效率可能不是很高。不过对于9*9规模不是很大的问题，也应该足够了，不知道大家有什么好的算法，千万别忘了留言告诉我啊，哈哈

数独游戏：

　　版权所有



　　数独的游戏规则：1.在9×9的大九宫格内，已给定若干数字，其他宫位留白，玩家需要自己按照逻辑推敲出剩下的空格里是什么数字。2.每一行与每一列都有1到9的数字，每个小九宫格里也有1到9的数字，并且一个数字在每行、每列及每个小九宫格里只能出现一次。3.每个数独游戏都可根据给定的数字为线索，推算解答出来。

　　短信参与说明：题中有一个待填数字用“★”标示，请将此数字作为答案按要求发送

更多请参见：http://bjyouth.ynet.com/article.jsp?oid=

// shuduyouxi.cpp : Defines the entry point for the console application.

//



#include "stdafx.h"



#include<string.h>

//#include <vfw.h>

//#include <mmsystem.h>

#include <windows.h>

int a[9][9] ;

int b[9] ;

int total ;



void print()

{

printf("\n");

for(int i = 0;i < 9;i++)

{

for(int j = 0;j < 9;j++)

{

printf("%d ",a[i][j]);

}

printf("\n");

}

printf("\n");

}



//判断x,y所在的小九宫是否已经出现了数字n

bool IsInRect(int x,int y,int n)

{

int k,j;

bool retval = false;

for(k = x;k<x+3;k++)

{

for(j = y;j<y+3;j++)

{

if(a[k][j] == n)

{

return true;

}

}

}

return retval;

}







bool satisfy(int x,int y,int n)

{

bool retval = true;



int j;



//行列判断

for(j = 0;j <9;j++)

{

if(a[j][y] == n a[x][j] == n)

{

retval = false;

break;

}

}

//如果行列满足，判断小九宫是否满足

if(retval)

{

if(x <3)

x = 0;

else if(x < 6)

x = 3;

else if(x < 9)

x = 6;

if( y < 3)

y = 0;

else if(y < 6)

y = 3;

else if(y < 9)

y = 6;

if(IsInRect(x,y,n))

retval = false;

}

return retval;

}

void solve(int row,int count)

{

//都已经填满,打印统计

if( row == 8 && count == 0)

{

print();

total++;

return;

}

if(count == 0)

{

row += 1;

count = b[row];

}



for(int i = 0;i <9 ;i++)

{

if(a[row][i] == 0)

{

for(int j = 1;j <= 9;j++)

{

if(satisfy(row,i,j))

{

a[row][i] = j;

solve(row,count-1);

a[row][i] = 0;

}

}

if(a[row][i] == 0)

return;

}

}





}



bool Usage()

{

bool retval = true;

int select = 0;

printf("1 继续\n");

printf("2 退出\n");



scanf("%d",&select);

if(select == 2)

retval = false;

return retval;

}



int main(int argc, char* argv[])

{



while(1)

{

if(!Usage())

break;

printf("清输入数独矩阵\n");

total =0;

memset(a,0,sizeof(a));

memset(b,0,sizeof(b));



for(int i = 0;i < 9;i++)

{

for(int j = 0;j < 9;j++)

{

scanf("%d",&a[i][j]);

if(a[i][j] == 0)

b[i]++;

}

}



solve(0,b[0]);



printf("共有%d种答案\n",total);

}

return 0;

}

43294235