N-puzzle solver using A* with Manhattan + Linear Conflict

Question

I've been working on this solution for a couple days now. Finally managed to get it to work and I got it to where it solves about half of the time. The other half goes for so long that it eventually just runs out of memory. The weird thing is that the solves are pretty fast. Before I updated the heuristic with linear conflict, it solved it anywhere from 0.5s to 3s. Now with the update, it averages around 0.05s to 0.5s.

The solver uses a priority queue sorted by the heuristic of the board for the open list, and an unordered map for the closed list. The map uses UINT64 values as keys that are encoded from the board array using bitwise operators. Each 8-bit number is encoded with two numbers, thus creating the 64 bit integer.

The main advice I'm looking for is a way to catch the harder boards and make progress with them. I'd also really appreciate some advice on how to make the linear conflict function look a lot better. I brute forced my way into something that works and tried to optimize it best I could. It isn't very OOP, but it is just a start. I finished it about an hour or so ago.

Here is a link to the GitHub I've got it in if you want to build and run it to see what's going on for yourself.

Edit: I've made several changes. Many of which were recommendations based on you guys. To the best of my ability anyway. I've still got a fair amount of work to do, like the linear conflict function, but it looks quite a bit different and better. It's in the gitHub link above. Once I get it more figured out, I'll post the full code here as an answer.

Manager.h

#include <chrono>
#include <iostream>
#include <math.h>
#include <queue>
#include <random>
#include <time.h>
#include <unordered_map>
#include <vector>
#include <Windows.h>

const int n = 4;

struct Container
{
    int b[n * n] = {};
    int heuristic;
    Container* parent = 0;
};

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

class Manager
{
    public:
    Manager();
    Manager(const Manager& other);
    ~Manager();

    void Run();

    int calculateManhattan(int b[]);
    int calculateLinear(int b[]);
    bool checkSolvable();

    UINT64 encode(int b[]);
    int* decode(UINT64 code);

    void addMoves();

    void up();
    void down();
    void left();
    void right();

    void findZero();
    void swapPos(Container* move, int newPos);

    bool checkDuplicate(Container* move);

    void printSolution(Container* top);

    private:
    std::priority_queue<Container*, std::vector<Container*>, GreaterThanByCost> open;
    std::unordered_map<UINT64, bool> closed;

    Container* current = 0;
    int zeroX, zeroY;

    std::chrono::system_clock::time_point start;
    std::chrono::system_clock::time_point end;
};

Manager.cpp

#include "Manager.h"

Manager::Manager()
{
    int nums[n * n];

    zeroX = zeroY = 0;

    current = new Container;

    //Initialize random number generator
    srand((unsigned int)time(0));

    do
    {
        //Initialize nums
        for (int i = 0; i < n * n; ++i)
        {
            nums[i] = 0;
        }

        int val = -1;

        for (int i = 0; i < n * n; ++i)
        {
            bool go = true;

            val = rand() % (n * n);

            //Loop until nums[val] != -1
            while (go)
            {
                if (nums[val] == -1)
                {
                    val = rand() % (n * n);
                }
                else
                {
                    go = false;
                }
            }

            current->b[i] = val;

            nums[val] = -1;

            //set position of zero
            if (val == 0)
            {
                zeroX = i % n;
                zeroY = i / n;
            }
        }
    } while (!checkSolvable());

    current->heuristic = calculateManhattan(current->b) + calculateLinear(current->b);

    open.push(current);
}

Manager::Manager(const Manager& other)
{}

Manager::~Manager()
{}

void Manager::Run()
{
    start = std::chrono::system_clock::now();

    bool solved = false;

    while (!solved)
    {
        //Check if open.top is solved
        if (open.top()->heuristic == 0)
        {
            end = std::chrono::system_clock::now();

            solved = true;

            printSolution(open.top());

            return;
        }

        //Add open.top to closed
        closed[encode(current->b)] = true;

        //Add moves to open
        addMoves(); 
    }
}

//Calculate manhattan value for board
int Manager::calculateManhattan(int b[])
{
    //Create solved board
    int manhattan = 0;

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

            bX = b[i] % n;
            bY = b[i] / n;

            x = i % n;
            y = i / n;

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

    return manhattan;
}

