#include <iostream>
#include <string>

#include "sudoku.h"
#include "debug.h"

#define EMPTY ' '

int guesses = 0;
int verbose = 1;

sudoku::sudoku()
{
	int x,y;

	for (y = 0; y < 9; y++)
		for (x = 0; x < 9; x++)
			table[x][y] = EMPTY;

	recursion_depth = 0;
}

sudoku::~sudoku()
{
}

static int check_validity(const int col, const int row)
{
	if (col < 0 || col >= 9) {
		DPRINT << "Invalid column: " << col << std::endl;
		return 0;
	}

	if (row < 0 || row >= 9) {
		DPRINT << "Invalid row: " << row << std::endl;
		return 0;
	}
	return 1;
}

char sudoku::get(const int col, const int row)
{
	if (!check_validity(row, col)) {
		DPRINT << "over here\n";
		return 0;
	}

	return table[col][row];
}

int sudoku::set(const int col, const int row, const char val)
{
	std::string str;

	if (!check_validity(col, row)) {
		DPRINT << "over here\n";
		return -1;
	}

	if (table[col][row] != EMPTY) {
		DPRINT << "Assigning value to a non-empty slot\n";
		return -1;
	}

	str = get_col_contents(col);
	if (str.find(val, 0) != std::string::npos) {
		DPRINT << "Illegal assignment " << col << "." << row << ": "
		       << val << std::endl;
		return -1;
	}

	str = get_row_contents(row);
	if (str.find(val, 0) != std::string::npos) {
		DPRINT << "Illegal assignment " << col << "." << row << ": "
		       << val << std::endl;
		return -1;
	}

	str = get_block_contents(col, row);
	if (str.find(val, 0) != std::string::npos) {
		DPRINT << "Illegal assignment " << col << "." << row << ": "
		       << val << std::endl;
		return -1;
	}


	table[col][row] = val;

	return 0;
}

int sudoku::str_to_row(const int row, const std::string &str)
{
	unsigned int i, col = 0;
	char chr;

	if (row < 0 || row >= 9) {
		DPRINT << "Illegal row " << row << std::endl;
		return -1;
	}

	for (i = 0; i < str.length(); i++) {
		chr = str.at(i);

		if ((chr == '?') ||
		    (chr == '_') ||
		    (chr == '.')){
			col++;
			continue;
		}

		/* Ignore non-numbers */
		if (chr < '1' || chr > '9')
			continue;

		set(col++, row, chr);
		if (col >= 9)
			break;
	}
	return 0;
}

void sudoku::print(void)
{
	int x,y;

	printf("+-------+------+--------+\n");
	for (y = 0; y < 9; y++) {
		printf("| ");
		for (x = 0; x < 9; x++) {
			printf("%c ", table[x][y]);
			if (!((x  + 1)% 3))
				printf("| ");
		}
		printf("\n");
		if (!((y + 1) % 3))
			printf("+-------+-------+-------+\n");
	}
}

void sudoku::clone_to(sudoku &to)
{
	sudoku clone;
	int x, y;

	for (x = 0; x < 9; x++)
		for (y = 0; y < 9; y++)
			to.table[x][y] = table[x][y];
}

std::string sudoku::get_row_contents(int row)
{
	std::string s;
	int col;

	for (col = 0; col < 9; col++) {
		if (table[col][row] != EMPTY)
			s += table[col][row];
	}

	return s;
}

std::string sudoku::get_col_contents(int col)
{
	std::string s;
	int row;

	for (row = 0; row < 9; row++) {
		if (table[col][row] != EMPTY)
			s += table[col][row];
	}

	return s;
}

std::string sudoku::get_block_contents(int col, int row)
{
	std::string s;
	int x, y;
	char c;

	if (col < 0 || col >= 9)
		DPRINT "Aiee " << col << std::endl;
	if (row < 0 || row >= 9)
		DPRINT "Aiee " << row << std::endl;

	col = (col /= 3) * 3;
	row = (row /= 3) * 3;

	for (y = 0; y < 3; y++)
		for (x = 0; x < 3; x++) {
			c = get(x + col, y + row);
			if (c != EMPTY)
				s += c;
		}

	return s;
}



static std::string exclude_common(std::string s1, std::string s2)
{
	std::string::iterator a, b;

restart:
	for (a = s1.begin(); a != s1.end(); a++) {
		for (b = s2.begin(); b != s2.end(); b++) {
			if (*a == *b) {
				a = s1.erase(a);
				b = s2.erase(b);
				goto restart;
			}
		}
	}
	return s1;
}

std::string sudoku::get_legal_numbers(int col, int row)
{
	char val;
	std::string a, b, c, ret;

	if (!check_validity(col, row)) {
		DPRINT << "over here\n";
		return NULL;
	}

	val = get(col, row);
	if (val != EMPTY) {
		return "0";
	}

//	std::cout << "[" << col << "." << row << "] ";

	a = get_col_contents(col);
//	std::cout << " col " << a;

	b = get_row_contents(row);
//	std::cout << " row " << b;

	c = get_block_contents(col, row);
//	std::cout << " block " << c;

	ret = exclude_common("123456789", a);
	ret = exclude_common(ret, b);
	ret = exclude_common(ret, c);

//	std::cout << " legal " << ret << std::endl;
	return ret;
}

