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

typedef struct _Array
{
    short *arr;
    unsigned short size;
} Array;

#define EMPTY_SQUARE -1
#define NOT_FINISH -2
#define FINISH_SUCCESS 0
#define FINISH_FAILURE -3
#define BOARD_SIZE 9
#define FILLED 1
#define FAIL 0


typedef int bool;
#define true 1
#define false 0

short* bucketsort(short sudokuBoard[][9], int row, int col, int size, unsigned short*arrSize);
Array ***PossibleDigits(short sudokuBoard[][9]);
int FillBoard(short board[][9], Array ***possibilities);
int OneStage(short board[][9], Array ***possibilities, int *x, int *y);
void UpdatePossibilities(short board[][9], Array***possibilities, int row, int col, int squareValue);
void UpdateSquarePossibilities(Array***possibilities, int row, int col, unsigned short arrSize, int squareValue);
bool SearchForDuplications(short board[][9], int row, int col, int SquareValue);
void printPossibilities(Array***possibilities, int x, int y);
void sudokoPrintBoard(short board[][9]);
void main()
{
    short board[9][9] =
    { 5, -1, 4, -1, 7, -1, -1, 1, -1,
    6, -1, 2, 1, -1, -1, 3, -1, -1,
    1, -1, 8, -1, 4, -1, -1, 6, -1,
    -1, 5, -1, -1, 6, -1, -1, 2, -1,
    -1, 2, -1, 8, -1, 3, -1, -1, -1,
    -1, -1, -1, -1, -1, 4, -1, 5, 6,
    -1, 6, 1, 5, 3, 7, 2, 8, 4,
    -1, 8, 7, -1, 1, 9, -1, 3, -1,
    -1, -1, -1, 2, 8, -1, -1, -1, 9 };
    Array*** possible_solutions;

    printf("Initial board\n");
    sudokoPrintBoard(board);

    printf("Press enter to start playing...\n");
    getchar();

    possible_solutions = PossibleDigits(board);

    if (FillBoard(board, possible_solutions) == -1)
        printf("User's selections led to duplications\n");
    else
    {
        sudokoPrintBoard(board);
        printf("Board filled successfully\n");
    }
}

void sudokoPrintBoard(short board[][9])
{
    int i, j;

    for (i = 0; i < BOARD_SIZE; i++)
    {
        for (j = 0; j < BOARD_SIZE; j++)
        {

            if (board[i][j] == -1)
                printf("%d ", board[i][j]);

            else
                printf(" %d ", board[i][j]);
        }
        printf("\n");

    }

}
int FillBoard(short board[][9], Array ***possibilities)
{
    int status;
    int x, y;
    int option;
    int squareValue;

    status = OneStage(board, possibilities, &x, &y);

    while (status == NOT_FINISH)
    {
        printPossibilities(possibilities, x, y);

        scanf("%d", &option);

        squareValue = possibilities[x][y]->arr[option - 1];
        board[x][y] = squareValue;

        UpdatePossibilities(board, possibilities, x, y, squareValue);

        status = OneStage(board, possibilities, &x, &y);
    }

    if (status == FINISH_SUCCESS)
        return(FILLED);
    else
        return(FAIL);

}

void printPossibilities(Array***possibilities,int x,int y)
{
    int i;

    for (i = 0; i < possibilities[x][y]->size; i++)
        printf("%d. %d\n", i+1, possibilities[x][y]->arr[i]);
    return;
}

