数独算法

2024-06-28 13:16| 来源: 网络整理| 查看: 265

1.概述

数独（Sudoku）是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。 1)终盘数量: 数独中的数字排列千变万化，那么究竟有多少种终盘的数字组合呢？ 6,670,903,752,021,072,936,960（约为6.67×10的21次方）种组合，2005年由Bertram Felgenhauer和Frazer Jarvis计算出该数字，并将计算方法发布在他们网站上，如果将等价终盘（如旋转、翻转、行行对换，数字对换等变形）不计算，则有5,472,730,538个组合。数独终盘的组合数量都如此惊人，那么数独题目数量就更加不计其数了，因为每个数独终盘又可以制作出无数道合格的数独题目。 2)标准数独: 目前（截止2011年）发现的最少提示数9×9标准数独为17个提示，截止2011年11月24日16:14，共发现了非等价17提示数谜题49151题，此数量仍在缓慢上升中，如果你先发现了17提示数的题目，可以上传至“17格数独验证”网站，当然你也可以在这里下载这49151题。 Gary McGuire的团队在2009年设计了新的算法，利用Deadly Pattern的思路，花费710万小时CPU时间后，于2012年1月1日提出了9×9标准数独不存在16提示唯一解的证明，继而说明最少需要17个提示数。并将他们的论文以及源代码更新在2009年的页面上。

以上内容来自于百度百科。

2.算法实现（Java）

网络上有很多解数独的算法，例如舞蹈链算法、遗传算法等。参考各种算法的性能比较：递归回溯对数独情有独钟。本文解数独用的是候选数法（人工选择）+万能搜索法，搜索+剪枝（递归+回溯），参考博文：数独算法及源代码

1）未优化的算法-只有递归回溯（单解或多解）

从第一个位置开始依次检索所有格子（暴力），执行时间会比较长。多解与单解：很简单，在找到解的语句返回false表示继续递归寻解，返回true表示停止寻解（不会复位，不回溯）

package com.sudoku; import java.util.Date; public class Sudoku { private int[][] matrix = new int[9][9];//注意下标从0开始 private int count=0;//解的数量 private int maxCount = 1;//解的最大数量 //输入格式要求0作为占位符(表示待填)，只接受数字字符串，长度为81位 public Sudoku(String input,int maxCount) throws Exception{ if(input==null||input.length()!=81||!input.matches("[0-9]+")) throw new Exception("必须为81位长度的纯数字字符串"); init(input); this.maxCount = maxCount; } public Sudoku(String input) throws Exception{ this(input,1); } public Sudoku(){ } public int getCount(){ return count; } //初始化数独 private void init(String input){ for(int i=0;i//对应于行列宫号，对应宫的起始位置为(x/3*3,x%3*3) 取余与乘除优先级相同 rowSet.clear(); colSet.clear(); gridSet.clear(); for(int index=0;index0&&!rowSet.add(matrix[x][index])){ //行重复 System.out.println(String.format("数独无效,第%d行重复！",x+1)); return false; } if(matrix[index][x]>0&&!colSet.add(matrix[index][x])){ //列重复 System.out.println(String.format("数独无效,第%d列重复！",x+1)); return false; } if(matrix[x/3*3+index/3][x%3*3+index%3]>0&&!gridSet.add(matrix[x/3*3+index/3][x%3*3+index%3])){ System.out.println(String.format("数独无效,第%d宫重复！",x+1)); return false;//宫重复 } } } return true; } //初始化候选数(唯一法或唯余法),数独无解返回false private boolean initCandidature() throws Exception{ for(int i=0;i

【本文地址】

公司简介

联系我们