cpp-sliding-eight-puzzle

Linux/UNIX command-line Sliding Eight-Puzzle solver with selectable strategies, written in C++.

Table Of Contents

• Motivation
• Features
• Design
• Requirements
• Quick Start
• Source Code Layout
• Full Usage / Options
• Examples
• Contributing

Motivation

Make an efficient, easy-to-use command-line program to solve an Eight-Puzzle. Implement selectable solving strategies to allow comparison of time complexity, space complexity, and optimality.

Features

• Use different strategies as simple options.
• Switch between different move costs with an option.
• Perform low-level, common operations in constant time to maximize the solving speed of any strategy.

Design

Architecture diagram of main Solver interface and supporting interfaces, base classes, and classes:

Requirements

• A Linux/UNIX system
• C++17 (gcc 7, clang 4)
• CMake

Quick Start

1. Clone the project into a local project directory:

   $ git clone --recurse-submodules git@github.com:digimokan/cpp-sliding-eight-puzzle.git

2. Change to the local project directory:

   $ cd cpp-sliding-eight-puzzle

3. Compile the program.

   $ ./third_party/smart-build/src/smart-build.sh -r

4. Solve a puzzle.

   $ ./eight-puzzle --depth-first "567408321" "123804765"

Source Code Layout

├─┬ cpp-sliding-eight-puzzle/
│ │
│ ├─┬ src/
│ │ ├── Board/            # a puzzle board, containing squares with values
│ │ ├── EstGoalCost/      # estimated cost to goal board (g(n), h(n), f(n), etc)
│ │ ├── FrontierQueue/    # search nodes for evaluation, ordered in some way
│ │ ├── Inputs/           # process program user input
│ │ ├── Move/             # a board move, or possible legal board moves
│ │ ├── MoveCost/         # cost of a board move (traditionally, 1 unit)
│ │ ├── Search/           # the search graph and its nodes
│ │ ├── Solver/           # produces solution steps using various strategies
│ │ ├── Utils/            # utility functions
│ │ └── main.cpp          # main program entry point
│ │
│ ├─┬ tests/
│ │ ├── unit_tests/             # unit test for each class and its methods
│ │ ├── doctest_testharness.cpp # configures the unit tester (doctest)
│ │ └── test_driver.sh          # one-line driver to smart-build the program
│ │
│ ├─┬ third_party/
│ │ ├── doctest/                # the unit-tester
│ │ └── smart-build             # the building/testing utility
│ │
│ ├── .project_config           # smart-build compilation/build config
│ └── CMakeLists.txt            # CMake build config

Full Usage / Options

USAGE

eight-puzzle -h

eight-puzzle [-v|-c] [-b|-d|-i|-u|-s|-1|-2|-3] <start_board> <goal_board>

ARGUMENTS

<start_board>
        starting board: a 3x3 with 0-8 (0 is empty), e.g. "134862705"

<goal_board>
        winning/goal board: a 3x3 with 0-8 (0 is empty), e.g. "123804765"

OPTIONS

-h, --help
        print this help message

-v, --move-cost-sq-val
        set move costs to the value of the square moved (default)

-c, --move-cost-const
        set move costs to 1 (the traditional cost)

-b, --breadth-first
        find solution using breadth-first search (default)

-d, --depth-first
        find solution using depth-first search

-i, --iterative-deepening
        find solution using depth-first search with iterative deepening

-u, --uniform-cost
        find solution using g(n) uniform-cost search

-s, --best-first
        find solution using h(n) num misplaced tiles

-1, --a-star-1
        find solution using A*1 search (g(n) + h(n) num misplaced tiles)

-2, --a-star-2
        find solution using A*2 search (g(n) + h(n) sum manhattan dists)

-3, --a-star-3
        find solution using A*3 search (g(n) + h(n) custom heuristic)

Examples

• Solve an easy puzzle, using the traditional move cost of 1:

  $ ./eight-puzzle -cb "134862705" "123804765"

• Solve a hard puzzle (requiring many steps) using a fast, but non-optimal solver:

  $ ./eight-puzzle --best-first "567408321" "123804765"

• Solve a hard puzzle (requiring many steps) using a balanced, optimal solver:

  $ ./eight-puzzle --a-star-3 "567408321" "123804765"

Contributing

• Feel free to report a bug or propose a feature by opening a new Issue.
• Follow the project's Contributing guidelines.
• Respect the project's Code Of Conduct.