递归回溯算法完成数独求解。
“数独”是一种智力游戏，一般认为起源于“正交拉丁方”，经日本人推广后风靡全球。如下图是一个数独的示例，玩家需要根据 9 × 9 盘面上的已知数字，推理出所有剩余空格的数字，并且满足每一行、每一列、每一个同色九宫内的数字均含1~9 不重复：
数独的答案一般都是唯一的，如果有多个解也称为无解。
思路：虽说原题目要我们递归 = =，但是偷懒 写出递归就会写非递归，dfs暴力，从左到右 从上往下开始搜索
import java.util.Scanner;public class c3_3 {public static int[][] qp = new int[9][9];public static Boolean t = false;public static void main(String[] args) {// TODO Auto-generated method stubint[][] qp = new int[9][9];//初始化矩阵chushi();dfs(0,0);}private static void dfs(int x, int y) {if(x==9 || y == 9) {return;}//判断是否棋盘给了初始值if(qp[x][y] != 0) {if(y==8) {dfs(x+1, 0);}else {dfs(x, y+1);}}else {//暴力for(int i = 1; i < 10; i++) {if(panduan(x,y,i)) {qp[x][y] = i;//System.out.println("("+x+","+y+")"+":"+qp[x][y]);if(x == 8 && y == 8) {t = true;for(int a = 0; a < 9; a++) {for(int b = 0; b < 9; b++) {System.out.print(qp[a][b]+" ");}System.out.println();}return;}if(y==8) {dfs(x+1, 0);qp[x][y] = 0;}else {dfs(x, y+1);qp[x][y] = 0;}}if(t) {return;}}}return;}private static boolean panduan(int x, int y, int z) {//横向判断for(int i = 0; i < 9; i++) {if(qp[x][i] == z) {return false;}}//纵向判断for(int i = 0; i < 9; i++) {if(qp[i][y] == z) {return false;}}//同一个方格判断if(x >= 0 && x < 3) {if(y >= 0 && y < 3) {for(int i = 0; i < 3; i++) {for(int j = 0; j < 3; j++) {if(qp[i][j] == z) {return false;}}}}else if(y >= 3 && y < 6){for(int i = 0; i < 3; i++) {for(int j = 3; j < 6; j++) {if(qp[i][j] == z) {return false;}}}}else {for(int i = 0; i < 3; i++) {for(int j = 6; j < 9; j++) {if(qp[i][j] == z) {return false;}}}}}else if(x >= 3 && x < 6) {if(y >= 0 && y < 3) {for(int i = 3; i < 6; i++) {for(int j = 0; j < 3; j++) {if(qp[i][j] == z) {return false;}}}}else if(y >= 3 && y < 6){for(int i = 3; i < 6; i++) {for(int j = 3; j < 6; j++) {if(qp[i][j] == z) {return false;}}}}else {for(int i = 3; i < 6; i++) {for(int j = 6; j < 9; j++) {if(qp[i][j] == z) {return false;}}}}}else {if(y >= 0 && y < 3) {for(int i = 6; i < 9; i++) {for(int j = 0; j < 3; j++) {if(qp[i][j] == z) {return false;}}}}else if(y >= 3 && y < 6){for(int i = 6; i < 9; i++) {for(int j = 3; j < 6; j++) {if(qp[i][j] == z) {return false;}}}}else {for(int i = 6; i < 9; i++) {for(int j = 6; j < 9; j++) {if(qp[i][j] == z) {return false;}}}}}return true;}private static void chushi() {qp[0][2] = 5;qp[0][3] = 3;qp[1][0] = 8;qp[1][7] = 2;qp[2][1] = 7;qp[2][4] = 1;qp[2][6] = 5;qp[3][0] = 4;qp[3][5] = 5;qp[3][6] = 3;qp[4][1] = 1;qp[4][4] = 7;qp[4][8] = 6;qp[5][2] = 3;qp[5][3] = 2;qp[5][7] = 8;qp[6][1] = 6;qp[6][3] = 5;qp[6][8] = 9;qp[7][2] = 4;qp[7][7] = 3;qp[8][5] = 9;qp[8][6] = 7;}}
