数独游戏终盘生成算法1
需积分: 0 87 浏览量
2022-08-08
18:34:54
上传
评论
收藏 20KB DOCX 举报
盘点数独终盘生成算法
数独难玩，那设置数独题目容易吗？为了讲解方便，先给数独的九宫格下一个定义，如下图
所示，将数独分为 9 个九宫格，从上到下，从左到右依次编号 1-9。将数独 81 个小格子定
义为一个二维数组 array[9][9]。如果对于数独的玩法还不了解的，那么本文并不适合你，请
先移步数独百度百科了解一下数独游戏的规则。
如要构思一个生成数独题目的程序，应该从哪里入手呢？这里有两种方案：方案一，提前设
置好数独库，将题量充足的数独题目先 作为数据保存起来，用的时候随机取出数独题目，
留一些空出来即可；方案二，通过算法实时 生成数独题目，再留空出来。作为一名优秀的
程序员，肯定要追求难度更大的方案二啦，那么如何设计算法 快速生成有解的 数独题目呢？
我在学习了《编程之美》和各位 博主的答案之后，总结成如下四种解决方案。
1、常规回溯方法
2、以宫为单位的矩阵置换法
3、以数字顺序的以宫为单位的回溯法
4、以某一数独为基础的数字替换法
1、常规回溯方法
这种方法是最容易想到的， 但是执行效率可能不是很高的方法。
思路分析：
常规回朔法的最原始方法即从数独的左上角（0,0）处开始，生成随机数，然后依次按照从
左往右、从上往下的顺序逐渐生成满足数独规则的最终数独。不过从前人总结的经验和我自
己编程过程中遇到的问题来看：这种方法实在是太笨了！笨到你不可能简简单单的通过一个
个随机生成的数来生成最终的数独。因此需要采用回朔法：在某一步生成 1-9 的数字均不能
满足数独要求的时候需要退回到上一个状态重新生成其他可能的解。如此直至最终拼成一个
完整的数独地图，这一个过程如下图示意：
C++代码：
#include <iostream>
#include <stdlib.h> // srand()
#include <time.h> // time()
using namespace std;
int sudoMap[9][9] = {0}; // initialise map.
int counter = 1; // the number of map already generated.
评论0