Npuzzle solver using A* with Manhattan + Linear Conflict (Updated Code)

Question

Here is the old thread that I started out with. The code I've got now is vastly different thanks to those two. What I have now functions fairly well and looks pretty good. I've managed to work it back down to some decent speeds, but I'm still encountering long solve states. I am "fairly" certain that I have both my solvable function and heuristic (manhattan and linear conflict) functions right.

If you want to test the heuristic functions on the board to check, I built an excel file. Just uncomment writeBoard(curr, n) in solve(...) and put in a stop. Then open up the file board.csv and copy that into heuristic.xlsx. Only the main sheet (Manhattan) needs to be copied. Linear reads from that. The full heuristic value is output on the left side of Manhattan.

I think I have something fundamentally wrong. I'm currently sorting by heuristic value instead of overall cost because that is what is actually working. When I change things to use cost, I rarely, if ever, get a solve.

I also tried two different data structures for my open list. std::priority_queue and std::set. Priority queue is much, much faster (avg 0.3-0.5 when solved) than set (avg 7-8 when solved), but set had more reliable solves. It would still occasionally hit something though and I'd just kill the program after like 30 seconds. I also noticed that set had a lower number of steps than the queue. I noticed when debugging that the queue will retain its size when using .pop(). I'm pretty sure it then just appends the incoming node on the end which causes some issues. My main question for this is if there is any way to resize a queue. I've done some research on it and come up with only one thing: inheriting from an stdlib class. Here is the best one I've found explaining it. Every time I found this, there were several condemning the very act. I'd also like a little clarification as to why. I noticed one comment on that accepted answer about "inheriting from a class that has a public non-virtual destructor makes feel bad, very bad". Why is that? Aside from this atrocity, is there maybe a better suited data structure I could use? I'm very comfortable with STL, but am open to learning a new library if need be.

I'm also still working on implementing changes suggested by the two who answered my own question. I've done a lot, but not everything. I probably won't touch expanding to higher boards until I get these smaller ones down, so encode and decode are just there for the time being. I know they are limited to a max of 16 square tiles. I'd still very much appreciate some advice on how to clean it up!

Edit: Forgot to post the GitHub link.

Main.cpp

#include "Functions.h"

int main()
{
    auto start = std::chrono::system_clock::time_point();
    auto end = std::chrono::system_clock::time_point();

    auto b = Npuzzle::Board();

    //Open list contains all unexplored nodes, sorted by heuristic value
    Npuzzle::set open;

    //Closed list contains all explored nodes, with values set to encoded parent board
    Npuzzle::map closed;

    auto n = 4;

    //std::cout << "Input size of board: " << std::endl;
    //std::cin >> n;

    start = std::chrono::system_clock::now();

    solve(b, open, closed, n);

    end = std::chrono::system_clock::now();

    auto t = std::chrono::duration<double>();
    t = end - start;

    auto steps = print(Npuzzle::encode(b, n), closed, n);

    std::cout << std::endl;
    std::cout << std::fixed;
    std::cout << std::setprecision(5);
    std::cout << steps << " steps in " << t.count() << " secs.";

    //Cleanup
    cleanup(open, closed);

    std::cin.get();

    return 0;
}

Functions.h

#include <ctime>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <thread>

#include "Npuzzle.h"

bool duplicate(
    const Npuzzle::Board b,
    Npuzzle::map& closed,
    const int n)
{
    return closed.count(Npuzzle::encode(b, n));
}

void addQueue(
    const Npuzzle::Board b,
    const Npuzzle::Board parent,
    Npuzzle::set& open,
    Npuzzle::map& closed,
    const int n)
{
    auto c = new Npuzzle::Structures::Container;

    c->board = b;
    c->heuristic = Npuzzle::heuristic(b, n);

    open.emplace(c);

    closed.insert({ Npuzzle::encode(b, n), Npuzzle::encode(parent, n) });
}

