数独

2024-07-15 03:20| 来源: 网络整理| 查看: 265

关于数独，来自维基百科的玩法解释：在9×9格的大九宫格中有9个3×3格的小九宫格，并提供一定数量的数字。根据这些数字，利用逻辑和推理，在其它的空格上填入1到9的数字。每个数字在每个小九宫格内只能出现一次，每个数字在每行、每列也只能出现一次。那么一共多少个数独矩阵呢？大家可以参看这个链接http://www.afjarvis.staff.shef.ac.uk/sudoku/。There are 6670903752021072936960 Sudoku grids (Bertram Felgenhauer and Frazer Jarvis)。这么个数字还真是挺大，没仔细学习之前我就以为仅有那么几个呢。

最近考研实在是无聊，总是会萌生一些，奇怪的想法，突然看着线性代数就想到了数独矩阵的问题，于是决定试着自己生成几个玩玩。

网上有不少写好的生成算法，我找到的几个大概的实现思路都是现在第一行生成一组1-9不重复的数字，然后第二行开始不停的验证，不停的回退，然后再不停的验证，这种方法叫“回溯法”。主要问题是效率真是不敢恭维，能不能得出结果了真得看人品。一些提供数独游戏的网站，看他的解释是说，没有做到随机生成，而是当你访问的时候去库里读一个出来给浏览者玩，这种方法也不是特别优雅。

数独的总个数是这么得出来的。9!×722×27× 27,704,267,971=6,670,903,752,021,072,936,960（约有6.67×10的21次方）种组合，2005年由Bertram Felgenhauer和Frazer Jarvis计算出该数字，如果将重复（如数字交换、对称等）不计算，那么有5,472,730,538个组合。那么有趣的来了，有个9！=362880，这个就等于9的全排列，是不是可以从这里做突破口呢？如果我可以随机的生成362880个完整的数独矩阵，然后随机的每行挖去4到5个那就是362880/24/120*9*362880=411505920个，这个数字够大家有生之年玩的了。

于是我产生了一个看上去比较WS的算法，思路如下：我先写一个数独出来，用二维数组A表示，然后再生成一个乱序的1-9一维数组，用一维数组b表示。遍历这个A数组，在b中找到A数组中当前值所在的位置，然后将b数组中下一个位置的数字赋给A的当前值，目的就是用b数组给A数组中的所有的值，循环的变一下。注意这个b数组的可能性恰好是9的全排列，也就是可以生成362880个数组，也即是生成362880个不同的随机矩阵。

我用JAVA实现了我的想法，证明是比较可行，如果你的机器不是上个世纪的古董的话，1秒钟内出一个矩阵是没有问题的。程序里用到的数据矩阵很容易就写出来了，中间的那个九宫格是1-9的顺序排列，第五行第五列都是有规律，然后一个九宫格一个九宫格的填充。

参考代码：

package com.tiaobug; import java.util.ArrayList; import java.util.Random; /** * @author * @version:1.0 * @since 2010年11月21日22:58:43 * @

快速生成数独算法

*/ public class Sudoku { /** *

打印二维数组，数独矩阵

*/ public static void printArray(int a[][]) { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { System.out.print(" " + a[i][j]); if (0 == ((j + 1) % 3)) { System.out.print(" "); } } System.out.println(); if (0 == ((i + 1) % 3)) { System.out.println(); } } } /** *

产生一个1-9的不重复长度为9的一维数组

*/ public static ArrayList creatNineRondomArray() { ArrayList list = new ArrayList(); Random random = new Random(); for (int i = 0; i < 9; i++) { int randomNum = random.nextInt(9) + 1; while (true) { if (!list.contains(randomNum)) { list.add(randomNum); break; } randomNum = random.nextInt(9) + 1; } } System.out.println("生成的一位数组为："); for (Integer integer : list) { System.out.print(" " + integer.toString()); } System.out.println(); return list; } /** *

通过一维数组和原数组生成随机的数独矩阵

遍历二维数组里的数据，在一维数组找到当前值的位置，并把一维数组 * 当前位置加一处位置的值赋到当前二维数组中。目的就是将一维数组为 * 依据，按照随机产生的顺序，将这个9个数据进行循环交换，生成一个随 * 机的数独矩阵。

*/ public static void creatSudokuArray(int[][] seedArray, ArrayList randomList) { int flag = 1; for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { for (int k = 0; k < 9; k++) { if (seedArray[i][j] == randomList.get(k)) { seedArray[i][j] = randomList.get((k + 1) % 9); break; } } } } System.out.println("处理后的数组"); Sudoku.printArray(seedArray); } // public static void main(String[] args) { int seedArray[][] = {{9, 7, 8, 3, 1, 2, 6, 4, 5}, {3, 1, 2, 6, 4, 5, 9, 7, 8}, {6, 4, 5, 9, 7, 8, 3, 1, 2}, {7, 8, 9, 1, 2, 3, 4, 5, 6}, {1, 2, 3, 4, 5, 6, 7, 8, 9}, {4, 5, 6, 7, 8, 9, 1, 2, 3}, {8, 9, 7, 2, 3, 1, 5, 6, 4}, {2, 3, 1, 5, 6, 4, 8, 9, 7}, {5, 6, 4, 8, 9, 7, 2, 3, 1}}; System.out.println("原始的二维数组:"); Sudoku.printArray(seedArray); ArrayList randomList = Sudoku.creatNineRondomArray(); Sudoku.creatSudokuArray(seedArray, randomList); } }

后记：

经多次测试，出结果是没问题的，但是思路上有点不是太正式的意思，怎么看怎么感觉还是有点不完美（本人是个轻微的完美主义者），但是效率还是让我很欣慰的。

评论区里的朋友有质疑生成的结果有规律，过于简单，我也不确定你说的对不对，放代码前已经说过了，这个思路不太正式，但是你可以试一下生成两个，自己玩玩，看看能不能找到规律。

希望这个东西能对大家有点帮助，写的不对的地方，请大家给予指正。

2019年7月8日16:28:52，现在看快十年前写的东西，虽然有点幼稚，但是还是很有趣味，没想到有三万多的阅读量了。格式乱了，顺手整理一下吧。

2021年2月2日14:53:14，update.

【本文地址】

数独

数独

今日新闻

推荐新闻