C Tutor... C Tutorial....

#include 
#include 

int update = 1;  // Global boolean, to ensure each update iteration is making progress.

struct cell
{
   int value;
   struct cell * next;  // Allows for storage of all possible values that cell can take.
}
sudokuArray[9][9];



struct list
{
   int x;
   int y;
   struct list * next;
} *pendingList;  // When a cell is set, it is added to queue, to keep track of which rows and columns need to be updated.



initCell(struct cell * cellPtr, int count)  // Each cell needs a linked list of number 1 to 9, inclusive.
{
   if (count <= 8)
   {
       cellPtr->next = (struct cell *) malloc(sizeof(struct cell));
       cellPtr->value = count;
       count++;
       initCell(cellPtr->next, count);
   }
   else
   {
       cellPtr->value = count;
       cellPtr->next = NULL;
   }
}



initialise(void)
{
   int x, y;
   for (x = 0; x <= 8; x++)
   {
       for(y = 0; y <= 8; y++)
       {
           initCell(&sudokuArray[x][y], 1);
       }
      
   }
}



int inPossible(int x, int y, int a)  // Checks if input cell is able to be set to 'a'.
{
   int boolean = 0;
   struct cell * tempPtr = &sudokuArray[x][y];
   while(tempPtr)
   {
       if (tempPtr->value == a)
       {
           boolean = 1;
           return;
       }
       else
           tempPtr = tempPtr->next;
   }
   return boolean;
}



addToPending(int a, int b)
{
   if (pendingList == NULL)
   {
       pendingList = (struct list *) malloc(sizeof(struct list));
       pendingList->x = a;
       pendingList->y = b;       
       pendingList->next = NULL;
   }
   else
   {
       struct list * tempPtr = pendingList;
       while(tempPtr->next)
           tempPtr = tempPtr->next;
       tempPtr->next = (struct list *) malloc(sizeof(struct list));
       tempPtr->next->x = a;
       tempPtr->next->y = b;
       tempPtr->next->next = NULL;
   }
}



possibles(int x, int y)  // Returns number of values cell can possibly take.
{
   int count = 0;
   struct cell * tempPtr = &sudokuArray[x][y];
   while(tempPtr)
   {
       count++;
       tempPtr = tempPtr->next;
   }
   return count;
}
      


updateCell(int x, int y, int a)  // Removes 'a' from linked list, pointed to by array[x][y]
{
   struct cell * cellPtr = &sudokuArray[x][y];
  
   if(!cellPtr->next)  // Already set.
       return;
   if(inPossible(x, y, a))
   {
       struct cell * tempPtr1;
       tempPtr1 = cellPtr;
       if (cellPtr->value == a)  // Value is at start of list.
       {
           * cellPtr = * cellPtr->next;
           if (a != 1)
               free(tempPtr1);
       }
       else
       {
           struct cell * tempPtr2;
           while((tempPtr1->next->value != a) && (tempPtr1->next->next))
               tempPtr1 = tempPtr1->next;
           if (tempPtr1->next->value == a)  // Value in middle of list.
           {
               tempPtr2 = tempPtr1->next;
               tempPtr1->next = tempPtr1->next->next;
               free(tempPtr2);
           }
           else
           {
               while(tempPtr1->next->next)  // Value is at end of list.
                   tempPtr1 = tempPtr1->next;
               tempPtr2 = tempPtr1->next;
               tempPtr1->next = NULL;
               free(tempPtr2);
           }
       }
   }
   //else  // This is problem, not working properly. If else contains nothing, when updateCell(x, y, b) is called, and [x][y] does not contain b, is is re-added.
       //printf("Cell %i, %i unable to take value %i\n", x, y, a);
   if(possibles(x, y) == 0)
       printf("Error - A cell has had all possible values removed from list.\n");
   else if(possibles(x, y) == 1)
       setCell(x, y, a);
}



getBox(int a)  // Returns top left cell co-ords of 3x3 box containing a, a (requires 2 calls)
{
   {
       if (a <= 2)
            return 0;
       else if (a <= 5)
           return 3;
       else
           return 6;
   }
}       



simpleUpdate(int x, int y)  // Updates all cells in same column, row and 3x3 box as input cell.
{
   int a, b, value, boxx, boxy;  // Is getting, as input, 1, 1.

   if (!sudokuArray[x][y].next)
   {
       value = sudokuArray[x][y].value;
   }
   else
   {
       printf("Error - Input cell %i, %i has not been set to a value.\n", x, y);  // Should not happen
       return;
   }
   for(b = 0; b <= 8; b++)  // Row
       updateCell(b, y, value);
   for(a = 0; a <= 8; a++)  // Column.
       updateCell(x, a, value);
   /*boxx = getBox(x);
   boxy = getBox(y);
   for(a = 0; a <= 2; a++)  // 3x3 box.
   {
       for(b = 0; b <= 2; b++)
       {
           //printf("x is %i, y is %i\n", boxx + a, boxy + b);
           //printPossibles(&sudokuArray[boxx + a][boxy + b]);
           updateCell(boxx + a, boxy + b, value);  // This line is problem, won't run if it is only member of for loop.
           //printPossibles(&sudokuArray[boxx + a][boxy + b]);
           printf("\n");
       }
   }*/
}



