java 数独算法_[Java] 数独生成和求解

  • Post author:
  • Post category:java


思路

1.生成数独

数独的生成总体思路是挖洞法。

首先在二维数组第一行随机填充1-9 9个数字,然后将这9个数字随机分布到整个二维数组中,然后使用求解数独的算法对此时的数组进行求解,得到一个完整的数独,然后按照用户输入的提示数量进行随机挖洞,得到最终的数独题目。

这种方法理论上可以随机生成(81!/72! = 9.5e+16)种不同的数独题目,足够人类玩上几百年了。

2.求解数独

求解数独使用的是计算机最擅长的暴力搜索中的回溯法。并结合人求解数独的思维过程增加了一点改进。

在每一层搜索中,首先计算每个格子可以填充的值的个数(我命名为不确定度),如果有格子不确定度为1,则直接填上数字就好,否则对不确定度最小的格子使用可能的数字逐个填充,并进入下一次递归。如果发现不确定度为0的格子,做说明之前的过程有问题,需要进行回溯。

代码

package sudo;

import java.util.Scanner;

/**

* @description 数独生成和求解

* @limit 支持从1-80的数字提示数量

* @method 深度优先搜索/回溯法

* @author chnmagnus

*/

public class Sudo {

private int[][] data = new int[9][9]; //muti_array

private int lef; //the number of zero in array

private int tip; //the number of nozer



版权声明:本文为weixin_35182280原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。