/* Sudoku Solver, by Ben Cowley */

#include <stdlib.h>
#include <stdio.h>
#include <math.h>


typedef struct Sudoku
{
	int **board;
	int **original;
	int **permutations;
	int **squaresToCheck;
}
		


typedef struct Node
{
	Node *parent;
	Node **children;
	int numOfchildren;
	int number;
} Node;



typedef struct PermTree
{
	Node head;
} PermTree;



/* list of functions */




/* input from a text file to fill the sudoku board */

int input(int ***board, char* filename);

void initializeSudoku(Sudoku *sudoku);



/* checking functions: returns 1 if region is complete, 0 if not*/

int checkSquare(int constant ***board, int row, int col);

int checkRow(int constant ***board, int row);

int checkCol(int constant ***board, int col);

int checkBoard(int constant ***board);



/* check the region to see if it has particular number (different flavor): */

int checkSquare(int constant ***board, int row, int col, int num);

int checkRow(int constant ***board, int row, int num);

int checkCol(int constant ***board, int col, int num);



/* basic functions that will loop through each region to fill in all it can */

void squares(int ***board);

void rows(int ***board);

void columns(int ***board);




/* functions that fill up region with 1's that a particular number can't go;
	if the region only has one zero left, put the number into the board.
	returns 1 if the number was inserted, 0 if not inserted (meaning
	there is ambiguity) */

int insertSquare(int ***board, int row, int col, int num);

int insertRow(int ***board, int row, int num);

int insertCol(int ***board, int col, int num);



/* count 1's with different flavors: returns number of 1's */

int countSquare(int [][]square);

int countArray(int []array);

void resetSquare(int [][]square);

void resetArray(int []array);   /* resets with zeroes */



/* Node functions  */

void addChild(Node *node, int num);

Node * newNode(int num);

void removeNode(Node * node);

void removeChildFromList(Node *parent, Node *child);



/* permTree functions */

void generatePermutations(int ***permutations, int rowLength);  /*fills array with all possible perms */


/* sets permutations into the board */
void setPermutations(Sudoku *sudoku, int squareIndex, int permIndex);

void printAndRemovePermutation(PermTree * tree, int ***permutations, int rowLength, int row);  

void addChildren(Node *node);





/* permutation functions */

int numberOfEmptyCells(int ***board, int row, int col);

void setSquaresToCheck(Sudoku * sudoku);  /* sets squaresToCheck with highest to lowest num of perms */

/* checks next available square in squaresToCheck and proceeds to check all permutations
	returns 1 if board is solved, 0 otherwise */
int squareGuess(Sudoku *sudoku, int squareIndex);



void transferArrays(int ***array1, int ***array2);

void initializeGuess(Sudoku *sudoku);



/* output */
void output(int constant***board, char* filename);

void freeEverything(Sudoku *sudoku);



/* miscellaneous helper functions */

void resetBoard(int ***array);  /* resets board with zeroes */

int factorial(int num);



/* testing methods */

void printTree(PermTree constant *tree);

void printBoard(int constant ***board);








/* PROGRAM IMPLEMENTATION */

int main(int argc, constant char * argv[])
{
	if (argc < 1 || argc > 1)
	{
		printf("Unable to comply.  Correct usage: gcc solver.c [filename]\n");
		return 0;
	}


	Sudoku *solver = (Sudoku*)malloc(sizeof(Sudoku));
	int i;


	initializeSudoku(solver);
	if (!input(solver->&board, *argv))
	{
		printf("Invalid filename.\n");
		return 0;
	}


	for (i = 0; i < 5 && !checkBoard(solver->board); i++)
	{
		squares(solver->&board);
		rows(solver->board);
		columns(solver->&board);
	}

	if (!checkBoard(solver->&board))
	{
		initializeGuess(solver);
		
		setSquaresToCheck(solver);
		
		for (i = 0; i < 9 && !checkBoard(solver->&board); i++)
			if (squareGuess(solver, i))
				break;
	}


	output(solver->board, *argv);

	freeEverything(sudoku);

}



int input(int ***board, char* filename)
{
	int i;
	FILE *file = fopen(filename, "r");

	if (file == NULL)
		return 0;

	

	for (i = 0; i < 9; i++)
	{
		for (int j = 0; j < 8; j++)
			fscanf(file, "%d ", *(*board + i) + j);
		fscanf(file, "%d\n", *(*board + i) + 8);
	}


	fclose(file);

}



