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

#include "debug.h"
#include "update.h"
#include "cell.h"
#include "display.h"

/*
 * For all unsolved cells on the board, solve them if they have been marked as
 * impossible to be 8/9 values
 */
int solve_row_col(struct cell (*b)[9][9])
{
	int change_count = 0;
	int x = 0;
	int y = 0;
	int i = 0;
	int val = 0;
	int total = 0;

	for (y = 0; y < 9; y++)
	{
		total = 0;
		for (x = 0; x < 9; x++)
		{
			if ((*b)[x][y].val != 0)
				continue;

			for (i = 0; i < 9; i++)
			{
				if ((*b)[x][y].not[i])
				{
					total++;
				} else {
					val = i + 1;
				}
			}
			if (total == 8) {
				printf("%c%c must be %d because it is the only missing value in its row or column\n", NAME_CELL(x,y), val);
				DEBUG_LOG("ROW/COL: (%d,%d) must be %d\n", x, y, val);
				(*b)[x][y].val = val;
				change_count++;
			}
		}
	}
	return change_count;
}


/*
 * FIXME rename - cell != cell
 * For all unsolved cells on the board, solve them if they are the only place
 * left in their local 3x3 (box) that a value missing from that box could fit
 */
int not_to_val_cell(struct cell (*b)[9][9])
{
	int change_count = 0;
	int bx = 0;
	int by = 0;
	int x = 0;
	int y = 0;
	int n = 0;
	int potentials = 0;
	int okx, oky;
	struct cell *c;

	/* refactor this crap */
	for (by = 0; by < 9; by += 3)
	{
		for (bx = 0; bx < 9; bx += 3)
		{
			/* for each val that has to be in cell */
			for (n = 1; n <= 9; n++)
			{
				for (y = 0; y < 3; y++)
				{
					for (x = 0; x < 3; x++)
					{
						c = &(*b)[bx+x][by+y];
						if (c->val == n)
						{
							potentials = 0;
							y = 3;
							break;
						}
						if (c->val)
							continue;

						if (c->not[n-1] == 0)
						{
							potentials++;
							okx = x;
							oky = y;
						}
					}
				}
				if (potentials == 1)
				{
					DEBUG_LOG("CELL: (%d,%d) must be %d\n", bx + okx, by + oky, n);
					printf("%c%c must be %d because it can't be anything else\n",
						NAME_CELL(bx+okx, by+oky), n);
					(*b)[bx+okx][by+oky].val = n;
					potentials = 0;
					change_count++;
				} else if(potentials) {
					DEBUG_LOG("CELL: (%d,%d) could be one of %d\n", bx + okx, by + oky, potentials);
					int k = 0;
					for (k = 0; k < 9; k++) {
						if (!(*b)[bx+okx][by+oky].not[k]) {
							DEBUG_LOG("   %d", k+1);
						}
					}
					DEBUG_LOG("\n\n");
				}
			}
		}
	}
	return change_count;
}


/* For the numbers 1-9 not filled into a cell, fill in those which have only
 * one place they can go */
