3 数独解法研究
3.1 求解约束条件
3.2 递归求解数独过程
3.2.1 递归算法
3.2.2 递归算法的流程图
图7 递归法求解数独流程图
recursive algorithm to
3.3 回溯解法
3.3.1 回溯法程序设计过程
3.3.2 回溯算法流程图
图8 回溯算法求解数独流程图
Flow chart of using backtracking algorithm to
3.4 算法对比与分析
附录1计算空格数
package com.qing.sudoku.public class CountBlankNum {public CountBlankNum() {sudoku = "";num = 0;}/*** 计空格数 */public int countBlank(String sudoku) {this.sudoku =String[] ary = ("," + sudoku + ",").split("0");num = ary.length - 1;return}/** * 根据空格数划分难度*/public int countLevel(int BlankNum) {intif (BlankNum & 46 && BlankNum & 39) {level = 1;} else if (BlankNum & 51 && BlankNum & 45) {level = 2;} else if (BlankNum & 56 && BlankNum & 50) {level = 3;} else if (BlankNum & 61 && BlankNum & 55) {level = 4;} else if (BlankNum & 66 && BlankNum & 60) {level = 5;} else {level = 0;}if (level == 0) {System.out.println("Sorry,你输入的数独的空格数：" + BlankNum + ",这超出我们的处理范围");} else {System.out.println("空格数:" + BlankNum);System.out.println("难度等级:" + level + "级");}return}public String getSudoku() {return}public Spublic int/** 主函数*/public static void main(String[] args) {CountBlankNum count = new CountBlankNum();Sint blackNintsu = count.getSudoku();blackNum = count.countBlank(su);level = count.countLevel(blackNum);}}
package com.qing.sudoku.import javax.swing.*;import java.awt.event.*;import java.awt.*;public class CountFree extends JFrame {public static void main(String[] args) {EventQueue.invokeLater(new Runnable() {public void run() {CountFree frame = new CountFree();frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);frame.setVisible(true);}});}public CountFree() {setTitle("难度系数计算");setSize(DEFAULT_WIDTH, DEFAULT_HEIGHT);buttonPanel = new JPanel();txtPanel = new JPanel();/** 输入数独题目*/JButton sudokuProBtn = new JButton("输入数独");buttonPanel.add(sudokuProBtn);sudokuProBtn.addActionListener(new ActionListener() {public void actionPerformed(ActionEvent e) {sudokuStr = JOptionPane.showInputDialog("请输入你想计算难度的数独题目：");}});/*** 计算数独的空格自由度*/JButton freeBtn = new JButton("空格自由度");buttonPanel.add(freeBtn);freeBtn.addActionListener(new ActionListener() {public void actionPerformed(ActionEvent e) {// sudokuStr = "";lab.setText("空格自由度:");countFree(sudokuStr);}});/** 计算数独难度系数*/JButton sudokuLevelBtn = new JButton("难度系数");buttonPanel.add(sudokuLevelBtn);sudokuLevelBtn.addActionListener(new ActionListener() {public void actionPerformed(ActionEvent e) {lab.setText("难度系数:");countLevel();}});/** 标签显示文本*/lab = new JLabel();txtLab = new JLabel();txtPanel.add(lab);txtPanel.add(txtLab);add(buttonPanel, BorderLayout.NORTH);add(txtPanel, BorderLayout.CENTER);}/* * 计算空格自由度*/public int countFree(String str) {strExArray(str);int countXY = lineRowFree(b);int count = nineFree(b);freeLevel = countXY +String s = String.valueOf(freeLevel);txtLab.setText(s);return freeL}/** 计算难度系数*/public int countLevel() {// sudokuStr = "";int free = countFree(sudokuStr);int sudokuLif (free & 0 && free & 721) {sudokuLevel = 1;} else if (free & 720 && free & 841) {sudokuLevel = 2;} else if (free & 840 && free & 961) {sudokuLevel = 3;} else if (free & 960 && free & 1081) {sudokuLevel = 4;} else if (free & 1080 && free & 2106) {sudokuLevel = 5;} else {sudokuLevel = 0;}if (sudokuLevel == 0) {System.out.println("空格数超出了考虑的范围");} else {String s = String.valueOf(sudokuLevel);txtLab.setText(s);}return sudokuL}/* * 将字符串转换为二维数组*/public void strExArray(String str) {char a[] = str.toCharArray();b = new char[9][9];int k = -1;for (int i = 0; i & 9; i++) {for (int j = 0; j & 9; j++) {k++;b[i][j] = a[k];}}}/*** 计算行列自由度的和*/public int lineRowFree(char[][] c) {int countX = 0;int countY = 0;for (int i = 0; i & c. i++) {for (int j = 0; j & 9; j++) {if (b[i][j] == '0') {int row =int line =for (int r = 0; r & 9; r++) {if (b[row][r] == '0') {countX++;}if (b[r][line] == '0') {countY++;}}}}}return countX + countY;}/** 接着计算九宫格的自由度*/public int nineFree(char[][] c) {int p = 0;int r = 0;int m = 9;int n = 9;int countZ = 0;int countH = 0;// 计算出为0的格数for (int i = 0; i & i++) {for (int j = 0; j & j++) {if (c[i][j] == '0') {countZ++;}}}// 计算九宫格内的空格数for (int i = 0; i & i++) {for (int j = 0; j & j++) {if (c[i][j] == '0') {int row = i % 3;int line = j % 3;if (row == 1 && line == 1) {for (p = i - 1; p & i + 2; p++) {for (r = j - 1; r & j + 2; r++) {if (c[p][r] == '0') {countH++;}}}} else if (row == 1 && line == 2) {for (p = i - 1; p & i + 2; p++) {for (r = j - 2; r & j + 1; r++) {if (c[p][r] == '0') {countH++;}}}} else if (row == 1 && line == 0) {for (p = i - 1; p & i + 2; p++) {for (r = r & j + 3; r++) {if (c[p][r] == '0') {countH++;}}}} else if (row == 2 && line == 1) {for (p = i - 2; p & i + 1; p++) {for (r = j - 1; r & j + 2; r++) {if (c[p][r] == '0') {countH++;}}}} else if (row == 2 && line == 2) {for (p = i - 2; p & i + 1; p++) {for (r = j - 2; r & j + 1; r++) {if (c[p][r] == '0') {countH++;}}}} else if (row == 2 && line == 0) {for (p = i - 2; p & i + 1; p++) {for (r = r & j + 3; r++) {if (c[p][r] == '0') {countH++;}}}} else if (row == 0 && line == 1) {for (p = p & i + 3; p++) {for (r = j - 1; r & j + 2; r++) {if (c[p][r] == '0') {countH++;}}}} else if (row == 0 && line == 2) {for (p = p & i + 3; p++) {for (r = j - 2; r & j + 1; r++) {if (c[p][r] == '0') {countH++;}}}} else if (row == 0 && line == 0) {for (p = p & i + 3; p++) {for (r = r & j + 3; r++) {if (c[p][r] == '0') {countH++;}}}} else {}} else {}}}return (countH - countZ);}private String sudokuStr = null;private JPanel buttonPprivate JPanel txtPprivate JLabel txtLprivate JLprivate intprivate int freeLprivate char[][]public static final int DEFAULT_WIDTH = 400;public static final int DEFAULT_HEIGHT = 150;}
SudokuSolving.javapackage SudokuSimport java.io.*;import java.util.*;public class SudokuSolving {public static void main(String[] args) throws Exception {String path = "sudoku.txt";FileReader rd = new FileReader(path);while(true){SudokuGrid grid = SudokuGrid.ReadGrid(rd);if(grid == null){break;}List&SudokuGrid& solutions = new ArrayList&SudokuGrid&();solve(grid, solutions);printSolutions(grid,solutions);}}private static void solve(SudokuGrid grid, List&SudokuGrid& solutions) {if (solutions.size() &= 2) {return;}int loc = grid.findEmptyCell();if (loc & 0) {solutions.add(grid.clone());return;}for (int n=1; n&10; n++){if (grid.set(loc, n)) {solve(grid, solutions);grid.clear(loc);}}}private static void printSolutions(SudokuGrid grid, List&SudokuGrid& solutions) {System.out.println("Original");System.out.println(grid);if (solutions.size() == 0) {System.out.println("Unsolveable");} else if (solutions.size() == 1) {System.out.println("Solved");} else {System.out.println("At least two solutions");}for (int i=0; i&solutions.size(); i++) {System.out.println(solutions.get(i));}System.out.println();System.out.println();}}SudokuGrid.javapackage SudokuSimport java.io.*;public class SudokuGrid implements Cloneable {int[] cells = new int[81];int[] columns = new int[9];int[] rows = new int[9];int[] boxes = new int[9];public static SudokuGrid ReadGrid(Reader stream)throws Exception{SudokuGrid grid = new SudokuGrid();for(int loc=0;loc&grid.cells.){//逐个读取字符int ch = stream.read();if(ch & 0){return null;}//字符＃是用于评论;随后字符将被忽略，直到遇到换行符.//这个地方不理解if(ch == '#'){if (ch &= 0 && ch != '\n' && ch != '\r') {ch = stream.read();}}else if(ch &= '1' && ch &= '9'){grid.set(loc, ch-'0');loc++;}else if(ch == '.' || ch == '0'){loc++;} }return}// 根据单元格的位置，尝试填入数字，如果符合要求则返回true，如果不符合要求则返回falseboolean set(int loc, int num) {int r = loc/9;int c = loc%9;int blockLoc = (r/3)*3+c/3;//检查是否有相同的单元格，如果有的话，则返回falseboolean canSet = (cells[loc] == 0&& (columns[c] & (1&&num)) == 0&& (rows[r] & (1&&num)) == 0&& (boxes[blockLoc] & (1&&num)) == 0);if (!canSet) {return false;}cells[loc] =columns[c] |= (1&&num);rows[r] |= (1&&num);boxes[blockLoc] |= (1&&num);return true;}//寻找空白处public int findEmptyCell() {
for (int i=0; i&cells. i++) {
if (cells[i] == 0) {return}}return -1;}public void clear(int loc) {int r = loc/9;int c = loc%9;int blockLoc = (r/3)*3+c/3;int num = cells[loc];cells[loc] = 0;columns[c] ^= (1&&num);rows[r] ^= (1&&num);boxes[blockLoc] ^= (1&&num);}//复制数独网格public SudokuGrid clone() {SudokuGrid grid = new SudokuGrid();grid.cells = cells.clone();grid.columns = columns.clone();grid.rows = rows.clone();grid.boxes = boxes.clone();return}//设置输出格式 public String toString() {StringBuffer buf = new StringBuffer();for (int r=0; r&9; r&span style="color:
阅读(...) 评论()世界上最难的九宫格游戏?解决你！ | 快乐数独小组 | 果壳网 科技有意思
7920人加入此小组
觉得自己跟聪明？那就来试试解开这个九宫格吧！芬兰数学家因卡拉花费3个月设计出了世界上迄今难度最大的九宫格游戏，而且它只有一个答案。因卡拉说只有思考能力最快、头脑最聪明的人才能破解这个游戏。10年前，九宫格游戏开始在西方流行起来，许多报纸都刊登有这种游戏。九宫格是一个填数字的游戏，规则是在每行、每列及每宫填入数字1到9且不能重复。通常这种游戏的难度被分为1到5级，但因卡拉表示他设计的这个游戏的难度实际达到了11级，其中最难的部分要求玩家提前想到10个数字的填写。因卡拉说，自己不敢肯定这是否永远会是世界最难解的九宫格，但他自信这是迄今为止被设计出来的最难的一个。中国日报----------------------------------------编辑更新： 给出了答案：另据@ 独数之道官方微博说：这两天微博上转的很多的一则关于数独的新闻，称芬兰Arto Inkala又出了一道11星的数独题，声称是世界最难数独。但是他在接受报纸的访问时，说的是他相信目前没有找到最难的数独，数独难度评价的标准还未建立，即使是目前gsf、hodoku、se等的评级标准下，他认为这些评级标准中最难的题还是没找到。其实想请教数独达人：这个数独具体难在哪里？冒昧编辑了主贴，还请楼主见谅。（吴师傅）
+ 加入我的果篮
mark一个，等考完试来试试
这是个假新闻，数独官方微博已经辟谣了好的数独都只有一个答案，并不是只有他才有一个答案
亮点不是只有唯一解好吧，关键是说难度有11级，要提前想好第11步。辟谣在哪里，我没找到……，到时看到好多媒体转载
的话：亮点不是只有唯一解好吧，关键是说难度有11级，要提前想好第11步。辟谣在哪里，我没找到……，到时看到好多媒体转载请不要相信“世界最难”这样的广告语，这里的常客每一个都能解这种数独，如果你到这里常来你也一定能解。不信，吃了午饭我把答案贴出来（只里大概只有我会被你激出答案来，其他高手只怕要笑话我呢）。
的话：请不要相信“世界最难”这样的广告语，这里的常客每一个都能解这种数独，如果你到这里常来你也一定能解。不信，吃了午饭我把答案贴出来（只里大概只有我会被你激出答案来，其他高手只怕要笑话我呢）。
我倒觉得他这个难度等级和那个推理方法比较新鲜！11级不说，但“要提前想好第11步”这个方法应该比较高级，以后解题时尽量体会体会，看会不会有惊喜。
辟谣：这两天微博上转的很多的一则关于数独的新闻，称芬兰Arto Inkala又出了一道11星的数独题，声称是世界最难数独。但是他在接受报纸的访问时，说的是他相信目前没有找到最难的数独，数独难度评价的标准还未建立，即使是目前gsf、hodoku、se等的评级标准下，他认为这些评级标准中最难的题还是没找到。
确实难度很高8 1 2 7 5 3 6 4 99 4 3 6 8 2 1 7 56 7 5 4 9 1 2 8 31 5 4 2 3 7 8 9 63 6 9 8 4 5 7 2 12 8 7 1 6 9 5 3 45 2 1 9 7 4 3 6 84 3 8 5 2 6 9 1 77 9 6 3 1 8 4 5 2
也解一解如何？你可以研究一下他的出题，初盘时用摒除法完全无效，找不出一个解。从玩数独的角度来讲，想纯用难度来难倒人是无意义的。当然我们大家也喜欢难题，不过是另一种性质的难，是一种找不到钥匙的难。
我倒觉得他这个难度等级和那个推理方法比较新鲜！11级不说，但“要提前想好第11步”这个方法应该比较高级，以后解题时尽量体会体会，看会不会有惊喜。真笑是围棋高手吗？感觉你是个喜欢围棋的人。
的话：真笑是围棋高手吗？感觉你是个喜欢围棋的人。
高中时学的围棋，经常和同桌上课时偷偷在手画的棋盘上打x、o,哈哈我不是高手，业余二段都能让我5子。
这个标准数独，我可一点头绪也没有啊，认输啦。
的话：确实难度很高8 1 2 7 5 3 6 4 99 4 3 6 8 2 1 7 56 7 5 4 9 1 2 8 31 5 4 2 3 7 8 9 63 6 9 8 4 5 7 2 12 8 7 1 6 9 5 3 45 2 1 9 7 4 3 6 84 3 8 5 2 6 9 1 77 9 6 3 1 8 4 5 2
也解一解如何？你可以研究一下他的出题，初盘时用摒除法完全无效，找不出一个解。从玩数独的角度来讲，想纯用难度来难倒人是无意义的。当然我们大家也喜欢难题，不过是另一种性质的难，是一种找不到钥匙的难。想问一下，为什么说这个很难啊？
的话：确实难度很高8 1 2 7 5 3 6 4 99 4 3 6 8 2 1 7 56 7 5 4 9 1 2 8 31 5 4 2 3 7 8 9 63 6 9 8 4 5 7 2 12 8 7 1 6 9 5 3 45 2 1 9 7 4 3 6 84 3 8 5 2 6 9 1 77 9 6 3 1 8 4 5 2我也有一解：可见并不是只有一个答案。
摒除法用不了，开始很难
我朋友说用excel解出来了~~11楼的那个好像错了吧！
我也有一解：可见并不是只有一个答案。你这错的不是一般的明显啊。。。
的话：确实难度很高8 1 2 7 5 3 6 4 99 4 3 6 8 2 1 7 56 7 5 4 9 1 2 8 31 5 4 2 3 7 8 9 63 6 9 8 4 5 7 2 12 8 7 1 6 9 5 3 45 2 1 9 7 4 3 6 84 3 8 5 2 6 9 1 77 9 6 3 1 8 4 5 2
也解一解如何？你可以研究一下他的出题，初盘时用摒除法完全无效，找不出一个解。从玩数独的角度来讲，想纯用难度来难倒人是无意义的。当然我们大家也喜欢难题，不过是另一种性质的难，是一种找不到钥匙的难。求解题方法，给点提示吧，第一步确实解不了。
基础的摒除法解不了，只能用假设代入。
的话：基础的摒除法解不了，只能用假设代入。假设代入就是暴力破解法了，呵呵~~如果用暴力破解法才能解出的题，这道题就没有意义了。
11楼。。。
的话：11楼。。。11楼可能不懂数独的玩法....不知道9官格里不能重复数字....另外连本来给出的数字都改写了，哈哈
的话：确实难度很高8 1 2 7 5 3 6 4 99 4 3 6 8 2 1 7 56 7 5 4 9 1 2 8 31 5 4 2 3 7 8 9 63 6 9 8 4 5 7 2 12 8 7 1 6 9 5 3 45 2 1 9 7 4 3 6 84 3 8 5 2 6 9 1 77 9 6 3 1 8 4 5 2
也解一解如何？你可以研究一下他的出题，初盘时用摒除法完全无效，找不出一个解。从玩数独的角度来讲，想纯用难度来难倒人是无意义的。当然我们大家也喜欢难题，不过是另一种性质的难，是一种找不到钥匙的难。可否请教一下解这道题的具体思路呢？
的话：我朋友说用excel解出来了~~11楼的那个好像错了吧！Excel可以解数独？O_O
这个数独，计算机暴力求解也只要0.125s...
楼上的方法牛~暴力求解器
的话：这是个假新闻，数独官方微博已经辟谣了好的数独都只有一个答案，并不是只有他才有一个答案我就奇了个怪 难道数独还是多选题？
数独、谜题玩家兼写手
的话：我就奇了个怪 难道数独还是多选题？ 数独本来就要求唯一解，唯一解的是合格的题目，不是唯一解的就是不合格的题目。唯一解的也谈不上好，实际解了才知道。
唉，完全没思路 编程的不能算啊。。
的话： 数独本来就要求唯一解，唯一解的是合格的题目，不是唯一解的就是不合格的题目。唯一解的也谈不上好，实际解了才知道。有评价数独难易程度的体系吗？
数独、谜题玩家兼写手
的话：有评价数独难易程度的体系吗？没有统一标准，只有几款软件的浅层分析，深层分析是相当难的，即使玩家论坛的那些程序高人们，也没看到某个人做到。包括最经典的一款软件sudoku explainer最高难度ER=11.9/11.9/11.9的题目还未被发现。
的话：这个数独，计算机暴力求解也只要0.125s...求代码。
心理学硕士
的话：求代码。这个还是蛮简单的~最笨的办法就是不停地if else就可以了~我有个同学为了向我证明数独不好玩，编了一个程序来刺激我……
话说除了暴力破解还有什么好的方法？
的话：这个数独，计算机暴力求解也只要0.125s...宙吧，这么巧啊。。。
的话：没有统一标准，只有几款软件的浅层分析，深层分析是相当难的，即使玩家论坛的那些程序高人们，也没看到某个人做到。包括最经典的一款软件sudoku explainer最高难度ER=11.9/11.9/11.9的题目还未被发现。soga……
的话：引用
的话：确实难度很高8 1 2 7 5 3 6 4 99 4 3 6 8 2 1 7 56 7 5 4 9 1 2 8 31 5 4 2 3 7 8 9 63 6 9 8 4 5 7 2 12 8 7 1 6 9 5 3 45 2 1 9 7 4 3 6 84 3 8 5 2 6 9 1 77 9 6 3 1 8 4 5 2我也有一解：可见并不是只有一个答案。==这个真的只有一个解而已。亲你的解是错误的哟。小3X3格子也是不重复的1-9才可哦。
GAMELOFT出的白金数独游戏，里面有SOLVER MODE。很快就能解出各类数独题。
的话：Excel可以解数独？O_O我也觉得奇怪，他是这样说的...可能用函数解的吧...
的话：GAMELOFT出的白金数独游戏，里面有SOLVER MODE。很快就能解出各类数独题。有程序解数独就失去了数独原有的意思了
的话：宙吧，这么巧啊。。。略巧略巧，恶呵呵弱弱问一下，是头像暴露了我么。。。
的话：求代码。你可以搜索一下 poj 2676
我想说这个题是个水题。。。。dfs一下就出来了。如果你还嫌不过快，可以用下dance link
数独、谜题玩家兼写手
的话：话说除了暴力破解还有什么好的方法？这题需要暴力破解，如果有人没用猜的，很像见识一下他的方法。这个档案里&10的题目，难度和这题比有过之而无不及，在。ER是一款很经典的标准数独软件的评级，最高是11.9/11.9/11.9，目前还没找到这样的题。此题是10.7/10.7/9.7。
我连暴力破解的程序都写不出来……
的话：略巧略巧，恶呵呵弱弱问一下，是头像暴露了我么。。。还有辽宁大连。。。
神经生物学硕士
来看看~~呵呵，这个，在微博里已经说过了
的话：我也觉得奇怪，他是这样说的...可能用函数解的吧...求Excel的具体操作法。。。
的话：我想说这个题是个水题。。。。dfs一下就出来了。如果你还嫌不过快，可以用下dance link果然一堆OIer/ACMer混迹于果壳=。=当年我死活看不懂dancing link其实启发式搜索基本能满足所有需求根本不需要dancing link -。 -写dancing link的都是在晒
的话：这个数独，计算机暴力求解也只要0.125s...你。。。好吧，机器的力量我还在计算中呢
这个行不，第一行第二行第三行第四行第五行第六行第七行第八行第九行这是横向看的，图我不会发，所以发了这个，不好看请见谅哈
(C)2015果壳网&京ICP备号-2&京公网安备高智商专区：难度只有2颗星的数独游戏！
日 16:07&&&转载：&& 作者:IQ测试与训练&& 编辑:网络 分享
今天给大家来点难度系数2颗星的数独题目。不管是小学、中学还是大学，数独都是非常好的脑力游戏，只是根据自身情况难度适当增加会更有意思。当你坚持一段时间后，你会发现自己智力和心态都会有所变化！数独：一直智力和毅力的考验；他是一种运用纸、笔进行演算的逻辑游戏。需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。 每一道合格的数独谜题都 有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。1.2.3.4.5.========答案=======更多精彩请关注微信公众号：IQ测试与训练1.2.3.4.5.
看过本文的人还看了
101人浏览 67人浏览 11人浏览 9人浏览
汽车之家内容精选
每日精选16120 编辑宋宋和大国推出的脱口秀节目3149玩客 最好玩的活动与试用平台 0编辑部的故事 0泡美美 分享最美科技 4797科技生活终于遇到高难度的数独了：（
从昨天到现在，俺一直被两个数独困扰着，实在很难，怎么想都想不出来，呜呜，信心受到打击了！不行！俺要知难而进，誓解此二数独！！！
&&最后修改于
请各位遵纪守法并注意语言文明}