This next algorithm was really fun and a bit more challenging. The Algorithms book I’m going through went through several more examples of breaking a problem into a smaller, simpler problem and letting recursion CPU its way to a solution, like the merge sort we just looked at. Then I moved on to chapter 2 about “backtracking” into the n Queens Problem!
How Many Queens?
According to the book, the “n Queens Problem” is a prime example of using backtracking to solve a problem. Backtracking is another way to reduce a hard problem down into smaller chunks that are more easily solvable. In this case, showing the solution as it is worked out with a recursion tree model really explains well the approach used here. Go see page numbered 71 of the PDF to check it out. After just a couple of pages, Erickson moves on to the related topic of Game Trees, but this n Queens Problem seemed really fun to me.
I first wanted to try and show the solutions as text-based chessboards (plus allow for the boring array version showing one solution per line). It took me a little while to setup the Rust crate crossterm to help me out with this. I had only recently heard of crossterm while watching a YouTube video by David Pedersen as he codes up a simple Git helper with Rust. I didn’t go crazy with color or UTF-8 like I could have, but feel free.
Let’s Rust
Then came the matter of converting the algorithm pseudo code from the PDF into Rust code. This was slightly more difficult as Rust is very careful about array bounds checking and I had to be a little safer with my IF checks than the pseudo code warned about.
Since it is Creative Commons, I can include the pseudo-code presented in Jeff Erickson’s Algorithm book – but go check it out via his site!
When you run the queens_problem binary, you pass along an argument of how big your chessboard square is. Optionally you can include a second param (of anything, the code doesn’t really care) which causes it to output chessboards rather than the array dumps.
main.rs for queens_problem
use crossterm::{
style::{Color, Colors, Print, ResetColor, SetColors},
ExecutableCommand,
};
use std::env;
use std::io::stdout;
const QUEEN: &str = "<W>";
const EMPTY: &str = " ";
/// Adapted from reading "Algorithms" by Jeff Erickson
/// freely available on http://jeffe.cs.illinois.edu/teaching/algorithms/
pub fn main() {
let args: Vec<String> = env::args().collect();
// nothing fancy at all, just brute-force it
if args.len() < 2 || args.len() > 3 {
println!("Usage: {} n [show]", args[0]);
println!(" n = size of chessboard");
println!(" [show] to actually see each chessboard solution");
return;
}
let boardsize = args[1].parse::<usize>().unwrap();
let chessboard = vec![-1i8; boardsize];
let showboard = args.len() == 3; // don't even care what it is
place_queens(chessboard.clone(), 0, showboard);
}
fn show_chessboard(board: Vec<i8>, showboard: bool) {
let mut light: bool = true;
if showboard {
for pos in board.to_vec() {
for cell in 0..board.len() {
match (pos == cell as i8, light) {
(true, true) => draw_square(Colors::new(Color::Black, Color::Grey), QUEEN),
(true, false) => draw_square(Colors::new(Color::Grey, Color::Black), QUEEN),
(false, true) => draw_square(Colors::new(Color::Black, Color::Grey), EMPTY),
(false, false) => draw_square(Colors::new(Color::Grey, Color::Black), EMPTY),
};
light = !light;
}
println!();
if board.len() % 2 == 0 {
// to checkerboard even-sized boards
light = !light;
}
}
println!("\n");
} else {
let adjusted: Vec<i8> = board.iter().map(|&p| p + 1).collect(); // lets remove the 0-based confusion
println!("{:?}", adjusted);
}
}
fn draw_square(color: Colors, chesspiece: &str) {
let mut stdout = stdout();
stdout.execute(SetColors(color)).unwrap();
stdout.execute(Print(chesspiece)).unwrap();
stdout.execute(ResetColor).unwrap();
}
/// n Queens Problem
/// Section2.1, page 69-71
fn place_queens(mut chessboard: Vec<i8>, row: usize, showboard: bool) {
if row == chessboard.len() {
show_chessboard(chessboard.to_vec(), showboard);
return;
}
for column in 0..chessboard.len() {
let mut legal = true;
for cell in 0..row {
let pos = cell as usize;
if chessboard[pos] == (column as i8)
|| (column + row >= cell && chessboard[pos] == ((column + row - cell) as i8))
|| (column + cell >= row && chessboard[pos] == ((column + cell - row) as i8))
{
legal = false;
}
}
if legal {
chessboard[row] = column as i8;
place_queens(chessboard.clone(), row + 1, showboard);
}
}
}
Just a Hint of Verification
As nerdy as they look, I used the array dumps to validate my code against what Wiki article on the 8 Queens Puzzle has as the number of valid solutions for different sized boards. I verified a 4×4 up to 14×14 board and matched the expected counts perfectly. Go check out the README for this repo in Github.
The post Next Algorithm: Backtracking into the n Queens Problem appeared first on Learning Rust.
Top comments (0)