Slidr (8 Puzzle Solver)

This project solves the famous 8 Puzzle problem.

Summary

8 Puzzle problem is a simple version of 15 Puzzle problem. In this project, A* algorithm is used to solve the problem. Each time through the main loop, A* examines the state $n$ sucht that it has the lowest value of $f(n) = g(n) + h(n)$. $g(n)$ is the actual cost (in this case, the number of moves) of a state from the starting state. $h(n)$ is the heuristic cost of a state to the goal, Manhattan Distance is used in this project. Then it will explore all possible movements (left, right, up, down), and keep on until it reaches the goal.

Requirements

The requirements are:

CMake 3.18 or better; 4.0+ highly recommended
A C++20 compatible compiler (gcc or llvm)
The Boost libararies
Git
Doxygen (optional, highly recommended)
Conda/Miniconda (optional, highly recommended)
Python (for gprof visualization)
Boost library (for benchmarking)
fmt 11.0 or higher (will automatically install if not present)
Catch2 3.8 or higher (will automatically install if not present)
nanobench 4.3 or higher (will automatically install if not present)
abseil 20250512.1 or newer (will automatically install if not present)

How to Use

Add this to your CMakeLists.txt:

FetchContent_Declare(
  slidr
  GIT_REPOSITORY https://github.com/neilchen1998/slidr
  GIT_TAG        v2.0)
  FetchContent_MakeAvailable(slidr)

Add this if you would like to skip building the example:

set(BUILD_EXAMPLES OFF CACHE BOOL "" FORCE)

Instructions

To configure:

cmake -S . -B build

Add --toolchain=./<your_toolchain_file>.toolchain if you want to use your own toolchain.

Add -GNinja if you have Ninja.

To build without example:

cmake --build build

To build with example:

cmake --build build -DBUILD_EXAMPLES=ON

To test (--target can be written as -t in CMake 3.15+):

cmake --build build --target test

To run the binary with example layout:

./build/apps/app

To run the binary with a custom puzzle layout (use 1 to 8 and 'x' or 'X' for the empty space):

./build/apps/app <puzzle>

To build and test:

cmake --build build -DCMAKE_BUILD_TYPE=Test && cmake --build build --target test

To build docs (requires Doxygen, output in build/docs/html):

cmake --build build --target docs

To build and run benchmark:

cmake -S . -B build -DCMAKE_BUILD_TYPE=Benchmark && ./build/bench/<name_of_benchmark>

To run the Unix performance analysis tool (tested only on Linux):

cmake -S . -B build -DCMAKE_BUILD_TYPE=Gprof && ./build/gprof/solverbenchmark && gprof ./build/gprof/solverbenchmark gmon.out > ./build/gprof/analysis.txt

To create and activate an environment if using conda:

conda create -n <env_name> && conda activate <env_name>

To install all dependencies:

pip install -r requirements.txt

To visualize gprof:

./build/gprof/solverbenchmark && gprof ./build/gprof/solverbenchmark | gprof2dot | dot -Tpng -o output.png

Example Result

This is how you would use the solver:

#include <slidr/solver/solver.hpp>

auto s = slidr::Solver(layout);
auto [isSolved, totalIters] = s.SolvePuzzle();

fmt::println("Numbers of moves: {}", s.GetNumOfMoves());
fmt::println("Solution: {}", s.GetSolution());
s.PrintPath();

Example Output

Run the example file:

./build/apps/app

Or enter a custom layout:

./build/apps/app 1274x5836

NOTE: Do not leave spaces between pieces and use x or X to denote the empty piece of the puzzle.

This is the default puzzle and its output:

5	3	6
2		8
4	1	7

No additional argument is provided! An example puzzle layout will be used.
Done in: 67 µs  # of iterations: 65     Total moves: 14
Step: 0
5 3 6
2 x 8
4 1 7
Step: 1
5 3 6
2 1 8
4 x 7
Step: 2
5 3 6
2 1 8
4 7 x
Step: 3
5 3 6
2 1 x
4 7 8
Step: 4
5 3 x
2 1 6
4 7 8
Step: 5
5 x 3
2 1 6
4 7 8
Step: 6
5 1 3
2 x 6
4 7 8
Step: 7
5 1 3
x 2 6
4 7 8
Step: 8
x 1 3
5 2 6
4 7 8
Step: 9
1 x 3
5 2 6
4 7 8
Step: 10
1 2 3
5 x 6
4 7 8
Step: 11
1 2 3
x 5 6
4 7 8
Step: 12
1 2 3
4 5 6
x 7 8
Step: 13
1 2 3
4 5 6
7 x 8
Step: 14
1 2 3
4 5 6
7 8 x
Moves: ↑←↓↓→↑→↓←↑→↑←←

