// triangle.cpp

#include <iostream>
using namespace std;

#include "triangle.h"

static const int moves[36][3] = {
						{0,   1,   3},
						{0,   2,   5},
						{1,   3,   6},
						{1,   4,   8},
						{2,   4,   7},
						{2,   5,   9},
						{3,   1,   0},
						{3,   7,   12},
						{3,   6,   10},
						{3,   4,   5},

						{4,   7,   11},
						{4,   8,   13},
						{5,   8,   12},
						{5,   4,   3},
						{5,   2,   0},
						{5,   9,   14},
						{6,   7,   8},
						{6,   3,   1},
						{7,   4,   2},
						{7,   8,   9},

						{8,   7,   6},
						{8,   4,   1},
						{9,   8,   7},
						{9,   5,   2},
						{10,  6,   3},
						{10,  11,  12},
						{11,  7,   4},
						{11,  12,  13},
						{12,  7,   3},
						{12,  8,   5},
						
						{12,  11,  10},
						{12,  13,  14},
						{13,  12,  11},
						{13,  8,   4},
						{14,  13,  12},
						{14,  9,   5}};


int Triangle::solve(int conf)	
{
	int nholes(1);   // Number of holes
	int mov(0);      // Current move, range 0..35
	int path[15];    // The first (nholes-1) positions of path specify the moves
	                 // done up to now.
	int count(0);    // Number of solutions from a specific start triangle
	bool do_print(true); // It is true if we want to print out individual solutions

	atriangle[conf] = 0;
	print_triangle();
	while (nholes > 0) {
		if (mov == 36) {
			nholes--;
			// undo last move except first
			if (nholes > 0) { 
				// undo last move
				atriangle[moves[path[nholes-1]][0]] = 1;
				atriangle[moves[path[nholes-1]][1]] = 1;
				atriangle[moves[path[nholes-1]][2]] = 0;
				mov = path[nholes-1]+1;
			}
			continue;
		}
		if (atriangle[moves[mov][0]] == 1 &&
			atriangle[moves[mov][1]] == 1 &&
			atriangle[moves[mov][2]] == 0) {  // The mov-th move can be applied
				atriangle[moves[mov][0]] = 0; // Apply mov-th move to obtain nextstate
				atriangle[moves[mov][1]] = 0;
			    	atriangle[moves[mov][2]] = 1;
				path[nholes-1] = mov;
				nholes++;
				mov = 0;
				if (nholes == 14) { // We got a solution
					if (do_print) {
						// print out this solution
						cout << "    Moves: -----------------------------------\n";
						for (int k = 0; k < 13; ++k) {
							cout << "\t  [" <<  moves[path[k]][0] << ", " << moves[path[k]][1] 
								 << ", " << moves[path[k]][2] << "]" << endl;
						}
						cout << "Do you want to print next solution [y/n]?";
						char line[256];
						cin.getline(line, 255);
						if (line[0] != 'y')
							do_print = false;
						else
							cout << "    ------------------------------------------\n";
					}
					count++;
				}
		} else
			mov++;
	}
	atriangle[conf] = 1;
	return count;
}


void Triangle::print_triangle(void) const
{
	int k = 0;
	for (int row = 0; row < 5; ++row) {
		cout << '\t';
		for (int h = 0; h < 4 - row; ++h)
			cout << "   ";
		for (int col = 0; col < 1 + row; ++col) 
			cout << ((atriangle[k++] == 0)?'o':'X') << "     ";
		cout << endl;
	}
}