int OneStage(short board[][9], Array ***possibilities, int *x, int *y)
{
    bool full = true;
    bool dupFound = false;
    int i, j;
    int xIndex, yIndex;
    int squareValue;
    unsigned short minPossibilities = 9;

    for (i = 0; i < BOARD_SIZE; i++)
    {
        for (j = 0; j < BOARD_SIZE; j++)
        {
            if (board[i][j] == EMPTY_SQUARE)
            {
                if (possibilities[i][j]->size == 1)
                {
                    squareValue = possibilities[i][j]->arr[0];
                    board[i][j] = squareValue;

                    dupFound = SearchForDuplications(board, i, j, squareValue);

                    if (dupFound == true)
                        return(FINISH_FAILURE);

                    free(possibilities[i][j]->arr);
                    free(possibilities[i][j]);
                    possibilities[i][j] = NULL;

                    UpdatePossibilities(board, possibilities, i, j, squareValue);

                }
                else
                {
                    full = false;
                    if (minPossibilities > possibilities[i][j]->size)
                    {
                        minPossibilities = possibilities[i][j]->size;
                        xIndex = i;
                        yIndex = j;
                    }
                }
            }
        }
    }

    if (full == false)
    {
        *x = xIndex;
        *y = yIndex;
        return(NOT_FINISH);
    }
    else
        return(FINISH_SUCCESS);
}

bool SearchForDuplications(short board[][9], int row, int col, int SquareValue)
{
    int count = 0;
    int i, j;
    int rowBlock;
    int colBlock;


    for (i = 0; i < BOARD_SIZE; i++)
    {
        if (board[row][i] == SquareValue)
            count++;
    }

    if (count>1)
        return(true);

    count = 0;

    for (i = 0; i < BOARD_SIZE; i++)
    {
        if (board[i][col] == SquareValue)
            count++;
    }

    if (count>1)
        return(true);

    count = 0;
    rowBlock = row / 3;
    colBlock = col / 3;

    for (i = 3 * rowBlock; i < 3 * rowBlock + 3; i++)
    {
        for (j = 3 * colBlock; j < 3 * colBlock + 3; j++)
        {
            if (board[i][j] == SquareValue)
                count++;
        }
    }

    if (count>1)
        return(true);
    else
        return(false);
}

void UpdatePossibilities(short board[][9], Array***possibilities, int row, int col, int squareValue)
{
    int i;
    int j;
    int rowBlock;
    int colBlock;

    for (i = 0; i < BOARD_SIZE; i++)
    {
        if (board[row][i] == EMPTY_SQUARE)
            UpdateSquarePossibilities(possibilities, row, i, possibilities[row][i]->size, squareValue);
    }

    for (i = 0; i < BOARD_SIZE; i++)
    {
        if (board[i][col] == EMPTY_SQUARE)
            UpdateSquarePossibilities(possibilities, i, col, possibilities[row][i]->size, squareValue);
    }

    rowBlock = row / 3;
    colBlock = col / 3;

    for (i = 3 * rowBlock; i < 3 * rowBlock + 3; i++)
    {
        for (j = 3 * colBlock; j < 3 * colBlock + 3; j++)
        {
            if (board[i][j] == EMPTY_SQUARE)
                UpdateSquarePossibilities(possibilities, i, j, possibilities[row][i]->size, squareValue);
        }
    }

    return;
}

void UpdateSquarePossibilities(Array***possibilities, int row, int col, unsigned short arrSize, int squareValue)
{
    unsigned short i;
    unsigned short newSize;
    int write = 0;
    short* updatedArr;
    bool found = false;

    for (i = 0; i < arrSize && found == false; i++)
    {
        if (possibilities[row][col]->arr[i] == squareValue)
        {
            found = true;
        }
    }

    if (found == false)
        return;

    newSize = arrSize - 1;
    updatedArr = (short*)malloc(newSize*sizeof(short));

    for (i = 0; i < arrSize; i++)
    {
        if (possibilities[row][col]->arr[i] != squareValue)
        {
            updatedArr[write] = possibilities[row][col]->arr[i];
            write++;
        }
    }

    free(possibilities[row][col]->arr);

    possibilities[row][col]->arr = updatedArr;
    possibilities[row][col]->size = newSize;

    return;
}