int cell_fill_certainties(struct cell (*b)[9][9], int bx, int by)
{
	int change_count = 0;
	int will_take_count = 0;
	int will_take_x = 0;
	int will_take_y = 0;
//	struct cell *will_take = NULL;
	int val = 0;
	int cell_has[9] = {0};
	int x,y;

	/* Translate cell-based index to tile-based */
	bx *= 3;
	by *= 3;

	/* First: walk the cell and find which values it has */
	for (x = bx; x < bx + 3; x++) {
		for (y = by; y < by + 3; y++) {
			val = (*b)[x][y].val;
			if (val) {
				DEBUG_LOG("CELL_CERT: Cell (%d,%d) has %d\n", bx/3, by/3, val);
				cell_has[val - 1] = 1;
			}
		}
	}

	/* Second: For all missing values, see if only one tile will take it.
	 * If only one will have it, put it in */
	for (val = 0; val < 9; val++) {

		will_take_count = 0;

		/* Does the cell lack the value? */
		if (!cell_has[val]) {

			DEBUG_LOG("Try to solve for %d\n", val + 1);

			/* Walk the cell and find which tile(s) will take it */
			for (x = bx; x < bx + 3; x++) {
				for (y = by; y < by + 3; y++) {
					if ((*b)[x][y].val) {
						continue;
					}
					if ((*b)[x][y].not[val] == 0) {
						will_take_count++;
						will_take_x = x;
						will_take_y = y;
					}
				}
			}
			DEBUG_LOG("will_take_count is %d\n", will_take_count);
			/* Don't make indeterminate choices here*/
			if (will_take_count == 1) {
				printf("%c%c must be %d because it is the only place in its boxthis will fit\n",
					NAME_CELL(will_take_x, will_take_y),
					val + 1);
				(*b)[will_take_x][will_take_y].val = val + 1;
				change_count++;
			}
		}
	}
	return change_count;
}

int cells_fill_certainties(struct cell (*b)[9][9])
{
	int change_count = 0;
	int x, y;

	for (x = 0; x < 3; x++) {
		for (y = 0; y < 3; y++) {
			change_count += cell_fill_certainties(b, x, y);
		}
	}
	return change_count;
}

/*
 * Check if every cell on a board is filled.
 * Returns -1 isf the board is not fully
 * Returns 0 if the board is filled
 */
int board_is_filled(struct cell (*b)[9][9])
{
	int x = 0;
	int y = 0;

	for (x = 0; x < 9; x++) {
		for (y = 0; y < 9; y++) {
			if ((*b)[x][y].val == 0) {
				return -1;
			}
		}
	}
	return 0;
}

/*
 * Check if all of the rows on are correctly solved on a board
 * Returns 0 for all rows correctly solved
 */
int board_rows_are_solved(struct cell (*b)[9][9])
{
	int row_has[9] = {0};
	int val = 0;
	int x = 0;
	int y = 0;

	for (y = 0; y < 9; y++) {
		memset(row_has, 0, sizeof(row_has));
		for (x = 0; x < 9; x++) {
			val = (*b)[x][y].val;
			if (val == 0) {
				return -1;
			}
			if (row_has[val - 1]) {
				DEBUG_LOG("Invalid board: Row %d duplicate %d\n", y, val);
				return -1;
			}
			row_has[val - 1] = 1;
		}
	}

	return 0;
}

/*
 * Check if all of the columns on are correctly solved on a board
 * Returns 0 for all columns correctly solved
 */
int board_cols_are_solved(struct cell (*b)[9][9])
{
	int col_has[9] = {0};
	int val = 0;
	int x = 0;
	int y = 0;

	for (x = 0; x < 9; x++) {
		memset(col_has, 0, sizeof(col_has));
		for (y = 0; y < 9; y++) {
			val = (*b)[x][y].val;
			if (val == 0) {
				return -1;
			}
			if (col_has[val - 1]) {
				DEBUG_LOG("Invalid board: Column %d duplicate %d\n", x, val);
				return -1;
			}
			col_has[val - 1] = 1;
		}
	}

	return 0;
}

/*
 * Check if one of the nine 3x3 boxes is correctly solved on a board
 * Returns 0 for a correctly solved 3x3
 */
int board_box_is_solved(struct cell (*b)[9][9], int bx, int by)
{
	int col_has[9] = {0};
	int val = 0;
	int x = 0;
	int y = 0;

	bx *= 3;
	by *= 3;

	for (x = bx; x < bx + 3; x++) {
		for (y = by; y < by + 3; y++) {
			val = (*b)[x][y].val;
			if (val == 0) {
				return -1;
			}
			if (col_has[val - 1]) {
				DEBUG_LOG("Invalid board: box %d,%d duplicate %d\n", bx/3, by/3 val);
				return -1;
			}
			col_has[val - 1] = 1;
		}
	}

	return 0;
}