rowScan(int y, int value)
{
   int a, count = 0;
   for (a = 0; a <= 8; a++)
   {
       if (inPossible(a, y, value))
           count++;
   }
   return count;
}



columnScan(int x, int value)
{
   int a, count = 0;
   for (a = 0; a <= 8; a++)
   {
       if (inPossible(x, a, value))
           count++;
   }
   return count;
}



boxScan(int x, int y, int value)
{
   int a, b, count;
   for (a = 0; a <= 2; a++)
   {
       for (b = 0; b <= 2; b++)
       {
           if (inPossible(x + a, y + b, value))
               count++;
       }
   }
   return count;
}



oneCellUpdate()  // Check columns, rows and boxes, to see if a value can only be put in 1 of the 9 cells.
{
   update = 0;
   int a, b, c, d, temp, count = 0, x, y;
   for(temp = 0; temp <= 8; temp++)  // Run check for all number 1 to 9.
   {
       //printf("Just before loop for temp value %i\n", temp);
       for(a = 0; a <= 8; a++)  // Iterate through 9 rows.
       {
           if (rowScan(a, temp) == 1)
           {
               b = 0;
               update = 1;
               while(!inPossible(b, a, temp))
                   b++;
               setCell(b, a, temp);
           }
       }
       //printf("Just after loop for temp value %i\n", temp);
       for(a = 0; a <= 8; a++)  // Iterate through 9 columns.
       {
           if (columnScan(a, temp) == 1)
           {
               b = 0;
               update = 1;
               while(!inPossible(a, b, temp))
                   b++;
               setCell(a, b, temp);
           }
       }
       for(a = 0; a <= 8; a = a + 3)  // Iterate through boxes
       {
           for(b = 0; b <= 8; b = b + 3)
           {
               //printf("Just before box scan\n");
               a = 6, b = 0;
               for(c = 0; c <= 2; c++)  // Iterate through box cell columns
               {
                   for(d = 0; d <= 2; d++)
                   {
                       if(inPossible(a + c, b + d, temp))
                       {
                           count++;
                           x = a + c, y = b + d;
                       }
                   }
               }
               //printf("Just after box scan\n");
               if (count == 1)
               {
                   setCell(x, y, temp);
                   update = 1;
               }
               count = 0;
           }
       }
   }
}



updateGrid(void)
{
   struct list * tempPtr;
   while(pendingList)
   {
       simpleUpdate(pendingList->x, pendingList->y);
       tempPtr = pendingList;
       pendingList = pendingList->next;
       free(tempPtr);
   }
   /*while(update)
       oneCellUpdate();*/
   printf("No more updates possible.\n");
}



clear(struct cell * cellPtr)  // Deletes a linked list.
{
   if (cellPtr == NULL)
       return;
   else if (cellPtr->next)
       clear(cellPtr->next);
   free(cellPtr);
}



setCell(int x, int y, int a)  // Gives cell a value, and deletes linked list (next = NULL indicates cell has been set).
{
   if (inPossible(x, y, a))
   {
       update = 1;
       printf("x is %i, y is %i\n", x, y);
       sudokuArray[x][y].value = a;
       clear(sudokuArray[x][y].next);
       sudokuArray[x][y].next = NULL;
       addToPending(x, y);
   }
   else
       printf("setCell called when value not a possible value, x is %i, y is %i, value is %i\n", x, y, a);
}



printLine(int y)
{
   int x, count = 0;
   for (x = 0; x <= 8; x++)
   {
       if (possibles(x, y) == 1)
           printf(" %i", sudokuArray[x][y].value);
       else
           printf("  ");
       count++;
       if ((count == 3) & (x != 8))
       {
           printf(" |");
           count = 0;
       }
   }
}
  



printGrid()
{
   int x, y, count = 0;
   printf("   0 1 2   3 4 5   6 7 8\n");
   for (y = 0; y <= 8; y++)
   {
       printf("%i ", y);
       printLine(y);
       count++;
       printf("\n");
       if ((count == 3) & (y != 8))
       {
           printf("  ------------------------\n");
           count = 0;
       }
   }
}



printPossibles(struct cell * cellPtr)
{
   if(cellPtr)
   {
       printf("%i, ", cellPtr->value);
       printPossibles(cellPtr->next);
   }
   else
       printf("\n");
}



int main(void)
{
   initialise();
  
   setCell(2, 0, 9);
   setCell(6, 2, 9);
   setCell(3, 3, 9);
   setCell(5, 6, 9);

   updateGrid();
  
   int a, b;
   for (a = 0; a <= 2; a++)
   {
       for (b = 0; b <= 2; b++)
       {
           printf("x is %i, y is %i, possibles are: ", a + 3, b);
           printPossibles(&sudokuArray[3 + a][b]);
       }
   }

   printf("\n");
   printGrid();

   getchar();
  
   return 1;
}

Related Links :