Now for something completely different, let’s do some work environment configuration. Here we will adapt the default I3 configuration to set it up not to interfere with tmux and Neovim shortcuts (more on configuring those two in later posts).

First a sidenote on starting I3: as with many minimalistic WMs, to get it to start you simply have to execute it from your .xinitrc. While I am at it I set it up to also launch my browser at the same time, since this is the very first thing I generally do anyway:

firefox &
exec /usr/bin/i3
exit 0

With the startup out of the way, we can focus on the actual configuration. The default location for the configuration file is ~/.config/i3/config at the time of this writing.

I personally use the Alt prefix for a lot of tmux commands: as a long time vim user the Alt + ijkl to swap between panes appeals to me for instance. I then decided to change I3’s default modifier to the Win (or Super, as you prefer) key. Note that Alt is referred to as Mod1 and Win as Mod4: this is because of how keypresses are handled by the OS.

set $mod Mod4 # from Mod1

As a former dwm user I still want to preserve some WM shortcuts on the Alt key however, which leads me to alter them manually at other points in the file:

bindsym Mod1+1 workspace 1
bindsym Mod1+2 workspace 2
bindsym Mod1+3 workspace 3
bindsym Mod1+4 workspace 4
bindsym Mod1+5 workspace 5
bindsym Mod1+6 workspace 6
bindsym Mod1+7 workspace 7
bindsym Mod1+8 workspace 8
bindsym Mod1+9 workspace 9
bindsym Mod1+0 workspace 10

bindsym Mod1+Return exec "st -f \\"Droid Sans Mono:size=14\\""
bindsym Mod1+Shift+q kill
bindsym Mod1+p exec "dmenu_run -fn \\"Droid Sans Mono:size=10\\""

Which brings us to another point: this is the place you should specify your terminal as well as various font parameters if you are so inclined. By default I3 uses a special i3-sensible-terminal command to determine which terminal to use, but as its name implies all it guarantees is a sensible terminal, not a practical or beautiful one.

One last quirk to sort out for my personal configuration was getting the Alt+Tab combination working for virtual desktop switching. The I3 developers are opposed to including it in the default configuration, and you even have to script the WM if you want window switching instead of desktop switching (you can find the developer-recommended script here). Anyway for our purpose what seems to be a legacy binding suffices:

bindsym Mod1+Tab workspace back_and_forth

Let us hope it does not end up removed in future versions.

Adjusting your personal environment should be done seldom and decisively: XKCD has a nice graphic representing the cut-off point for time spent optimizing effectively given a task’s length. Not that you should always strive for efficiency, aesthetic concerns are valid too when it comes to desktop configuration for instance, but then it is important to be honest with yourself and recognize you are not actually trying improve your productivity.

On that note, you can find my full configuration file in my GitHub config repository. Have fun customizing your tools!

In this post we will proceed to solve the classical 8 queens problem using Rust, and even put in some overtime to go up to N queens on a board of any given size. This problem is a prime example in which backtracking shines, and we will naturally use it.

Let’s start by implementing a basic chess board and a function to display it. Having a way to view your data structures is a good first step in any development project.

struct Board {
    width: usize,
    height: usize,
    queens: Vec<(usize, usize)>
}

impl Board {
    fn display(&self) {
        let mut squares = vec![vec![false; self.height]; self.width];

        for queen in &self.queens {
            let &(qi, qj) = queen;
            squares[qi][qj] = true;
        }

        for row in squares {
            let mut line = String::from("");
            for square in row {
                match square {
                    true => line += "Q ",
                    false => line += ". "
                }
            }
            println!("{}", line);
        }
    }
}

The display method lets us visualize the board in a crude but efficient way. For instance a board with queens in a8 and b6 will be represented this way:

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

Not the pinnacle of visual art but very helpful to manually validate solutions. Now we are all set to go through with implementing the solution to our problem. Let’s consider what we need. Conceptually, a backtracking algorithm relies on a recursive function that goes like this :

procedure backtrack(step):
	if incorrect(step) then return
	// No need to go deeper from the current state, we know we're off track anyway

	if correct(step) then output(state)
	// Yay, we found a solution!

	for next_step in followup(step):
		backtrack(next_step)

The core idea of backtracking is to take steps towards a possible solution until you find out the path you are following cannot be valid, and then move back to iterate over other paths until you either find a correct solution or conclude there is none. To go into more detail over the function used in the above pseudocode :

