/* pqsolver.cpp
 * Copyright (c) 2007 Joe Rumsey
 *
 * Solves Puzzle Quest capture puzzles.
 *
 * License: You must do what you think is right, of course.
 */

#include <stdio.h>
#include <string.h>

enum Gem {
	empty,
	red,
	yellow,
	blue,
	green,
	skull,
	skullx5,
	money,
	xp,
	wildcard
};

static int s_moveCount = 0;
const int BOARD_SIZE = 8;
class Board {
public:
	Gem m_board[BOARD_SIZE][BOARD_SIZE];

	Board() { 
		memset(m_board, 0, sizeof(m_board));
	}
	Board(const Board &src) {
		memcpy(m_board, src.m_board, sizeof(m_board));
	}

	bool IsManaGem(Gem g) {
		return (g == red) || (g == yellow) || (g == blue) || (g == green);
	}

	bool Match(Gem g1, Gem g2) {
		if(IsManaGem(g1) && g2 == wildcard)
			return true;
		if(IsManaGem(g2) && g1 == wildcard)
			return true;

		if(g1 == skull && g2 == skullx5)
			return true;
		if(g1 == skullx5 && g2 == skull)
			return true;

		return g1 == g2;
	}

	void Explode(int xc, int yc, Board &into) {
		into.m_board[xc][yc] = empty; // Don't recurse on this square
		int x, y;
		for(x = xc - 1; x <= xc + 1; x++) {
			if(x < 0 || x >= BOARD_SIZE)
				continue;

			for(y = yc -1; y <= yc + 1; y++) {
				if(y < 0 || y >= BOARD_SIZE)
					continue;

				Clear(x, y, into);
			}
		}
	}

	void Clear(int x, int y, Board &into) {
		if(m_board[x][y] == skullx5 && into.m_board[x][y] == skullx5) {
			Explode(x, y, into);
		} else {
			into.m_board[x][y] = empty;
		}
	}

	bool CheckRow(int xstart, int y, Board &into) {
		bool changed = false;
		int x;
		Gem start = m_board[xstart][y];
		int count = 1;
		for(x = xstart + 1; x < BOARD_SIZE; x++) {
			if(!Match(m_board[x][y], start)) {
				return changed;
			}
			count++;
			if(count == 3) {
				changed = true;
				int nx;
				for(nx = xstart; nx <= x; nx++) {
					Clear(nx, y, into);
				}
			} else if(count > 3) {
				Clear(x, y, into);
			}
		}
		return changed;
	}

	bool CheckColumn(int x, int ystart, Board &into) {
		bool changed = false;
		int y;
		Gem start = m_board[x][ystart];
		int count = 1;
		for(y = ystart + 1; y < BOARD_SIZE; y++) {
			if(!Match(m_board[x][y], start)) {
				return changed;
			}
			count++;
			if(count == 3) {
				changed = true;
				int ny;
				for(ny = ystart; ny <= y; ny++) {
					Clear(x, ny, into);
				}
			} else if(count > 3) {
				Clear(x, y, into);
			}
		}
		return changed;
	}

	bool DropGems() {
		bool changed = false;
		int x, y;
		for(x = 0; x < BOARD_SIZE; x++) {
			for(y = BOARD_SIZE - 1; y >= 0; y--) {
				if(m_board[x][y] == empty) {
					int ny;
					for(ny = y; ny >= 0; ny--) {
						if(m_board[x][ny] != empty) {
							m_board[x][y] = m_board[x][ny];
							m_board[x][ny] = empty;
							changed = true;
							break;
						}
					}
				}
			}
		}
		return changed;
	}

    void Resolve(Board &into) {
		bool changed = false;
		int x, y;
		for(y = 0; y < BOARD_SIZE; y++) {
			for(x = 0; x < BOARD_SIZE; x++) {
				if(m_board[x][y] == empty)
					continue;

				changed = CheckRow(x,y,into) || changed;
				changed = CheckColumn(x,y,into) || changed;
			}
		}

		changed = into.DropGems() || changed;
		if(changed) {
			Board step(into);
			into.Resolve(step);
			memcpy(into.m_board, step.m_board, sizeof(m_board));
		}
	}

