» 随笔

解决 N 皇后问题

群里偶然聊起了面试考的算法题,提到了经典的 八皇后问题 。早在5年前就听说了 Sidekiq 作者面试 Facebook 不会解八皇后惨遭拒绝的都市传说,但一直没有自己解过。正好这段时间想学学 Rust,就用它练手吧!

题目的要求是在8*8的棋盘中放置8枚皇后,使得任何一枚皇后不能吃掉其他皇后,即任两枚皇后不能在同一行、列、对角线上。

刚上手是按棋盘的思路来解的,每个格子和落子位置都用一个坐标来表示,当时还沾沾自喜自己在每一轮递归中都把最近一次落子后不能再落子的格子去掉比暴力 for 循环省时间……

后来发现由于总共需落子的数量 n 等于棋盘的边长,因此每枚棋子所在行、列都只有它自己,也就是说其中一个维度上它们的坐标已经固定了,剩下的只是在从 1 到 n 的排列中找到符合条件的排列。下面就是写代码了。

/* 参数 nq: 要放置的皇后数量,也是棋盘边长。
 * 返回值:一组整数数组,每个数组表示一种纵坐标排列。
 */
fn solve_n_queens(nq: i32) -> Vec<Vec<i32>> {
	let mut queens_y = vec![]; /* 各枚皇后的纵坐标 */
	let mut solutions = vec![];

	/* 初始化填充,这里以1开始方便理解 */
	for _ in 0..nq {
		queens_y.push(1);
	}

	loop {
		/* 下面一段是给第一个坐标+1,然后进位 */
		queens_y[0] += 1;
		for i in 0..nq {
			let s_i = i as usize;
			if queens_y[s_i] > nq {
				if i < nq - 1 {
					queens_y[s_i] = 1;
					queens_y[s_i + 1] += 1;
				} else {
					/* 这里所有可能性都遍历完毕,可以返回了 */
					return solutions
				}
			}
		}

		/* 计算是否符合条件 */
		let mut is_solution = true;
		for i in 0..nq {
			let s_i = i as usize;
			for j in i + 1..nq {
				let s_j = j as usize;
				if queens_y[s_i] == queens_y[s_j] || (queens_y[s_i] - queens_y[s_j]).abs() == (i - j).abs() {
					is_solution = false;
					break;
				}
			}
		}
		if is_solution {
			solutions.push(queens_y.clone());
		}
	}
}

运行测试,对8个皇后能正确得出92种答案。