Triangle cube puzzle solver

TriangleCube.cpp

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>

#include <cassert>

int add(int const a, int const b)
{
	int val = a + b;
	if (val >= 4)
		val -= 4;
	if (val < 0)
		val += 4;
	return val;
}

int sub(int const a, int const b)
{
	return add(a, -b);
}

struct Piece
{
	int Id;
	int LeftFace, RightFace, TopFace;
	int Rotation;

	Piece rotate() const
	{
		return Piece(Id, add(TopFace, -2), add(RightFace, -1), add(LeftFace, -1), Rotation + 1);
	}

	Piece(int const id, int const leftFace, int const topFace, int const rightFace, int const rotation = 0)
		: Id(id), LeftFace(leftFace), RightFace(rightFace), TopFace(topFace), Rotation(rotation)
	{
		if (Rotation >= 3)
			Rotation -= 3;
	}

	bool const operator == (Piece const & o) const
	{
		return o.LeftFace == LeftFace && o.RightFace == RightFace && o.TopFace == TopFace && o.Rotation == Rotation;
	}

	void print()
	{
		std::cout << Id << " (" << Rotation << ") " << LeftFace << ", " << TopFace << ", " << RightFace << std::endl;
	}
};

bool const matchl(int face1, int face2)
{
	return face2 == add(face1, 1);
}

bool const matchlend(int face1, int face2)
{
	return face2 == add(face1, 3);
}

bool const matchlt(int face1, int face2)
{
	return face2 == add(face1, -1);
}

bool const matcht(int face1, int face2)
{
	return face2 == add(face1, 2);
}

bool const equal(int face1, int face2)
{
	return face1 == face2;
}

bool const matchOffset(int const face1, int const face2, int const offset)
{
	return face2 == add(face1, offset);
}

bool const matchSide(int const face1, int const face2)
{
	switch (face1)
	{
	case 0:
		return 3 == face2;
	case 1:
		return 2 == face2;
	case 2:
		return 1 == face2;
	case 3:
		return 0 == face2;
	}

	assert(false);
	return false;
}

bool const matchTop(int const face1, int const face2)
{
	switch (face1)
	{
	case 0:
		return 0 == face2;
	case 1:
		return 3 == face2;
	case 2:
		return 2 == face2;
	case 3:
		return 1 == face2;
	}

	assert(false);
	return false;
}

bool const isOk(std::vector<Piece> const & solution)
{
	bool OK = true;

	if (solution.size() > 1)
		OK &= matchSide(solution[0].RightFace, solution[1].LeftFace);
	if (solution.size() > 2)
		OK &= matchSide(solution[1].RightFace, solution[2].LeftFace);
	if (solution.size() > 3)
		OK &= matchSide(solution[2].RightFace, solution[3].LeftFace);
	if (solution.size() > 3)
		OK &= matchSide(solution[3].RightFace, solution[0].LeftFace);

	if (solution.size() > 4)
		OK &= matchTop(solution[0].TopFace, solution[4].TopFace);
	if (solution.size() > 5)
		OK &= matchTop(solution[1].TopFace, solution[5].TopFace);
	if (solution.size() > 6)
		OK &= matchTop(solution[2].TopFace, solution[6].TopFace);
	if (solution.size() > 7)
		OK &= matchTop(solution[3].TopFace, solution[7].TopFace);

	if (solution.size() > 5)
		OK &= matchSide(solution[4].LeftFace, solution[5].RightFace);
	if (solution.size() > 6)
		OK &= matchSide(solution[5].LeftFace, solution[6].RightFace);
	if (solution.size() > 7)
		OK &= matchSide(solution[6].LeftFace, solution[7].RightFace);
	if (solution.size() > 7)
		OK &= matchSide(solution[7].LeftFace, solution[4].RightFace);

	return OK;
}

int solutionCount = 0;

