1.准备

继上篇文章《c语言暴力递归实现数独求解》 思路，本章编写一个数独生成器，按照数独的规则生成题目，但不保证题目可解。

2.思路

按照数独的规则：

水平方向的每一横行有九格，每一横行称为行（Row） 垂直方向的每一纵列有九格，每一纵列称为列（Column） 三行与三列相交之处有九格，每一单元称为小九宫（Box、Block） 格子上填入1-9数字，使1-9每个数字在每一行、每一列和每一宫中都只出现一次

所以，我们程序还是使用三个bitmap来进行标记1-9数字是否被使用。 其他的，数独的表示我们还是用一维数组转二维数组的思路进行。

3.实现

定义与上篇文章一样：

#define SIZE_BLK 3 #define SIZE_NUM (SIZE_BLK * SIZE_BLK) #define bit_set(b, n) ((b) |= (0x1 << (n))) #define bit_clr(b, n) ((b) &= ~(0x1 << (n))) #define bit_chk(b, n) (((b) >> (n)) & 0x1) struct instance { unsigned times; unsigned bits_lines[SIZE_NUM]; unsigned bits_colum[SIZE_NUM]; unsigned bits_block[SIZE_NUM]; };

核心逻辑：随机挑选一个位置，选择一个合适的、随机值填入。

int sudoku_roll(struct instance *pinst, char board[SIZE_NUM][SIZE_NUM]) { int rx = rand() % 9; // random value int ix = rand() % 9; int jx = rand() % 9; int bx = ix / SIZE_BLK * SIZE_BLK + jx / SIZE_BLK; for (int nx = rx; ; nx = (nx + 1) % 9) { if ((nx + 1) % 9 == rx) { printf("Retry\n"); // 实在没有合适的数值可填了，放弃该位置 return -1; } if (bit_chk(pinst->bits_lines[ix], nx)|| bit_chk(pinst->bits_colum[jx], nx)|| bit_chk(pinst->bits_block[bx], nx)) { printf("Exist[%d, %d, %d] = %d\n", ix, jx, bx, 1 + nx); continue; // 该值违反了数独规则，重新选取新数值 } // 找到了合适的值，标记上去 bit_set(pinst->bits_lines[ix], nx); bit_set(pinst->bits_colum[jx], nx); bit_set(pinst->bits_block[bx], nx); board[ix][jx] = '1' + nx; printf("Roll [%d, %d, %d] = %c\n", ix, jx, bx, board[ix][jx]); break; } return 0; }

往上一层逻辑，我们就还要考虑填充几个数字，经验值上是填充到30~40的时候，题目变得不好求解。

int sudoku_auto(char board[SIZE_NUM][SIZE_NUM], int times) { int ix = 0; int jx = 0; int res = -1; struct instance inst = {0}; memset(board, '.', SIZE_NUM * SIZE_NUM); // 循环的考虑：ix是正常填充值 // jx是防止数独无解死循环 for (ix = jx = 0; ix < times && jx < SIZE_NUM * SIZE_NUM; jx++) { res = sudoku_roll(&inst, board); if (0 != res) { printf("Retry\n"); continue; } ix++; } printf("%s, times: M, result: %s\n", "Random ", times, (char *)board); sudoku_display(board); return 0; }

为了直观的显示，我们加入了打印函数：

void sudoku_display(char board[SIZE_NUM][SIZE_NUM]) { for (int ix = 0; ix < SIZE_NUM; ix++) { if (ix % SIZE_BLK == 0) { printf("+---+---+---+\n"); } for (int jx = 0; jx < SIZE_NUM; jx++) { if (jx % SIZE_BLK == 0) { printf("|"); } printf("%c", board[ix][jx]); } printf("|\n"); } printf("+---+---+---+\n"); }

主函数

#define SUDOKU_AUTO(_times) do { \ char _input[SIZE_NUM * SIZE_NUM + 1] = {0}; \ sudoku_auto((char (*)[SIZE_NUM])_input, _times); \ } while (0) int main(int argc, char *argv[]) { SUDOKU_AUTO(10); SUDOKU_AUTO(20); SUDOKU_AUTO(30); SUDOKU_AUTO(40); exit(EXIT_SUCCESS); }

运行结果：

Random , times: 10, result: ..........5......8...............2...............2..8.5.....9..2....6...........1 +---+---+---+ |...|...|...| |.5.|...|..8| |...|...|...| +---+---+---+ |...|...|2..| |...|...|...| |...|.2.|.8.| +---+---+---+ |5..|...|9..| |2..|..6|...| |...|...|..1| +---+---+---+ Random , times: 20, result: 3.1..7...........2.....8..7..3.8.6......6......54...7.8.......9....2.....3....... +---+---+---+ |3.1|..7|...| |...|...|..2| |...|..8|..7| +---+---+---+ |..3|.8.|6..| |...|.6.|...| |..5|4..|.7.| +---+---+---+ |8..|...|..9| |...|.2.|...| |.3.|...|...| +---+---+---+ Random , times: 30, result: .3.8...61.1..769.376.....85......75...7...1...94.....85.6.3...7..1............... +---+---+---+ |.3.|8..|.61| |.1.|.76|9.3| |76.|...|.85| +---+---+---+ |...|...|75.| |..7|...|1..| |.94|...|..8| +---+---+---+ |5.6|.3.|..7| |..1|...|...| |...|...|...| +---+---+---+ Random , times: 40, result: .37...4..9........428..7.358....19.2...3.4..6.92.......7...2.63..1685.24.8...37.. +---+---+---+ |.37|...|4..| |9..|...|...| |428|..7|.35| +---+---+---+ |8..|..1|9.2| |...|3.4|..6| |.92|...|...| +---+---+---+ |.7.|..2|.63| |..1|685|.24| |.8.|..3|7..| +---+---+---+

4.结论

该方法能够简单快速生成数独题目，但并不能保证数独有解。如果要保证生成的有解，那么就需要在sudoku_rand()函数中，引入求解的验证，但势必会带来额外计算量（提高检测算法也算另外一个调研方向）。