// Sliding blocks puzzle solver by Michael Chock, USA
//
// The basic algorithm is Iterative Deepening A* using total Manhattan
// distance as the metric.  Funky optimizations include representing
// the entire board as a 64-bit integer and transforming the cost
// function.  If a tile moves toward its goal position the cost estimate
// does not change, but if it moves away then the cost estimate increases
// by two moves, so the cost estimate can be calculated purely in terms
// of the current move and the cost estimate for the previous board.
// There is no need to accurately compute the initial cost estimate since
// it just winds up being a constant added to every other estimate.
// Since a Manhattan distance increase always adds 2 to the cost estimate
// it's possible to just use a simple increment to eliminate the constant
// factor of 2.  Finally, any cost estimate that exceeds the maximum used
// by the IDA* algorithm always does so by exactly 1, so there is no
// need to track what the next maximum should be; it will always be an
// increase of 1.
#include <iomanip>
#include <iostream>
#include <fstream>
#include <queue>
#include <string>
#include <vector>

#include <windows.h>

using namespace std;

namespace
{

const int NUM_PUZZLES(1000);
string puzzles[NUM_PUZZLES];
string solutions[NUM_PUZZLES];
LONG lastPuzzle(-1);

struct State
{
	__int64 board;
	short score;
	char emptyPos;
	char lastMoved;
};

int getValue(__int64 board, int index)
{
	return (((0xfLL << index * 4) & board) >> index * 4) & 0xf;
}
void setValue(__int64& board, int index, __int64 value)
{
	// target position should already be zero
	board |= value << index * 4;
}
void clearValue(__int64& board, int index)
{
	board &= ~(0xfLL << index * 4);
}
int getTargetPos(char c)
{
	if (c == 0)
		return 15;
	return c - 1;
}

bool createMove(State& newState, const State& lastState, int maxScore, int toMove)
{
	if (getValue(lastState.board, toMove) == lastState.lastMoved)
		return false;

	newState = lastState;
	newState.emptyPos = toMove;
	newState.lastMoved = getValue(newState.board, toMove);
	clearValue(newState.board, toMove);
	setValue(newState.board, lastState.emptyPos, newState.lastMoved);
	int targetPos(getTargetPos(newState.lastMoved));
	int targetRow(targetPos >> 2);
	int targetCol(targetPos & 0x3);

	// Increased Manhattan distance
	if (abs((toMove & 0x3) - targetCol) + abs((toMove >> 2) - targetRow) <
		abs((lastState.emptyPos & 0x3) - targetCol) + 
		abs((lastState.emptyPos >> 2) - targetRow))
	{
		++newState.score;
	}

	// Other heuristics (linear conflict, last moves, corner tiles) would
	// probably improve things, but I ran out of time.
	return newState.score <= maxScore;
}

bool dfs_solve(const State& state, int maxScore, vector<char>& result)
{
	static const char digits[] = "0123456789ABCDEF";

	if (state.score > maxScore)
		return false;

	if (state.board == 0x0FEDCBA987654321LL)
	{
		result.push_back('\0');
		return true;
	}

	State newState;
	if ((state.emptyPos & 0x3) != 0)
	{
		if (createMove(newState, state, maxScore, state.emptyPos - 1))
		{
			result.push_back(digits[newState.lastMoved]);
			if (dfs_solve(newState, maxScore, result))
				return true;

			result.pop_back();
		}
	}

	if ((state.emptyPos & 0x3) != 3)
	{
		if (createMove(newState, state, maxScore, state.emptyPos + 1))
		{
			result.push_back(digits[newState.lastMoved]);
			if (dfs_solve(newState, maxScore, result))
				return true;

			result.pop_back();
		}
	}

	if ((state.emptyPos >> 2) != 0)
	{
		if (createMove(newState, state, maxScore, state.emptyPos - 4))
		{
			result.push_back(digits[newState.lastMoved]);
			if (dfs_solve(newState, maxScore, result))
				return true;

			result.pop_back();
		}
	}

	if ((state.emptyPos >> 2) != 3)
	{
		if (createMove(newState, state, maxScore, state.emptyPos + 4))
		{
			result.push_back(digits[newState.lastMoved]);
			if (dfs_solve(newState, maxScore, result))
				return true;

			result.pop_back();
		}
	}

	return false;
}

string idas_solve(const char* initialBoard)
{
	State initialState;
	initialState.board = 0;

	for (int i(0); i < 16; ++i)
	{
		if (initialBoard[i] <= '9')
			setValue(initialState.board, i, initialBoard[i] - '0');
		else
			setValue(initialState.board, i, initialBoard[i] - 'A' + 10);
	}

	initialState.emptyPos = find(initialBoard, initialBoard + 16, '0') - 
		initialBoard;
	initialState.score = 0;
	initialState.lastMoved = 0;

	vector<char> result;
	int maxScore(0);
	while (!dfs_solve(initialState, maxScore, result))
		++maxScore;
	return &result[0];
}

DWORD WINAPI solveCallback(LPVOID /*lpParam*/)
{
	while (true)
	{
		int index(InterlockedIncrement(&lastPuzzle));

		if (index >= NUM_PUZZLES)
			return 0;

		cout << '*' << flush;
		string result = idas_solve(puzzles[index].c_str());
		solutions[index] = result;
	}

	return 0;
}

} // namespace


int main(int argc, char* argv[])
{
	SYSTEM_INFO info = { 0 };
	::GetNativeSystemInfo(&info);
	DWORD numThreads(info.dwNumberOfProcessors); 
	vector<HANDLE> threads;
	threads.reserve(numThreads);
	LARGE_INTEGER frequency;
	::QueryPerformanceFrequency(&frequency);
	LARGE_INTEGER start, stop;

	::QueryPerformanceCounter(&start);

	ifstream inFile("moves.txt");
	for (int i(0); i < NUM_PUZZLES; ++i)
		inFile >> puzzles[i];

	if (inFile.fail())
	{
		cerr << "Couldn't read input file!" << endl;
		return 1;
	}

	for (DWORD i(0); i < numThreads; ++i)
		threads.push_back(CreateThread(0, 0, solveCallback, 0, 0, 0));

	WaitForMultipleObjects(numThreads, &threads[0], TRUE, INFINITE);

	ofstream outFile("solutions.txt");
	outFile << setfill('0');

	for (int i(0); i < NUM_PUZZLES; ++i)
	{
		outFile << setw(4) << i + 1 << ' ' << puzzles[i] << ' ' << 
			solutions[i] << '\n';
	}

	outFile.flush();
	QueryPerformanceCounter(&stop);
	cout << "\nTotal time: " <<
		double(stop.QuadPart - start.QuadPart) / frequency.QuadPart <<
		" seconds" << endl;
	return 0;
}