朋友手机装有数独游戏,开会报告等无聊的场合常拿来玩玩,游戏的算法似乎并不难,想想我也能做出来。今早闲的蛋疼,就写了个数独玩玩。记录如下:
数独规则不知道的可以参考这里: http://baike.baidu.com/view/961.htm?fr=ala0_1 。游戏关键的算法就在于生成一个符合数独游戏规则的初始矩阵,首先想到的自然是号称万能解题法的“搜索+剪枝”了。
1.
产生符合数独规则的初始矩阵
第一行是随机生成的1~9的排列,第2到9行就要通过搜索来产生了。对于第2到9行的每一个空格,要从1到9逐个尝试放入,看同一列、同一行、同一个3×3的小方阵中是否出现过相同的数字,若没有就尝试放入,然后递归地搜索下一个位置的数字,若1到9都不行就返回上一个位置尝试下一个数字。直到找到一组解就返回。
先上C++代码:
#include<iostream>
#include<algorithm>
#include <ctime>
using
namespace std;
int Initial_State [ 10 ] [ 10 ] ;
bool get_Initial_State( int i , int j ) //搜索第( i , j )位置处可以存储的数字,找到解则返回true,否则返回false
{
if( i >
9
|| j >
9 )
return
true;
for( int k =
1 ; k <=
9 ; ++k )
{
bool can =
true; // can 变量用于记录数字k能否放在 ( i , j ) 处
for( int m =
1 ; m < i ; ++m )
if( Initial_State[m][j] == k ) // 检查同一列是否出现过数字k
{
can =
false ;
break ;
}
if ( can )
for( int n =
1 ; n < j ; ++n )
if( Initial_State[n] == k ) // 检查同一行是否出现过数字k
{
can =
false ;
break;
}
if( can )
{
int up1 = ( i/3 ) *
3
+
3 ; // (i,j)方格所在的3×3小方格i坐标的上限
int up2 = ( j/3 ) *3
+
3; // (i,j)方格所在的3×3小方格在j坐标的上限
if( i %
3
==
0 ) //这是针对特殊情况的处理
up1 = i ;
if( j %
3
==
0 )
up2 = j ;
|