void addMoves(
    const Npuzzle::Board b,
    Npuzzle::set& open,
    Npuzzle::map& closed,
    const int n)
{
    auto moves = std::vector<Npuzzle::Board>(4);
    auto parent = b;

    moves[0] = Npuzzle::up(b, n);
    moves[1] = Npuzzle::down(b, n);
    moves[2] = Npuzzle::left(b, n);
    moves[3] = Npuzzle::right(b, n);

    for (auto i = 0; i < 4; ++i)
    {
        if (moves[i].size() == (n * n))
        {
            if (!duplicate(moves[i], closed, n))
            {
                addQueue(moves[i], parent, open, closed, n);
            }
        }
    }
}

void cleanup(
    Npuzzle::set& open,
    Npuzzle::map& closed)
{
    //Used for set
    //open.clear();

    //Used for priority queue
    while (!open.empty())
    {
        delete open.top();

        open.pop();
    }

    closed.clear();
}

void printBoard(
    const Npuzzle::Board b,
    const int n)
{
    for (auto j = 0; j < n * n; ++j)
    {
        std::cout << b[j] << "\t";

        if (j % n == 3)
        {
            std::cout << std::endl;
        }
    }
}

int print(
    Npuzzle::i64 b,
    Npuzzle::map closed,
    const int n)
{
    std::vector<Npuzzle::Board> solution;

    do
    {
        auto p = b;

        solution.push_back(Npuzzle::decode(b, n));

        b = closed[p];
    } while (b != 0);

    auto size = int(solution.size() - 1);

    for (auto i = size; i >= 0; --i)
    {
        printBoard(solution[i], n);

        std::this_thread::sleep_for(std::chrono::milliseconds(25));

        if (i != 0)
        {
            system("CLS");
        }
    }

    return size;
}

void reset(
    Npuzzle::Board& curr,
    Npuzzle::set& open,
    Npuzzle::map& closed,
    const int n)
{
    cleanup(open, closed);

    curr = Npuzzle::createBoard(n);

    addQueue(curr, Npuzzle::Board(n * n), open, closed, n);
}

void writeBoard(
    const Npuzzle::Board b,
    const int n)
{
    std::ofstream board("board.csv");

    for (auto i = 0; i < n; ++i)
    {
        for (auto j = 0; j < n; ++j)
        {
            auto k = i * n + j;

            board << b[k] << ",";
        }

        board << std::endl;
    }
}

void solve(
    Npuzzle::Board& curr,
    Npuzzle::set& open,
    Npuzzle::map& closed,
    const int n)
{
    auto solved = false;

    //Create initial board
    curr = Npuzzle::createBoard(n);

    //Test state
    //curr = { 0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 1, 14, 15 };

    addQueue(curr, Npuzzle::Board(n * n), open, closed, n);

    while (!solved)
    {
        //Used for set
        //auto top = *open.begin();

        curr = open.top()->board;


        if (open.top()->heuristic == 0)
        {
            solved = true;
        }
        else
        {
            //writeBoard(curr, n);

            //Used for set
            //open.erase(top);

            //Used for priority queue
            delete open.top();
            open.pop();

            addMoves(curr, open, closed, n);
        }
    }
}

Npuzzle.h

#include <assert.h>
#include <cstdint>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <unordered_map>
#include <vector>

namespace Npuzzle
{
    using Board = std::vector<int>;
    using i64 = std::uint_fast64_t;

    namespace Structures
    {
        struct Point
        {
            int x, y;
        };

        struct Container
        {
            int heuristic;
            Board board;
        };

        struct LessThanByHeur
        {
            bool operator()(
                const Container* lhs,
                const Container* rhs) const
            {
                return lhs->heuristic > rhs->heuristic;
            }
        };
    }

    //using set = std::set<Structures::Container*, Structures::LessThanByHeur>;
    using set = std::priority_queue<Structures::Container*, std::vector<Structures::Container*>, Structures::LessThanByHeur>;
    using map = std::unordered_map<i64, i64>;

    Structures::Point findZero(
        const Board b,
        const int n)
    {
        for (auto i = 0; i < n * n; ++i)
        {
            if (b[i] == 0)
            {
                return { i % n, i / n };
            }
        }

        return { -1, -1 };
    }

