分治回溯---数独

数独

如图，一个9*9的方阵，格子中可以填1-9，每一行不能有相同的数字，每一列也不能有相同的数字，同时每一个小的九宫格也不能有相同的数字

像上图这样我们可以表示成

5 3 0 0 7 0 0 0 0 
6 0 0 1 9 5 0 0 0 
0 9 8 0 0 0 0 6 0 
8 0 0 0 6 0 0 0 3 
4 0 0 8 0 3 0 0 1 
7 0 0 0 2 0 0 0 6 
0 6 0 0 0 0 2 8 0 
0 0 0 4 1 9 0 0 5 
0 0 0 0 8 0 0 7 9 

需要填数字格子可以用0去表示
在编写代码前，我们需要去解决几个问题
9*9的方格我们将他们存储在一个二维数组中
其中行列的范围都是0-8

在进行解决问题时，我们第一步需要去判断改格子是否为0，是的话再进行填字，不是的话我们需要对下一个格子进行判断

如果是0，我们则对改格子进行赋值，从1-9依次去赋值，判断可以不，可以的话进行下一个格子判断，如果下一个格子将1-9都填了一遍都不行，那么就会回退到上一个状态，并将当前格子进行清零，然后上一个状态再继续进行填格子

当对下一个格子进行判断时，如果下一个格子和当前格子是在同一行，那么行不变，列加一即可，但是如果当前格子在行的最后一个，那么下一个格子位置就是行加1，列置为0

row + (col + 1) / 9, (col + 1) % 9

判断九宫格内元素是否相同时
九宫格的行和列的范围是：0-2,3-5,6-8

int rowMin = (row / 3) * 3; // 4
int rowMax = rowMin + 2;int colMin = (col / 3) * 3;
int colMax = colMin + 2;

package p4.分治回溯;import java.io.*;
//数独
public class Sudoku {private static int i = 0;private static int[][] board = new int[9][9];public static void main(String[] args) throws IOException {readFile("sudoku_data_01.txt"); // 将文件中的数据读取存储在board中solve(0, 0);// 从0,0这个位置开始填数独,进行解题}//求解x-y格子的解 再继续向下递归求解下一个格子//本质求多个解 但实际 数独问题只能有一个解 如果没解 程序啥也不输出！private static void solve(int row, int col) {if (row == 9) { // 角标是0-8i++;System.out.println("===========" + i + "==========");printBoard();//System.exit(0);} else {if (board[row][col] == 0) {//需要填数字1~9for (int num = 1; num <= 9; num++) {if (!isExist(row, col, num)) {board[row][col] = num; //8//解决下一个格子solve(row + (col + 1) / 9, (col + 1) % 9);}//如果此处没解 必须清零board[row][col] = 0;}} else {//已经存在一个已知数字 直接跳过去解决下一个格子solve(row + (col + 1) / 9, (col + 1) % 9);}}}private static boolean isExist(int row, int col, int num) {//同行for (int c = 0; c < 9; c++) {if (board[row][c] == num) {return true;}}//同列for (int r = 0; r < 9; r++) {if (board[r][col] == num) {return true;}}//同九宫 3*3int rowMin = (row / 3) * 3; // 4int rowMax = rowMin + 2;int colMin = (col / 3) * 3;int colMax = colMin + 2;for (int r = rowMin; r <= rowMax; r++) {for (int c = colMin; c <= colMax; c++) {if (board[r][c] == num) {return true;}}}return false;}private static void readFile(String fileName) throws IOException {File file = new File(fileName);FileReader fr = new FileReader(file);BufferedReader br = new BufferedReader(fr);String line = null;int row = 0;while ((line = br.readLine()) != null) {for (int col = 0; col < 9; col++) {board[row][col] = Integer.parseInt(line.charAt(col) + "");}row++;}}private static void printBoard() {for (int i = 0 ; i < 9; i++) {for (int j = 0; j < 9; j++) {System.out.print(board[i][j] + " ");}System.out.println();}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！