关于数独的生成
这次从深圳回来的火车上，由于过于无聊，玩了一下数独游戏，和吕政委（同学）讨论了下数独的生成方法，这篇日志算是对车上思路的一个实现。即使是一个简单的问题，也可以引申出很多有趣的东西，这种乐趣只有写代码的时候才能发现，只可意会不可言传……
以前其实写过一个数独游戏，但是重装了无数次系统之后源代码不知道哪去了，估计是让猫给吃了；《编程之美》里面貌似有一篇文章是讲数独的生成的，而且不止一种方法，不过我的这本书估计也让猫给吃了……我这里是用回溯法生成完整的数独。
哈哈哈，周末时光翻看到了高中时期写的这篇文章，感叹一下（逝去的我的高中时光）
现在从事着大数据开发工作，依旧喜欢写代码。
拥有自己的大数据学习交流群：606859705
喜欢代码的伙伴可以一起交流经验
其实有很多地方可以说的，但是还是算了，贴上代码：
/*
* Name: main.c
* Purpose: 数独生成
* Author: HSZ @ HNU
* Created: 2013/7/11 星期四 17:42:56
* LastChange: 2013/7/11 星期四 17:42:56
* History:
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define MAX_NUM 9
#define MAP_H MAX_NUM
#define MAP_W MAX_NUM
// 可选数字缓冲区
struct num_list {
int nums[MAX_NUM];
int size;
};
// 随机打乱数组
static void randomize(int nums[], int size);
// 初始化可选数字缓冲区
static void init_num_list(struct num_list *list, const int map[MAP_H][MAP_W], int row, int col);
// 初始化地图
static void init_map(int map[MAP_H][MAP_W]);
int main(int argc, char *argv[])
{
int map[MAP_H][MAP_W] = {0};
int i, k;
srand(time(NULL));
init_map(map);
for (i = 0; i < MAP_H; ++i) {
for (k = 0; k < MAP_W; ++k) {
printf("%d, ", map[i][k]);
}
printf("\n");
}
return 0;
}
void init_map(int map[MAP_H][MAP_W])
{
int i, k;
struct num_list list[MAP_H][MAP_W] = {0};
// 遍历地图，填充合适的数字
i = 0;
while (i < MAP_H) {
k = 0;
while (k < MAP_W) {
// 如果map[i][k] == 0，说明这个格对应的可选数字列表没有初始化过
if (map[i][k] == 0) {
// 初始化
init_num_list(list[i] + k, map, i, k);
// 打乱
randomize(list[i][k].nums, list[i][k].size);
}
// 如果此时map[i][k]不为0，说明是回溯，清0，否则继续回溯会出错
map[i][k] = 0;
if (list[i][k].size == 0) {
// 如果没有可选的数字，回溯
--k;
if (k < 0) {
k = 8;
--i;
}
continue;
} else {
// 否则，填充地图，移除可选数字列表中的一个数字
map[i][k] = list[i][k].nums[list[i][k].size - 1];
--list[i][k].size;
}
++k;
}
++i;
}
}
void randomize(int nums[], int size)
{
int i, k;
int tmp;
for (i = 0; i < size; ++i) {
// 令k = [i, size-1)区间随机的一个数
k = (i + rand() % (size - i));
// 交换nums[i]与nums[k]
tmp = nums[i];
nums[i] = nums[k];
nums[k] = tmp;
}
}
void init_num_list(struct num_list *list, const int map[MAP_H][MAP_W], int row, int col)
{
int i, k;
// 初始可选数字1~9，0是一个占位符
int allow_nums[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
// 去除横纵两个方向上已经存在的数字,这里其实可以稍稍优化一下
for (i = 0; i < 9; ++i) {
allow_nums[map[row][i]] = 0;
allow_nums[map[i][col]] = 0;
}
// 定位到这个九宫格的左上角坐标
row = row - (row % 3);
col = col - (col % 3);
// 遍历这个九宫格
for (i = row; i < row + 3; ++i) {
for (k = col; k < col + 3; ++k)
allow_nums[map[i][k]] = 0;
}
// 遍历剩下的数字填充数字缓冲区
list->size = 0;
for (i = 1; i < 10; ++i) {
if (allow_nums[i] != 0) {
list->nums[list->size] = allow_nums[i];
++list->size;
}
}
}