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));
}
}