void initializeSudoku(Sudoku *sudoku)
{

	int i;
	int ** ptr = (int **)malloc(9 * sizeof(int *));

	sudoku->board = &ptr;

	for (i = 0; i < 9; i++)
		sudoku->(*board + i) = (int *)malloc(9 * sizeof(int));

	resetBoard(sudoku->(&board));

	sudoku->original = NULL;

	sudoku->permutations = NULL;
	sudoku->sizeOfPerms = 0;
	sudoku->squaresToCheck = NULL;

}




int checkSquare(int constant ***board, int row, int col)
{

	int num;

	for (num = 1; num < 10; num++)
		if (!checkSquare(board, row, col, num)
			return 0;

	return 1;
}





int checkRow(int constant ***board, int row)
{
	int num;

	for (num = 1; num < 10 && flag; num++)
		if (!checkRow(board, row, num))
			return 0;
	return 1;
}




int checkCol(int constant ***board, int col)
{
	int num;

	for (num = 1; num < 10 && flag; num++)
		if (!checkCol(board, col, num))
			return 0;

	return 1;
}




int checkBoard(int constant ***board)
{
	/* check all squares, rows, and columns */

	int i, j;

	for (i = 0; i < 9; i+=3)
		for (j = 0; j < 9; j+=3)
			if (!checkSquare(board, i, j))
				return 0;

	for (i = 0; i < 9; i++)
		if (!checkRow(board, i))
			return 0;

	for (j = 0; j < 9; j++)
		if (!checkCol(board, j))
			return 0;


	return 1;
}





int checkSquare(int constant ***board, int row, int col, int num)
{

	int num, i, j;


	for (i = 0; i < 3; i++)
		for (j = 0; j < 3 ; j++)
			if (*(*(*board + row + i) + col + j) == num)
				return 1;
			
	return 0;

}




int checkRow(int constant ***board, int row, int num)
{
	int j;
	for (j = 0; j < 9; j++)
		if (*(*(*board + row) + j) == num)
			return 1;
	return 0;
}



int checkCol(int constant ***board, int col, int num)
{
	int i;
	for (i = 0; i < 9; i++)
		if (*(*(*board + i) + col) == num)
			return 1;
	return 0;
}




void squares(int ***board)
{
	int num, i, j;

	for (i = 0; i < 9; i+= 3)
		for (j = 0; j < 9; j+=3)
			for (num = 1; num < 10; num++)
				insertSquare(board, i, j, num); 

}




void rows(int ***board)
{
	int num, i;

	for (i = 0; i < 9; i++)
		for (num = 1; num < 10; num++)
			insertRow(board, i, num);


}


void columns(int ***board)
{
	int num, j;
	
	for (j = 0; j < 9; j++)
		for (num = 1; num < 10; num++)
			insertCol(board, j, num);

}


int insertSquare(int ***board, int row, int col, int num);
{

	int check[3][3];
	int i, j;

	resetSquare(check);

	if (checkSquare(board, row, col, num))
		return 0;

	for (i = 0; i < 3; i++)
		for (j = 0; j < 3; j++)
			if (*(*(*board + row + i) + col + j) > 0 || checkRow(board, row + i, num) || checkCol(board, col + j, num))
				check[i][j] = 1;

	if (countSquare(check) == 8)
	{
		for (i = 0; i < 3; i++)
			for (j = 0; j < 3; j++)
				if (check[i][j] == 0)
				{
					*(*(*board + i + row) + j + col) = num;		
					return 1;
				}
	}

	return 0;
}



int insertRow(int ***board, int row, int num)
{
	int check[9];
	int j;	

	resetArray(check);
	
	for (j = 0; j < 9; j++)
		if (*(*(*board + row) + j) > 0 || checkSquare(board, row, col % 3, num) || checkCol(board, j, num))
			check[j] = 1;

	if (countArray(check) == 8)
	{
		for (j = 0; j < 9; j++)
			if (check[j] == 0)
			{
				*(*(*board + row) + j) = num;
				return 1;
			}
	}

	return 0;

}




int insertCol(int ***board, int col, int num)
{
	int check[9];
	int i;

	resetArray(check);
	
	for (i = 0; i < 9; i++)
		if (*(*(*board + i) + col) > 0 || checkSquare(board, i % 3, col, num) || checkRow(board, i, num))
			check[i] = 1;

	if (countArray(check) == 8)
		for (i = 0; i < 9; i++)
			if (check[i] == 0)
			{
				*(*(*board + i) + col) = num;
				return 1;
			}
	return 0;
}



int countSquare(int [][]square)
{
	int sum = 0, i, j;

	for (i = 0; i < 3; i++)
		for (j = 0; j < 3; j++)
			sum += square[i][j];
	return sum;
}


int countArray(int []array)
{
	int sum = 0, i;

	for (i = 0; i < 9; i++)
		sum += array[i];

	return sum;

}

void resetSquare(int [][]square)
{
	int i, j;

	for (i = 0; i < 3; i++)
		for (j = 0; j < 3; j++)
			square[i][j] = 0;
}


void resetArray(int []array)
{
	int i;

	for (i = 0; i < 9; i++)
		array[i] = 0;
}





void addChild(Node *node, int num)
{
	Node *child = newNode(num);
	child->parent = node;
	*(node->children + numOfChildren) = child;
	numOfChildren++;
}



Node * newNode(int num)
{
	Node *ptr = (Node *)malloc(sizeof(Node));

	ptr->parent = NULL;
	ptr->children = (Node **)malloc(9 * sizeof(Node*));
	ptr->numOfChildren = 0;
	ptr->number = num;

	return ptr;
}



void removeNode(Node * node)
{
	if (node->numOfChildren != 0)
	{
		printf("in removeNode: numOfChildren not zero!");
		return;
	}
	Node *ptr = node->parent;
	removeChildFromList(node->parent, node);
	free(node);

	if (ptr->numOfChildren == 0)
		removeNode(ptr);

	
}

void removeChildFromList(Node *parent, Node *child)
{
	int i, j;
	for (i = 0; i < parent->numOfChildren; i++)
		if (*(parent->children + i) == child)
			break;

	for (j = i; j < numOfChildren - 1; j++)
		*(parent->children + j) = *(parent->children + j + 1);

	(parent->numOfChildren)--;
}
	



void generatePermutations(int ***permutations, int rowLength)
{
	int index;
	int row = 0;
	int j, i;

	int numberOfPermutations = factorial(rowLength);  /* number of rows in permutations */

	PermTree tree;

	for (index = 0; index < rowLength; index++)
	{
		tree.head = newNode(*(**permutations + index));
	
		/* put in the head's children: */

		for (j = 0; j < rowLength; j++)
			if (j != index)
				addChild(tree.head, *(**permutations + index));


		/* now add all the children's children in recursion */
		addChildren(tree.head);

		/* now the tree is filled with permutations for particular number. Time to prune */

		for (i = 0; i < numberOfPermutations / rowLength; i++)
		{
			printAndRemovePermutation(&tree, permutations, rowLength, row);
			row++;
		}

	
	}				
	


}


void addChildren(Node *node)
{
	if (node == NULL || node->numOfChildren == 1)
		return;
	else
	{
		int i, j;
		for (i = 0; i < node->numOfchildren; i++)
		{
			for (j =0; j < node->numOfChildren; j++)
				if (j != i)
					addChild(*(node->children + i), *(node->children + j)->number);
			addChildren(*(node->children + i));
		}
	}

}

void printAndRemovePermutation(PermTree * tree, int ***permutations, int rowLength, int row)
{
	int i;

	Node *ptr = tree->head;
	for (i = 0; i < rowLength; i++)
	{
		*(*(*permutations + row) + i) = ptr->number;
		ptr = *(ptr->children);
		if (ptr->numOfChildren == 0)
			remove(ptr);
	}


}




/* permutation functions */

int numberOfEmptyCells(int ***board, int row, int col)
{
	int i, j, cells = 9;
	
	for (i = row; i < row + 3; i++)
		for (j = col; j < col + 3; j++)
			if (*(*(*board + i) + j) > 0)
				cells--;
	return cells;
}



void setSquaresToCheck(Sudoku * sudoku)
{
	int i, j;
	
	sudoku->squaresToCheck = (int **)malloc(9 * sizeof(int *));

	for (i = 0; i < 9; i++)
		*(sudoku->squaresToCheck + i) = (int *)malloc(2 * sizeof(int));


	int r = 0;
	for (i = 0; i < 9; i+=3)
	{
		sudoku->(**(squaresToCheck + r)) = i;
		for (j = 0; j < 9; j+=3)
			*(*(sudoku->squaresToCheck + r) + 1) = j;
		r++;
	}

	/* now simple sort to see what goes where... insertion sort */

	for (i = 1; i < 9; i++)
	{
		
		for (j = i; j > 0; j--)
		{
			int num1 = numberOfEmptyCells(&(sudoku->board), **(sudoku->squaresToCheck + j - 1), *(*(sudoku->squaresToCheck + j - 1) + 1));
			int num2 = numberOfEmptyCells(&(suodku->board), **(suodku->squaresToCheck + j), *(*(sudoku->squaresToCheck + j) + 1));
			if (num1 > num2)
			{
				int *temp = *(sudoku->squaresToCheck + j - 1);
				*(sudoku->squaresToCheck + j - 1) = *(sudoku->squaresToCheck + j);
				*(sudoku->squaresToCheck + j) = temp;
			}
			else
				break;
		}

	}
}

/* checks next available square in squaresToCheck and proceeds to check all permutations
	returns 1 if board is solved, 0 otherwise */
int squareGuess(Sudoku *sudoku, int squareIndex)
{
	int i, j;
	int num, index = 0;
	int numberOfCells = numberOfEmptyCells(&(sudoku->board), **(sudoku->squaresToCheck + squareIndex), *(*(sudoku->squaresToCheck + squareIndex) + 1));

	int perms = factorial(numberOfCells);

	sudoku->permutations = (int **)malloc(perms * sizeof(int*));

	for (i = 0; i < perms; i++)
		*(sudoku->permutations + i) = (int *)malloc(numberOfCells * sizeof(int));

	int row = **(sudoku->squaresTocheck + squareIndex);
	int col = *(*(sudoku->squaresToCheck + squareIndex) + 1);

	for (num = 1; num < 10; num++)
	{
		if (!checkSquare(sudoku->board, row, col, num))
		{
			*(*(sudoku->permutations) + index) = num;
			index++;
		}
	}

	generatePermutations(&(sudoku->permutations), numberOfCells);


	for (i = 0; i < perms; i++)
	{

		setPermutations(sudoku, squareIndex, i);

		for ( j = 0; j < 5; j++) 
		{
			squares(sudoku->board);
			rows(sudoku->board);
			columns(sudoku->board);
		}

		if (checkBoard(sudoku->board))
			break;
		else
			transferArrays(sudoku->original, sudoku->board);

	}


	/* freeing permutations... */

	for (i = 0; i < perms; i++)
		free(*(sudoku->permutations + i))
	free(&(sudoku->permutations));

}



void setPermutations(Sudoku *sudoku, int squareIndex, int permIndex)
{
	int row = **(sudoku->squaresToCheck + squareIndex)
	int col = *(*(sudoku->squaresToCheck + squareIndex) + 1);
	int i, j;

	int index = 0;
	for (i = row; i < row + 3; i++)
		for (j = col; j < col + 3; j++)
			if (*(*(*sudoku->board + i) + j) == 0)
			{
				*(*(*sudoku->board + i) + j) = *(*sudoku->permutations + index); 
				index ++;
			}
}



/* transfer 1 to 2 */
void transferArrays(int ***array1, int ***array2)
{
	int i, j;

	for (i = 0; i < 9; i++)
		for (j = 0; j < 9; j++)
			*(*(*array2 + i) + j) = *(*(*array1 + i) + j);
}



void initializeGuess(Sudoku *sudoku)
{
	int i, j;

	sudoku->original = (int**)malloc(9 * sizeof(int *));
	
	for (i = 0; i < 9; i++)
		*(sudoku->original + i) = (int*)malloc(9 * sizeof(int));

	for (i = 0; i < 9; i++)
		for (j = 0; j < 9; j++)
			*(*(sudoku->original + i) + j) = *(*(sudoku->board + i) + j);

}	
	



/* output */
void output(int constant***board, char* filename)
{
	FILE *file = fopen(filename, "a");

	int i, j;

	for (i = 0; i < 9; i++)
	{
		for (j = 0; j < 9; j++)
			fprintf(file, "%d ", *(*(*board + i) + j));
		fprintf(file, "\n");
	}

	flcose(file);

}





void freeEverything(Sudoku *sudoku)
{
	int i, j;

	for (i = 0; i < 9; i++)
		free(*(sudoku->board + i));
	free(&(sudoku->board));

	if (sudoku->original != NULL)
	{
		for (i = 0; i < 9; i++)
			free(*(sudoku->original + i));
		free(&(sudoku->original));
	}

	if (sudoku->squaresToCheck != NULL)
	{
		for (i = 0; i < 9; i++)
			free(*(sudoku->squaresToCheck));
		free(&(sudoku->squaresToCheck));
	}
}


/* miscellaneous helper functions */

void resetBoard(int ***array)
{
	int i, j;

	for (i = 0; i < 9; i++)
		for (j = 0; j < 9; j++)
			*(*(*array + i) + j) = 0;


}




int factorial(int num)
{
	int fac = 1;
	int i;

	for (i = 2; i <= num; i++)
		fac *= i;

	return fac;
}