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

/* I hate those sudoko puzzles. This is an attempt to write code to solve them 
for me without any thought at all. No doubt it will require several levels of
optimization before if runs sufficiently fast. */
/* UPDATE: Apparently these puzzles aren't as processor intensive and upon 
first attempt at optimization it solves the hardest in just under 2 seconds. */

/* Each position in the board is one of these */
struct gameNodes
{
    /* Previous attempts. These numbers are to be skipped when backtracking */
    /* Each value stored in its correct position. 1->attempts[0] 2->attempts[1] */
    int attempts[9];
    /* Value of the current board position. 0-9 */
    int value;
    /* If the number was entered originally. It can't be changed so lock it */
    /* 1 is locked. 0 is unlocked */
    int locked;
};

/* The absolute current board position */
int absolutePos = -1;

/* Make an array to hold all these structs */
struct gameNodes board[9][9];
/*
    Name: resetArray
    Description: bzero() for a specific array size of 9.
    Method: Set all values to 0.
    Returns: none
*/
void resetArray(int array[])
{
    int i;
    for(i=0;i<9;i++)
    {
        array[i]=0;
    }
} /* End resetArray */

/*
    Name: init
    Description: bzero() all the structs in the game board.
    Method: Set all values to 0.
    Returns: none
*/
void init()
{
    int i, j = 0;
    for(i=0;i<9;i++)
    {
        for(j=0;j<9;j++)
        {
            resetArray(board[i][j].attempts);
            board[i][j].value=0;
            board[i][j].locked=0;
        }
    }
}

/*
    Name: move
    Parameters: The direction as an int. 1 for forwards, -1 for backwards.
    Description: Move to the board position to solve next. Skip locked squares.
    Method: Add the direction to the absolute position and break into x and y 
            values, check if this position is locked. If it is, skip in the same 
            direction.
            If the position is negative, exit. The puzzle is impossible.
    Returns: None
*/
void move(int dir)
{
    int xPos,yPos;
    absolutePos += dir;
    /* This does find the correct x and y positions. */
    xPos = absolutePos%9;
    /* Integer division when you can't remember it. I think its div() */
    yPos = (absolutePos-xPos)/9;
    if(board[xPos][yPos].locked)
    {
        /* Move in the same direction */
        move(dir);
    }
    if(absolutePos<0)
    {
        /* Failed to solve */
        printf("This appears to be impossible..\n\n");
        system("PAUSE");
        exit(1);
    }
}

/*
    Name: solve
    Parameters: x and y coordinates for the game board.
    Description: Solve a value in the puzzle. If it can't be solved, The previous
                 vaules are wrong.
    Method: Check each row, column and 3x3 square for numbers. Anything not found
            is a possible value. Pick the last one, put it in the attempts[] array
            and board value and move on.
            If there are no possible values left. Set this value to 0, reset all
            attempts and try re-solve the previous.
    Returns: None
*/
int solve(int x, int y)
{
    /* Assume all numbers are possible for a square */
    int poss[]={1,2,3,4,5,6,7,8,9};
    /* Meaning there are 9 possible values */
    int possCount = 9;
    int i, j, m, n = 0;
    /* Get rid of values we've tried before that didn't work. */
    for(i=0;i<9;i++)
    {
        if((board[x][y].attempts[i]==poss[i]) && (board[x][y].attempts[i] != 0))
        {
            poss[i]=0;
            possCount--;
        }
    }
    /* Get rid of any values that are elsewhere in the row */
    for(i=0;i<9;i++)
    {
        if(board[x][i].value == poss[board[x][i].value-1] && board[x][i].value!=0)
        {
            poss[board[x][i].value-1]=0;
            possCount--;
        }
    }
    /* Get rid of any values that are elsewhere in the column */
    for(i=0;i<9;i++)
    {
        if(board[i][y].value == poss[board[i][y].value-1]&& board[i][y].value!=0)
        {
            poss[board[i][y].value-1]=0;
            possCount--;
        }
    }
    /* Get rid of any values that are elsewhere in the 3x3 square */
    m = x-x%3;
    n = y-y%3;
    for(i=m;i<m+3;i++)
    {
        for(j=n;j<n+3;j++)
        {
            if(board[i][j].value == poss[board[i][j].value-1] && board[i][j].value!=0)
            {
                poss[board[i][j].value-1]=0;
                possCount--;
            }
        }
    }
    /* Are there any numbers left to put into this square? */
    if(possCount < 1)
    {
        /* No. so reset valeus and BACKTRACK */
        resetArray(board[x][y].attempts);
        board[x][y].value = 0;
        move(-1);
    }
    else
    {
        /* Yes. so set values and CONTINUE */
        for(i=0;i<9;i++)
        {
            if(poss[i]!=0)
            {
                board[x][y].value = poss[i];
            }
        }
        /* The value must be stored in its correct position. attempts[value-1] */
        board[x][y].attempts[board[x][y].value-1] = board[x][y].value;
        move(1);
    }
}

