数独程序求解世界最难数独——JAVA版

news/2024/11/14 14:08:35/

目录

  • 号称世界最难的数独
  • 程序源码
  • 运行结果
  • 答案

号称世界最难的数独

在这里插入图片描述

程序源码

import java.util.ArrayList;
import java.util.HashSet;public class Main {private static final int MAX_GUESS_COUNT = 4096;private static int guessCount = 0;private static long startTime;private static void guessOneUnit(Sudoku sudoku) {if (++guessCount > MAX_GUESS_COUNT) {System.err.println("sudoku can't find the answer after " + guessCount + " times' guess so have to exit");sudoku.printEx(true);long endTime = System.currentTimeMillis();System.out.println("sudoku costs " + (endTime - startTime) + "ms to analyze this problem");System.exit(-1);}Sudoku.UnitToGuess unitToGuess = sudoku.fetchOneUnitToGuess();if (unitToGuess == null) {sudoku.printEx(true);System.err.println("sudoku enter a impossible situation and has to exit");return;}for (Integer e : unitToGuess.getOnes()) {Sudoku sudokuNew = sudoku.clone();sudokuNew.setOneUnit(unitToGuess.getRowIndex(), unitToGuess.getColIndex(), e);sudokuNew.printEx(true);if (sudokuNew.setUnitLoop()) {guessOneUnit(sudokuNew);}}}public static void solve(String input) {String[] lines = input.split("\\n");int[][] matrix = new int[Sudoku.LINE_UNIT_COUNT][Sudoku.LINE_UNIT_COUNT];for (int i = 0; i < Sudoku.LINE_UNIT_COUNT; ++i) {String[] units = lines[i].split(",");for (int j = 0; j < Sudoku.LINE_UNIT_COUNT; ++j) {matrix[i][j] = Integer.parseInt(units[j]);}}Sudoku sudoku = new Sudoku(matrix);sudoku.print("----------------original sudo matrix----------------");sudoku.initArray();sudoku.printEx(true);sudoku.setUnitLoop();guessOneUnit(sudoku);}public static class Sudoku implements Cloneable {public static final int LINE_MATRIX_UNIT_COUNT = 3;public static final int MATRIX_LINT_UNIT_COUNT = LINE_MATRIX_UNIT_COUNT;public static final int LINE_MATRIX_COUNT = LINE_MATRIX_UNIT_COUNT;public static final int MATRIX_UNIT_COUNT = LINE_MATRIX_UNIT_COUNT * LINE_MATRIX_UNIT_COUNT;public static final int LINE_UNIT_COUNT = MATRIX_UNIT_COUNT;public static final int PRINT_STEP_COUNT = 2000;private int[][] matrix;private ArrayList<Integer>[][] matrixEx;private HashSet<Integer>[] matrixRow;private HashSet<Integer>[] matrixCol;private HashSet<Integer>[][] matrixBlocks;private int finish;private int effective;private int empty;private static int index = 0;public Sudoku() {this(new int[LINE_UNIT_COUNT][LINE_UNIT_COUNT]);}public Sudoku(int[][] matrix) {this.finish = 0;this.effective = 0;this.empty = LINE_UNIT_COUNT * LINE_UNIT_COUNT;this.matrix = new int[LINE_UNIT_COUNT][LINE_UNIT_COUNT];this.matrixEx = new ArrayList[LINE_UNIT_COUNT][LINE_UNIT_COUNT];this.matrixRow = new HashSet[LINE_UNIT_COUNT];this.matrixCol = new HashSet[LINE_UNIT_COUNT];this.matrixBlocks = new HashSet[LINE_MATRIX_COUNT][LINE_MATRIX_COUNT];for (int i = 0; i < LINE_UNIT_COUNT; ++i) {for (int j = 0; j < LINE_UNIT_COUNT; ++j) {this.matrix[i][j] = matrix[i][j];this.matrixEx[i][j] = new ArrayList<>();if (matrix[i][j] != 0) {--this.empty;++this.finish;}}}for (int k = 0; k < LINE_UNIT_COUNT; ++k) {matrixRow[k] = new HashSet<>();matrixCol[k] = new HashSet<>();}for (int i = 0; i < LINE_MATRIX_COUNT; ++i) {for (int j = 0; j < LINE_MATRIX_COUNT; ++j) {matrixBlocks[i][j] = new HashSet<>();}}}public Sudoku clone() {Sudoku sudoku = new Sudoku();sudoku.empty = empty;sudoku.effective = effective;sudoku.finish = finish;for (int i = 0; i < LINE_UNIT_COUNT; ++i) {for (int j = 0; j < LINE_UNIT_COUNT; ++j) {sudoku.matrix[i][j] = matrix[i][j];for (Integer e : matrixEx[i][j]) {sudoku.matrixEx[i][j].add(e);}}}for (int k = 0; k < LINE_UNIT_COUNT; ++k) {for (Integer e : matrixRow[k]) {sudoku.matrixRow[k].add(e);}for (Integer e : matrixRow[k]) {sudoku.matrixRow[k].add(e);}}for (int i = 0; i < LINE_MATRIX_COUNT; ++i) {for (int j = 0; j < LINE_MATRIX_COUNT; ++j) {for (Integer e : matrixBlocks[i][j]) {sudoku.matrixBlocks[i][j].add(e);}}}return sudoku;}private ArrayList<Integer> getInitUnit() {ArrayList<Integer> unit = new ArrayList<>();for (int i = 1; i <= LINE_UNIT_COUNT; ++i) {unit.add(i);}return unit;}private ArrayList<Integer> getInitUnitWithValue(int i) {ArrayList<Integer> unit = new ArrayList<>();unit.add(i);return unit;}private void initArray() {for (int i = 0; i < LINE_UNIT_COUNT; ++i) {for (int j = 0; j < LINE_UNIT_COUNT; ++j) {if (matrix[i][j] != 0) {matrixEx[i][j] = getInitUnitWithValue(matrix[i][j]);matrixRow[i].add(matrix[i][j]);matrixCol[j].add(matrix[i][j]);matrixBlocks[i / LINE_MATRIX_UNIT_COUNT][j / LINE_MATRIX_UNIT_COUNT].add(matrix[i][j]);}}}for (int i = 0; i < LINE_UNIT_COUNT; ++i) {for (int j = 0; j < LINE_UNIT_COUNT; ++j) {if (matrix[i][j] == 0) {matrixEx[i][j] = getInitUnit();}}}}private void print(String title) {System.out.println(title);System.out.println("empty:" + empty + ",finish:" + finish + ",effective:" + effective);StringBuilder stringBuilder = new StringBuilder();for (int i = 0; i < LINE_UNIT_COUNT; ++i) {for (int j = 0; j < LINE_UNIT_COUNT; ++j) {if (matrix[i][j] != 0) {stringBuilder.append(" ").append(matrix[i][j]).append(" ");} else {stringBuilder.append("   ");}if (j != LINE_UNIT_COUNT - 1) {if (j % 3 == 2) {stringBuilder.append('║');} else {stringBuilder.append('│');}}}stringBuilder.append(System.lineSeparator());if (i != LINE_UNIT_COUNT - 1) {boolean isDouble = i % 3 == 2;printRowLine(isDouble, stringBuilder);}}stringBuilder.append(System.lineSeparator());System.out.println(stringBuilder);}private void printRowLine(boolean isDouble, StringBuilder stringBuilder) {String edge;char cross1;char cross2;if (isDouble) {edge = "═══";cross1 = '╪';cross2 = '╬';} else {edge = "───";cross1 = '┼';cross2 = '╫';}for (int i = 0; i < LINE_UNIT_COUNT; ++i) {stringBuilder.append(edge);if (i != LINE_UNIT_COUNT - 1) {if (i % LINE_MATRIX_UNIT_COUNT == 2) {stringBuilder.append(cross2);} else {stringBuilder.append(cross1);}}}stringBuilder.append(System.lineSeparator());}private void printEx(boolean force) {if (!force && ++index % PRINT_STEP_COUNT != 0) {return;}System.out.println("this is the " + index + "'th loop result");System.out.println("empty:" + empty + ",finish:" + finish + ",effective:" + effective);StringBuilder stringBuilder = new StringBuilder();for (int i = 0; i < LINE_UNIT_COUNT; ++i) {for (int l = 0; l < MATRIX_LINT_UNIT_COUNT; ++l) {for (int j = 0; j < LINE_UNIT_COUNT; ++j) {for (int k = 0; k < MATRIX_LINT_UNIT_COUNT; ++k) {int n = l * MATRIX_LINT_UNIT_COUNT + k + 1;if (matrixEx[i][j].contains(n)) {stringBuilder.append(" ").append(n).append(" ");} else {stringBuilder.append("   ");}}if (j != LINE_UNIT_COUNT - 1) {if (j % 3 == 2) {stringBuilder.append('║');} else {stringBuilder.append('│');}}}stringBuilder.append(System.lineSeparator());}if (i != LINE_UNIT_COUNT - 1) {boolean isDouble = i % 3 == 2;printRowLineEx(isDouble, stringBuilder);}}stringBuilder.append(System.lineSeparator());System.out.println(stringBuilder);}private void printRowLineEx(boolean isDouble, StringBuilder stringBuilder) {String edge;char cross1;char cross2;if (isDouble) {edge = "═══";cross1 = '╪';cross2 = '╬';} else {edge = "───";cross1 = '┼';cross2 = '╫';}for (int j = 0; j < LINE_UNIT_COUNT; ++j) {for (int k = 0; k < LINE_MATRIX_UNIT_COUNT; ++k) {stringBuilder.append(edge);}if (j != LINE_UNIT_COUNT - 1) {if (j % LINE_MATRIX_UNIT_COUNT == 2) {stringBuilder.append(cross2);} else {stringBuilder.append(cross1);}}}stringBuilder.append(System.lineSeparator());}private void finish() {print("sudoku has find one answer showed followed so will exit normally");long endTime = System.currentTimeMillis();System.out.println("sudoku costs " + (endTime - startTime) + "ms to analyze this problem");System.exit(0);}public static class UnitToGuess {private int rowIndex;private int colIndex;private ArrayList<Integer> ones = new ArrayList<>();public int getRowIndex() {return rowIndex;}public int getColIndex() {return colIndex;}public ArrayList<Integer> getOnes() {return ones;}public UnitToGuess(int rowIndex, int colIndex, ArrayList<Integer> ones) {this.rowIndex = rowIndex;this.colIndex = colIndex;for (Integer e : ones) {this.ones.add(e);}}}private boolean setOneUnit(int rowIndex, int colIndex, int element) {System.out.println("try to set unit[" + rowIndex + "," + colIndex + "]=" + element + " for next loop");return setUnit(false, rowIndex, colIndex, element);}public UnitToGuess fetchOneUnitToGuess() {int miniSize = MATRIX_UNIT_COUNT;int rowIndex = -1;int colIndex = -1;for (int i = 0; i < LINE_UNIT_COUNT; ++i) {for (int j = 0; j < LINE_UNIT_COUNT; ++j) {if (matrixEx[i][j].size() > 1 && matrixEx[i][j].size() < miniSize) {rowIndex = i;colIndex = j;miniSize = matrixEx[i][j].size();}}}if (rowIndex != -1 && colIndex != -1) {return new UnitToGuess(rowIndex, colIndex, matrixEx[rowIndex][colIndex]);}return null;}public boolean setUnitLoop() {while (true) {int lastEffective = effective;if (!setUnitOfOneSize() || !setUnitInBlock() || !setUnitInLine(true) || !setUnitInLine(false)) {printEx(true);return false;}if (empty == 0) {finish();}if (effective == lastEffective) {System.out.println("this removeLoop can't remove any more");break;}}return true;}private ArrayList<Integer> getUnit(boolean revert, int rowIndex, int colIndex) {return revert ? matrixEx[colIndex][rowIndex] : matrixEx[rowIndex][colIndex];}private boolean checkRight() {boolean flag = true;for (int i = 0; i < LINE_UNIT_COUNT; ++i) {for (int j = 0; j < LINE_UNIT_COUNT; ++j) {if (matrix[i][j] != 0) {for (int ii = i / LINE_MATRIX_UNIT_COUNT * LINE_MATRIX_UNIT_COUNT;ii < i / LINE_MATRIX_UNIT_COUNT * LINE_MATRIX_UNIT_COUNT + LINE_MATRIX_UNIT_COUNT; ++ii) {for (int jj = j / LINE_MATRIX_UNIT_COUNT * LINE_MATRIX_UNIT_COUNT;jj < j / LINE_MATRIX_UNIT_COUNT * LINE_MATRIX_UNIT_COUNT + LINE_MATRIX_UNIT_COUNT; ++jj) {if ((i != ii || j != jj) && matrix[i][j] == matrix[ii][jj]) {System.out.println("[" + i + ',' + j + "]=[" + ii + ',' + jj + "]=" + matrix[i][j]);flag = false;}}}for (int k = 0; k < LINE_UNIT_COUNT; ++k) {if (i != k && matrix[i][j] == matrix[k][j]) {System.out.println("[" + i + ',' + j + "]=[" + k + ',' + j + "]=" + matrix[i][j]);flag = false;}if (j != k && matrix[i][j] == matrix[i][k]) {System.out.println("[" + i + ',' + j + "]=[" + i + ',' + k + "]=" + matrix[i][j]);flag = false;}}}}}if (!flag) {System.out.println("sudoku's first guess is error and will try the other guess again");printEx(true);}return flag;}private boolean setUnit(boolean revert, int rowIndex, int colIndex, Integer e) {int i;int j;if (revert) {i = colIndex;j = rowIndex;} else {i = rowIndex;j = colIndex;}if (matrix[i][j] == 0 && matrixEx[i][j].contains(e)) {matrixEx[i][j].clear();matrixEx[i][j].add(e);matrix[i][j] = e;matrixRow[i].add(e);matrixCol[j].add(e);matrixBlocks[i / LINE_MATRIX_UNIT_COUNT][j / LINE_MATRIX_UNIT_COUNT].add(e);--empty;++finish;++effective;printEx(false);return checkRight();}return true;}private boolean setUnitInLine(boolean isRow) {boolean revert = !isRow;for (int j = 0; j < LINE_UNIT_COUNT; ++j) {int[] count = new int[LINE_UNIT_COUNT + 1];for (int i = 0; i < LINE_UNIT_COUNT; ++i) {for (int e : getUnit(revert, i, j)) {count[e]++;}}ArrayList<Integer> ones = new ArrayList<>();for (int k = 1; k <= MATRIX_UNIT_COUNT; ++k) {if (count[k] == 1) {ones.add(k);}}for (int e : ones) {for (int i = 0; i < LINE_UNIT_COUNT; ++i) {boolean flag = setUnit(revert, i, j, e);if (!flag) {return false;}}}}return true;}private boolean setUnitInBlock() {for (int i = 0; i < LINE_MATRIX_COUNT; ++i) {for (int j = 0; j < LINE_MATRIX_COUNT; ++j) {int[] count = new int[MATRIX_UNIT_COUNT + 1];for (int ii = 0; ii < LINE_MATRIX_UNIT_COUNT; ++ii) {for (int jj = 0; jj < LINE_MATRIX_UNIT_COUNT; ++jj) {int indexI = i * LINE_MATRIX_UNIT_COUNT + ii;int indexJ = j * LINE_MATRIX_UNIT_COUNT + jj;for (int e : matrixEx[indexI][indexJ]) {count[e]++;}}}ArrayList<Integer> ones = new ArrayList<>();for (int k = 1; k <= MATRIX_UNIT_COUNT; ++k) {if (count[k] == 1) {ones.add(k);}}for (int e : ones) {for (int ii = 0; ii < LINE_MATRIX_UNIT_COUNT; ++ii) {for (int jj = 0; jj < LINE_MATRIX_UNIT_COUNT; ++jj) {int indexI = i * LINE_MATRIX_UNIT_COUNT + ii;int indexJ = j * LINE_MATRIX_UNIT_COUNT + jj;boolean flag = setUnit(false, indexI, indexJ, e);if (!flag) {return false;}}}}}}return true;}private boolean setUnitOfOneSize() {for (int i = 0; i < LINE_UNIT_COUNT; ++i) {for (int j = 0; j < LINE_UNIT_COUNT; ++j) {if (matrix[i][j] == 0) {if (matrixEx[i][j].removeAll(matrixRow[i]) || matrixEx[i][j].removeAll(matrixCol[j])|| matrixEx[i][j].removeAll(matrixBlocks[i / LINE_MATRIX_UNIT_COUNT][j / LINE_MATRIX_UNIT_COUNT])) {if (effective > 1000) {System.out.println("may error occur");}++effective;}if (matrixEx[i][j].size() == 0) {return false;} else if (matrixEx[i][j].size() == 1) {boolean flag = setUnit(false, i, j, matrixEx[i][j].get(0));if (!flag) {return false;}}}}}return true;}}public static void main(String[] args) {startTime = System.currentTimeMillis();String input =  "8,0,0,0,0,0,0,0,0\n" +"0,0,3,6,0,0,0,0,0\n" +"0,7,0,0,9,0,2,0,0\n" +"0,5,0,0,0,7,0,0,0\n" +"0,0,0,0,4,5,7,0,0\n" +"0,0,0,1,0,0,0,3,0\n" +"0,0,1,0,0,0,0,6,8\n" +"0,0,8,5,0,0,0,1,0\n" +"0,9,0,0,0,0,4,0,0";
//                "0,0,0,1,0,2,0,0,0\n" +
//                "0,0,8,0,6,0,7,0,5\n" +
//                "0,9,0,0,0,0,0,8,0\n" +
//                "4,0,0,0,1,0,0,0,0\n" +
//                "0,8,0,3,0,4,0,6,0\n" +
//                "3,0,0,0,2,0,8,0,0\n" +
//                "0,6,0,0,0,5,4,7,0\n" +
//                "0,0,5,0,7,0,6,0,9\n" +
//                "0,7,0,0,0,0,0,5,0";
//                        "0,0,0,0,0,2,0,5,0\n" +
//                        "0,7,8,0,0,0,3,0,0\n" +
//                        "0,0,0,0,0,4,0,0,0\n" +
//                        "5,0,0,0,0,0,0,0,0\n" +
//                        "0,0,0,0,0,0,1,0,0\n" +
//                        "0,0,0,0,3,0,7,0,8\n" +
//                        "2,0,0,0,0,0,0,4,0\n" +
//                        "0,0,0,0,0,5,0,9,0\n" +
//                        "0,1,0,0,7,0,0,0,0";
//                "0,0,0,0,0,0,7,0,0\n" +
//                "0,4,0,0,3,0,0,6,5\n" +
//                "0,0,1,0,0,8,0,0,0\n" +
//                "0,6,0,0,5,0,0,3,9\n" +
//                "4,0,0,6,0,0,0,0,0\n" +
//                "0,0,0,0,0,0,0,2,0\n" +
//                "8,0,0,0,0,3,0,9,7\n" +
//                "0,0,0,0,7,0,4,0,0\n" +
//                "0,9,0,0,0,0,2,0,0";solve(input);}
}

运行结果

... ...this is the 2068'th loop result
empty:21,finish:60,effective:309│ 1       │    2    ║         │         │       3 ║         │         │         │         │         ║         │    5    │         ║       6 │ 4       │         8    │         │         ║ 7       │         │         ║         │         │       9 
─────────┼─────────┼─────────╫─────────┼─────────┼─────────╫─────────┼─────────┼─────────│         │       3 ║         │    2    │         ║ 1       │         │ 1       │ 4       │         ║       6 │         │         ║    5    │         │    5    9 │         │         ║         │         │    8    ║         │ 7       │         
─────────┼─────────┼─────────╫─────────┼─────────┼─────────╫─────────┼─────────┼─────────│         │         ║         │         │ 1       ║    2    │         │       3 6 │         │    5    ║ 4       │         │         ║         │         │         │ 7       │         ║         │       9 │         ║         │    8    │         
═════════╪═════════╪═════════╬═════════╪═════════╪═════════╬═════════╪═════════╪═════════1       │         │         ║    2  3 │       3 │         ║         │    2    │         │    5    │ 4     6 ║         │       6 │         ║         │         │ 4     6 │         │       9 ║         │    8    │ 7       ║    8    │       9 │         
─────────┼─────────┼─────────╫─────────┼─────────┼─────────╫─────────┼─────────┼─────────│       3 │         ║    2  3 │         │         ║         │    2    │ 1       │       6 │       6 ║         │ 4       │    5    ║         │         │       6 │    8    │       9 ║    8    │         │         ║ 7       │       9 │         
─────────┼─────────┼─────────╫─────────┼─────────┼─────────╫─────────┼─────────┼─────────2    │         │         ║ 1       │         │         ║         │       3 │         │       6 │ 4     6 ║         │       6 │         ║    5    │         │ 4  5  6 │    8    │ 7       ║         │    8    │       9 ║    8    │         │         
═════════╪═════════╪═════════╬═════════╪═════════╪═════════╬═════════╪═════════╪═════════│    2    │ 1       ║         │         │         ║       3 │         │         5    │         │         ║         │         │ 4       ║         │       6 │         │         │         ║       9 │ 7       │         ║         │         │    8    
─────────┼─────────┼─────────╫─────────┼─────────┼─────────╫─────────┼─────────┼─────────│       3 │         ║         │       3 │    2    ║         │ 1       │         4       │       6 │         ║    5    │       6 │         ║         │         │         │         │    8    ║         │         │         ║       9 │         │ 7       
─────────┼─────────┼─────────╫─────────┼─────────┼─────────╫─────────┼─────────┼─────────3 │         │         ║         │ 1       │         ║         │         │    2    │         │       6 ║         │         │       6 ║ 4       │    5    │         │       9 │ 7       ║    8    │         │         ║         │         │         try to set unit[1,4]=8 for next loop
this is the 2069'th loop result
empty:29,finish:52,effective:291│ 1       │    2    ║         │         │       3 ║         │         │         │         │         ║         │    5    │         ║       6 │ 4       │         8    │         │         ║ 7       │         │         ║         │         │       9 
─────────┼─────────┼─────────╫─────────┼─────────┼─────────╫─────────┼─────────┼─────────│         │       3 ║         │         │    2    ║ 1       │         │ 1       │ 4       │         ║       6 │         │         ║    5    │         │    5    9 │         │         ║         │    8    │    8    ║         │ 7       │         
─────────┼─────────┼─────────╫─────────┼─────────┼─────────╫─────────┼─────────┼─────────│         │         ║         │         │ 1       ║    2    │         │       3 6 │         │    5    ║ 4       │         │         ║         │         │         │ 7       │         ║         │       9 │         ║         │    8    │         
═════════╪═════════╪═════════╬═════════╪═════════╪═════════╬═════════╪═════════╪═════════1  2  3 │         │         ║    2  3 │    2  3 │         ║ 1       │    2    │ 1       │    5    │ 4     6 ║         │       6 │         ║         │         │ 4     6 │         │       9 ║    8    │    8    │ 7       ║    8    │       9 │         
─────────┼─────────┼─────────╫─────────┼─────────┼─────────╫─────────┼─────────┼─────────1  2  3 │       3 │         ║    2  3 │         │         ║         │    2    │ 1       │       6 │       6 ║         │ 4       │    5    ║         │         │       6 │    8    │       9 ║    8    │         │         ║ 7       │       9 │         
─────────┼─────────┼─────────╫─────────┼─────────┼─────────╫─────────┼─────────┼─────────2    │         │         ║ 1       │    2    │         ║         │       3 │         │       6 │ 4     6 ║         │       6 │         ║    5    │         │ 4  5  6 7       │    8    │ 7       ║         │    8    │       9 ║    8    │         │         
═════════╪═════════╪═════════╬═════════╪═════════╪═════════╬═════════╪═════════╪═════════│    2    │ 1       ║         │         │         ║       3 │         │         5    │         │         ║         │         │ 4       ║         │       6 │         │         │         ║       9 │ 7       │         ║         │         │    8    
─────────┼─────────┼─────────╫─────────┼─────────┼─────────╫─────────┼─────────┼─────────│       3 │         ║         │    2  3 │    2    ║         │ 1       │         4       │       6 │         ║    5    │       6 │       6 ║         │         │         │         │    8    ║         │         │         ║       9 │         │ 7       
─────────┼─────────┼─────────╫─────────┼─────────┼─────────╫─────────┼─────────┼─────────3 │         │         ║       3 │ 1       │         ║         │         │    2    │         │       6 ║         │         │       6 ║ 4       │    5    │         7       │       9 │ 7       ║    8    │         │    8    ║         │         │         sudoku has find one answer showed followed so will exit normally
empty:0,finish:81,effective:3438 │ 1 │ 2 ║ 7 │ 5 │ 3 ║ 6 │ 4 │ 9 
───┼───┼───╫───┼───┼───╫───┼───┼───9 │ 4 │ 3 ║ 6 │ 8 │ 2 ║ 1 │ 7 │ 5 
───┼───┼───╫───┼───┼───╫───┼───┼───6 │ 7 │ 5 ║ 4 │ 9 │ 1 ║ 2 │ 8 │ 3 
═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══1 │ 5 │ 4 ║ 2 │ 3 │ 7 ║ 8 │ 9 │ 6 
───┼───┼───╫───┼───┼───╫───┼───┼───3 │ 6 │ 9 ║ 8 │ 4 │ 5 ║ 7 │ 2 │ 1 
───┼───┼───╫───┼───┼───╫───┼───┼───2 │ 8 │ 7 ║ 1 │ 6 │ 9 ║ 5 │ 3 │ 4 
═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══5 │ 2 │ 1 ║ 9 │ 7 │ 4 ║ 3 │ 6 │ 8 
───┼───┼───╫───┼───┼───╫───┼───┼───4 │ 3 │ 8 ║ 5 │ 2 │ 6 ║ 9 │ 1 │ 7 
───┼───┼───╫───┼───┼───╫───┼───┼───7 │ 9 │ 6 ║ 3 │ 1 │ 8 ║ 4 │ 5 │ 2 sudoku costs 128ms to analyze this problem进程已结束,退出代码0

答案

在这里插入图片描述


http://www.ppmy.cn/news/563459.html

相关文章

小游戏制作-其他系列-数独

文章目录 游戏思路游戏代码游戏优化试玩路径 本文章是小游戏制作系列&#xff0c;其他系列-数独篇章 游戏思路 数独游戏的规律是&#xff0c;同一行&#xff0c;同一列&#xff0c;每3*3的9宫格中只能存在1-9的数字&#xff0c;不能重复。 步骤1&#xff1a;知道游戏规则之后&…

C语言实现数独游戏

一、功能&#xff1a; &#xff08;1&#xff09;输出排名 从文件中读出数据&#xff0c;保存在单链表中&#xff0c;并利用选择排序对数据进行排序后输出。 &#xff08;2&#xff09;开始游戏 进入该游戏系统后&#xff0c;系统先随机创建一个唯一解的数独&#xff0c;并解出…

数独游戏-C语言实现

数独游戏-C语言实现 目标 写一个数独游戏&#xff0c;有以下功能&#xff1a; 1&#xff1a;能随机产生题目并给出答案。 2&#xff1a;求解输入的题目并输出答案。 实现说明 参照百度百科等资料可以知道求解数独的主要算法是&#xff1a;1.通过行、列和宫格确定可填数字…

<<算法很美>>——(七)——DFS典题(二):数独游戏

目录 问题描述 问题分析 放码过来: 问题描述 如【图1.png】&#xff0c;玩家需要根据99盘面上的已知数字&#xff0c;推理出所有剩余空格的数字&#xff0c;并满足每一 行、每一列、每一个同色九宫内的数字均含1-9&#xff0c;不重复。 数独的答案都是唯一的&#xff0c;所…

数独出题与破解器

关于数独&#xff0c;我们应该并不陌生&#xff0c;这是个比较老牌的数字游戏&#xff0c;非常锻炼人的思维能力。 很多电影中描述主角牛逼&#xff0c;就是在空闲的时候&#xff0c;拿着报纸或者数独题库狂刷&#xff0c;以展现其高智商。 从此奠定了数独在数字游戏领域的大哥…

Java破解9X9数独小游戏

背景 最近刷到LeetCode上这道有趣的题目&#xff0c;想起了初中时候对数独的热爱&#xff0c;不禁感慨万分&#xff0c;原来这个用编程不到1m就能出结果&#xff0c;害我以前还浪费了这么多时间去研究。 效果 据说这是最难的数独题目【点此链接进入】&#xff0c;就拿它开刀…

C语言数独游戏求解

数独游戏的解法&#xff1a; 先将数独分为九个格子&#xff0c;用一个数组将每个小九宫格的候选数存放下来&#xff0c;将候选数挨个放进数独里的空位&#xff0c;如果这一行和这一列都没有这个数字&#xff0c;继续放入下一个&#xff0c;如果不能放入的话就回到上一步继续尝…

POJ2676数独游戏题解

第三次才AC我好菜 一道“简单”的问题。 Description Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smaller squares 3x3 as shown on the Figure. In some of the cells are written decimal digits from 1 to 9. The other c…