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，