suduGame.zip

  • Bibheng
    了解作者
  • Java
    开发工具
  • 16KB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 1
    下载次数
  • 2019-01-24 15:14
    上传日期
求解数独,根据递归唯一余数法和摒除法求解,如果无法解决在递归假设法求解。
suduGame.zip
内容介绍
import java.util.*; /** * @Author: Matthew * @Date: 2019/01/21 16:47 */ public class SolveSudu { private final static String UNDONE = "无解"; private final static String SUCCESS = "有解"; private final static String FAIL = "求解失败"; public static void main(String[] args) { //char[][] board = inputBoard(); // char[][] board = { // {'5', ' ', ' ', '9', ' ', ' ', '7', ' ', ' '}, // {' ', ' ', '4', ' ', '2', ' ', ' ', ' ', ' '}, // {' ', '7', ' ', ' ', ' ', '5', '4', '9', '2'}, // {'4', ' ', ' ', '2', ' ', ' ', '3', ' ', ' '}, // {' ', ' ', '9', ' ', '4', ' ', ' ', ' ', ' '}, // {' ', '3', ' ', ' ', ' ', '8', '9', '1', '4'}, // {'7', ' ', ' ', '6', ' ', ' ', ' ', ' ', ' '}, // {'2', '9', ' ', '4', ' ', '1', '5', ' ', ' '}, // {'1', ' ', ' ', '3', ' ', ' ', ' ', ' ', ' '}, // };//中级 char[][] board = { {' ', ' ', '8', '9', ' ', ' ', ' ', '7', ' '}, {' ', '5', '3', ' ', ' ', ' ', ' ', ' ', ' '}, {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '}, {'7', '6', ' ', '1', ' ', ' ', ' ', '9', ' '}, {'2', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '}, {' ', ' ', ' ', ' ', '8', ' ', ' ', ' ', ' '}, {' ', ' ', ' ', ' ', '2', ' ', '8', ' ', '5'}, {'4', ' ', ' ', ' ', ' ', '7', ' ', ' ', ' '}, {' ', ' ', ' ', ' ', ' ', ' ', '3', ' ', ' '}, };//大师 Map<Integer, List<Character>> unsolve = initUnsolveMap(board); System.out.println("需求解数独:"); printArray(board); System.out.println(recursion(board, unsolve)); } //常规求解 private static String solve(char[][] board, Map<Integer, List<Character>> unsolve) { boolean change = false; /*唯一余数法*/ //检查每个格横,纵,九宫格的重复数字 for (Integer integer : unsolve.keySet()) { boolean thisChange = false; List<Character> resX = checkX(board, unsolve, integer); if (resX.size() > 0) { thisChange = true; } List<Character> resY = checkY(board, unsolve, integer); if (resY.size() > 0) { thisChange = true; } List<Character> resC = checkCube(board, unsolve, integer); if (resC.size() > 0) { thisChange = true; } if (thisChange) { change = true; } } //将筛选过一次后的唯一可能单元格确定下来 List<Integer> needRemove = new ArrayList<Integer>(); for (Integer integer : unsolve.keySet()) { List<Character> integers = unsolve.get(integer); if (integers.size() == 1) { board[integer / 9][integer % 9] = integers.get(0); needRemove.add(integer); } if (integers.size() == 0) { return FAIL; } } //将已求解的单元格剔除 for (Integer integer : needRemove) { unsolve.remove(integer); } /*摒除法*/ for (char c = '1'; c <= '9'; c++) { boolean thisChange = eliminateXMethod(board, unsolve, c); if (thisChange) change = true; boolean thisChange2 = eliminateYMethod(board, unsolve, c); if (thisChange || thisChange2) change = true; } if (change) { return solve(board, unsolve); } System.out.println("常规求解结果:"); printArray(board); if (unsolve.size() == 0) { if (isValidBoard(board)) { System.out.println("本次结果正确"); return SUCCESS; } else { System.out.println("本次结果错误"); return FAIL; } } else { return UNDONE; } } //判断当前数独是否符合要求 private static boolean isValidBoard(char[][] board) { //检查行是否有重复数字 for (int i = 0; i < 9; i++) { int sum = 0; for (int j = 0; j < 9; j++) { sum += Integer.valueOf(String.valueOf(board[i][j])); } if (sum != 45) return false; } //检查列是否有重复数字 for (int i = 0; i < 9; i++) { int sum = 0; for (int j = 0; j < 9; j++) { sum += Integer.valueOf(String.valueOf(board[j][i])); } if (sum != 45) return false; } //检查单元格内是否有重复数字 for (int i = 0; i < 9; i += 3) { for (int j = 0; j < 9; j += 3) { int sum = 0; for(int x = i; x < i + 3; x++){ for(int y = j; y < j + 3; y++){ sum += Integer.valueOf(String.valueOf(board[x][y])); } } if(sum != 45) return false; } } return true; } //获取最小可能性单元格的数独集合 private static List<char[][]> getGuessBoards(char[][] board, Map<Integer, List<Character>> unsolve) { //定义最小可能的单元格可能解的个数 Integer minUnsolveCell = 9; Integer minUnsolveCellIndex = 0; //遍历每个单元格找到最小解单元格 for (Integer integer : unsolve.keySet()) { if (unsolve.get(integer).size() < minUnsolveCell) { minUnsolveCell = unsolve.get(integer).size(); minUnsolveCellIndex = integer; } if (minUnsolveCell == 2) break; } List<Character> possibleKeys = unsolve.get(minUnsolveCellIndex); List<char[][]> boards = new ArrayList<char[][]>(); for (Character possibleKey : possibleKeys) { char[][] newBoard = new char[9][9]; for (int i = 0; i < 9; i++) { System.arraycopy(board[i], 0, newBoard[i], 0, 9); } newBoard[minUnsolveCellIndex / 9][minUnsolveCellIndex % 9] = possibleKey; boards.add(newBoard); } return boards; } //递归猜测结果 private static String recursion(char[][] board, Map<Integer, List<Character>> unsolve) { String status = solve(board, unsolve); if (status.equals(UNDONE)) {//如果当前为无解状态,则进行假设求解 System.out.println("开始进行猜测求解:"); List<char[][]> boards = getGuessBoards(board, unsolve);//获取假设集合 for (char[][] chars : boards) { System.out.println("本次猜测求解的数独为:"); printArray(chars); String newStatus = recursion(chars, initUnsolveMap(chars));//对假设后的某一种可能性进行常规求解 if (newStatus.equals(SUCCESS)) { for (int i = 0; i < 9; i++) { System.arraycopy(chars[i], 0, board[i], 0, 9); } return SUCCESS; } } return FAIL; } return status; } //摒除法 /*摒除法:用数字去找单元内唯一可填空格,称为摒除法。例如9这个数字,在第一行和第二行都出现过了, 那第三行的9一定不会在前2行出现过的宫格(9个格子的小方块)中,所以只剩下一个宫格的第三行会出现9,
评论
    相关推荐
    • 数独求解器Java
      数独求解器Java
    • JS实现数独求解算法
      非暴力尝试,利用数独规则计算后选数,选择最少方案格子进行填写 示例给出了芬兰数学家三个月做出的“世界最难数独”作为例子,用非ie浏览器运行时间在200ms以内 简单数独时间更少
    • 数独求解程序
      数独求解程序,可以求出所有的解,并且算法效率很高在理想时间内求解出所有结果。
    • sudoku:数独求解器使用回溯
      数独求解器使用回溯 基本上在数独中,我们希望能够在给定这样输入的情况下解决数独难题,它代表了数独板: [[x00, x01, x02, x03... x08], [x10, x11, x12, x13... x18], ... [x80, x81, x82, x83... x88]] 这些...
    • 数独求解文件
      数独求解小程序 欢迎对数独有兴趣的同学使用,谢谢浏览!
    • 基准数独求解器:对各种数独求解器进行基准测试-matlab开发
      在文件交换中提交了 20 多个数独求解器。 该软件包为各种 MATLAB 数独求解器提供了基准。 基准测试是通过将性能(正确性和计算时间)与基准求解器 YA​​SS(Yet Another Sudoku Solver,从作者的 GUI 求解器 ...
    • 数独求解源代码
      数独求解C/C++源代码
    • 数独求解算法
      自己写的一个求解数独的算法,对此有兴趣的朋友可以交流下。自己调试没什么问题,不知道经不经得起别人的考验。
    • 数独求解算法
      此算发求解数独好快 大概也就几百次的循环 目前只能求解有唯一解的数独 进行一定优化后可求解多解数独 有好大的研究价值
    • 数独求解程序
      C#语言 回溯法求解数独 因为是初学者写的不太好