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;
}
<Windows.h>
? If I include<cstdint>
instead, I canusing UINT64 = std::uint64_t;
and replace theSleep()
withstd::this_thread::sleep_for()
, and it compiles more portably. Well, almost compiles - there's nomain()
! \$\endgroup\$ – Toby Speight Oct 16 '18 at 9:41main()
that creates the starting positions, it's hard to tell... \$\endgroup\$ – Toby Speight Oct 16 '18 at 9:44