DFS算法

一般步驟

void dfs(int step)
{
	if(边界成立)
	{
		走到最深处
		。。。。。。
		return;
	}
	for(尝试每一种可能的状态)
	{
		if(如果这种状态可行){  //剪枝
            把这种可能的状态标记，表示走过 
            继续下一步dfs(step+1)   //状态转移
            把这种标记去除  //回溯
		}
	}
}

训练

N-皇后问题

问题

n−n−皇后问题是指将 nn 个皇后放在 n×nn×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现在给定整数 nn，请你输出所有的满足条件的棋子摆法。

输入格式

共一行，包含整数 nn。

输出格式

每个解决方案占 nn 行，每行输出一个长度为 nn 的字符串，用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后，输出一个空行。

注意：行末不能有多余空格。

输出方案的顺序任意，只要不重复且没有遗漏即可。

数据范围

1≤n≤91≤n≤9

输入样例

4

输出样例

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

答案

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static Scanner scanner = new Scanner(System.in);
	static int n;
	static int[] rec;
	static int ans = 0;

	static boolean cheak(int col, int row) { // 判断当前位置是否可以放皇后
		for (int i = 0; i < row; i++) {
			if (rec[i] == col || (i + rec[i] == row + col) || (rec[i] - i == col - row)) {
				return false;
			}
		}
		return true;
	}

	static void outPut() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (j == rec[i]) {
					System.out.print("Q");
				} else {
					System.out.print(".");
				}
			}
			System.out.println();
		}
	}

	static void DFS(int row) {
		if (row == n) {  
			outPut();
			System.out.println();
			return;
		}
		for (int col = 0; col < n; col++) {
			if (cheak(col, row)) { 
				rec[row] = col;
				DFS(row + 1);
				rec[row] = -1; // 回溯
			}
		}

	}

	public static void main(String[] args) {
		n = scanner.nextInt();
		rec = new int[n];
		Arrays.fill(rec, -1);
		DFS(0);
	}

}

数独

问题

数独是一种传统益智游戏，你需要把一个 9×99×9 的数独补充完整，使得图中每行、每列、每个 3×33×3 的九宫格内数字 1∼91∼9 均恰好出现一次。

请编写一个程序填写数独。

输入格式

输入包含多组测试用例。

每个测试用例占一行，包含 8181 个字符，代表数独的 8181 个格内数据（顺序总体由上到下，同行由左到右）。

每个字符都是一个数字（1−91−9）或一个 .（表示尚未填充）。

您可以假设输入中的每个谜题都只有一个解决方案。

文件结尾处为包含单词 end 的单行，表示输入结束。

输出格式

每个测试用例，输出一行数据，代表填充完全后的数独。

输入样例

4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end

输出样例

417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936

答案

import java.util.Scanner;

public class Main {
	static Scanner scanner = new Scanner(System.in);
	static char[][] table = new char[9][9];

	static void DFS(int x, int y) {
		if (x == 9) {
			outPut();
			return;
		}
		if (table[x][y] == '.') { // 当前位置可以填数
			for (int i = 1; i < 10; i++) {
				if (cheak(x, y, i)) { // 检查当前填入这个数字是否合理
					table[x][y] = (char) ('0' + i);
					DFS(x + (y + 1) / 9, (y + 1) % 9);
					table[x][y] = '.'; // 回溯
				}
			}
		} else { // 当前位置有数
			DFS(x + (y + 1) / 9, (y + 1) % 9);
		}
	}

	static boolean cheak(int x, int y, int num) {
		// 检擦同行同列
		for (int l = 0; l < 9; l++) {
			if (table[x][l] == (char) ('0' + num))
				return false; // 同行检查
			if (table[l][y] == (char) ('0' + num))
				return false; // 同列检查
		}
		// 检查小九宫格
		for (int l = (x / 3) * 3; l < (x / 3 + 1) * 3; l++) {
			for (int m = (y / 3) * 3; m < (y / 3 + 1) * 3; m++) {
				if (table[l][m] == (char) ('0' + num))
					return false;
			}
		}
		return true;
	}

	static void outPut() {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				System.out.print(table[i][j]);
			}

		}
	}

	public static void main(String[] args) {
		String string = scanner.nextLine();
		while (string.equals("end") == false) {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					table[i][j] = string.charAt(i * 9 + j);
				}
			}
			string = scanner.nextLine();
			DFS(0, 0);
			System.out.println();
		}

	}

}

注：思路正确，但是超时了，在剪枝处还可以再优化处理

结语

如果你发现文章有什么问题，欢迎留言指正。
如果你觉得这篇文章还可以，别忘记点个赞加个关注再走哦。
如果你不嫌弃，还可以关注微信公众号———梦码城（持续更新中）。
梦码在这里感激不尽！！