Next Algorithm: Backtracking into the n Queens Problem
Tags: rust, learning, practice, algorithms
Published: 2020-07-17 13:02:16

---
title: Next Algorithm: Backtracking into the n Queens Problem
published: true
date: 2020-07-17 02:04:19 UTC
tags: Rust,Learning,Practice,algorithm
canonical_url: https://rust.graystorm.com/2020/07/16/next-algorithm-backtracking-into-the-n-queens-problem/
cover_image: https://rust.graystorm.com/wp-content/uploads/2019/06/plant-wood-old-rust-equipment-gear-1278587-pxhere.com_.jpg
---

![Chessboard showing a Queen... how would you function with multiple queens on the same board?.](https://i1.wp.com/rust.graystorm.com/wp-content/uploads/2020/07/board-wood-game-play-summer-recreation-454984-pxhere.com_.jpg?w=840&ssl=1)<figcaption>Stalking her prey…</figcaption>

This next algorithm was really fun and a bit more challenging. The [Algorithms book](http://jeffe.cs.illinois.edu/teaching/algorithms/) 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](https://rust.graystorm.com/2020/07/15/merge-sort-with-rust/) 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](https://crates.io/crates/crossterm) to help me out with this. I had only recently heard of crossterm while watching a [YouTube video](https://www.youtube.com/watch?v=YFzF1AHYjes&t=7563s) 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](http://jeffe.cs.illinois.edu/teaching/algorithms/)!

![](https://i1.wp.com/rust.graystorm.com/wp-content/uploads/2020/07/queens_problem.png?w=840&ssl=1)<figcaption><em>Figure 2.2, Page 71 from Algorithm by Jeff Erickson</em></figcaption>

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](https://en.wikipedia.org/wiki/Eight_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](https://github.com/jculverhouse/queens_problem).

The post [Next Algorithm: Backtracking into the n Queens Problem](https://rust.graystorm.com/2020/07/16/next-algorithm-backtracking-into-the-n-queens-problem/) appeared first on [Learning Rust](https://rust.graystorm.com).