回溯法解数独游戏问题

1.数独游戏：九宫格是在81个格子(9×9)中，要满足以下条件：① 每个横行和竖列中的9个格子都包含数字1～9，且不重复；② 每个黑色粗实线围住的9个格子(3×3)都包含数字1～9，且不重复。如图所示：

要求：找出给定数字的九宫格。

输入：输入9行9列81个数字，其中0表示要填的数字。

输出：输出满足条件的九宫格。

某测试样例如下：

import java.util.Scanner;

public class 数独游戏 {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = 9;
		int Sudoku[][] = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++)
				Sudoku[i][j] = in.nextInt();
		}
		backTrack(Sudoku, n * n, 0);//其中n*n，每一个单元格表示一层深度
	}

	static void backTrack(int[][] Sudoku, int N, int k) {//数独棋盘元素数组，最大单元格数，当前单元格数
		int x = k / 9;//0,0,0,0,0,0,0,0,0, 1,1,1,1...
		int y = k % 9;//0,1,2,3,4,5,6,7,8, 0,1,2,3...
		//由此遍历所有数独单元格
		if (k == N) {//搜索完毕，输出结果
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					System.out.print(Sudoku[i][j]+" ");
				}
				System.out.println();
			}
			return;
		}
		if (Sudoku[x][y] == 0) {//表示此单元格未填写
			for (int i = 1; i <= 9; i++) {//每个空格有0~9，9种可能
				Sudoku[x][y] = i;//逐个测试
				if (constraint1(Sudoku, x, y) && constraint2(Sudoku, x, y)) {//如果满足约束条件
					backTrack(Sudoku, N, k + 1);//才能深度搜索到下一个单元格
				}
				else { //不满足约束条件
					Sudoku[x][y] = 0;//回溯法将上一个单元格重置为0				
				}
			}
		} 
		else {//表示此单元格已填写，深度搜索下一个单元格
			backTrack(Sudoku, N, k + 1);
		}
	}

	private static boolean constraint1(int[][] Sudoku, int x, int y) {
		for (int i = 0; i < 9; i++) {
			if (Sudoku[x][i] == Sudoku[x][y] && i != y) {//搜索每一列中是否有重复数值
				return false;
			}
			if (Sudoku[i][y] == Sudoku[x][y] && i != x) {//搜索每一行中是否有重复数值
				return false;
			}
		}
		return true;
	}

	private static boolean constraint2(int[][] Sudoku, int x, int y) {
		for (int i = (x / 3) * 3; i < (x / 3) * 3 + 3; i++) {//九宫格中行的约束条件（(x / 3) * 3为九宫格第一行，加3为最后一行）
			for (int j = (y / 3) * 3; j < (y / 3) * 3 + 3; j++) {//九宫格中列的约束条件（(y / 3) * 3为九宫格第一列，加3为最后一列）
				if (Sudoku[i][j] == Sudoku[x][y]) {//出现重复数值
					if (i != x && j != y) {//不满足约束条件
						return false;						
					}
					else {
						continue;						
					}
				}
			}
		}
		return true;
	}
}