int sudoku::fill_missing()
{
	int x, y, solved = 0;
	std::string num;

	for (y = 0; y < 9; y++)
		for (x = 0; x < 9; x++) {
				num = get_legal_numbers(x, y);
				if ((num != "0") && (num.length() == 1)) {
					set(x, y, num[0]);
					solved++;
			}
		}
	if (verbose) {
		std::cout << "Solved " << solved << " numbers\n";
	}

	return solved;
}

int sudoku::get_best_guess(int &col, int &row)
{
	int x, y;
	int min = 0, filled = 0, illegals = 0;
	std::string numbers;

	/*
	 * Initialize row and col with illegal values to spot possible
	 * misuse
	 */
	col = -1;
	row = -1;

	for (y = 0; (y < 9) && !illegals; y++)
		for (x = 0; x < 9; x++) {
			numbers = get_legal_numbers(x, y);

			if (numbers == "0") {
				filled++;
				continue;
			}

			if (numbers.length() == 0) {
				illegals++;
				break;
			}

			if (!min) {
				min = numbers.length();
				col = x;
				row = y;
				continue;
			}

			if ((int)numbers.length() < min) {
				min = numbers.length();
				col = x;
				row = y;
				if (min == 1)
					return min;
			}
//			std::cout <<  x << "." << y << ": " << " min " 
//				  << numbers << col << "." << row << std::endl;
		}

	if ((!min && !filled) || illegals) {
//		DPRINT << "Is this sudoku has no solutions?\n";
		return -1;
	}

	if (!min && (filled == 99)) {
		DPRINT << "This sudoku is solved\n";
		return 0;
	}

	return min;
}

sudoku sudoku::solve(int &solvable)
{
	int x, y, i, ret;
	std::string str;
	sudoku empty;

	// Fill in as much as possible
	do {
		if (verbose) {
			std::cout << std::endl;
			print();
		}
	} while (fill_missing() != 0);

	ret = get_best_guess(x, y);

	// Did we solve it yet?
	switch (ret) {
	case -1:
		// Unsolvable
		solvable = 0;
		if (verbose) {
			std::cout << "This is unsolvable, recursion: " 
				  << recursion_depth << std::endl;
		}
		return empty;
	case 0:
		// Solved
		solvable = 1;
		if (verbose) {
			std::cout << "Solution found , recursion: " 
				  << recursion_depth << std::endl;
		}
		return *this;
	}

	if (verbose) {
		std::cout << "Not solved yet, guessing at depth "
			  << recursion_depth << std::endl;
	}

	// Try guessim something
	str = get_legal_numbers(x, y);
	for (i = 0; i < (int)str.length(); i++) {

		sudoku guess = *this;
		guess.set(x, y, str[i]);

		if (verbose) {
			std::cout << "Guessing number " << str[i] << " to "
				  << x << "." << y << std::endl;
		}
		
		guess.recursion_depth = recursion_depth + 1;

		int can_solve;
		guess = guess.solve(can_solve);
		
		//Did it solve?
		if (can_solve)
			return guess;
	}

	// It didn't solve
	solvable = 0;
	return empty;
}

std::vector<sudoku> sudoku::solve_all()
{
	int x, y, i, j, ret;
	std::string str;
	std::vector<sudoku> sudokus;

	// Fill in as much as possible
	do {
		if (verbose) {
			std::cout << std::endl;
			print();
		}
	} while (fill_missing() != 0);

	ret = get_best_guess(x, y);

	// Did we solve it yet?
	switch (ret) {
	case -1:
		// Unsolvable
		if (verbose) {
			std::cout << "This is unsolvable, recursion: " 
				  << recursion_depth << std::endl;
		}
		return sudokus;
	case 0:
		// Solved
		if (verbose) {
			std::cout << "Solution found , recursion: " 
				  << recursion_depth << std::endl;
		}
		sudokus.push_back(*this);
		print();
		return sudokus;
	}

	if (verbose) {
		std::cout << "Not solved yet, guessing at depth "
			  << recursion_depth << std::endl;
	}

	// Try guessim something
	str = get_legal_numbers(x, y);
	for (i = 0; i < (int)str.length(); i++) {
		std::vector<sudoku> results;

		sudoku guess = *this;
		guesses++;

		if (verbose) {
			std::cout << "Guessing number " << str[i] << " to "
				  << x << "." << y << std::endl;
		}

		guess.set(x, y, str[i]);
		guess.recursion_depth = recursion_depth + 1;

		results = guess.solve_all();
		
		//Did it solve?
		if (!results.empty()) {
/*			printf("Got %d solutions, guessed %d: %s\n",
			       (int)results.size(), (int)str.size(),
			       str.c_str());*/

			for(j = 0;j < (int)results.size(); j++) 
				sudokus.push_back(results.at(j));
		}
	}

	// Return what was solved
	return sudokus;
}