[[id_[[]5816]][[]]4002]]

“数独”是一种智力游戏。通常认为它起源于“正交拉丁方”。经日本人推广后，在全球范围内迅速流行起来。如下图所示，这是一个数独的示例。玩家要依据 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) {
		请提供需要改写的句子呀，你没有给出具体的内容呢。
		int[][] 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;
					输出括号内 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;
	}
}