#include "StdAfx.h"
#include "puzzle.h"

//#define output

Puzzle::Puzzle(int dx, int dy, int dz) : projection()
{
	instanceCounter = 0;
	for(int i = 0; i < xD * yD * zD; i++)
		for(int p = 0; p < numParts; p++) instancesByBitsCounter[i][p] = 0;
}

Puzzle::~Puzzle(void)
{
}

void Puzzle::addPart(Part* part)
{
	part->addToPuzzle(this);
}

int Puzzle::solve(void)
{
	usedParts = new bool[numParts];
	for(int p = 0; p < numParts; p++) usedParts[p] = false;
	foundPossibilities = 0;
	int x, y, z;

	//initializing space
	for(z = 0; z < zD; z++)
		for(y = 0; y < yD; y++)
			for(x = 0; x < xD; x++)
				space[x][y][z] = -1;

	recursiveSolve(0, 0, 0);

	return foundPossibilities;
}

void Puzzle::insertInstance(Instance instance)
{
	instances[instanceCounter++] = instance;
	for(int i = 0; i < xD * yD * zD; i++) 
		if(instance.hash.getBit(i))
			instancesByBits[i][instance.part->partNo][instancesByBitsCounter[i][instance.part->partNo]++] = instance;
}

void Puzzle::recursiveSolve(int depth, int nextBit, BitVector allocation)
{
	if(depth >= numParts)
	{
		foundPossibilities++;
#ifdef output
		debugOutput();
		allocation.debugOutput(&projection);
#endif
		return;
	}
	
	BitVector nextAllocation;
	int zeroBit, low = 0;
	__int64 mask = ((__int64) 1) << (nextBit + 1), nextMask;
	for(int p = 0; p < numParts; p++)
	{
		if(!usedParts[p])
		{
			usedParts[p] = true;
			for(int i = 0; i < instancesByBitsCounter[nextBit][p]; i++)
			{
				if(depth == 0) cout << low++ << "/109: " << foundPossibilities  << endl;
				if((instancesByBits[nextBit][p][i].hash & allocation) == 0)
				{
					nextAllocation = allocation | instancesByBits[nextBit][p][i].hash;
#ifdef output
					instancesByBits[nextBit][p][i].map(this);
#endif
					nextMask = mask;
					for(zeroBit = nextBit + 1; nextMask & nextAllocation; zeroBit++) nextMask <<= 1;

					recursiveSolve(depth + 1, zeroBit, nextAllocation);

#ifdef output
					instancesByBits[nextBit][p][i].map(this, true);
#endif
				}
			}
			usedParts[p] = false;
		}
	}
}

void Puzzle::debugOutput(void)
{
	int x, y, z;

	cout << "---------------------------------------------------" << endl;
	for(x = 0; x < xD; x++)
	{
		cout << "x = " << x << endl;
		for(y = 0; y < yD; y++)
		{
			for(z = 0; z < zD; z++)
			{
				if(space[x][y][z] == -1) cout << "  ";
				else cout << hex << space[x][y][z] << ' ';
			}
			cout << endl;
		}
	}
	waitkey();
}
