Question

数独算法思路

最近在玩数独游戏,感觉很神奇,就想自己编个程序来实现,可是没有思路,不知道从哪里下手,有哪位高手知道,或者有类似的经验的,请不吝赐教,高分!只要思路就可以,无论用哪种语言都可以,给个相关网站也行,只要有用的,我就给分

Answer 1

数独(数和)（英：Cross Sums；日：カックロ）是一种数学智力游戏。数和把填字游戏和数独巧妙地结合在一起，采用填字游戏式的棋盘，解题时在空格中填上1-9的数字。这种游戏不仅需要逻辑思维能力，还需要一点加法运算。

电脑自动生成数独游戏的谜题

要得出所有满足条件的组合确实不是件容易的事情（主要是很多，打印起来很慢） 。但偶们的目标只是每次能得到一个新的组合，然后从格子里面随机遮掉一些数字就可以了。所以只需要在解数独游戏算法的基础上稍作修改即可。

所以，算法的步骤是：

1.往第一行或第一列随机填1-9的数字

2.调用解数独算法得到一个结果

3.每行随机遮掉1-8个数字。如果需要较大的难度，也可以将1-8改为2-8或3-8，等等。

以下是console工程的代码：

// sudoku.cpp : 定义控制台应用程序的入口点。
// by superarhow(superarhow@hotmail.com)

#include "stdafx.h"

#include "conio.h"

#define SUCCESS 1
#define _FAILED 0

/* 地图类型9*9的char，每个char从0-9，0表示待填 */
typedef char MAPTYPE[9][9];
/* 行数据，同时用作“可能性”数据。如LINETYPE a; 当a[0]为真时表示
当前位置可填1，a[1]为真时表示可填2，以此类推 */
typedef char LINETYPE[9];

typedef void (*ONMAPOKCALLBACK)(MAPTYPE map);

/* 打印地图 */
void dump_map(MAPTYPE dest)
{
for ( int j = 0; j < 9; j++ )
{
for ( int i = 0; i < 9; i++ )
{
printf("%d ", dest[i][j]);
}
printf("\n");
}
printf("\n");
}

int fill_line(MAPTYPE dest, int line, ONMAPOKCALLBACK callback);

/* 填下一个格子。本行的可能性已在调用前算好，要考虑的是列的可能性和九宫格的可能性 */
/* nums_possible : array (0-8) means possible of number (1-9) */
int fill_pos(MAPTYPE dest, LINETYPE nums_possible, int line, int pos, ONMAPOKCALLBACK callback)
{
if ( pos >= 9 )
{
return fill_line(dest, line + 1, callback);
}
if ( dest[pos][line] != 0 ) return fill_pos(dest, nums_possible, line, pos + 1, callback);
for ( int i = 0; i < 9; i++ )
{
if ( !nums_possible[i] ) continue;
/* 检查本列是否重复 */
int vetical_failed = 0;
for ( int j = 0; j < 9; j++ )
if ( dest[pos][j] == i + 1 )
{
vetical_failed = 1;
break;
}
if ( vetical_failed ) continue;
/* 检查九宫格是否重复 */
int nine_failed = 0;
int m = pos / 3;
int n = line / 3;
m *= 3;
n *= 3;
for ( int y = n; y < n + 3; y++ )
{
for ( int x = m; x < m + 3; x++ )
{
if ( dest[x][y] == i + 1 )
{
nine_failed = 1;
break;
}
}
if ( nine_failed ) break;
}
if ( nine_failed ) continue;
/* all ok, try next position */
dest[pos][line] = i + 1;
nums_possible[i] = 0;
if ( fill_pos(dest, nums_possible, line, pos + 1, callback) )
{
/* 本行已全部OK，尝试下一行 */
if ( fill_line(dest, line + 1, callback) ) return SUCCESS;
/* 下一行失败，重新尝试本位置的剩余可能性 */
}
nums_possible[i] = 1;
dest[pos][line] = 0;
}
return _FAILED;
}

/* 填下一行 */
int fill_line(MAPTYPE dest, int line, ONMAPOKCALLBACK callback)
{
if ( line >= 9 )
{
/* copy map */
callback(dest);
return SUCCESS;
}
LINETYPE nums;
LINETYPE saveline;
/* calc possibility(for the current line) */
for ( int i = 0; i < 9; i++ ) nums[i] = 1; /* all can be */
for ( int i = 0; i < 9; i++ )
{
char n = dest[i][line];
/* save line */
saveline[i] = dest[i][line];
if ( n != 0 ) nums[n - 1] = 0; /* appears */
}
if ( !fill_pos(dest, nums, line, 0, callback) )
{
/* restore line */
for ( int i = 0; i < 9; i++ ) dest[i][line] = saveline[i];
return _FAILED;
}
return SUCCESS;
}

MAPTYPE g_result;

void on_map_ok(MAPTYPE map)
{
memcpy(g_result, map, sizeof(MAPTYPE));
}

#include "windows.h"

int _tmain(int argc, _TCHAR* argv[])
{
MAPTYPE dest;
memset(dest, 0, sizeof(MAPTYPE));
srand( GetTickCount() );
/* 随机填充第一行 */
char ch[9] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
for ( int i = 0; i < 9; i++ )
{
int p = rand() % 9;
char t = ch[p];
ch[p] = ch[i];
ch[i] = t;
}
for ( int i = 0; i < 9; i++ ) dest[i][0] = ch[i];
if ( fill_line(dest, 0, on_map_ok) )
{
/* 修剪掉一些块 */
for ( int i = 0; i < 9; i++ )
{
/* 调整n的取值范围可改变难度 %6 + 3是比较难的 */
int n = (rand() % 6) + 3;
for ( int j = 0; j < 9; j++ ) ch[j] = j; /* ch: index to erase */
for ( int j = 0; j < 9; j++ )
{
int p = rand() % 9;
char t = ch[p];
ch[p] = ch[i];
ch[i] = t;
}
for ( int j = 0; j < n; j++ ) g_result[ch[j]][i] = 0;
}
dump_map(g_result);
}
getch();
return 0;
}

看完这些，你对数独的算法了解了吗？