朋友手机装有数独游戏，开会报告等无聊的场合常拿来玩玩，游戏的算法似乎并不难，想想我也能做出来。今早闲的蛋疼，就写了个数独玩玩。记录如下：
数独规则不知道的可以参考这里： 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 ;
|