void solve(std::vector<Piece> solution, std::vector<Piece> remaining)
{
	//std::cout << solution.size() << " layers deep!" << std::endl;
	if (solution.size() == 8)
	{
		if (remaining.size() == 0)
			solutionCount ++;//std::cout << "Found solution! " << std::endl;
		else
			std::cout << "Partial solution: " << std::endl;
		if (solutionCount == 1)
		{
			for (auto it = solution.begin(); it != solution.end(); ++ it)
				std::cout << it->Id << " (" << it->Rotation << ") " << it->LeftFace << ", " << it->TopFace << ", " << it->RightFace << std::endl;
			std::cout << std::endl;
		}
		//system("PAUSE");
	}

	int i = 0;
	for (auto it = remaining.begin(); it != remaining.end(); ++ it, ++ i)
	{
		Piece p = * it;
		for (int rotation = 0; rotation < 3; ++ rotation)
		{
			p = p.rotate();

			std::vector<Piece> remaining_now = remaining;
			remaining_now.erase(remaining_now.begin() + i);

			std::vector<Piece> solution_now = solution;
			solution_now.push_back(p);

			if (isOk(solution_now))
				solve(solution_now, remaining_now);
		}
		assert(p == * it);
	}
}

std::vector<Piece> makeSolution(std::vector<Piece> const & Pieces, 
	int i0, int i1, int i2, int i3, int i4, int i5, int i6, int i7)
{
	std::vector<Piece> solution;
	solution.push_back(Pieces[i0]);
	solution.push_back(Pieces[i1]);
	solution.push_back(Pieces[i2]);
	solution.push_back(Pieces[i3]);
	solution.push_back(Pieces[i4]);
	solution.push_back(Pieces[i5]);
	solution.push_back(Pieces[i6]);
	solution.push_back(Pieces[i7]);
	return solution;
}

int main()
{
	std::vector<Piece> Pieces;
	/*Pieces.push_back(Piece(0, 2, 2, 0));
	Pieces.push_back(Piece(1, 2, 2, 2));
	Pieces.push_back(Piece(2, 3, 3, 1));
	Pieces.push_back(Piece(3, 3, 3, 3));
	Pieces.push_back(Piece(4, 2, 3, 2));
	Pieces.push_back(Piece(5, 1, 1, 3));
	Pieces.push_back(Piece(6, 2, 1, 3));
	Pieces.push_back(Piece(7, 1, 2, 1));*/

	/*Pieces.push_back(Piece(0, 0, 3, 1).rotate());
	Pieces.push_back(Piece(1, 0, 1, 1));
	Pieces.push_back(Piece(2, 2, 1, 0).rotate());
	Pieces.push_back(Piece(3, 0, 1, 0).rotate().rotate());

	Pieces.push_back(Piece(4, 1, 1, 1).rotate().rotate());
	Pieces.push_back(Piece(5, 0, 3, 2).rotate().rotate());
	Pieces.push_back(Piece(6, 0, 0, 2).rotate());
	Pieces.push_back(Piece(7, 0, 0, 0));*/

	Pieces.push_back(Piece(0, 0, 3, 1));
	Pieces.push_back(Piece(1, 0, 1, 1));
	Pieces.push_back(Piece(2, 2, 1, 0));
	Pieces.push_back(Piece(3, 0, 1, 0));

	Pieces.push_back(Piece(4, 1, 1, 1));
	Pieces.push_back(Piece(5, 0, 3, 2));
	Pieces.push_back(Piece(6, 0, 0, 2));
	Pieces.push_back(Piece(7, 0, 0, 0));

	/*std::vector<Piece> solution = makeSolution(Pieces, 0, 1, 6, 7, 3, 4, 2, 5);

	for (auto it = solution.begin(); it != solution.end(); ++ it)
		std::cout << it->Id << " (" << it->Rotation << ") " << it->LeftFace << ", " << it->TopFace << ", " << it->RightFace << std::endl;
		
	std::cout << std::endl;
	std::cout << isOk(solution) << std::endl;
	Pieces[0].print();
	Pieces[0].rotate().print();
	Pieces[0].rotate().rotate().print();*/

	for (auto it = Pieces.begin(); it != Pieces.end(); ++ it)
		assert((* it) == (* it).rotate().rotate().rotate());

	std::vector<Piece> solution;
	solution.push_back(Pieces[0]);
	Pieces.erase(Pieces.begin());
	solve(solution, Pieces);

	std::cout << "There are" << solutionCount << "solutions" << std::endl;
	system("PAUSE");
	return 0;
}