    //Count inversions in board
    int inversions(
        const Board b,
        const int n)
    {
        auto count = 0;

        for (auto i = 0; i < n * n - 1; ++i)
        {
            for (auto j = i + 1; j < n * n; ++j)
            {
                if (b[i] == 0)
                {
                    if (b[j] < n * n)
                    {
                        ++count;
                    }
                }
                else if (b[j] < b[i])
                {
                    ++count;
                }
            }
        }

        return count;
    }

    bool solvable(
        const Board b,
        const int n)
    {
        auto zero = findZero(b, n);
        auto count = inversions(b, n);

        //If width is odd and count is even
        if ((n & 1) && !(count & 1))
        {
            return true;
        }
        //If width is even
        else
        {
            //If zero y pos is odd from bottom, and count is even
            if (((n - zero.y) & 1) && !(count & 1))
            {
                return true;
            }
            else if (count & 1)
            {
                return true;
            }
        }

        return false;
    }

    Board createBoard(
        const int n)
    {
        auto b = Board(n * n);
        auto rng = std::mt19937_64(std::random_device()());

        do
        {
            //Fill vector from 0 to n * n
            std::iota(b.begin(), b.end(), 0);

            //Randomize vector
            std::shuffle(b.begin(), b.end(), rng);

        } while (!solvable(b, n));

        return b;
    }

    Board decode(
        i64& code,
        const int n)
    {
        static Board b(n * n);

        for (auto i = (n * n) - 1; i >= 0; --i)
        {
            auto val = 0;

            //Get first n bits
            val = code & ((1 << n) - 1);

            //Delete first n bits
            code = code >> n;

            //Save val in board
            b[i] = val;
        }

        return b;
    }

    i64 encode(
        const Board b,
        const int n)
    {
        i64 code = 0;

        for (auto i = 0; i < n * n; ++i)
        {
            //Set first n bits
            if (i == 0)
            {
                code |= b[i];
            }
            //Set rest of bits
            else
            {
                code = ((code << n) | b[i]);
            }
        }

        return code;
    }

    int linear(
        const Board b,
        const int n)
    {
        auto count = 0;

        Board inCol(n * n), inRow(n * n);

        for (auto y = 0; y < n; ++y)
        {
            for (auto x = 0; x < n; ++x)
            {
                auto i = y * n + x;

                if (b[i] == 0)
                {
                    continue;
                }

                auto bX = 0;
                auto bY = 0;

                if (b[i] % n == 0)
                {
                    bX = n - 1;
                    bY = b[i] / n - 1;
                }
                else
                {
                    bX = b[i] % n - 1;
                    bY = b[i] / n;
                }

                inCol[i] = (bX == x);
                inRow[i] = (bY == y);
            }
        }

        for (auto y = 0; y < n; ++y)
        {
            for (auto x = 0; x < n; ++x)
            {
                auto i = y * n + x;

                if (b[i] == 0)
                {
                    continue;
                }

                if (inCol[i])
                {
                    for (auto z = y; z < n; ++z)
                    {
                        auto j = z * n + x;

                        if (b[j] == 0)
                        {
                            continue;
                        }

                        if (inCol[j])
                        {
                            if ((b[j] < b[i]) && ((abs(b[j] - b[i]) % n) == 0))
                            {
                                ++count;
                            }
                        }
                    }
                }

                if (inRow[i])
                {
                    auto bI = b[i];

                    for (auto z = x + 1; z < n; ++z)
                    {
                        auto j = y * n + z;
                        auto bJ = b[j];

                        if (b[j] == 0)
                        {
                            continue;
                        }

                        if (inRow[j])
                        {
                            if ((bJ < bI) && (0 <= (bI - bJ)) && ((bI - bJ) < n))
                            {
                                ++count;
                            }
                        }
                    }
                }
            }
        }

        return 2 * count;
    }