Gprof

Gprof is a performance analysis tool running on Unix systems. It can help you see what how much time does each function take. It is useful for code optimization. This is the visualization of the result of gprof which is generated by gprof2dot:

Notes

Hash Algorithm

A simple way to hash two values is using boost::hash_combine from the Boost library. Or as this post suggests, use the following:

template <class T>
inline void hash_combine(std::size_t& seed, const T& v)
{
    std::hash<T> h;
    seed ^= h(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    // seed ^= (std::hash<T>{}(u) << 1); // this MIGHT get the job done, it passess all the test cases
}

There is no significant performance difference between two approaches according to the benchmark that can be found in bench/mathbenchlib. The archeive file size when using boost::hash_combine and that when using hash_combine are identical.

An even more simplified version as shown in the comment MIGHT work. It passes all the test cases in the repo. But it is not advised.

benchmark	op/s	ns/op
hash_vector	74,615,800.46	13.40
hash_range	90,301,886.39	11.07

`const std::vector<T>& vec` vs. `std::span<T> s`

According to the benchmark bench/mathbenchlib powered by nanobench and Quick C++ Benchmark, there is no significant performance difference between hashing a const std::vector<T>& vec and std::span<T> s. The overhead of converting a std::vector<T> vec to std::span<T> s is minimal. Since this project uses C++20, this is the way to go.

Manhattan Distance Calculation

Manhattan Distance is used to calculate the heuristic value of a puzzle in a given state.

In our problem, $p_1$ represents the goal position and $p_2$ represents the current position of a piece of the puzzle and the formula is $|x_1 - x_2| + |y_1 - y_2|$, where $x$ denotes the row position and $y$ denotes the column position.

There are three implementations, using a simple for-loop, using std::accumulate, and using std::reduce:

int GetManhattanDistance(std::span<int> s)
{
    int manhattanDistance = 0;
    for (auto i = 0; i < constants::EIGHT_PUZZLE_NUM; ++i)
    {
        if (s[i] != constants::EMPTY)
        {
            int curRow = (s[i] - 1) / constants::EIGHT_PUZZLE_SIZE;
            int curCol = (s[i] - 1) % constants::EIGHT_PUZZLE_SIZE;

            int goalRow = i / constants::EIGHT_PUZZLE_SIZE;
            int goalCol = i % constants::EIGHT_PUZZLE_SIZE;

            manhattanDistance += (std::abs(goalRow - curRow) + std::abs(goalCol - curCol));
        }
    }

    return manhattanDistance;
}

int GetManhattanDistanceAccumulate(std::span<int> s)
{
    auto v = std::views::iota(0, constants::EIGHT_PUZZLE_NUM);
    return std::accumulate(
        v.begin(),
        v.end(),
        0,
        [&](int acc, int i) {
            if (s[i] == constants::EMPTY)
            return acc;

            int curRow = (s[i] - 1) / constants::EIGHT_PUZZLE_SIZE;
            int curCol = (s[i] - 1) % constants::EIGHT_PUZZLE_SIZE;
            int goalRow = i / constants::EIGHT_PUZZLE_SIZE;
            int goalCol = i % constants::EIGHT_PUZZLE_SIZE;

            return acc + std::abs(goalRow - curRow) + std::abs(goalCol - curCol);
        }
    );
}

int GetManhattanDistanceReduce(std::span<int> s)
{
    auto v = std::views::iota(0, constants::EIGHT_PUZZLE_NUM);
    return std::reduce(
        v.begin(),
        v.end(),
        0,
        [&](int acc, int i) {
            if (s[i] == constants::EMPTY)
                return acc;

            int curRow = (s[i] - 1) / constants::EIGHT_PUZZLE_SIZE;
            int curCol = (s[i] - 1) % constants::EIGHT_PUZZLE_SIZE;
            int goalRow = i / constants::EIGHT_PUZZLE_SIZE;
            int goalCol = i % constants::EIGHT_PUZZLE_SIZE;

            return acc + std::abs(goalRow - curRow) + std::abs(goalCol - curCol);
        }
    );
}

std::reduce utilizes parallelism which in theory be faster than std::accumulate. In our case the order of the operations does not matter, therefore we can use std::reduce. Nonetheless, based on the benchmark, the three different approaches do not have discernable difference in terms of speed.

benchmark	op/s	ns/op
for loop	160,295,728.06	6.24
std::accumulate	156,853,151.47	6.38
std::reduce	157,072,439.95	6.37

`std::priortiy_queue` vs. Bucket Queue

The most commonly used data structure for the queue is a priority queue. It has O(log n) for insertion, O(log n) for deletion, and O(1) for peak operation. Whenever the solver enters the node with the lowest value of f(n), it will need to pop out the state from the priority queue. And when the solver finds a new valid state, it will need to add the new state to the priority queue. Both operations are done frequently and both operations have a time complexity of O(log n). Therefore a better data structure is needed. A bucket queue is choosen to replace std::priortiy_queue. A bucket queue has O(1) for insertion, O(#priorities) for deletion, and O(1) for peak operation. Therefore, a bucket queue is faster than a std::priortiy_queue. The default number of buckets is 64. The rationale behind that is due to the maximum number of moves is 31. In this benchmark, a bucket queue with 32 buckets is added for eductional purposes. However, the downsize of using a bucket queue is the underlying container is std::vector and reallocations will be needed if there are two many nodes in a single bucket. This downside is pronounced when the given puzzle falls under the category of easy (less than 20 steps to solve). In this project, 9 test cases are used for benchmarking. Those are divided into three categories: easy, medium, and hard. easy takes less than 20 steps to solve, medium takes between 20 and 30, and hard takes 31 steps (which is the most steps possible). The result is shown in the following table:

Group 1: Easy Puzzles

ns/op	op/s	err%	total	Group 1: Easy Puzzles
44,935.60	22,254.07	0.3%	0.08	`Priority Queue Solver`
80,091.72	12,485.69	0.9%	0.14	`Bucket Queue Solver`
79,752.33	12,538.82	0.3%	0.14	`Bucket Queue Solver (32)`

Group 2: Medium Puzzles

ns/op	op/s	err%	total	Group 2: Medium Puzzles
1,091,326.69	916.32	0.8%	1.95	`Priority Queue Solver`
1,308,747.56	764.09	0.5%	2.35	`Bucket Queue Solver`
1,314,774.23	760.59	0.5%	2.36	`Bucket Queue Solver (32)`

Group 3: Hard Puzzles

ns/op	op/s	err%	total	Group 3: Hard Puzzles
3,451,364.99	289.74	0.6%	6.17	`Priority Queue Solver`
3,397,622.16	294.32	0.4%	6.09	`Bucket Queue Solver`

We can see that bucket queue wins the third group but loses in the first and the second group. The bucket queue with 32 buckets performs similar to that with 64 buckets in the first and the second group. However, it fails to solve the third category of puzzles due those puzzles have f value greater than 32.

Linear Conflict

Piece A (the lower index) and piece B (the higher index) are in a linear confict if both of them are on the goal row (or column) and the value of piece A is greater than that of piece B. For instance, 3 and 1 are in a linear conflict since both pieces are in their goaal row and 3 is greater than 1.

3	x	1
x	x	x
x	x	x

However, there is no linear conflict in the following puzzle. Notice that 3 and 6 are not in theira goal positions but 3 is smaller than 6.

1	2	x
4	5	3
7	8	6

The total heuristic value h(n) is now the Manhattan distance plus two times the number of linear conflicts of the puzzle. This is still admissible, meaning that the value is still less than the actual number of steps that is required to solve the puzzle.

The following table is the comparison between using the Manhattan distance and using the Manhatatn distance plus the linear conflict. The improvement is huge for easy puzzles. Significant improvement can also be observed for both medium and hard puzzles as well.

Group 1: Easy Puzzles	Manhattan Dist.	M. Dist. + Linear Cnflct.	Improvement
Priority Queue Solver	5,567.37	13,713.16	246.3%
Bucket Queue Solver	4,130.10	7,035.54	170.3%
Bucket Queue Solver (32)	4,088.10	7,010.57	171.5%

Group 2: Medium Puzzles	Manhattan Dist.	M. Dist. + Linear Cnflct.	Improvement
Priority Queue Solver	334.56	607.25	181.5%
Bucket Queue Solver	424.59	484.35	114.1%
Bucket Queue Solver (32)	426.45	480.73	112.7%

Group 3: Hard Puzzles	Manhattan Dist.	M. Dist. + Linear Cnflct.	Improvement
Priority Queue Solver	123.22	194.19	157.6%
Bucket Queue Solver	139.41	186.12	133.5%

Interface Library

An interface library is for a header-only library. It does not create an output library. But it can and will be used by other libraries. In this project, constantslib, mathlib, and solverlib are all interface libraries. constantslib is where all constants are defined. mathlib, and solverlib are both template classes.

Use Pointers

After changing the data type in our std::priortiy_queue, a significant performance increase is observed. NOTE: those are using -Ofast compiler flag.

benchmark	op/s	ns/op
Priority Queue Solver	2,089.45	478,594.10
Priority Queue Solver (using pointers)	2,578.67	387,796.43
Bucket Queue Solver	1,876.87	532,802.08
Bucket Queue Solver (using pointers)	2,139.18	467,469.06

Fold Expressions

Fold expressions were introduced in C++17. This is a way to reduce a template parameter pack over a binary operator. A template parameter pack is a template parameter that accepts zero or more arguments. hash_combine uses fold expressions to take multiple arguments and hashes them in left order. For instance,

hash_combine(h, u, v);

is equivalent to

hash_combine(h, u);
hash_combine(h, v);

This is extremely useful since we need to hash the value and the position of the current puzzle. Hence, we only need to write all the arguments that we need in a single line of code instead of two lines.

FetchContent

FetchContent is used to managed external dependencies. It fetches dependencies at configuration time and those dependencies will be available at compilation time. In this project, if a version of fmt library (newer than 11.0.0) is available on the system, then the version on the system will be used. Otherwise, fmt 11.2.0 will be fetched, compiled, and be used. This approach is flexible for the user since it does not require to download the library.

Concepts

A concept is a set of requirements. This was introduced in C++20. Each concept is a predicate, evaluated at compile time, and becomes a part of the interface of a template where it is used as a constraint. A std::priority_queue is used as the default queue of Solver. As mentioned before, a different Solver with different queue, i.e., BucketQueue, is used for comparison. This is when making a concept is important since we need to make sure only queues can be used.

template<typename T>
concept PQLike = requires(T pq, const T const_pq, const typename T::value_type& v)
{
    // type requirements
    typename T::value_type; // T::value_type represents the type that this priority queue stores
    typename T::const_reference;  // const T::value_type

    // compound requirements
    { pq.empty() } -> std::same_as<bool>;
    { pq.size() } -> std::convertible_to<std::size_t>;
    { pq.push(v) } -> std::same_as<void>;   // lvalue
    { pq.push(std::move(v)) } -> std::same_as<void>;  // rvalue
    { pq.pop() } -> std::same_as<void>;
    { const_pq.top() } -> std::same_as<typename T::const_reference>;
};

We defined a new concept such that it fulfills the following requirements:

the queue has a nested type (value type)
the queue has a constant reference of its value type
the queue has empty expression and returns bool
the queue has size expression and returns something that can be convertible to size_t
the queue has push expression that takes an lvalue or an rvalue and returns void
the queue has pop expression that returns void
the queue has top expression that returns the constant reference of its value type

Flat Hash set

slidr::Solver uses a hash set to record what nodes it has visited. abseil offers absl::flat_hash_set. This is also called a Swiss Table, it stores elements within a contiguous array. It offers better cache locality compared to std::unordered_set, which is beneficial for lookup operations. In our case, lookups are performed thousands of times especially if the puzzle is hard. In the first group (easy), using absl::flat_hash_set results in 102.7% improvement. In the second (medium) and third (hard) group, switching to absl::flat_hash_set gains around 106% and 107.8%, respectively.

Group 1: Easy Puzzles

ns/op	op/s	err%	total	Group 1: Easy Puzzles
44,974.51	22,234.82	0.6%	0.28	`Priority Queue Solver`
43,784.68	22,839.04	0.2%	0.26	`Priority Queue Solver (flat_hash_set)`
80,331.08	12,448.48	0.6%	0.48	`Bucket Queue Solver`
82,591.90	12,107.72	0.7%	0.49	`Bucket Queue Solver (32)`

Group 2: Medium Puzzles

ns/op	op/s	err%	total	Group 2: Medium Puzzles
1,082,656.50	923.65	0.3%	1.04	`Priority Queue Solver`
1,021,647.87	978.81	0.3%	0.98	`Priority Queue Solver (flat_hash_set)`
1,296,488.02	771.31	0.8%	1.27	`Bucket Queue Solver`
1,287,686.52	776.59	0.2%	1.23	`Bucket Queue Solver (32)`

Group 3: Hard Puzzles

ns/op	op/s	err%	total	Group 3: Hard Puzzles
3,412,984.37	293.00	1.0%	1.24	`Priority Queue Solver`
3,165,287.88	315.93	0.2%	1.15	`Priority Queue Solver (flat_hash_set)`
3,390,451.40	294.95	0.9%	1.23	`Bucket Queue Solver`

Mean and Standard Deviation

The mean formula is $x_1 + x_2 + ... + x_n$. The standard deviation formula is $\sqrt{1 / N * \Sigma_{i=1}^{n} (x_i - \mu) ^ 2}$. We can utilize the boost library to calculate the mean and the variance of samples as follows:

#include <algorithm>
#include <boost/accumulators/accumulators.hpp>
#include <boost/accumulators/statistics/stats.hpp>
#include <boost/accumulators/statistics/variance.hpp>
using namespace boost::accumulators;
accumulator_set<float, stats<tag::sum, tag::variance>> acc;
std::for_each(samples.cbegin(), samples.cend(), [&](float sample)
{
  acc(sample);
});

This is easier and cleaner to calculate the mean and the variance. However, if we want to calculate the standard deviation, we need to take the square root of the variance.

Standard Error of the Mean

The standard error (SEM) measures the accuracy of several means. It tells how well the estimation of the true mean is. We can calculate the value with this formula: $\sigma / \sqrt{n}$

Continuous Uniform Distribution

All random variable are between a minimum value and a maximum value and they have the same probability. The probability density function is $f(x) = 1 / (b - a)$. The mean function is $(b - a) / 2$. The standard deviation is $(b - a) / \sqrt{12}$. There is no a non-trivial formula for the standard error of mean and the standard error of standard deviation. However, with the help of the law of large number, we can approximate these two values with those of a normal distribution.

Discrete Uniform Distribution

Each whole number $n$ between two number is equally likely to be observed. The mean function is $(b - a) / 2$. The standard deviation is $((b - a + 1)^2 - 1) / \sqrt{12}$.

Name		Name	Last commit message	Last commit date
Latest commit History 193 Commits
apps		apps
benchmarks		benchmarks
docs		docs
gprof		gprof
include/slidr		include/slidr
resources		resources
src		src
tests		tests
.gitignore		.gitignore
CMakeLists.txt		CMakeLists.txt
README.md		README.md
compile_and_benchmark.sh		compile_and_benchmark.sh
compile_and_gprof.sh		compile_and_gprof.sh
compile_and_release.sh		compile_and_release.sh
compile_and_run.sh		compile_and_run.sh
compile_and_test.sh		compile_and_test.sh
gprof-visualization.png		gprof-visualization.png
requirements.txt		requirements.txt

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Repository files navigation

Slidr (8 Puzzle Solver)

Summary

Requirements

How to Use

Instructions

Example Result

Example Output

Gprof

Notes

Hash Algorithm

`const std::vector<T>& vec` vs. `std::span<T> s`

Manhattan Distance Calculation

`std::priortiy_queue` vs. Bucket Queue

Group 1: Easy Puzzles

Group 2: Medium Puzzles

Group 3: Hard Puzzles

Linear Conflict

Interface Library

Use Pointers

Fold Expressions

FetchContent

Concepts

Flat Hash set

Group 1: Easy Puzzles

Group 2: Medium Puzzles

Group 3: Hard Puzzles

Mean and Standard Deviation

Standard Error of the Mean

Continuous Uniform Distribution

Discrete Uniform Distribution

Reference

About

Releases

Packages

Contributors

Languages

Folders and files

Latest commit

History

Repository files navigation

Slidr (8 Puzzle Solver)

Summary

Requirements

How to Use

Instructions

Example Result

Example Output

Gprof

Notes

Hash Algorithm

const std::vector<T>& vec vs. std::span<T> s

Manhattan Distance Calculation

std::priortiy_queue vs. Bucket Queue

Group 1: Easy Puzzles

Group 2: Medium Puzzles

Group 3: Hard Puzzles

Linear Conflict

Interface Library

Use Pointers

Fold Expressions

FetchContent

Concepts

Flat Hash set

Group 1: Easy Puzzles

Group 2: Medium Puzzles

Group 3: Hard Puzzles

Mean and Standard Deviation

Standard Error of the Mean

Continuous Uniform Distribution

Discrete Uniform Distribution

Reference

About

Resources

Stars

Watchers

Forks

Releases

Packages

Contributors

Languages

`const std::vector<T>& vec` vs. `std::span<T> s`

`std::priortiy_queue` vs. Bucket Queue