//Calculate linear conflict
int Manager::calculateLinear(int b[])
{
    int count = 0;

    for (int i = 0; i < n * n; ++i)
    {
        //Check if b[i] is in the right spot
        if (b[i] != i)
        {
            //Calculate row and col it's supposed to be in
            int x = b[i] % n;
            int y = b[i] / n;

            //Calculate row and col it's in
            int bx = i % n;
            int by = i / n;

            //Check cols
            if (x == bx)
            {
                bool found = false;

                //Check above
                if (b[i] < i)
                {
                    int colStart = i - n;

                    for (int j = colStart; j >= 0; j -= n)
                    {
                        if ((j != b[i]) && !found)
                        {
                            if ((b[i] - b[j]) % n == 0)
                            {
                                ++count;
                            }
                        }
                        else if ((j == b[i]) && !found)
                        {
                            if ((b[i] - b[j]) % n == 0)
                            {
                                ++count;
                            }

                            found = true;
                        }
                        else
                        {
                            break;
                        }
                    }
                }

                //Check below
                if (b[i] > i)
                {
                    int colEnd = n * (n - 1) + bx;

                    for (int j = i + 4; j <= colEnd; j += 4)
                    {
                        if ((j != b[i]) && !found)
                        {
                            if ((b[i] - b[j]) % n == 0)
                            {
                                ++count;
                            }
                        }
                        else if ((j == b[i]) && !found)
                        {
                            if ((b[i] - b[j]) % n == 0)
                            {
                                ++count;
                            }

                            found = true;
                        }
                        else
                        {
                            break;
                        }
                    }
                }
            }

            //Check rows
            if (y == by)
            {
                bool found = false;

                //Check left
                if (b[i] < i)
                {
                    int rowStart = i - 1;

                    for (int j = rowStart; j >= by * n; --j)
                    {
                        if ((j != b[i]) && !found)
                        {
                            if (((b[i] - b[j]) < 0) && (abs(b[i] - b[j]) < n))
                            {
                                ++count;
                            }
                        }
                        else if ((j == b[i]) && !found)
                        {
                            if (((b[i] - b[j]) < 0) && (abs(b[i] - b[j]) < n))
                            {
                                ++count;
                            }

                            found = true;
                        }
                        else
                        {
                            break;
                        }
                    }
                }

                //Check right
                if (b[i] > i)
                {
                    int nextRowStart = n * (by + 1);

                    for (int j = i + 1; j < nextRowStart; ++j)
                    {
                        if ((j != b[i]) && !found)
                        {
                            if (((b[i] - b[j]) > 0) && (abs(b[i] - b[j]) < n))
                            {
                                ++count;
                            }
                        }
                        else if ((j == b[i]) && !found)
                        {
                            if (((b[i] - b[j]) > 0) && (abs(b[i] - b[j]) < n))
                            {
                                ++count;
                            }

                            found = true;
                        }
                        else
                        {
                            break;
                        }
                    }
                }
            }
        }
    }

    return 2 * count;
}

//Check if board is solvable
bool Manager::checkSolvable()
{
    int count = 0;
    int pos = 0;

    //Assume board is not solvable
    bool solvable = false;

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

    //If width is odd and count is even
    if ((n % 2 == 1) && (count % 2 == 0))
    {
        solvable = true;
    }
    //If width is even, zeroY pos is odd from bottom, and count is even
    else if (((n - zeroY) % 2 == 1) && (count % 2 == 0))
    {
        solvable = true;
    }
    //If width is even, zeroY pos is even from bottom, and count is odd
    else if (count % 2 == 1)
    {
        solvable = true;
    }

    return solvable;
}

//Encode binary board
UINT64 Manager::encode(int b[])
{
    UINT64 code = 0;

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

    return code;
}

//Decode binary board
int* Manager::decode(UINT64 code)
{
    static int b[n * n];

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

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

        //Delete first four bits
        code = code >> 4;

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

        if (val == 0)
        {
            zeroX = i % n;
            zeroY = i / n;
        }
    }

    return b;
}

void Manager::addMoves()
{
    //Set current to open.top
    current = open.top();
    findZero();

    //Create new move
    Container* move = 0;

    //Remove top from open
    open.pop();

    //Check for directional moves
    up();
    down();
    left();
    right();
}