    int manhattan(
        const Board b,
        const int n)
    {
        auto m = 0;

        Board solution(n * n);
        std::iota(solution.begin(), solution.end(), 1);

        solution[n * n - 1] = 0;

        //Calculate manhattan distance for each value
        for (auto i = 0; i < n * n; ++i)
        {
            if (b[i] != solution[i])
            {
                auto bX = 0;
                auto bY = 0;
                auto x = 0;
                auto y = 0;

                if (b[i] == 0)
                {
                    ++i;
                }

                //Calculate goal pos
                if ((b[i] % n) == 0)
                {
                    bX = n - 1;
                    bY = b[i] / n - 1;
                }
                else
                {
                    bX = b[i] % n - 1;
                    bY = b[i] / n;
                }

                //Calculate the current pos
                auto val = i + 1;

                if ((val % n) == 0)
                {
                    x = n - 1;
                    y = val / n - 1;
                }
                else
                {
                    x = val % n - 1;
                    y = val / n;
                }

                m += abs(bX - x) + abs(bY - y);
            }
        }

        return m;
    }

    int heuristic(
        const Board b,
        const int n)
    {
        return manhattan(b, n) + linear(b, n);
    }

    Board swapPos(
        const Board b,
        const int n,
        const Structures::Point zero,
        const int newPos)
    {
        auto oldPos = 0;
        Board move(n * n);

        //Calculate old pos
        oldPos = zero.x + (zero.y * n);

        //Copy current board
        for (auto i = 0; i < n * n; ++i)
        {
            move[i] = b[i];
        }

        //Swap pos
        move[oldPos] = move[newPos];
        move[newPos] = 0;

        return move;
    }

    Board down(
        const Board b,
        const int n)
    {
        Structures::Point zero = findZero(b, n);
        auto newPos = zero.y + 1;

        //Check if move is possible
        if (newPos > (n - 1))
        {
            return Board(0);
        }

        //Create new board based on newPos
        return swapPos(b, n, zero, zero.x + (newPos * n));
    }

    Board left(
        const Board b,
        const int n)
    {
        Structures::Point zero = findZero(b, n);
        auto newPos = zero.x - 1;

        //Check if move is possible
        if (newPos < 0)
        {
            return Board(0);
        }

        //Create new board based on newPos
        return swapPos(b, n, zero, newPos + (zero.y * n));
    }

    std::vector<int> right(
        const Board b,
        const int n)
    {
        Structures::Point zero = findZero(b, n);
        auto newPos = zero.x + 1;

        //Check if move is possible
        if (newPos > (n - 1))
        {
            return Board(0);
        }

        //Create new board based on newPos
        return swapPos(b, n, zero, newPos + (zero.y * n));
    }

    Board up(
        const Board b,
        const int n)
    {
        Structures::Point zero = findZero(b, n);
        auto newPos = zero.y - 1;

        //Check if move is possible
        if (newPos < 0)
        {
            return Board(0);
        }

        //Create new board based on newPos
        return swapPos(b, n, zero, zero.x + (newPos * n));
    }
}

Answer 1

Good job refactoring. It looks much neater without the globals / Manager class. Good effort with cleaning up allocated memory, but we can do better (see below). The csv output is a good idea too. :)

