#include <iostream>
#include <string>

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

#define EMPTY ' '

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;
	guesses = 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::print_compact(void)
{
	int x, y, i = 0;
	char str[82];
	str[81] = 0;

	for (y = 0; y < 9; y++)
		for (x = 0; x < 9; x++, i++)
			str[i] = table[x][y] != EMPTY ? table[x][y] : '.';

	printf("%s\n", str);
}

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;
}

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);
		if (verbose)
			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;
		guess.guesses = 0;

		results = guess.solve_all();
		guesses += guess.guesses;
		
		//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));
				guesses += results.at(j).guesses;
			}
		}
	}

	if (verbose)
		std::cout << "Guesses: " << guesses << std::endl;

	// Return what was solved
	return sudokus;
}

sudoku sudoku::fill_with_random(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 fill 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 filling with something
	str = get_legal_numbers(x, y);
	while (str.length()) {
		i = get_random() % str.length();

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

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

		guess.recursion_depth = recursion_depth + 1;

		int can_solve;
		guess = guess.fill_with_random(can_solve);

		//Did it solve?
		if (can_solve) {
			solvable = 1;
			return guess;
		}

		str.erase(i,1);
	}

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

int sudoku::used_numbers()
{
	int x, y, count = 0;
	for (x = 0; x < 9; x++)
		for (y = 0; y < 9; y++)
			if (table[x][y] != EMPTY)
				count++;
	return count;
}

static int done = 0;

sudoku sudoku::remove_randomly(int min_guesses, int depth)
{
	int count = used_numbers();
	sudoku result;
	int stop = 0;
	sudoku work = *this;

#pragma omp parallel for firstprivate(stop, work)
	for (int i = 0; i < count; i++) {
		int x, y;
		sudoku tmp,tmp2;
		std::vector<sudoku> results;

		if (done || stop)
			continue;

		/* remove a number */
		do {
			x = get_random() % 9;
			y = get_random() % 9;
		} while(work.get(x,y) == EMPTY);
		work.table[x][y] = EMPTY;

		//printf("Got now:\n");
		//work.print();

		tmp2 = work;
		/* solve it */
		results = work.solve_all();

		/* Does it still have only one solution */
		if (results.size() == 1 && !done) {
			/* but not hard enough yet? */
			if (work.guesses >= min_guesses) {
				/* It's good now */
				printf("%d, Good!\n", depth);
				result = work;
				done = 1;
				#pragma omp flush(done)
			} else {
				printf("%2d, got only %3d guesses ", depth,
				       work.guesses);
				tmp2.print_compact();
			}

			if (!done) {
				work = tmp2;
				tmp = work.remove_randomly(min_guesses,
						   depth + 1);

				/* test for emptiness */
				if (tmp.guesses == 0) {
					continue;
				}

				if (tmp.guesses >= min_guesses) {
					result = tmp;
					done = 1;
					#pragma omp flush(done)
				} else {
					printf("%d: Guesses: %d, "
					       "not good enough\n",
					       depth, tmp2.guesses);
				}
				continue;
			}
		}

		if ((results.size() > 1) && !done) {
			/* oops, removed too many */
			sudoku empty;
			//printf("%d, Got multiple results\n", depth);
			result = empty;
			stop = 1;
		}

		if (results.empty() && !done) {
			fprintf(stderr, "%d, Fail. This can't happen?\n",
				depth);
			sudoku empty;
			result = empty;
		}
	}
	return result;
}

int sudoku::generate(int min_guesses)
{
	int solvable;
	sudoku tmp = fill_with_random(solvable);

	if (!solvable)
		return -1;

	/* Right, we got it filled */
	tmp = tmp.remove_randomly(min_guesses, 0);

	*this = tmp;

	return solvable;
}