解决 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());
		}
	}
}