Thursday, February 11, 2016

sudoku in C

//not perfect, but a fun start
//have file 'sudoku114.txt' in working directory
//contains 9x9 starting condition for puzzle, ie:

/*
020600005
589240000
310000704
407090218
000000000
260005300
000109060
172560803
090830471
*/

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

struct sudoku
{
    int puzzle[9][9];
    int iteration;
    struct sudoku* next;
    struct sudoku* prev;
};

struct sudoku *Head;
struct sudoku *Ref;
struct sudoku *New;
struct sudoku *Back;

char Filename[15] = "sudoku114.txt";
int avail[9];
int TOTAL,cheat;

int AvailSum()
{
    int p,sum = 0;
    for(p=0; p<9; p++)
        sum += avail[p];
    return sum;
};

void FindAvailables(int r, int c)
{
    int i,j,n,m;
    for(i=0; i<9; i++)  //init available
        avail[i] = 1;
    for(i=0; i<9; i++)  //elim availables
        if(Ref->puzzle[r][i]>0)
            avail[Ref->puzzle[r][i]-1] = 0;  //along row
    for(j=0; j<9; j++)
        if(Ref->puzzle[j][c]>0)
            avail[Ref->puzzle[j][c]-1] = 0;  //along column
    n = 3*(r/3); m = 3*(c/3);
    for(i=n; i<3+n; i++)
        for(j=m; j<3+m; j++)
            if(Ref->puzzle[i][j]>0)
                avail[Ref->puzzle[i][j]-1] = 0;  //within group
};

void PrintPuzzle()
{
    int r,c;
    TOTAL = 0;
    printf("\n-Iteration %d-\n\n",Ref->iteration);
    printf("   012 345 678\n");
    for(r=0; r<9; r++)
    {
        if(r%3==0) printf("\n");
        printf("%d ",r);
        for(c=0; c<9; c++)
        {
            if(c%3==0) printf(" ");
            printf("%d",Ref->puzzle[r][c]);
            TOTAL += Ref->puzzle[r][c];
        } printf("\n");
    }
   
    if(TOTAL==405)
    {
        printf("\n************\n* YOU WON! *\n************\n");
        exit(EXIT_SUCCESS);
    }
};

void Hints()  //find the # avails for each cell, report list
{
    int a=0,r,c,i,j,k,m,n,p=1;   //format: [r,c] : (avails)

    printf("\nHINTS\n");
    while(p<10)  //change to higher numbers for larger avail lists
    {
        printf("\nAVAIL-%d CELLS\n",p);
        for(r=0; r<9; r++)
        {
            for(c=0; c<9; c++)
            {
                if(Ref->puzzle[r][c]==0)  //find availabilities for non-occupied cells only
                {
                    FindAvailables(r,c);
                    if(AvailSum()==p)
                    {
                        a++;
                        printf("[%d %d]:(",r,c);
                        for(k=0; k<9; k++)   
                        {
                            if(avail[k]>0)
                            {
                                printf("%d ",k+1);
                                if(p==1 && cheat==1)
                                    Ref->puzzle[r][c] = k+1;  //input "9 11" autofills avail-1 cells
                            }
                        }
                        printf("\b)\n");
                    }
                }
            }
        } p++;
    }
    PrintPuzzle();
    if(!a)
    {
        printf("\nNO AVAIL-1 CELLS REMAIN\n");
        if(cheat) cheat = 0;
    }
};

int main()
{
    Head = (struct sudoku*)malloc(sizeof(struct sudoku));
   
    if(Head==NULL)
    { printf("CANT MAKE HEAD NODE"); exit(EXIT_FAILURE); }
   
    Head->next = NULL;
    Head->prev = NULL;
    Head->iteration = 0;  //Head will store the initial read-in from file

    FILE *fptr;
    fptr = fopen(Filename,"r");
    if(fptr==NULL)
    {
        printf("\nUnable to access file \"%s\".\n",Filename);
        printf("Please ensure it exists in working directory\n\n");
        printf("Program Terminated...\n\n");
        exit(EXIT_FAILURE);
    }
   
    int row=0,col=0,entry,i,j,n,m,c;
    while((c = fgetc(fptr)-48)!=EOF)
    {
        if(c!=-38) Head->puzzle[row][col++] = c;  //sep col++?
        if(col>8)
        { col = 0; row++; }
        if(row>8) break;
    }
   
    fclose(fptr);
    Ref = Head;
   
bkup:
    PrintPuzzle();
   
    do
    {
        printf("\n(9 9 = HINTS)\n(9 11 = AUTOSOLVE)\n\n(row col): ");
        scanf("%d %d",&row,&col);
       
        if(row==9 && col==9) Hints();
        else if(row==9 && col==11)
        { cheat = 1; while(cheat) Hints(); cheat = 0; }
        else if(row>8 || col>8) printf("\nOut of Range\n");
        else if(Ref->puzzle[row][col]) printf("\nOccupied\n");
        else
        {
            FindAvailables(row,col);
           
            if(!AvailSum())
            {
                printf("** -- DEADLOCKED -- **\nIteration: %d",Ref->iteration);
                printf("\nBack up how many steps: ");
                scanf("%d",&entry);
               
                if(entry>Ref->iteration) entry = 0;
                else entry = (Ref->iteration)-entry;
               
                while((Ref->iteration)>entry)
                { Back = Ref->prev; Back->next = NULL; free(Ref); Ref = Back; }
                goto bkup;
            }
           
            printf("\nAvailable: (");
            for(i=0; i<9; i++)
                if(avail[i])
                    printf("%d ",i+1);
            printf("\b)");
                   
            printf("\nEntry(0 QUITS): ");
            scanf("%d",&entry);
            if(!avail[entry-1])
                printf("\"%d\" NOT AVAILABLE",entry);
           
            else
            {
                New = (struct sudoku*)malloc(sizeof(struct sudoku));
                if(New==NULL)
                    return 1;
                *New = *Ref;
                New->puzzle[row][col] = entry;
                New->iteration = (Ref->iteration)+1;
                New->next = NULL;
                New->prev = Ref;
                Ref->next = New;
                Ref = New;
                PrintPuzzle();
            }
        }
    } while(entry > 0);
   
    return 0;
}