1 /*

     2  *     $Id: sudoku.c,v 1.3 2008-04-29 15:18:53 mbroeker Exp $

     3  * $Source: /development/c/demos/sudoku.c,v $

     4  *

     5  */

     6 

     7 /* Sudoku - The Game */

     8 

     9 #include <stdio.h>

    10 #include <stdlib.h>

    11 #include <getopt.h>

    12 #include <string.h>

    13 #include <errno.h>

    14 #include <limits.h>

    15 

    16 #ifndef DIM

    17 #define DIM 9

    18 #endif

    19 

    20 #define COLORED "\e[31m"

    21 #define FGCOLOR "\e[37m"

    22 #define BGCOLOR "\e[40m\e[2J"

    23 #define   RESET "\e[0m"

    24 

    25 #define TRUE   1

    26 #define FALSE  0

    27 

    28 #ifndef u_int

    29 typedef unsigned int u_int;

    30 #endif

    31 

    32 #ifndef MAX_ITERATIONS

    33 #define MAX_ITERATIONS 10000000

    34 #endif

    35 

    36 struct Field {

    37     u_int value;

    38     int isConst;

    39 };

    40 

    41 /* the easiest way to get statistics */

    42 static unsigned long iterations = 0;

    43 

    44 typedef struct Field Field;

    45 typedef Field **Board;

    46 

    47 /**

    48  * read nxn fields from commandline and store it in the Board variable

    49  */

    50 int readBoard (Board board)

    51 {

    52     int i, j;

    53 

    54     u_int c;

    55 

    56     for (i = 0; i < DIM; i++) {

    57         for (j = 0; j < DIM; j++) {

    58             if (scanf ("%u", &c) < 1) {

    59                 fprintf (stderr, "readBoard: Not enough elements\n");

    60                 fprintf (stderr, "readBoard: Got %d, needed %d\n", i * DIM + j, (DIM) * (DIM));

    61                 return FALSE;

    62             }

    63             board[i][j].value = c;

    64             board[i][j].isConst = (c == 0) ? 0 : 1;

    65         }

    66     }

    67     return TRUE;

    68 }

    69 

    70 /**

    71  * Show the content of the Board in a human readable manner

    72  */

    73 void showBoard (Board board, int colored)

    74 {

    75     int i, j;

    76 

    77     for (i = 0; i < DIM; i++) {

    78         if ((i % 3) == 0)

    79             printf ("\n");

    80 

    81         for (j = 0; j < DIM; j++) {

    82             if ((board[i][j].isConst && colored))

    83                 printf ("%s%2u%s ", COLORED, board[i][j].value, FGCOLOR);

    84             else

    85                 printf ("%2u ", board[i][j].value);

    86             if (((j + 1) % 3) == 0)

    87                 printf ("  ");

    88         }

    89         printf ("\n");

    90     }

    91 }

    92 

    93 /**

    94  * checks for the possibility of value at board[row][col]

    95  */

    96 int check (Board board, int row, int col, u_int value)

    97 {

    98     int i, j;

    99 

   100     if (board[row][col].value > 0)

   101         return FALSE;

   102 

   103     for (i = 0; i < DIM; i++) {

   104         /*

   105          * check vertically

   106          */

   107         if (board[row][i].value == value)

   108             return FALSE;

   109         /*

   110          * check horizontally

   111          */

   112         if (board[i][col].value == value)

   113             return FALSE;

   114     }

   115 

   116     /*

   117      * check block for unique values

   118      */

   119     for (i = row - (row % 3); i < row - (row % 3) + 3; i++)

   120         for (j = col - (col % 3); j < col - (col % 3) + 3; j++)

   121             if (board[i][j].value == value)

   122                 return FALSE;

   123 

   124     return TRUE;

   125 }

   126 

   127 /**

   128  * go recursive from k to DIM^2 and try to solve the puzzle

   129  */

   130 int solveBoard (Board board, int k)

   131 {

   132     u_int i;

   133     int q;

   134 

   135     if ((++iterations > MAX_ITERATIONS))

   136         return FALSE;

   137 

   138     while (k < (DIM) * (DIM) && (board[k / DIM][k % DIM].value != 0))

   139         k++;

   140 

   141     if (k == (DIM) * (DIM))

   142         return TRUE;

   143 

   144     for (q = FALSE, i = 1; q == FALSE && i <= 9; i++) {

   145         if (check (board, k / DIM, k % DIM, i) == TRUE) {

   146             board[k / DIM][k % DIM].value = i;

   147             if (((DIM) * (DIM) - 1) == k)

   148                 q = TRUE;

   149             else if ((q = solveBoard (board, k + 1)) == FALSE) {

   150                 board[k / DIM][k % DIM].value = 0;

   151             }

   152         }

   153     }

   154 

   155     return q;

   156 }

   157 

   158 /**

   159  * Deletes every Field of the Board (CLEANUP)

   160  */

   161 void freeBoard (const Board board)

   162 {

   163     int i;

   164 

   165     for (i = 0; i < DIM; i++) {

   166         if (board[i] != NULL)

   167             free (board[i]);

   168     }

   169 }

   170 

   171 /**

   172  * Show plain usage screen

   173  */

   174 void usage (char *name)

   175 {

   176     printf ("Usage: %s [-c] [-h]\n\n", name);

   177     printf ("-c\t\tcolored output\n");

   178     printf ("-h\t\tshows this help\n");

   179     printf ("Report bugs to mbroeker@largo.homelinux.org\n");

   180 }

   181 

   182 int main (int argc, char **argv)

   183 {

   184     Board b;

   185     int i;

   186     int ret;

   187     int colored = 0;

   188 

   189     while ((i = getopt (argc, argv, "ch")) != -1) {

   190         switch (i) {

   191         case 'h':

   192             usage (argv[0]);

   193             return EXIT_SUCCESS;

   194         case 'c':

   195             printf ("%s%s", BGCOLOR, FGCOLOR);

   196             colored = 1;

   197             break;

   198         default:

   199             usage (argv[0]);

   200             return EXIT_FAILURE;

   201         }

   202     }

   203 

   204     if ((DIM % 3) != 0) {

   205         fprintf (stderr, "DIM must be a multiple of 3\n");

   206         fprintf (stderr, "RECOMPILE WITH -DDIM=9\n");

   207         return EXIT_FAILURE;

   208     }

   209 

   210     if ((b = calloc (DIM, sizeof (Field *))) == NULL) {

   211         perror ("calloc");

   212         return EXIT_FAILURE;

   213     }

   214 

   215     for (i = 0; i < DIM; i++) {

   216         if ((b[i] = malloc ((DIM * sizeof (Field)) + 1)) == NULL) {

   217             perror ("malloc");

   218             return EXIT_FAILURE;

   219         }

   220     }

   221 

   222     printf ("Sudoku - Enter a %dx%d Matrix\n", DIM, DIM);

   223 

   224     if (readBoard (b) == FALSE) {

   225         fprintf (stderr, "Input Error: Aborting\n");

   226         return EXIT_FAILURE;

   227     }

   228 

   229     showBoard (b, colored);

   230 

   231     if ((ret = solveBoard (b, 0)) == TRUE)

   232         printf ("\nPuzzle solved after %lu recursions\n", iterations);

   233     else

   234         printf ("\nCannot solve your puzzle after %lu recursions\n", iterations);

   235 

   236     showBoard (b, colored);

   237     freeBoard (b);

   238 

   239     if (b != NULL)

   240         free (b);

   241 

   242     if (colored)

   243         printf ("%s", RESET);

   244 

   245     return EXIT_SUCCESS;

   246 }