Leptonica  1.83.1
Image processing and image analysis suite
sudoku.c
Go to the documentation of this file.
1 /*====================================================================*
2  - Copyright (C) 2001 Leptonica. All rights reserved.
3  -
4  - Redistribution and use in source and binary forms, with or without
5  - modification, are permitted provided that the following conditions
6  - are met:
7  - 1. Redistributions of source code must retain the above copyright
8  - notice, this list of conditions and the following disclaimer.
9  - 2. Redistributions in binary form must reproduce the above
10  - copyright notice, this list of conditions and the following
11  - disclaimer in the documentation and/or other materials
12  - provided with the distribution.
13  -
14  - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15  - ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16  - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17  - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY
18  - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19  - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20  - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21  - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22  - OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23  - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24  - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  *====================================================================*/
26 
27 
141 #ifdef HAVE_CONFIG_H
142 #include <config_auto.h>
143 #endif /* HAVE_CONFIG_H */
144 
145 #include "allheaders.h"
146 
147 static l_int32 sudokuValidState(l_int32 *state);
148 static l_int32 sudokuNewGuess(L_SUDOKU *sud);
149 static l_int32 sudokuTestState(l_int32 *state, l_int32 index);
150 static l_int32 sudokuCompareState(L_SUDOKU *sud1, L_SUDOKU *sud2,
151  l_int32 quads, l_int32 *psame);
152 static l_int32 *sudokuRotateArray(l_int32 *array, l_int32 quads);
153 
154 /* --------------------------------------------------------------- */
155 /* An example of a valid solution */
156 /* --------------------------------------------------------------- *
157 static const char valid_solution[] = "3 8 7 2 6 4 1 9 5 "
158  "2 6 5 8 9 1 4 3 7 "
159  "1 4 9 5 3 7 6 8 2 "
160  "5 2 3 7 1 6 8 4 9 "
161  "7 1 6 9 4 8 2 5 3 "
162  "8 9 4 3 5 2 7 1 6 "
163  "9 7 2 1 8 5 3 6 4 "
164  "4 3 1 6 7 9 5 2 8 "
165  "6 5 8 4 2 3 9 7 1 ";
166 */
167 
168 
169 /*---------------------------------------------------------------------*
170  * Read input data from file or string *
171  *---------------------------------------------------------------------*/
186 l_int32 *
187 sudokuReadFile(const char *filename)
188 {
189 char *str, *strj;
190 l_uint8 *data;
191 l_int32 i, j, nlines, val, index, error;
192 l_int32 *array;
193 size_t size;
194 SARRAY *saline, *sa1, *sa2;
195 
196  if (!filename)
197  return (l_int32 *)ERROR_PTR("filename not defined", __func__, NULL);
198  data = l_binaryRead(filename, &size);
199  sa1 = sarrayCreateLinesFromString((char *)data, 0);
200  sa2 = sarrayCreate(9);
201 
202  /* Filter out the comment lines; verify that there are 9 data lines */
203  nlines = sarrayGetCount(sa1);
204  for (i = 0; i < nlines; i++) {
205  str = sarrayGetString(sa1, i, L_NOCOPY);
206  if (str[0] != '#')
207  sarrayAddString(sa2, str, L_COPY);
208  }
209  LEPT_FREE(data);
210  sarrayDestroy(&sa1);
211  nlines = sarrayGetCount(sa2);
212  if (nlines != 9) {
213  sarrayDestroy(&sa2);
214  L_ERROR("file has %d lines\n", __func__, nlines);
215  return (l_int32 *)ERROR_PTR("invalid file", __func__, NULL);
216  }
217 
218  /* Read the data into the array, verifying that each data
219  * line has 9 numbers. */
220  error = FALSE;
221  array = (l_int32 *)LEPT_CALLOC(81, sizeof(l_int32));
222  for (i = 0, index = 0; i < 9; i++) {
223  str = sarrayGetString(sa2, i, L_NOCOPY);
224  saline = sarrayCreateWordsFromString(str);
225  if (sarrayGetCount(saline) != 9) {
226  error = TRUE;
227  sarrayDestroy(&saline);
228  break;
229  }
230  for (j = 0; j < 9; j++) {
231  strj = sarrayGetString(saline, j, L_NOCOPY);
232  if (sscanf(strj, "%d", &val) != 1)
233  error = TRUE;
234  else
235  array[index++] = val;
236  }
237  sarrayDestroy(&saline);
238  if (error) break;
239  }
240  sarrayDestroy(&sa2);
241 
242  if (error) {
243  LEPT_FREE(array);
244  return (l_int32 *)ERROR_PTR("invalid data", __func__, NULL);
245  }
246 
247  return array;
248 }
249 
250 
263 l_int32 *
264 sudokuReadString(const char *str)
265 {
266 l_int32 i;
267 l_int32 *array;
268 
269  if (!str)
270  return (l_int32 *)ERROR_PTR("str not defined", __func__, NULL);
271 
272  /* Read in the initial solution */
273  array = (l_int32 *)LEPT_CALLOC(81, sizeof(l_int32));
274  for (i = 0; i < 81; i++) {
275  if (sscanf(str + 2 * i, "%d ", &array[i]) != 1) {
276  LEPT_FREE(array);
277  return (l_int32 *)ERROR_PTR("invalid format", __func__, NULL);
278  }
279  }
280 
281  return array;
282 }
283 
284 
285 /*---------------------------------------------------------------------*
286  * Create/destroy sudoku *
287  *---------------------------------------------------------------------*/
302 L_SUDOKU *
303 sudokuCreate(l_int32 *array)
304 {
305 l_int32 i, val, locs_index;
306 L_SUDOKU *sud;
307 
308  if (!array)
309  return (L_SUDOKU *)ERROR_PTR("array not defined", __func__, NULL);
310 
311  locs_index = 0; /* into locs array */
312  sud = (L_SUDOKU *)LEPT_CALLOC(1, sizeof(L_SUDOKU));
313  sud->locs = (l_int32 *)LEPT_CALLOC(81, sizeof(l_int32));
314  sud->init = (l_int32 *)LEPT_CALLOC(81, sizeof(l_int32));
315  sud->state = (l_int32 *)LEPT_CALLOC(81, sizeof(l_int32));
316  for (i = 0; i < 81; i++) {
317  val = array[i];
318  sud->init[i] = val;
319  sud->state[i] = val;
320  if (val == 0)
321  sud->locs[locs_index++] = i;
322  }
323  sud->num = locs_index;
324  sud->failure = FALSE;
325  sud->finished = FALSE;
326  return sud;
327 }
328 
329 
336 void
338 {
339 L_SUDOKU *sud;
340 
341  if (psud == NULL) {
342  L_WARNING("ptr address is NULL\n", __func__);
343  return;
344  }
345  if ((sud = *psud) == NULL)
346  return;
347 
348  LEPT_FREE(sud->locs);
349  LEPT_FREE(sud->init);
350  LEPT_FREE(sud->state);
351  LEPT_FREE(sud);
352  *psud = NULL;
353 }
354 
355 
356 /*---------------------------------------------------------------------*
357  * Solve the puzzle *
358  *---------------------------------------------------------------------*/
366 l_int32
368 {
369  if (!sud)
370  return ERROR_INT("sud not defined", __func__, 0);
371 
372  if (!sudokuValidState(sud->init))
373  return ERROR_INT("initial state not valid", __func__, 0);
374 
375  while (1) {
376  if (sudokuNewGuess(sud))
377  break;
378  if (sud->finished == TRUE)
379  break;
380  }
381 
382  if (sud->failure == TRUE) {
383  lept_stderr("Failure after %d guesses\n", sud->nguess);
384  return 0;
385  }
386 
387  lept_stderr("Solved after %d guesses\n", sud->nguess);
388  return 1;
389 }
390 
391 
405 static l_int32
406 sudokuValidState(l_int32 *state)
407 {
408 l_int32 i;
409 
410  if (!state)
411  return ERROR_INT("state not defined", __func__, 0);
412 
413  for (i = 0; i < 81; i++) {
414  if (!sudokuTestState(state, i))
415  return 0;
416  }
417 
418  return 1;
419 }
420 
421 
440 static l_int32
442 {
443 l_int32 index, val, valid;
444 l_int32 *locs, *state;
445 
446  locs = sud->locs;
447  state = sud->state;
448  index = locs[sud->current]; /* 0 to 80 */
449  val = state[index];
450  if (val == 9) { /* backtrack or give up */
451  if (sud->current == 0) {
452  sud->failure = TRUE;
453  return 1;
454  }
455  state[index] = 0;
456  sud->current--;
457  } else { /* increment current value and test */
458  sud->nguess++;
459  state[index]++;
460  valid = sudokuTestState(state, index);
461  if (valid) {
462  if (sud->current == sud->num - 1) { /* we're done */
463  sud->finished = TRUE;
464  return 0;
465  } else { /* advance to next position */
466  sud->current++;
467  }
468  }
469  }
470 
471  return 0;
472 }
473 
474 
482 static l_int32
483 sudokuTestState(l_int32 *state,
484  l_int32 index)
485 {
486 l_int32 i, j, val, row, rowstart, rowend, col;
487 l_int32 blockrow, blockcol, blockstart, rowindex, locindex;
488 
489  if ((val = state[index]) == 0) /* automatically valid */
490  return 1;
491 
492  /* Test row. Test val is at (x, y) = (index % 9, index / 9) */
493  row = index / 9;
494  rowstart = 9 * row;
495  for (i = rowstart; i < index; i++) {
496  if (state[i] == val)
497  return 0;
498  }
499  rowend = rowstart + 9;
500  for (i = index + 1; i < rowend; i++) {
501  if (state[i] == val)
502  return 0;
503  }
504 
505  /* Test column */
506  col = index % 9;
507  for (j = col; j < index; j += 9) {
508  if (state[j] == val)
509  return 0;
510  }
511  for (j = index + 9; j < 81; j += 9) {
512  if (state[j] == val)
513  return 0;
514  }
515 
516  /* Test local 3x3 block */
517  blockrow = 3 * (row / 3);
518  blockcol = 3 * (col / 3);
519  blockstart = 9 * blockrow + blockcol;
520  for (i = 0; i < 3; i++) {
521  rowindex = blockstart + 9 * i;
522  for (j = 0; j < 3; j++) {
523  locindex = rowindex + j;
524  if (index == locindex) continue;
525  if (state[locindex] == val)
526  return 0;
527  }
528  }
529 
530  return 1;
531 }
532 
533 
534 /*---------------------------------------------------------------------*
535  * Test for uniqueness *
536  *---------------------------------------------------------------------*/
553 l_ok
554 sudokuTestUniqueness(l_int32 *array,
555  l_int32 *punique)
556 {
557 l_int32 same1, same2, same3;
558 l_int32 *array1, *array2, *array3;
559 L_SUDOKU *sud, *sud1, *sud2, *sud3;
560 
561  if (!punique)
562  return ERROR_INT("&unique not defined", __func__, 1);
563  *punique = 0;
564  if (!array)
565  return ERROR_INT("array not defined", __func__, 1);
566 
567  sud = sudokuCreate(array);
568  sudokuSolve(sud);
569  array1 = sudokuRotateArray(array, 1);
570  sud1 = sudokuCreate(array1);
571  sudokuSolve(sud1);
572  array2 = sudokuRotateArray(array, 2);
573  sud2 = sudokuCreate(array2);
574  sudokuSolve(sud2);
575  array3 = sudokuRotateArray(array, 3);
576  sud3 = sudokuCreate(array3);
577  sudokuSolve(sud3);
578 
579  sudokuCompareState(sud, sud1, 1, &same1);
580  sudokuCompareState(sud, sud2, 2, &same2);
581  sudokuCompareState(sud, sud3, 3, &same3);
582  *punique = (same1 && same2 && same3);
583 
584  sudokuDestroy(&sud);
585  sudokuDestroy(&sud1);
586  sudokuDestroy(&sud2);
587  sudokuDestroy(&sud3);
588  LEPT_FREE(array1);
589  LEPT_FREE(array2);
590  LEPT_FREE(array3);
591  return 0;
592 }
593 
594 
612 static l_int32
614  L_SUDOKU *sud2,
615  l_int32 quads,
616  l_int32 *psame)
617 {
618 l_int32 i, same;
619 l_int32 *array;
620 
621  if (!psame)
622  return ERROR_INT("&same not defined", __func__, 1);
623  *psame = 0;
624  if (!sud1)
625  return ERROR_INT("sud1 not defined", __func__, 1);
626  if (!sud2)
627  return ERROR_INT("sud1 not defined", __func__, 1);
628  if (quads < 1 || quads > 3)
629  return ERROR_INT("valid quads in {1,2,3}", __func__, 1);
630 
631  same = TRUE;
632  if ((array = sudokuRotateArray(sud1->state, quads)) == NULL)
633  return ERROR_INT("array not made", __func__, 1);
634  for (i = 0; i < 81; i++) {
635  if (array[i] != sud2->state[i]) {
636  same = FALSE;
637  break;
638  }
639  }
640  *psame = same;
641  LEPT_FREE(array);
642  return 0;
643 }
644 
645 
653 static l_int32 *
654 sudokuRotateArray(l_int32 *array,
655  l_int32 quads)
656 {
657 l_int32 i, j, sindex, dindex;
658 l_int32 *rarray;
659 
660  if (!array)
661  return (l_int32 *)ERROR_PTR("array not defined", __func__, NULL);
662  if (quads < 1 || quads > 3)
663  return (l_int32 *)ERROR_PTR("valid quads in {1,2,3}", __func__, NULL);
664 
665  rarray = (l_int32 *)LEPT_CALLOC(81, sizeof(l_int32));
666  if (quads == 1) {
667  for (j = 0, dindex = 0; j < 9; j++) {
668  for (i = 8; i >= 0; i--) {
669  sindex = 9 * i + j;
670  rarray[dindex++] = array[sindex];
671  }
672  }
673  } else if (quads == 2) {
674  for (i = 8, dindex = 0; i >= 0; i--) {
675  for (j = 8; j >= 0; j--) {
676  sindex = 9 * i + j;
677  rarray[dindex++] = array[sindex];
678  }
679  }
680  } else { /* quads == 3 */
681  for (j = 8, dindex = 0; j >= 0; j--) {
682  for (i = 0; i < 9; i++) {
683  sindex = 9 * i + j;
684  rarray[dindex++] = array[sindex];
685  }
686  }
687  }
688 
689  return rarray;
690 }
691 
692 
693 /*---------------------------------------------------------------------*
694  * Generation *
695  *---------------------------------------------------------------------*/
716 L_SUDOKU *
717 sudokuGenerate(l_int32 *array,
718  l_int32 seed,
719  l_int32 minelems,
720  l_int32 maxtries)
721 {
722 l_int32 index, sector, nzeros, removefirst, tries, val, oldval, unique;
723 L_SUDOKU *sud, *testsud;
724 
725  if (!array)
726  return (L_SUDOKU *)ERROR_PTR("array not defined", __func__, NULL);
727  if (minelems > 80)
728  return (L_SUDOKU *)ERROR_PTR("minelems must be < 81", __func__, NULL);
729 
730  /* Remove up to 30 numbers at random from the solution.
731  * Test if the solution is valid -- the initial 'solution' may
732  * have been invalid. Then test if the sudoku with 30 zeroes
733  * is unique -- it almost always will be. */
734  srand(seed);
735  nzeros = 0;
736  sector = 0;
737  removefirst = L_MIN(30, 81 - minelems);
738  while (nzeros < removefirst) {
739  genRandomIntOnInterval(0, 8, 0, &val);
740  index = 27 * (sector / 3) + 3 * (sector % 3) +
741  9 * (val / 3) + (val % 3);
742  if (array[index] == 0) continue;
743  array[index] = 0;
744  nzeros++;
745  sector++;
746  sector %= 9;
747  }
748  testsud = sudokuCreate(array);
749  sudokuSolve(testsud);
750  if (testsud->failure) {
751  sudokuDestroy(&testsud);
752  L_ERROR("invalid initial solution\n", __func__);
753  return NULL;
754  }
755  sudokuTestUniqueness(testsud->init, &unique);
756  sudokuDestroy(&testsud);
757  if (!unique) {
758  L_ERROR("non-unique result with 30 zeroes\n", __func__);
759  return NULL;
760  }
761 
762  /* Remove more numbers, testing at each removal for uniqueness. */
763  tries = 0;
764  sector = 0;
765  while (1) {
766  if (tries > maxtries) break;
767  if (81 - nzeros <= minelems) break;
768 
769  if (tries == 0) {
770  lept_stderr("Trying %d zeros\n", nzeros);
771  tries = 1;
772  }
773 
774  /* Choose an element to be zeroed. We choose one
775  * at random in succession from each of the nine sectors. */
776  genRandomIntOnInterval(0, 8, 0, &val);
777  index = 27 * (sector / 3) + 3 * (sector % 3) +
778  9 * (val / 3) + (val % 3);
779  sector++;
780  sector %= 9;
781  if (array[index] == 0) continue;
782 
783  /* Save the old value in case we need to revert */
784  oldval = array[index];
785 
786  /* Is there a solution? If not, try again. */
787  array[index] = 0;
788  testsud = sudokuCreate(array);
789  sudokuSolve(testsud);
790  if (testsud->failure == TRUE) {
791  sudokuDestroy(&testsud);
792  array[index] = oldval; /* revert */
793  tries++;
794  continue;
795  }
796 
797  /* Is the solution unique? If not, try again. */
798  sudokuTestUniqueness(testsud->init, &unique);
799  sudokuDestroy(&testsud);
800  if (!unique) { /* revert and try again */
801  array[index] = oldval;
802  tries++;
803  } else { /* accept this */
804  tries = 0;
805  lept_stderr("Have %d zeros\n", nzeros);
806  nzeros++;
807  }
808  }
809  lept_stderr("Final: nelems = %d\n", 81 - nzeros);
810 
811  /* Show that we can recover the solution */
812  sud = sudokuCreate(array);
813  sudokuOutput(sud, L_SUDOKU_INIT);
814  sudokuSolve(sud);
815  sudokuOutput(sud, L_SUDOKU_STATE);
816 
817  return sud;
818 }
819 
820 
821 /*---------------------------------------------------------------------*
822  * Output *
823  *---------------------------------------------------------------------*/
837 l_int32
839  l_int32 arraytype)
840 {
841 l_int32 i, j;
842 l_int32 *array;
843 
844  if (!sud)
845  return ERROR_INT("sud not defined", __func__, 1);
846  if (arraytype == L_SUDOKU_INIT)
847  array = sud->init;
848  else if (arraytype == L_SUDOKU_STATE)
849  array = sud->state;
850  else
851  return ERROR_INT("invalid arraytype", __func__, 1);
852 
853  for (i = 0; i < 9; i++) {
854  for (j = 0; j < 9; j++)
855  lept_stderr("%d ", array[9 * i + j]);
856  lept_stderr("\n");
857  }
858  return 0;
859 }
@ L_COPY
Definition: pix.h:505
@ L_NOCOPY
Definition: pix.h:503
SARRAY * sarrayCreate(l_int32 n)
sarrayCreate()
Definition: sarray1.c:169
char * sarrayGetString(SARRAY *sa, l_int32 index, l_int32 copyflag)
sarrayGetString()
Definition: sarray1.c:673
l_int32 sarrayGetCount(SARRAY *sa)
sarrayGetCount()
Definition: sarray1.c:617
void sarrayDestroy(SARRAY **psa)
sarrayDestroy()
Definition: sarray1.c:353
SARRAY * sarrayCreateWordsFromString(const char *string)
sarrayCreateWordsFromString()
Definition: sarray1.c:228
SARRAY * sarrayCreateLinesFromString(const char *string, l_int32 blankflag)
sarrayCreateLinesFromString()
Definition: sarray1.c:276
l_ok sarrayAddString(SARRAY *sa, const char *string, l_int32 copyflag)
sarrayAddString()
Definition: sarray1.c:435
l_int32 num
Definition: sudoku.h:54
l_int32 * init
Definition: sudoku.h:57
l_int32 * locs
Definition: sudoku.h:55
l_int32 failure
Definition: sudoku.h:63
l_int32 nguess
Definition: sudoku.h:61
l_int32 current
Definition: sudoku.h:56
l_int32 * state
Definition: sudoku.h:59
l_int32 finished
Definition: sudoku.h:62
l_int32 * sudokuReadFile(const char *filename)
sudokuReadFile()
Definition: sudoku.c:187
static l_int32 sudokuNewGuess(L_SUDOKU *sud)
sudokuNewGuess()
Definition: sudoku.c:441
static l_int32 sudokuValidState(l_int32 *state)
sudokuValidState()
Definition: sudoku.c:406
l_int32 * sudokuReadString(const char *str)
sudokuReadString()
Definition: sudoku.c:264
L_SUDOKU * sudokuGenerate(l_int32 *array, l_int32 seed, l_int32 minelems, l_int32 maxtries)
sudokuGenerate()
Definition: sudoku.c:717
static l_int32 * sudokuRotateArray(l_int32 *array, l_int32 quads)
sudokuRotateArray()
Definition: sudoku.c:654
static l_int32 sudokuCompareState(L_SUDOKU *sud1, L_SUDOKU *sud2, l_int32 quads, l_int32 *psame)
sudokuCompareState()
Definition: sudoku.c:613
void sudokuDestroy(L_SUDOKU **psud)
sudokuDestroy()
Definition: sudoku.c:337
L_SUDOKU * sudokuCreate(l_int32 *array)
sudokuCreate()
Definition: sudoku.c:303
static l_int32 sudokuTestState(l_int32 *state, l_int32 index)
sudokuTestState()
Definition: sudoku.c:483
l_int32 sudokuOutput(L_SUDOKU *sud, l_int32 arraytype)
sudokuOutput()
Definition: sudoku.c:838
l_ok sudokuTestUniqueness(l_int32 *array, l_int32 *punique)
sudokuTestUniqueness()
Definition: sudoku.c:554
l_int32 sudokuSolve(L_SUDOKU *sud)
sudokuSolve()
Definition: sudoku.c:367
l_ok genRandomIntOnInterval(l_int32 start, l_int32 end, l_int32 seed, l_int32 *pval)
genRandomIntOnInterval()
Definition: utils1.c:651
void lept_stderr(const char *fmt,...)
lept_stderr()
Definition: utils1.c:306
l_uint8 * l_binaryRead(const char *filename, size_t *pnbytes)
l_binaryRead()
Definition: utils2.c:1310