//Y - 1
void Manager::up()
{
    int newPos;
    Container* move = new Container;

    newPos = zeroY - 1;

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

    //Calculate new pos
    newPos = zeroX + (newPos * n);

    //Swap positions
    swapPos(move, newPos);

    //Check for duplicate board
    checkDuplicate(move);
}

//Y + 1
void Manager::down()
{
    int newPos;
    Container* move = new Container;

    newPos = zeroY + 1;

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

    //Calculate new pos
    newPos = zeroX + (newPos * n);

    //Swap positions
    swapPos(move, newPos);

    //Check for duplicate board
    checkDuplicate(move);
}

//X - 1
void Manager::left()
{
    int newPos;
    Container* move = new Container;

    newPos = zeroX - 1;

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

    //Calculate new pos
    newPos = newPos + (zeroY * n);

    //Swap positions
    swapPos(move, newPos);

    //Check for duplicate board
    checkDuplicate(move);
}

//X + 1
void Manager::right()
{
    int newPos;
    Container* move = new Container;

    newPos = zeroX + 1;

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

    //Calculate new pos
    newPos = newPos + (zeroY * n);

    //Swap positions
    swapPos(move, newPos);

    //Check for duplicate board
    checkDuplicate(move);
}

void Manager::findZero()
{
    for (int i = 0; i < n * n; ++i)
    {
        if (current->b[i] == 0)
        {
            zeroX = i % n;
            zeroY = i / n;
        }
    }
}

void Manager::swapPos(Container* move, int newPos)
{
    int oldPos;

    //Calculate old pos
    oldPos = zeroX + (zeroY * n);

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

    //Swap pos
    move->b[oldPos] = move->b[newPos];
    move->b[newPos] = 0;
}

bool Manager::checkDuplicate(Container* move)
{
    UINT64 code = encode(move->b);

    //Check if board has been found
    if (closed[code] == true)
    {
        return false;
    }
    else
    {
        //If it hasn't been found, set container values and add to open
        move->heuristic = calculateManhattan(move->b) + calculateLinear(move->b);
        move->parent = current;

        open.push(move);
    }

    return true;
}