/*
    Name: solveManager
    Description: Probably not required
    Method: Call solve(x, y) after getting x and y from absolutePos
    Returns: None
*/
int solveManager()
{
    int xPos,yPos;
    xPos = absolutePos%9;
    yPos = (absolutePos-xPos)/9;
    solve(xPos, yPos);
}

/*
    Name: load
    Parameters: The filename to open as a char[]
    Description: Reads input from a file.
    Method: Opens the file and reads the first 81 digits as a game board.
    Returns: success as int. 0 for success, 1 for fail.
*/
int load(char filename[])
{
    FILE * fp;
    int i,j = 0;
    /* Try open the file */
    if((fp = fopen(filename, "r"))!=NULL)
	{
        for(i=0;i<9;i++)
        {
            for(j=0;j<9;j++)
            {
                /* Read 81 characters */
                board[j][i].value = getc(fp)-48;
                if(board[j][i].value == -48)
                {
                    /* EOF */
                    return 1;   
                }
                else if(board[j][i].value < 0 || board[j][i].value > 9)
                {
                    /* If invalid digit, read extra charater for that position */
                    j--;
                }
                else if(board[j][i].value>0)
                {
                    /* lock the values read in */
                    board[j][i].locked = 1;
                }
            }
        }
		fclose(fp);
		/* Success! Game collected */
		return 0;
	}
	else
	{
        /* unable to open the file for reading */
        return 1;
    }
}

int main(int argc, char *argv[])
{
    int i,j=0;
    if(argc==2)
    {
        /* program and path to input puzzle */
        if(load(argv[1])!=0)
        {
            printf("Unable to read a game from the specified file.\n\n");
            system("PAUSE");
            return 1;
        }
    }
    else if(argc==1)
    {
        printf("Please enter the game in 9 rows of 9 digits using 0 for spaces\n");
        printf("e.g.\n");
        printf("030960050\n");
        printf("260000004\n");
        printf("004001...\n");
        printf("\n");
        printf("Enter puzzle now:\n");
        for(i=0;i<9;i++)
        {
            for(j=0;j<9;j++)
            {
                /* Read characters from stdin */
                board[j][i].value = getchar()-48;
                if(board[j][i].value < 0 || board[j][i].value > 9)
                {
                    /* Invalid value. Read an extra one */
                    j--;
                }
                else
                {
                    if(board[j][i].value>0)
                    {
                        /* lock this non-zero value. */
                        board[j][i].locked = 1;
                    }
                }
            }
        }
    }
    else
    {
        printf("\nUSAGE: %s [path]\n\n", argv[0]);
        printf("\t[path]: Path to the puzzle to solve. If omitted, input\n");
        printf("\t        will be read from the keyboard at runtime.\n\n");
        printf("\tThe puzzle should be in the format of 9 rows of 9 digits\n");
        printf("\twith 0's for the spaces. E.g.:\n");
        printf("\t\t030960050\n");
        printf("\t\t260000004\n");
        printf("\t\t004001...\n\n");
        system("PAUSE");	
        return 1;
    }
    /* Print the game board without answers */
    printf("Currently working on..\n\n");
    for(i=0;i<9;i++)
    {
        for(j=0;j<9;j++)
        {
            printf("%d ", board[j][i].value);
        }
        printf("\n");
    }
    printf("\n");
    /* Move to the first position */
    move(1);
    while(absolutePos<81)
    {
        /* solve the puzzle */
        solveManager();
    }
    /* Print the answer */
    for(i=0;i<9;i++)
    {
        for(j=0;j<9;j++)
        {
            printf("%d ", board[j][i].value);
        }
        printf("\n");
    }
    printf("\nI hope this is right! - Maz from http://maz.net.au/\n\n");
    /* Pause to let the view the answer */
    system("PAUSE");
    /* Finish. Success! */
    return 0;
}