/*
 * Check if all of the nine 3x3 boxes are correctly solved on a board
 * Returns 0 for correctly solved boxes
 */
int board_boxes_are_solved(struct cell (*b)[9][9])
{
	int ret = 0;
	int x = 0;
	int y = 0;
	for (x = 0; x < 3; x++) {
		for (y = 0; y < 3; y++) {
			ret = board_box_is_solved(b, x, y);
			if (ret)
				return ret;
		}
	}
	return ret;
}

/*
 * Check if a board is solved.
 * Returns 0 if the board is solved correctly
 */
int board_is_solved(struct cell (*b)[9][9])
{
	int ret = 0;
	ret = board_is_filled(b);
	if (ret)
		return ret;

	ret = board_rows_are_solved(b);
	if (ret)
		return ret;

	ret = board_cols_are_solved(b);
	if (ret)
		return ret;

	ret = board_boxes_are_solved(b);

	return ret;
}

int main(int argc, char **argv)
{
	struct cell board[9][9];

	memset(board, 0, sizeof(board));

	board[1][0].val = 6;
	board[2][0].val = 1;
	board[3][0].val = 5;
	board[8][0].val = 9;

	board[1][1].val = 7;
	board[2][1].val = 5;
	board[3][1].val = 4;
	board[4][1].val = 9;
	board[5][1].val = 3;
	board[6][1].val = 6;

	board[0][2].val = 9;
	board[3][2].val = 6;
	board[7][2].val = 7;

	board[0][3].val = 4;
	board[3][3].val = 2;
	board[5][3].val = 6;

	board[0][4].val = 3;
	board[2][4].val = 9;
	board[6][4].val = 2;
	board[8][4].val = 7;

	board[3][5].val = 9;
	board[5][5].val = 5;
	board[8][5].val = 3;

	board[1][6].val = 8;
	board[5][6].val = 9;
	board[8][6].val = 5;


	board[2][7].val = 4;
	board[3][7].val = 7;
	board[4][7].val = 5;
	board[5][7].val = 2;
	board[6][7].val = 8;
	board[7][7].val = 9;


	board[0][8].val = 5;
	board[5][8].val = 1;
	board[6][8].val = 7;
	board[7][8].val = 3;

//	board[7][0].val = 3;
//	board[4][1].val = 3;
//	board[0][7].val = 3;
//	board[1][4].val = 3;
//
//	/* dummy board taken from the guardian lol */
//	/* FIXME: have  a way to input boards, silly */
//	board[0][0].val = 7;
//	board[0][4].val = 5;
//
//	board[1][2].val = 5;
//	board[1][4].val = 9;
//
//	board[2][1].val = 6;
//	board[2][2].val = 4;
//	board[2][5].val = 2;
//
//	board[3][0].val = 1;
//	board[3][5].val = 9;
//	board[3][6].val = 7;
//
//	board[4][0].val = 9;
//	board[4][2].val = 6;
//	board[4][3].val = 4;
//	board[4][7].val = 8;
//	board[4][8].val = 5;
//
//	board[5][4].val = 2;
//
//	board[6][4].val = 8;
//	board[6][6].val = 5;
//	board[6][7].val = 6;
//
//	board[7][1].val = 8;
//	board[7][6].val = 3;
//
//	board[8][0].val = 4;
//	board[8][4].val = 1;
//	board[8][5].val = 7;
//	board[8][8].val = 8;



	display(board);

	int i = 0;
	int total_changes = 0;
	int change_count = -1;
	/* 9*9 is worst case */
	for (i = 0; i < 9*9 && change_count; i++) {
		change_count = 0;
		update_not_row_col(&board);
		change_count += not_to_val_cell(&board);
		change_count += solve_row_col(&board);
		change_count += cells_fill_certainties(&board);
		total_changes += change_count;
//		display(board);
	}

	if (board_is_solved(&board) < 0) {
		printf("Could not solve the board! Here is the closest (%d changes)\n", total_changes);
	} else {
		printf("Solution (%d changes)\n", total_changes);
	}
	display(board);

}