Array ***PossibleDigits(short sudokuBoard[][9])
{
    Array*** newBoard;
    int i;
    int j;

    newBoard = (Array***)malloc(BOARD_SIZE*(sizeof(Array**)));

    if (!newBoard)  //if allocation faild
    {
        //allocation faild
    }

    for (i = 0; i < BOARD_SIZE; i++)
    {
        newBoard[i]= (Array**)malloc(BOARD_SIZE*(sizeof(Array*)));
        if (!newBoard)  //if allocation faild
        {
            //allocation faild
        }
    }

    for (i = 0; i<9; i++)
    {
        for (j = 0; j<9; j++)
        {
            newBoard[i][j] = (Array*)malloc(sizeof(Array));   //allocation every cell to Array struct
            if (!newBoard[i][j])  //if allocation faild
            {
                //exit
            }
        }
    }


    for (i = 0; i <BOARD_SIZE; i++)
    {
        for (j = 0; i < BOARD_SIZE; i++)
        {
            if (sudokuBoard[i][j] == EMPTY_SQUARE)
                newBoard[i][j]->arr = bucketsort(sudokuBoard, i, j, BOARD_SIZE, &newBoard[i][j]->size);
            else
                newBoard[i][j]->arr = NULL;
        }
    }

    return(newBoard);
}

short* bucketsort(short sudokuBoard[][9], int row, int col, int size, unsigned short*arrSize)
{
    int i, j;   //index for
    int count[10];   //new array
    unsigned short sizeCount = 0;
    int squareValue;
    int sudokuBlockSize = 3;
    short *arr;
    int write = 0;
    int rowBlock;
    int colBlock;

    for (i = 0; i < size; i++)
        count[i] = 0;

    for (i = 0; i < size; i++)
    {
        squareValue = sudokuBoard[i][col];

        if (squareValue != EMPTY_SQUARE)
            count[sudokuBoard[i][col]]++;
    }

    for (i = 0; i < size; i++)
    {
        squareValue = sudokuBoard[row][i];

        if (squareValue != EMPTY_SQUARE)
            count[sudokuBoard[row][i]]++;
    }

    rowBlock = row / 3;
    colBlock = col / 3;

    for (i = 3 * rowBlock; i < 3 * rowBlock + 3; i++)
    {
        for (j = 3 * colBlock; j < 3 * colBlock + 3; j++)
        {
            squareValue = sudokuBoard[i][j];

            if (squareValue != EMPTY_SQUARE)
                count[sudokuBoard[i][j]]++;
        }
    }

    for (i = 1; i <= size; i++)
    if (count[i] == 0)
        sizeCount++;

    *arrSize = sizeCount;

    arr = (short*)malloc(sizeCount*sizeof(short));

    for (i = 1; i <= size; i++)
    {
        if (count[i] == 0)
        {
            arr[write] = i;
            write++;
        }
    }

    return(arr);
}

int countDigits(int num)  /*This function count the amount of digits in 'num'*/
{
    int count;
    count = 0;

    while (num > 0)
    {
        num = num / 10;
        count++;
    }

    return(count);
}

void printMultTable(int maxMult) /*This function prints the Multiplication Table at the size of maxMult x maxMult*/
{
int i; /*loop index*/
int j; /*loop index*/
int maxcount;/*holds the maximum amount of digits a number can reach in the current mult table*/
int count;  /*Holds the current amount of digits*/
int nextcount; /*Holds the amount of digits of the next number*/

    maxcount = countDigits(maxMult);  /*Call to function*/

    for (i = 1; i <= maxMult; i++) /*Main loop*/
    {
        printf("%*d", maxcount, i);

       for (j = 2; j <= maxMult; j++)
    {

        count = countDigits(i*j);
        nextcount = countDigits((maxMult)*j);

if (count < nextcount)
    {
        printf("%*d", nextcount + 1, i*j);
        }
    else
            printf("%*d", count + 1, i*j);
    }

        printf("\n");
    }

 }