• The backtrack procedure evaluates each step of the way to determine what to do next : are we on a wrong path, did we find a solution, do we need to go deeper?
• The incorrect function straight up tells us whether there can be a good solution derived from our current state. If there is none we can just go back up and stop exploring this particular branch.
• The correct function is the one that can end the recursion successfully. It assesses whether the conditions of our problem are met at the current state, and if so lets us call the output function to communicate the solution we found.
• The followup function gives us all the possible steps following the one we are at. It lists all the directions we should explore next, so that we can call backtrack over them one at a time until we find a solution.

Enough explaining, let’s do it! The incorrect and correct functions are rather simple as long as you know how to check diagonals, so let’s start with them. (Tip: you can tell whether two chess pieces are on a same diagonal by checking if the differences in their horizontal and vertical positions are equal, which is what this code does.)

fn incorrect(board : &Board) -> bool {
    for queen in &board.queens {
        let &(qi, qj) = queen;
        for other_queen in &board.queens {
            let &(oi, oj) = other_queen;
            let h_diff = max(oi, qi) - min(oi, qi);
            let v_diff = max(oj, qj) - min(oj, qj);

            if oi == qi && oj == qj {
                continue;
            } else if oi == qi || oj == qj || h_diff == v_diff {
                return true;
            }
        }
    }

    return false;
}

fn correct(board : &Board, queen_number: usize) -> bool {
    if board.queens.len() == queen_number {
        return true;
    } else {
        return false;
    }
}

Now about the followup function, we have a slight problem; in its simpler form it would simply return a vector containing all boards with the previous queens plus a new one. But this approach would require us to store in memory a full board for each square at every backtracking step, which would be costly even at small board sizes. Maybe it would not make a noticeable difference in runtime for 8 queens, but it would still be better practice to go for a solution that scales better.

What we need is what is called a generator in Python, that is to say an object that behaves like an iterator by yielding elements in sequence but without computing and storing them all first. There is no syntax sugar for this in Rust but nothing stops us from implementing it: all we need is a structure to hold the current state of our generator and a next method updating it and returning elements one at a time.

struct BoardGenerator {
    initial_board: Board,
    i: usize,
    j: usize
}

impl BoardGenerator {
    fn next(&mut self) -> Option<Board> {
        self.j += 1;

        if self.j >= self.initial_board.height {
            self.i += 1;
            self.j = 0;
        }

        if self.i >= self.initial_board.width {
            return None;
        }

        match self.initial_board.queens.binary_search(&(self.i, self.j)) {
            Ok(_) => return self.next(),
            Err(idx) => {
                let mut next_board = Board::new(&self.initial_board);
                next_board.queens.insert(idx, (self.i, self.j));
                return Some(next_board);
            }
        }
    }
}

With that we are all set to complete our solver by putting the pieces together in the backtrack function, along a main function to call it:

fn backtrack(board : Board, queen_requirement: usize) -> Option<Board> {
    if incorrect(&board) { return None; }
    if correct(&board, queen_requirement) { return Some(board) }

    let mut generator = BoardGenerator::from(board);
    while let Some(next_board) = generator.next() {
        if let Some(solution) = backtrack(next_board, queen_requirement) {
            return Some(solution);
        }
    }

    return None;
}

fn main() {
    let board = Board { width: 8, height: 8, queens: vec![] };
    if let Some(solution) = backtrack(board, 8) {
        solution.display();
    } else {
        println!("No solution found.")
    }
}

And voila! A simple solver for an interesting problem. This configuration solves the 8 queen problem, but can also tackle larger or smaller ones simply by altering the initial board. The code of this program is available in a GitHub repository should you want to run it.

Bonus: an actual solution of the 8 queens problem!

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

Sometimes you come across stuff while browsing that make you ponder. You don’t have an use for them right away, but you’re not sure you’ll be able to find them again when you do. I used to use bookmarks to keep track of all these links, but I found out the hard way that they don’t always survive system migration very well. Archiving seems a better answer, and what better place for that than this wonderful blog?

So here comes my personal link collection for (possible) future use. I don’t expect it to be of use to anyone else, but if you want to you can have a look anyway!

Languages

• https://jekyllrb.com/docs/templates/
• https://eev.ee/blog/2012/04/09/php-a-fractal-of-bad-design/
• https://github.com/ashleygwilliams/rust-emergency-compliment
• https://github.com/rust-unofficial/patterns

Git

• http://tbaggery.com/2008/04/19/a-note-about-git-commit-messages.html

Here comes the first post of a brand new blog. I will be using this space to share advice about the tools and practices I use for programming day-to-day, as well as insights on the topics I work on. I hope some of those come in handy for you!