回溯法數獨題。

import java.util.Scanner;public class Sudoku {public static void main(String[] args) {// Read a Sudoku puzzleint[][] grid = readAPuzzle();if (!isValid(grid))System.out.println("Invalid input");else if (search(grid)) {System.out.println("The solution is found:");printGrid(grid);} elseSystem.out.println("No solution");}/** * Read a Sudoku puzzle from the keyboard */public static int[][] readAPuzzle() {//todoScanner input = new Scanner(System.in);int[][] grid = new int[9][9];for (int i=0;i<grid.length;i++)for (int j=0;j<grid[i].length;j++){grid[i][j] = input.nextInt();}return grid;}/** * Obtain a list of free cells from the puzzle */public static int[][] getFreeCellList(int[][] grid) {//todoint row = 0;for (int i=0;i<grid.length;i++) {for (int j = 0; j < grid[i].length; j++) {if (grid[i][j] == 0)row++;}}int[][] freeCellList = new int[row][2];int k = 0;for (int i=0;i<grid.length;i++){for (int j=0;j<grid[i].length;j++){if (grid[i][j] == 0){freeCellList[k][0] = i;freeCellList[k][1] = j;k++;}}}return freeCellList;}/** * Print the values in the grid */public static void printGrid(int[][] grid) {//todofor (int i=0;i<grid.length;i++){for (int j=0;j<grid[i].length;j++){System.out.printf("%3d",grid[i][j]);}System.out.println();}}/** * Search for a solution */public static boolean search(int[][] grid) {//todoint[][] freeCellList = getFreeCellList(grid);if (freeCellList.length == 0)return true;int k = 0;while (true){int i = freeCellList[k][0];int j = freeCellList[k][1];if (grid[i][j]==0)grid[i][j] = 1;if (isValid(i,j,grid)){if (k+1 == freeCellList.length)return true;else{k++;}}else{if (grid[i][j]<9)grid[i][j]++;else{while (grid[i][j]==9){if (k==0)return false;grid[i][j] = 0;k--;i = freeCellList[k][0];j = freeCellList[k][1];}grid[i][j]++;}}}}/** * Check whether grid[i][j] is valid in the grid */public static boolean isValid(int i, int j, int[][] grid) {//todofor (int row=0;row<grid[i].length;row++){if (row!=i&&grid[row][j]==grid[i][j])return false;}for (int col=0;col<grid.length;col++){if (col!=j && grid[i][col]==grid[i][j])return false;}for (int a=i/3;i<i/3+3;i++){for (int b=j/3;j<j/3+3;j++){if (a!=i && b!=j && grid[a][b]==grid[i][j])return false;}}return true;}/** * Check whether the fixed cells are valid in the grid */public static boolean isValid(int[][] grid) {//todofor (int i=0;i<grid.length;i++){for (int j=0;j<grid[i].length;j++){if (grid[i][j]<0 || grid[i][j]>9 || (grid[i][j]!=0 && !isValid(i,j,grid)))return false;}}return true;} }

一題寫了我一天且火大的java作業。

總結

以上是生活随笔為你收集整理的Java 数独题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。