void Manager::printSolution(Container* top)
{
    std::chrono::duration<double> t = end - start;

    Container* curr = top;
    std::vector<Container*> rev;
    bool go = true;
    int steps = 0;

    while (curr->parent)
    {
        rev.insert(rev.begin(), curr);

        curr = curr->parent;

        ++steps;
    }

    for (int i = 0; i < steps; ++i)
    {
        for (int j = 0; j < n * n; ++j)
        {
            std::cout << rev[i]->b[j] << "\t";

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

        Sleep(25);

        if (i != steps - 1)
        {
            system("CLS");
        }
    }

    std::cout << steps << " steps in " << t.count() << "s.";

    std::cin.get();
}

Main.cpp

#include "Manager.h"

int main()
{
    Manager manager;
    manager.Run();

    return 0;
}

Answer 1

Bugs:

• A lot of memory is allocated (foo = new Container) and never deallocated (delete foo).
• N-puzzle implementations usually make the blank tile the bottom-right corner, while this code puts it at the top-left. Are you sure the solvability conditions are still correct with this change? (I suspect it's currently trying to solve unsolvable problems).
• The linear conflict calculation seems slightly wrong (see below).

---

Code

General

• Use <cmath> not <math.h>. <cmath> defines things in the std:: namespace, instead of defining them globally.

• n would be more flexible if it were split into separate width and height (I don't think there's a requirement for these puzzles to be square?). It should also be tied to specific puzzle instances, and not a global variable. At the moment, if you want to test a 3x3 puzzle, and a 4x4 puzzle in the same program, it's impossible to do so.

• Changing n may silently break the encode function.

• Consider defining a Point class to store pairs of x and y values. Since converting from index to point (i % n, i / n) is common throughout the code, it would be neater to define something like:

  struct Point
  {
      Point() = delete;
  
      int x, y;
  };
  
  Point makePoint(int index)
  {
      assert(index >= 0);
      assert(index < n * n);
  
      return{ index % n, index / n };
  }
  
  int makeIndex(Point const& p)
  {
      assert(p.x >= 0);
      assert(p.x < n);
      assert(p.y >= 0);
      assert(p.y < n);
  
      return p.y * n + p.x;
  }
  

  If you decide to change how the indexing or storage works (e.g. to support variable width / height), you only need to change these two functions, instead of every instance of foo % n throughout the code.

• Be aware that std::map / std::unordered_map subscript operator creates a value in the map if one doesn't already exist with that key. It is usually better to use the count(), and insert() or emplace() functions.

---

Manager::Manager()

• Use the C++11 <random> functionality instead of srand and rand:

  auto rng = std::mt19937_64(std::random_device()());
  auto dist = std::uniform_int_distribution<int>(0, (n * n) - 1);
  ...
  val = dist(rng);
  

  Seeding the random number generator with std::random_device is the equivalent of seeding srand with time. However, omitting this argument will use the default seed, and thus produce the same output sequence every time, which might be useful to examine specific test cases.

• Define variables as close to their usage as possible. This means you don't have to worry about re-setting values in a loop (e.g. nums, val), and prevents variables being declared, and never used (there are a few of those in this code).

• There's a simpler way to generate a random test case using algorithms from the standard library:

  #include <numeric>
  #include <algorithm>
  ...
      auto rng = std::mt19937_64(std::random_device()());
  
      do
      {
          std::iota(current->b, current->b + n * n, 0); // fill current->b with values 0, 1, 2... (n * n - 1)
          std::shuffle(current->b, current->b + n * n, rng); // randomly shuffle the values!
  
          findZero();
  
      } while (!checkSolvable());
  

Manager copy constructor and destructor

• These should either do something (e.g. clean up allocated memory), or not be defined.

Manager::calculateLinear()

• The current implementation appears to be incorrect (based on this article):

  • It counts each conflict twice (because it searches in both directions for every tile).
  • It counts the blank space (value zero) in conflicts, which it shouldn't.

• We can make it a bit simpler by pre-calculating whether each value is in the correct row / column, then search down and right for conflicts:

  int Manager::calculateLinear(int b[])
  {
      auto conflicts = 0;
  
      {
          bool in_col[n * n] = { }; // set to true if this value is in the correct column
          bool in_row[n * n] = { }; // set to true if this value is in the correct row
  
          for (auto y = 0; y != n; ++y)
          {
              for (auto x = 0; x != n; ++x)
              {
                  auto i = y * n + x;
  
                  auto bx = b[i] % n;
                  auto by = b[i] / n;
  
                  in_col[i] = (bx == x);
                  in_row[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) // ignore the empty space
                      continue;
  
                  if (in_col[i])
                  {
                      for (auto r = y; r != n; ++r) // check down for conflicts
                      {
                          auto j = r * n + x;
  
                          if (b[j] == 0) // ignore the empty space
                              continue;
  
                          if (in_col[j] && b[j] < b[i])
                              ++conflicts;
                      }
                  }
  
                  if (in_row[i])
                  {
                      for (auto c = x; c != n; ++c) // check right for conflicts
                      {
                          auto j = y * n + c;
  
                          if (b[j] == 0) // ignore the empty space
                              continue;
  
                          if (in_row[j] && b[j] < b[i])
                              ++conflicts;
                      }
                  }
              }
          }
      }
  
      return 2 * conflicts;
  }
  

---

Memory Use

• Rather than storing booleans in the closed map, we can store the encoded parent. This allows the path to be reconstructed from the closed map, and the Containers themselves don't need to store a parent pointer.
• This means Containers can be stored by value (or at least inside std::unique_ptrs), which will solve the memory leak.

---

Design

• Since this is a search algorithm, I'd actually suggest removing the Manager class entirely, and going for a purely functional approach.

• Don't use global variables at all. Data structures can be passed between functions by value, reference or const reference as appropriate. This might seem like more work to start with, but it ends up being a lot cleaner as the inputs to each function are immediately apparent. Testing individual parts of the code (e.g. checkSolvable) becomes much simpler as test cases can be passed directly to the function to be tested.

  namespace NPuzzles
  {
  
      using BoardT = std::vector<std::uint8_t>;
  
      namespace
      {
  
          bool solvable(BoardT const& board, std::uint8_t width, std::uint8_t height)
          {
              // ...
          }
  
          // other functions
  
      } // anonymous
  
  
      std::vector<BoardT> solve(BoardT const& board, std::uint8_t width, std::uint8_t height)
      {
          if (!solvable(board, width, height))
              return{ };
  
          // solve ...
      }
  
  } // NPuzzles
  

  solve is the main entry point, and enclosed in a namespace. The inner functions are defined in an anonymous namespace that effectively makes them visible only in this code file. Creating test cases or printing out the solution should be done separately.

• std::vector is much easier to use than c-style arrays (it initializes its contents properly, and can be passed by value if desired).

Answer 2

Platform-dependent code

There's no need to bring in <Windows.h> - with a couple of small changes, this can be portable C++, accessible to everyone:

#include <cstdint>
using UINT64 = std::uint_fast64_t;  /* this is the quick fix - really, just
                                       use the standard type everywhere */

// another quick fix
#include <thread>
void Sleep(unsigned int ms)
{
    std::this_thread::sleep_for(std::chrono::milliseconds{ms});
}

Prefer C++ headers

Unless you're providing functions with C linkage, prefer to include the C++ versions of standard headers (e.g. <ctime>, <cmath>).

Don't include unnecessary headers

The header brings in many standard headers that aren't required for the interface, only for the implementation. Remove these and move them into Manager.cpp where they don't affect other translation units (e.g. Main.cpp):

#include <cmath>
#include <ctime>
#include <iostream>
#include <random>
#include <thread>

Don't expose internals

n, Container and GreaterThanByCost shouldn't be visible to client code - these could usefully be private static members. And we should aspire to allowing n to be specified as a parameter.

Naming

Manager is the single least useful class name I've encountered. And the vague naming is then reflected in its contents: it doesn't seem to know what its job is. It holds a starting position and finds a solution, but it also seems to perform timing and it exposes methods such as encode() that have no value to users of the class (and should probably be private).

Copy constructor

This constructor is worse than useless:

Manager::Manager(const Manager& other)
{}

It's better to make Manager non-copyable:

Manager(const Manager&) = delete;
void operator=(const Manager&) = delete;

Encode and decode

That's a cute method to cram a 4x4 board position into 64 bits of storage, but it all falls apart with larger board sizes. The cleverness constrains the code.

It might be possible to use this technique for small boards and fall back to more general code at bigger sizes; my recommendation is to write the general code first, and then determine whether there's a benefit to optimising.

Solvability check

There's likely a bug in checkSolvable(), but it's hard to identify it, because we can't test this method in isolation. This is a good motivation to break apart the big monolithic Manager class into smaller components that can be used together, then we'll be able to test functions such as this before putting them together into a program.

Printing solution

This method really should be const, as should its argument.

It's very inefficient to insert() to the front of a vector. Use a container such as std::stack that's designed for that, or push_back() instead, and std::reverse once, afterwards. Better still, push_back() and then access the elements in reverse order:

void Manager::printSolution(const Container* top) const
{
    std::chrono::duration<double> t = end - start;

    std::vector<const Container*> steps;
    for (auto c = top;  c->parent;  c = c->parent) {
        steps.push_back(c);
    }

    for (auto i = steps.crbegin();  i != steps.crend();  ++i) {
        printBoard(*i);
        std::this_thread::sleep_for(std::chrono::milliseconds{25});
    }

    std::cout << steps.size() << " steps in " << t.count() << "s." << std::endl;
}

Memory leaks

I get several megabytes leaked each run:

==28303== 35,680 (31,680 direct, 4,000 indirect) bytes in 396 blocks are definitely lost in loss record 6 of 9
==28303==    at 0x4835E2F: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==28303==    by 0x10B15E: Manager::right() (205667.cpp:496)
==28303==    by 0x10AFCE: Manager::addMoves() (205667.cpp:417)
==28303==    by 0x10A685: Manager::Run() (205667.cpp:127)
==28303==    by 0x10B5BA: main (205667.cpp:606)
==28303== 
==28303== 35,680 (32,080 direct, 3,600 indirect) bytes in 401 blocks are definitely lost in loss record 7 of 9
==28303==    at 0x4835E2F: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==28303==    by 0x10B0E4: Manager::left() (205667.cpp:472)
==28303==    by 0x10AFC2: Manager::addMoves() (205667.cpp:416)
==28303==    by 0x10A685: Manager::Run() (205667.cpp:127)
==28303==    by 0x10B5BA: main (205667.cpp:606)
==28303== 
==28303== 44,160 (29,600 direct, 14,560 indirect) bytes in 370 blocks are definitely lost in loss record 8 of 9
==28303==    at 0x4835E2F: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==28303==    by 0x10AFE8: Manager::up() (205667.cpp:424)
==28303==    by 0x10AFAA: Manager::addMoves() (205667.cpp:414)
==28303==    by 0x10A685: Manager::Run() (205667.cpp:127)
==28303==    by 0x10B5BA: main (205667.cpp:606)
==28303== 
==28303== 53,520 (33,440 direct, 20,080 indirect) bytes in 418 blocks are definitely lost in loss record 9 of 9
==28303==    at 0x4835E2F: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==28303==    by 0x10B066: Manager::down() (205667.cpp:448)
==28303==    by 0x10AFB6: Manager::addMoves() (205667.cpp:415)
==28303==    by 0x10A685: Manager::Run() (205667.cpp:127)
==28303==    by 0x10B5BA: main (205667.cpp:606)

These really need to be fixed.

Answer 3

I have updated my code quite a bit with many of your guys' suggestions. At least to the best of my ability anyway. I haven't done absolutely everything, but I did away with the class structure, went with the namespace structure suggested by @user673679. It's not perfect, but I think it looks better. I also implemented the linear conflict function according to your code as well. Took me a little bit to fully understand it, but I typed it line-by-line and I think I got it. I had to change a couple things to !bool though. I passed in an almost solved board and it returned a heuristic of like 18.

I also believe I've fixed the checkSolvable. I also tried to go through and update some variable names to be more concise. Passed things as const when they weren't going to be changed. Stuff like that.

Now, somewhere down the line, I managed to mess up the priority queue. It is no longer being inserted in a sorted manner. I say this because I know it doesn't sort, it just inserts according to whatever priority you give it. Do you guys think it might be better to go with a plain vector and use std::sort?

Main.cpp

#include "Functions.h"

int main()
{
    std::chrono::system_clock::time_point start, end;
    std::vector<int> b;

    //Open list contains all unexplored nodes, sorted by heuristic value
    std::priority_queue<Npuzzle::Container*,
                        std::vector<Npuzzle::Container*>,
                        Npuzzle::GreaterThanByHeur> open;

    //Closed list contains all explored nodes, with values set to encoded parent board
    std::unordered_map<std::uint_fast64_t,
                        std::uint_fast64_t> closed;

    int 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();

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

    int 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 <iomanip>
#include <iostream>
#include <unordered_map>
#include <queue>
#include <thread>

#include "Npuzzle.h"

bool duplicate(
    std::vector<int> b,
    std::unordered_map<std::uint_fast64_t, std::uint_fast64_t>& closed,
    const int n)
{
    return closed.count(Npuzzle::encode(b, n));
}

void addQueue(
    std::vector<int> b,
    std::vector<int> parent,
    std::priority_queue<Npuzzle::Container*, std::vector<Npuzzle::Container*>, Npuzzle::GreaterThanByHeur>& open,
    std::unordered_map<std::uint_fast64_t, std::uint_fast64_t>& closed,
    const int n)
{
    auto c = new Npuzzle::Container;

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

    open.emplace(c);

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

void addMoves(
    const std::vector<int> b,
    std::priority_queue<Npuzzle::Container*, std::vector<Npuzzle::Container*>, Npuzzle::GreaterThanByHeur>& open,
    std::unordered_map<std::uint_fast64_t, std::uint_fast64_t>& closed,
    const int n)
{
    auto moves = std::vector<std::vector<int>>(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(
    std::priority_queue<Npuzzle::Container*, std::vector<Npuzzle::Container*>, Npuzzle::GreaterThanByHeur>& open,
    std::unordered_map<std::uint_fast64_t, std::uint_fast64_t>& closed)
{
    while (!open.empty())
    {
        delete open.top();
        open.pop();
    }

    closed.clear();
}

void printBoard(
    const std::vector<int> 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(
    std::uint_fast64_t b,
    std::unordered_map<std::uint_fast64_t, std::uint_fast64_t> closed,
    const int n)
{
    std::vector<std::vector<int>> solution;

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

    for (auto p = closed[b]; p != 0; p = closed[p])
    {
        solution.push_back(Npuzzle::decode(p, n));
    }

    system("CLS");

    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(
    std::vector<int>& curr,
    std::priority_queue<Npuzzle::Container*, std::vector<Npuzzle::Container*>, Npuzzle::GreaterThanByHeur>& open,
    std::unordered_map<std::uint_fast64_t, std::uint_fast64_t>& closed,
    const int n)
{
    cleanup(open, closed);

    curr = Npuzzle::createBoard(n);

    addQueue(curr, std::vector<int>(n * n), open, closed, n);
}

void solve(
    std::vector<int>& curr,
    std::priority_queue<Npuzzle::Container*, std::vector<Npuzzle::Container*>, Npuzzle::GreaterThanByHeur>& open,
    std::unordered_map<std::uint_fast64_t, std::uint_fast64_t>& closed,
    const int n)
{
    auto solved = false;

    //Create initial board
    curr = Npuzzle::createBoard(n);
    //curr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 0, 15 };

    addQueue(curr, std::vector<int>(n * n), open, closed, n);

    while (!solved)
    {
        if (open.top()->heuristic == 0)
        {
            solved = true;
        }
        else
        {
            curr = Npuzzle::decode(open.top()->code, n);

            delete open.top();
            open.pop();

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

Npuzzle.h

#include <assert.h>
#include <cstdint>
#include <numeric>
#include <random>
#include <vector>

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

    struct Container
    {
        int heuristic;
        std::uint_fast64_t code;
    };

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

    Point findZero(
        const std::vector<int> b,
        const int n)
    {
        for (int 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 std::vector<int> b,
        const int n)
    {
        auto count = 0;

        for (auto i = 0; i < n * n - 1; ++i)
        {
            for (int 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 std::vector<int> b,
        const int n)
    {
        Point zero = findZero(b, n);
        int 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;
    }

    std::vector<int> createBoard(
        const int n)
    {
        std::vector<int> board(n * n);
        std::mt19937_64 rng = std::mt19937_64(std::random_device()());

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

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

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

        return board;
    }

    std::vector<int> decode(
        std::uint_fast64_t code,
        const int n)
    {
        static std::vector<int> b(n * n);

        for (int i = (n * n) - 1; i >= 0; --i)
        {
            int 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;
    }

    std::vector<int> swapPos(
        const std::vector<int> b,
        const int n,
        const Point zero,
        const int newPos)
    {
        int oldPos;
        std::vector<int> move(n * n);

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

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

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

        return move;
    }

    std::vector<int> down(
        const std::vector<int> b,
        const int n)
    {
        Point zero = findZero(b, n);
        int newPos = zero.y + 1;

        //Check if move is possible
        if (newPos > (n - 1))
        {
            return std::vector<int>(0);
        }

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

    std::uint_fast64_t encode(
        const std::vector<int> b,
        const int n)
    {
        std::uint_fast64_t code = 0;

        for (int 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 std::vector<int> b,
        const int n)
    {
        auto conflicts = 0;

        std::vector<bool> inCol(n * n);
        std::vector<bool> inRow(n * n);

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

                auto bX = b[i] % n;
                auto 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] && (b[j] < b[i]))
                        {
                            ++conflicts;
                        }
                    }
                }

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

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

                        if (!inRow[j] && (b[j] < b[i]))
                        {
                            ++conflicts;
                        }
                    }
                }
            }
        }

        return 2 * conflicts;
    }

    int manhattan(
        const std::vector<int> b,
        const int n)
    {
        int m = 0;

        std::vector<int> solution(n * n);
        std::iota(solution.begin(), solution.end(), 1);

        solution[n * n - 1] = 0;

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

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

                //Calculate the current pos
                x = i % n;
                y = i / n;

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

        return m;
    }

    int heuristic(
        const std::vector<int> b,
        const int n)
    {
        return manhattan(b, n) + linear(b, n);
    }

    std::vector<int> left(
        const std::vector<int> b,
        const int n)
    {
        Point zero = findZero(b, n);
        int newPos = zero.x - 1;

        //Check if move is possible
        if (newPos < 0)
        {
            return std::vector<int>(0);
        }

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

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

        //Check if move is possible
        if (newPos > (n - 1))
        {
            return std::vector<int>(0);
        }

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

    std::vector<int> up(
        const std::vector<int> b,
        const int n)
    {
        Point zero = findZero(b, n);
        int newPos = zero.y - 1;

        //Check if move is possible
        if (newPos < 0)
        {
            return std::vector<int>(0);
        }

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