• Use <cassert> not <assert.h>. (If a standard library header ends in .h it's a C header, and there should be a version that starts with c for C++).
• It's best to include local headers first (it's easier to ensure a header is independent and includes everything it needs to), so NPuzzle.h should be included before the standard library headers.
• Header files need an include guard to prevent multiple definitions. With modern compilers, the easiest way is to add #pragma once as the first line. Otherwise you need to use preprocessor definitions.
• Generally, a header file is used for code that needs to be accessed elsewhere (by #includeing the header). However, we only need to put the declarations of functions in the header (and include other headers that declare the appropriate types). The definitions of functions can be placed in an accompanying .cpp file, along with everything that those functions depend on. (See modified code below).

---

• start and end and t can be initialized with the correct values where they're used, instead of declared early with an intermediate value:

  auto start = std::chrono::system_clock::now();
  ...
  auto end = std::chrono::system_clock::now();
  auto t = std::chrono::duration<double>(end - start);
  

---

• The const Board b arguments to functions should nearly all be const Board& b. The general rule is that builtin types (and classes that effectively only contain a built in type) should be passed by value, and anything larger by const&. The idea is to avoid copying unless we actually have to, and we don't want to copy the board vector if we can avoid it.

---

• I'd suggest rearranging the variables used in the main and solve functions a little. It might be better for solve to take the generated board as input (generating the board isn't solving, and probably shouldn't be timed either), and produce the solution vector as output (rather than doing that in the print function). This way, the open and closed lists can be internal as well.
• I guess the reason the open and closed lists are external is because of the need to cleanup data. However, we can solve this by cleaning up as we go along (i.e having strong ownership of the Containers by the relevant data structure).
• Although it might seem slow to store Containers by value in the priority queue we can actually use move semantics to avoid any extra copying.

---

• up() down() left() and right() can be refactored into one function taking an x and yoffset.
• Since we're using a std::vector instead of a C-style array, we don't need to copy data manually, and swapPos can use std::vector's copy constructor. We can also use std::swap to do the actual swapping of the zero value.

---

Bugs: in solvable:

• Since the number zero represents a blank tile, not an actual index, it should simply be ignored in the inversion calculation:

  int inversions(
      const Board& b,
      const int n)
  {
      auto count = 0;
  
      for (auto i = 0; i < n * n - 1; ++i)
      {
          for (auto j = i + 1; j < n * n; ++j)
          {
              if (b[i] == 0 || b[j] == 0)
                  continue;
  
              if (b[i] > b[j])
                  ++count;
          }
      }
  
      return count;
  }
  

• The else if in solvable needs to check both conditions again, not just count & 1. This is because we're checking two conditions in the if statement. If we passed the first check in the if, but not the second, we'll end up (erroneously) in the else-if clause.

      ...
      if (((n - zero.y) & 1) && !(count & 1))
      {
          return true;
      }
      else if (!((n - zero.y) & 1) && (count & 1)) // check both conditions!
      {
          return true;
      }
  

• We can condense this logic quite a bit. The last if ... else if is actually saying that one of the two variables must be odd, and the other even. (Also, if we make sure that n is even, we can check the y-position is in an even row from the top, instead of based on n.)

  bool isEven(int i)
  {
      return ((i % 2) == 0);
  }
  
  bool solvable(
      const Board& b,
      const int n)
  {
      auto i = inversions(b, n);
  
      if (!isEven(n))
          return isEven(i);
  
      return isEven(findZero(b, n).y) != isEven(i);
  }
  

---

Modified code:

Npuzzle.h:

#pragma once

#include <vector>

namespace Npuzzle
{

    using Board = std::vector<int>;

    Board createBoard(
        const int n);

    void printBoard(
        const Npuzzle::Board& b,
        const int n);

    void printSolution(
        std::vector<Npuzzle::Board> const& solution,
        const int n);

    void writeBoard(
        const Npuzzle::Board& b,
        const int n);

    std::vector<Npuzzle::Board> solve(
        Npuzzle::Board b, // note: this copy is intentional! we need to copy the starting position so we can move it into the priority queue.
        const int n);

} // Npuzzle

Npuzzle.cpp (Everything that isn't main! Unchanged code cut for length).

#include "Npuzzle.h"

#include <array>
#include <cassert>
#include <cstdint>
#include <fstream>
#include <iostream>
#include <thread>
#include <random>
#include <numeric>
#include <queue>
#include <set>
#include <unordered_map>

namespace Npuzzle
{

    using i64 = std::uint_fast64_t;

    namespace Structures
    {
        struct Point
        {
            int x, y;
        };

        struct Container
        {
            int heuristic;
            Board board;
        };

        struct LessThanByHeur
        {
            bool operator()(
                const Container& lhs,
                const Container& rhs) const
            {
                return lhs.heuristic > rhs.heuristic;
            }
        };
    }

    using set = std::priority_queue<Structures::Container, std::vector<Structures::Container>, Structures::LessThanByHeur>;
    using map = std::unordered_map<i64, i64>;


    Structures::Point findZero(
        const Board& b, // by ref!
        const int n)
    {
        for (auto i = 0; i < n * n; ++i)
        {
            if (b[i] == 0)
            {
                return{ i % n, i / n };
            }
        }

        assert(false); // added this so we get some warning in debug mode at least!
        return{ -1, -1 };
    }

    int inversions(
        const Board& b, // by ref!
        const int n)
    {
        auto count = 0;

        for (auto i = 0; i < n * n - 1; ++i)
        {
            for (auto j = i + 1; j < n * n; ++j)
            {
                if (b[i] == 0 || b[j] == 0) // ignore the blank tile!
                    continue;

                if (b[i] > b[j])
                    ++count;
            }
        }

        return count;
    }

    bool isEven(int i)
    {
        return ((i % 2) == 0);
    }

    bool solvable(
        const Board& b, // by ref!
        const int n)
    {
        auto i = inversions(b, n);

        if (!isEven(n))
            return isEven(i);

        return isEven(findZero(b, n).y) != isEven(i);
    }

    Board createBoard(
        const int n)
    {
        // snip! (unchanged)
    }

    Board decode(
        i64& code,
        const int n)
    {
        // snip! (unchanged)
    }

    i64 encode(
        const Board& b, // by ref!
        const int n)
    {
        // snip! (unchanged)
    }

    int linear(
        const Board& b, // by... well, you get the idea!
        const int n)
    {
        // snip! (unchanged)
    }

    int manhattan(
        const Board& b,
        const int n)
    {
        // snip! (unchanged)
    }

    int heuristic(
        const Board& b,
        const int n)
    {
        // snip! (unchanged)
    }

    Board swapPos(
        const Board& b,
        const int n,
        const Structures::Point& oldZero,
        const Structures::Point& newZero)
    {
        Board move = b; // use std::vector copy constructor!

        auto oldIndex = oldZero.x + (oldZero.y * n);
        auto newIndex = newZero.x + (newZero.y * n);

        std::swap(move[oldIndex], move[newIndex]);

        return move;
    }

    bool inBounds(
        const Structures::Point& point,
        const int n)
    {
        return (point.x >= 0 && point.x < n && point.y >= 0 && point.y < n);
    }

    Board makeMove(
        const Board& b,
        const Structures::Point& offset,
        const int n)
    {
        Structures::Point zero = findZero(b, n);
        auto newPos = Structures::Point{ zero.x + offset.x, zero.y + offset.y };

        if (!inBounds(newPos, n))
            return{ }; // returns empty vector

        return swapPos(b, n, zero, newPos);
    }

    bool duplicate(
        const Npuzzle::Board& b,
        Npuzzle::map& closed,
        const int n)
    {
        return (closed.count(Npuzzle::encode(b, n)) != 0);
    }

    void addQueue(
        Npuzzle::Board&& b, // by r-value reference! i.e. it has to be `std::move`d in
        const Npuzzle::Board& parent,
        Npuzzle::set& open,
        Npuzzle::map& closed,
        const int n)
    {
        closed.emplace(Npuzzle::encode(b, n), Npuzzle::encode(parent, n));

        open.push({ Npuzzle::heuristic(b, n), std::move(b) }); // constructs a Container (moving b into place), then moves the container into the priority queue

        // note that std::move(b) has to be the last thing we do with b
        // this should be enforced by modern compilers, as the initialization order of the Container (initialized by the {}) should be well-defined
    }

    std::vector<Npuzzle::Board> makeSolution( // extracted from the print function!
        Npuzzle::i64 b,
        Npuzzle::map const& closed,
        const int n)
    {
        std::vector<Npuzzle::Board> solution;

        do
        {
            auto p = b;

            solution.push_back(Npuzzle::decode(b, n));

            b = closed.at(p);
        } while (b != 0);

        std::reverse(solution.begin(), solution.end()); // easier than iterating backwards

        return solution;
    }

    void addMoves(
        const Npuzzle::Board& b,
        Npuzzle::set& open,
        Npuzzle::map& closed,
        const int n)
    {
        auto moves = std::array<Npuzzle::Board, 4u> // there will always be 4, so we can use a std::array
        {
            Npuzzle::makeMove(b, { 0, -1 }, n), // up
            Npuzzle::makeMove(b, { 0, 1 }, n), // down
            Npuzzle::makeMove(b, { -1, 0 }, n), // left
            Npuzzle::makeMove(b, { 1, 0 }, n), // right
        };

        for (auto& move : moves) // range-based for loop is a bit easier (note the & is because we want to move the board out of the array)
        {
            if (!move.empty() && !duplicate(move, closed, n))
            {
                addQueue(std::move(move), b, open, closed, n);
            }
        }
    }

    void printBoard(
        const Board& b,
        const int n)
    {
        // snip! (unchanged)
    }

    void printSolution(
        std::vector<Board> const& solution,
        const int n)
    {
        for (auto const& board : solution)
        {
            system("CLS");

            printBoard(board, n);

            std::this_thread::sleep_for(std::chrono::milliseconds(25));
        }
    }

    void writeBoard(
        const Board& b,
        const int n)
    {
        // snip! (unchanged)
    }

    std::vector<Npuzzle::Board> solve(
        Board b,
        const int n)
    {
        Npuzzle::set open;
        Npuzzle::map closed;

        addQueue(std::move(b), Npuzzle::Board(n * n), open, closed, n);

        while (!open.empty()) // we should eventually run out of positions...
        {
            auto curr = std::move(open.top());
            open.pop();

            if (curr.heuristic == 0)
            {
                return makeSolution(Npuzzle::encode(curr.board, n), closed, n);
            }
            else
            {
                addMoves(curr.board, open, closed, n);
            }
        }

        assert(false); // if we get here, we're attempting to solve an unsolvable problem...
        return{ };
    }

} // Npuzzle

main.cpp:

#include "Npuzzle.h"

#include <chrono>
#include <iostream>
#include <iomanip>

int main()
{
    auto n = 4;
    auto b = Npuzzle::createBoard(n);
    //auto b = Npuzzle::Board{ 0, 14, 11, 2, 15, 1, 10, 12, 5, 7, 3, 8, 6, 13, 9, 4 }; // unsolvable!

    auto start = std::chrono::system_clock::now();

    auto solution = Npuzzle::solve(b, n);

    auto end = std::chrono::system_clock::now();
    auto t = std::chrono::duration<double>(end - start);

    Npuzzle::printSolution(solution, n);

    std::cout << std::endl;
    std::cout << std::fixed;
    std::cout << std::setprecision(5);
    std::cout << solution.size() << " steps in " << t.count() << " secs.";

    std::cin.get();

    return 0;
}

Answer 2

Don't put implementation in header files

You moved all of your code into header files. That's not what they are for. It is better to have only the declarations of the classes and functions in the .h files, and put the definitions of the functions in .cpp files. Compile your code using link time optimization (-flto) to ensure the compiler can still inline functions.

Unnecessary namespace Structures

There is no need to have the namespace Structures. The classes inside it are already inside namespace Npuzzle. There is no benefit at all, and just adds more typing.

Avoid overly generic names

If I read something like Structures::Container, it doesn't tell me much. What kind of structure? What kind of container?

Also, don't use generic names that are already used for standard types, because that will cause a lot of confusion. Take for example using set = std::priority_queue<...> in Npuzzle.h. It is not even a set, it's a priority queue. I would avoid writing those aliases, especially since you only use them once or twice.

Avoid passing a container and its size as arguments

A container should know its own size. For example, if you write:

someFunction(const Board b, const int n) {
    for (auto i = 0; i < n *n; i++)
         do_something_with(b[i])
}

That could've been rewritten to:

someFunction(const Board b) {
    for (auto element: b)
         do_something_with(element);
    }
}

In your case, your boards are n * n, and you need n often, and writing sqrt(b.size()) is awkward. Maybe you can create a proper class for the board, that gives you access to n directly?

struct board: public vector<int> {
    const int n;
    board(int n): vector<int>(n * n), n(n) {}
};

Pass by reference where appropriate

You are passing some variables by value, when it is more efficient to pass them by reference. For example, every time you call findZero() a copy of the Board is made. Just pass it by reference to avoid that overhead.

Avoid calling std::iota() unnecessarily

In createBoard(), you call std::iota() inside the do-while loop, but it only needs to be called once before the loop.

What if n > 4?

Since your encode() function returns a 64-bit integer, you are limiting yourself to boards of up to 4 * 4 elements. So your code doesn't scale to bigger boards. Is this intentional? If not, you have to redesign this part to handle arbitrarily large boards.