Block Fill Cracker

This is a fun math experiment and a good excuse to talk about Rust, math and algorithms :)

Description

This is a project meant to solve the "block fill" puzzles of the "Offline Games" Android app. I found the concept to be pretty fun and the underlying math behind solving the problem to be pretty interesting.

I think this game is a pretty good example of hamiltonian path in a graph and makes it pretty easy to understand.

This is how the game looks like:

An empty grid-like board with one blue tile

The goal is to start from the blue tile and find a path that goes through every tile of the board but only once. This is how the resolution looks like: The same board but with a path going from the original blue tile that goes through every tile

However those can be tough to find manually and immediatly when I found this I thought "that's an hamiltonian path!". And decided to build this small project to find solutions automatically.

Usage

To install the project run those commands, assuming you already have Rust and git installed.

git clone https://codeberg.org/SnowCode/block-fill-cracker
cd block-fill-cracker
cargo build --release

Then you need to edit the puzzle.txt file to contain a representation of the grid, each gap (where there is no tile) is represented by a space, each tile is represented by an x and the starting tile is represented by a X (uppercase).

Make sure that each line has the same width and you don't have any additional lines.

The default file contains the representation of the puzzle taken as example previously.

Finally, you can then run the project :

./target/release/block-fill-cracker

And you should get an output like this:

← ← ← ← ↑ → → → ↑ ← ↑ ← ← ← ↑ ↑ → ↑ ← ↑ → → ↓ → ↓ ← ↓ → → ↑ → ↑ ← ↑

And there you go! This is the sequence you need to enter in order to complete the puzzle :)

Mathematical and technical description

This project uses backtracking to construct an hamiltonian path from a given starting coordinate in a grid-like undirected graph structure.

How's that stupid game a graph ?

A graph in math is a structure that contains vertexes and edges connecting those vertexes. For instance a network is a graph where each machine is a vertex and each connection is an edge.

Another example is map, each place is a vertex and each road connecting places is an edge.

In this case, every tile is a vertex and their adjacency (vertically or horizontally) are the edges.

What is an hamiltoninan path ?

A hamiltonian path within a graph contains every vertex of the graph by only going through each of them once.

In this case we know that the puzzle contains a hamiltonian path and we know its starting point.

In order words, we need to make a path that goes through every tile only once and we already know where it starts.

How is this project structured ?

This project has 3 files :

• The graph module which is used to convert a grid to a graph and represent the graph
• The hamilton module which is used to construct the path in the graph using backtracking
• The main module which is used to read the puzzle file and convert the path to a set of directions

How to code a solution to a mathematical problem ?

I think this is an interesting part to note because it's something I struggle quite often with.

When given a mathematical problem such as "How to create this puzzle solver ?", it's hard to know even where to start and not get lost in code and bugs.

This is my personal method for tackling this issue:

1. Do your research

Search online for a more "abstract" version of your problem. For instance in this case "How to solve this puzzle?" becomes "How to find an hamiltonian path given I know its source?".

Basically the goal is to get the best possible understanding of the problem and possible ways to solve it. For instance I've came accross some explanation of "backtracking" that helped me to build my own version.

2. Create a small example and solve it on paper

Initially I tried to sketch a small example of problem like this that looks like that :

xxx
xX 

Then I tried to write down each step as I would do them as well as the collections.

/!\ THIS WON'T WORK /!\ SEE BELOW FOR MORE DETAILS
Add the starting point to the "next" list
As long as the next list is not empty:
 Add the last element of "next" and add it to the "path" list
 For each neighbor that's not already in the path:
 Add it to the next list
 If there is no neighbor and the size of the path is the same as the size of the graph:
 Return the path
 If there is no neighbor but the path is not complete:
 Remove the element from the path and continue on the next list

That's what I initially came up with, but quickly I noticed that it was impossible because in many cases I would end up looping on the same elements because when it backtracks it has no way to know which neighbor node has been visited or not.

So I decided to add a "nth" information to the next list. So every item in the list is a combinaison of the vertex AND the nth of its neighbors (so 0 would mean the first neighbor, 1 the second, etc).

So I continued trying to improve the algorithm and after a few tries I found this working pseudo code:

Add the starting point to the "next" list with a nth of 0 (first neighbor)
As long as the next list is not empty:
 Add the last element of "next" to the path
 Take the nth neighbor and add it to the next list
 If the neighbor doesn't exist AND the length of the path is the same as the size of the graph:
 The path has been found and is returned
 Else, if the neighbor doesn't exist BUT the path is not complete:
 Remove the last two elements of the path
 Remove the last element of the "next" list
 Increment the nth of the last element (asking them to skip 1 more neighbor)

Once the algorithm passed my "brain test" we can start coding...

3. Creating the structure of the program

So now that I know the algorithm I need to know how the program is going to be structured in order to not have everything in one big gliberish.

For this I think about everything that needs to be done in the graph:

• Create the graph from a text file
• Add vertexes and edges
• Know the neighbors of a vertex
• Know the size of the graph
• Find the hamilton path
• Know which elements to visit and the current path

Then I try to group those "responsibilities" in different "modules" (or classes in other languages).

• Graph : Creates itself from a text file, can add vertexes and edges to itself, knows the neighbors of a vertex and its size
• Hamilton : Build the path on the graph

// graph.rs
usestd::collections::{HashMap,HashSet};/// A vertex is defined as a (x, y) coordinate in the graph
pubtype Vertex=(usize,usize);/// Representation of an undirected graph 
pubstruct Graph{neighbors: HashMap<Vertex,HashSet<Vertex>>,}implGraph{/// Create a new empty graph
pubfn new()-> Self{neighobrs: HashMap::new(),}/// Get the set of neighbor vertexes of a given vertex in the graph
pubfn get_neighbors_of(&self,vertex: Vertex)-> HashSet<Vertex>{todo!();}/// Get the number of vertexes in the graph
pubfn get_size(&self)-> usize {todo!();}/// Add vertexes and edges to the graph
pubfn add_edge(&mutself,first: Vertex,second: Vertex){todo!();}/// Create the graph from a grid file content
pubfn from_grid(grid_string: String)-> Self{todo!();}}

// hamilton.rs
usecrate::graph::{Graph,Vertex};/// Finds a hamiltonian path in a graph that starts from a given vertex
/// # Panics
/// This function will panic if it's impossible to find a hamiltonian path satisfying those conditions
pubfn find_path(graph: Graph,start: Vertex)-> Vec<Vertex>{todo!();}

4. Add tests

Now before even starting to implement the algorithm we can add tests that will ensure the algorithm works as expected. For the sake of this readme, I'm not including all the tests here but I did write some for both graph and hamilton.

// hamilton.rs
// ...the stuff of earlier...
#[cfg(test)]mod test{usesuper::*;#[test]fn test_with_degree_one_graph(){letgrid="x x\nxxx".to_string();letgraph=Graph::from_grid(grid);letpath=find_path(graph,(0,0));assert_eq!(vec![(0,0),(0,1),(1,1),(2,1),(2,0)],path);}}

5. Start implementing

Now that the tests are in place, we can start actually coding, for this we simply have to translate the pseudo code into code.

pubfn find_path(graph: Graph,start: Vertex)-> Vec<Vertex>{letmutpath: Vec<Vertex>=Vec::new();letmutnext: Vec<(Vertex,usize)>=Vec::new();next.push((start,0));while!next.is_empty(){let(vertex,neighbor_id)=next.last().copied().unwrap();path.push(vertex);letneighbor=graph.get_neighbors_of(vertex).iter().filter(|v|!path.contains(v)).skip(neighbor_id).next().copied();matchneighbor{Some(neighbor)=>next.push((neighbor,0)),None=>{ifpath.len()==graph.get_size(){returnpath;}else{path.pop();path.pop();next.pop();letnext_task=next.last_mut().unwrap();next_task.1+=1;}}}}path}

Once done we then have to execute the tests with cargo test and if everything passes and it's great! Otherwise we can do some debugging or additional tests to find where things are going wrong.

Note that this part gets very easy in Rust compared to other languages because of Rust's type system. Rust forces you to check for the absence of value or possible errors while other languages don't.

If you're using a language other than Rust, make sure to put extra care in checking for presence of "null" values or exceptions, most bugs come from there.

6. Refactoring

Now what's cool with the fact we made the tests before, is that we can now refactor the code so it looks cleaner and still be sure to not mess things up as long as the tests passes.

For this, I usually try to limit the number of lines and the amount of indentation (which is usually a pretty good red flag for shitty code).

So I just select parts and extract them into functions, name them accordingly and eventually document them until the code looks readable and clean.

Then to go a little bit further and apply the good formatting and rules of Rust we can use clippy and fmt :

cargo clippy --fix --allow-dirty -- -Dclippy::unwrap_used
cargo fmt

Clippy will try to change some of your code to match good Rust practices but some won't work so you'll have to do some of that fixing yourself...

Additionally I configured clippy in the command to disallow any use of .unwrap() in the code and force you to either give an explanation or find another way to manage absence of values/exceptions. Unwrap is only good for prototyping.

Finally fmt will simply apply the standard formatting guidelines to your code automatically. Now you're code is all cool and nice :)

Additional notes and tips

• You can install cargo-wizard to help you configure the Cargo.toml options for optimizing the binary speed/size
• You should generally prefer using iterators in Rust than doing things manually with loops as they are a lot more elegant and easier to work with.
  • You can also find this in other langauges such as Java (Stream API), C# (LINQ) or JavaScript. However in those languages there is a bigger overhead for slowness than doing things manually with primitive types
• Take good care of yourself and don't go crazy with math <3