	void Load(FILE *f) {
		char line[200];
		int x, y;
		for(y = 0; y < BOARD_SIZE; y++) {
			fgets(line, sizeof(line), f);
			for(x = 0; x < BOARD_SIZE; x++) {
				if(!line[x]) {
					fprintf(stderr, "Error: Short line %d\n", y + 1);
					return;
				}
				switch(line[x]) {
					case 'r': m_board[x][y] = red; break;
					case 'y': m_board[x][y] = yellow; break;
					case 'g': m_board[x][y] = green; break;
					case 'b': m_board[x][y] = blue; break;
					case 's': m_board[x][y] = skull; break;
					case '5': m_board[x][y] = skullx5; break;
					case 'x': m_board[x][y] = xp; break;
					case 'm': m_board[x][y] = money; break;
					case '.': m_board[x][y] = empty; break;
					default:
						fprintf(stderr, "Error: Unknown character %c at line %d\n", line[x], y + 1);
						return;
				}
			}
		}
	}
	void Print() {
		int x, y;
		for(y = 0; y < BOARD_SIZE; y++) {
			for(x = 0; x < BOARD_SIZE; x++) {
				char c;
				switch(m_board[x][y]) {
					case red:     c = 'r'; break;
					case yellow:  c = 'y'; break;
					case green:   c = 'g'; break;
					case blue:    c = 'b'; break;
					case skull:   c = 's'; break;
					case skullx5: c = '5'; break;
					case xp:      c = 'x'; break;
					case money:   c = 'm'; break;
					case empty:   c = '.'; break;
					default:      c = '?'; break;
				}
				printf("%c", c);
			}
			printf("%d\n", y);
		}
		printf("01234567\n");
	}

	bool CheckMove(int xc, int yc) {
		if(m_board[xc][yc] == empty)
			return false;

		int x, y;
		int count = 0;
		for(x = xc; x < BOARD_SIZE; x++) {
			if(!Match(m_board[xc][yc], m_board[x][yc]))
				break;
			count++;
		}
		for(x = xc - 1; x >= 0; x--) {
			if(!Match(m_board[xc][yc], m_board[x][yc]))
				break;
			count++;
		}
		if(count >= 3)
			return true;

		count = 0;
		for(y = yc; y < BOARD_SIZE; y++) {
			if(!Match(m_board[xc][yc], m_board[xc][y]))
				break;
			count++;
		}
		for(y = yc - 1; y >= 0; y--) {
			if(!Match(m_board[xc][yc], m_board[xc][y]))
				break;
			count++;
		}
		if(count >= 3)
			return true;
		return false;
	}

	bool Swap(int x1, int y1, int x2, int y2) {
		if(x2 < 0 || x2 >= BOARD_SIZE)
			return false;
		if(y2 < 0 || y2 >= BOARD_SIZE)
			return false;

		Board check(*this);
		Gem temp = m_board[x1][y1];
		check.m_board[x1][y1] = check.m_board[x2][y2];
		check.m_board[x2][y2] = temp;
		if(check.CheckMove(x1, y1) || check.CheckMove(x2,y2)) {
			s_moveCount++;
			Board step(check);
			check.Resolve(step);
			if(step.Solve()) {
				printf("%d,%d => %d,%d\n", x1, y1, x2, y2);
				Print();
				return true;
			}
		}
		return false;
	}

	bool Solve() {
		int x, y;
		bool allEmpty = true;
		for(y = 0; y < BOARD_SIZE; y++) {
			for(x = 0; x < BOARD_SIZE; x++) {
				if(m_board[x][y] != empty) {
					allEmpty = false;
				}
				if(Swap(x, y, x+1, y)) { return true; }
				if(Swap(x, y, x, y+1)) { return true; }
				//if(Swap(x, y, x-1, y)) { return true; }
				//if(Swap(x, y, x, y-1)) { return true; }
			}
		}
		return allEmpty;
	}
};


int main(int argc, char **argv)
{
	Board init;
	init.Load(stdin);
	Board step(init);
	init.Resolve(step);

	if(step.Solve()) {
		printf("Solved\n");
	} else {
		printf("Not solved\n");
	}
	printf("%d moves considered\n", s_moveCount);
}