Leptonica  1.82.0
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  PROCNAME("sudokuReadFile");
197 
198  if (!filename)
199  return (l_int32 *)ERROR_PTR("filename not defined", procName, NULL);
200  data = l_binaryRead(filename, &size);
201  sa1 = sarrayCreateLinesFromString((char *)data, 0);
202  sa2 = sarrayCreate(9);
203 
204  /* Filter out the comment lines; verify that there are 9 data lines */
205  nlines = sarrayGetCount(sa1);
206  for (i = 0; i < nlines; i++) {
207  str = sarrayGetString(sa1, i, L_NOCOPY);
208  if (str[0] != '#')
209  sarrayAddString(sa2, str, L_COPY);
210  }
211  LEPT_FREE(data);
212  sarrayDestroy(&sa1);
213  nlines = sarrayGetCount(sa2);
214  if (nlines != 9) {
215  sarrayDestroy(&sa2);
216  L_ERROR("file has %d lines\n", procName, nlines);
217  return (l_int32 *)ERROR_PTR("invalid file", procName, NULL);
218  }
219 
220  /* Read the data into the array, verifying that each data
221  * line has 9 numbers. */
222  error = FALSE;
223  array = (l_int32 *)LEPT_CALLOC(81, sizeof(l_int32));
224  for (i = 0, index = 0; i < 9; i++) {
225  str = sarrayGetString(sa2, i, L_NOCOPY);
226  saline = sarrayCreateWordsFromString(str);
227  if (sarrayGetCount(saline) != 9) {
228  error = TRUE;
229  sarrayDestroy(&saline);
230  break;
231  }
232  for (j = 0; j < 9; j++) {
233  strj = sarrayGetString(saline, j, L_NOCOPY);
234  if (sscanf(strj, "%d", &val) != 1)
235  error = TRUE;
236  else
237  array[index++] = val;
238  }
239  sarrayDestroy(&saline);
240  if (error) break;
241  }
242  sarrayDestroy(&sa2);
243 
244  if (error) {
245  LEPT_FREE(array);
246  return (l_int32 *)ERROR_PTR("invalid data", procName, NULL);
247  }
248 
249  return array;
250 }
251 
252 
265 l_int32 *
266 sudokuReadString(const char *str)
267 {
268 l_int32 i;
269 l_int32 *array;
270 
271  PROCNAME("sudokuReadString");
272 
273  if (!str)
274  return (l_int32 *)ERROR_PTR("str not defined", procName, NULL);
275 
276  /* Read in the initial solution */
277  array = (l_int32 *)LEPT_CALLOC(81, sizeof(l_int32));
278  for (i = 0; i < 81; i++) {
279  if (sscanf(str + 2 * i, "%d ", &array[i]) != 1) {
280  LEPT_FREE(array);
281  return (l_int32 *)ERROR_PTR("invalid format", procName, NULL);
282  }
283  }
284 
285  return array;
286 }
287 
288 
289 /*---------------------------------------------------------------------*
290  * Create/destroy sudoku *
291  *---------------------------------------------------------------------*/
306 L_SUDOKU *
307 sudokuCreate(l_int32 *array)
308 {
309 l_int32 i, val, locs_index;
310 L_SUDOKU *sud;
311 
312  PROCNAME("sudokuCreate");
313 
314  if (!array)
315  return (L_SUDOKU *)ERROR_PTR("array not defined", procName, NULL);
316 
317  locs_index = 0; /* into locs array */
318  sud = (L_SUDOKU *)LEPT_CALLOC(1, sizeof(L_SUDOKU));
319  sud->locs = (l_int32 *)LEPT_CALLOC(81, sizeof(l_int32));
320  sud->init = (l_int32 *)LEPT_CALLOC(81, sizeof(l_int32));
321  sud->state = (l_int32 *)LEPT_CALLOC(81, sizeof(l_int32));
322  for (i = 0; i < 81; i++) {
323  val = array[i];
324  sud->init[i] = val;
325  sud->state[i] = val;
326  if (val == 0)
327  sud->locs[locs_index++] = i;
328  }
329  sud->num = locs_index;
330  sud->failure = FALSE;
331  sud->finished = FALSE;
332  return sud;
333 }
334 
335 
342 void
344 {
345 L_SUDOKU *sud;
346 
347  PROCNAME("sudokuDestroy");
348 
349  if (psud == NULL) {
350  L_WARNING("ptr address is NULL\n", procName);
351  return;
352  }
353  if ((sud = *psud) == NULL)
354  return;
355 
356  LEPT_FREE(sud->locs);
357  LEPT_FREE(sud->init);
358  LEPT_FREE(sud->state);
359  LEPT_FREE(sud);
360  *psud = NULL;
361 }
362 
363 
364 /*---------------------------------------------------------------------*
365  * Solve the puzzle *
366  *---------------------------------------------------------------------*/
374 l_int32
376 {
377  PROCNAME("sudokuSolve");
378 
379  if (!sud)
380  return ERROR_INT("sud not defined", procName, 0);
381 
382  if (!sudokuValidState(sud->init))
383  return ERROR_INT("initial state not valid", procName, 0);
384 
385  while (1) {
386  if (sudokuNewGuess(sud))
387  break;
388  if (sud->finished == TRUE)
389  break;
390  }
391 
392  if (sud->failure == TRUE) {
393  lept_stderr("Failure after %d guesses\n", sud->nguess);
394  return 0;
395  }
396 
397  lept_stderr("Solved after %d guesses\n", sud->nguess);
398  return 1;
399 }
400 
401 
415 static l_int32
416 sudokuValidState(l_int32 *state)
417 {
418 l_int32 i;
419 
420  PROCNAME("sudokuValidState");
421 
422  if (!state)
423  return ERROR_INT("state not defined", procName, 0);
424 
425  for (i = 0; i < 81; i++) {
426  if (!sudokuTestState(state, i))
427  return 0;
428  }
429 
430  return 1;
431 }
432 
433 
452 static l_int32
454 {
455 l_int32 index, val, valid;
456 l_int32 *locs, *state;
457 
458  locs = sud->locs;
459  state = sud->state;
460  index = locs[sud->current]; /* 0 to 80 */
461  val = state[index];
462  if (val == 9) { /* backtrack or give up */
463  if (sud->current == 0) {
464  sud->failure = TRUE;
465  return 1;
466  }
467  state[index] = 0;
468  sud->current--;
469  } else { /* increment current value and test */
470  sud->nguess++;
471  state[index]++;
472  valid = sudokuTestState(state, index);
473  if (valid) {
474  if (sud->current == sud->num - 1) { /* we're done */
475  sud->finished = TRUE;
476  return 0;
477  } else { /* advance to next position */
478  sud->current++;
479  }
480  }
481  }
482 
483  return 0;
484 }
485 
486 
494 static l_int32
495 sudokuTestState(l_int32 *state,
496  l_int32 index)
497 {
498 l_int32 i, j, val, row, rowstart, rowend, col;
499 l_int32 blockrow, blockcol, blockstart, rowindex, locindex;
500 
501  if ((val = state[index]) == 0) /* automatically valid */
502  return 1;
503 
504  /* Test row. Test val is at (x, y) = (index % 9, index / 9) */
505  row = index / 9;
506  rowstart = 9 * row;
507  for (i = rowstart; i < index; i++) {
508  if (state[i] == val)
509  return 0;
510  }
511  rowend = rowstart + 9;
512  for (i = index + 1; i < rowend; i++) {
513  if (state[i] == val)
514  return 0;
515  }
516 
517  /* Test column */
518  col = index % 9;
519  for (j = col; j < index; j += 9) {
520  if (state[j] == val)
521  return 0;
522  }
523  for (j = index + 9; j < 81; j += 9) {
524  if (state[j] == val)
525  return 0;
526  }
527 
528  /* Test local 3x3 block */
529  blockrow = 3 * (row / 3);
530  blockcol = 3 * (col / 3);
531  blockstart = 9 * blockrow + blockcol;
532  for (i = 0; i < 3; i++) {
533  rowindex = blockstart + 9 * i;
534  for (j = 0; j < 3; j++) {
535  locindex = rowindex + j;
536  if (index == locindex) continue;
537  if (state[locindex] == val)
538  return 0;
539  }
540  }
541 
542  return 1;
543 }
544 
545 
546 /*---------------------------------------------------------------------*
547  * Test for uniqueness *
548  *---------------------------------------------------------------------*/
565 l_ok
566 sudokuTestUniqueness(l_int32 *array,
567  l_int32 *punique)
568 {
569 l_int32 same1, same2, same3;
570 l_int32 *array1, *array2, *array3;
571 L_SUDOKU *sud, *sud1, *sud2, *sud3;
572 
573  PROCNAME("sudokuTestUniqueness");
574 
575  if (!punique)
576  return ERROR_INT("&unique not defined", procName, 1);
577  *punique = 0;
578  if (!array)
579  return ERROR_INT("array not defined", procName, 1);
580 
581  sud = sudokuCreate(array);
582  sudokuSolve(sud);
583  array1 = sudokuRotateArray(array, 1);
584  sud1 = sudokuCreate(array1);
585  sudokuSolve(sud1);
586  array2 = sudokuRotateArray(array, 2);
587  sud2 = sudokuCreate(array2);
588  sudokuSolve(sud2);
589  array3 = sudokuRotateArray(array, 3);
590  sud3 = sudokuCreate(array3);
591  sudokuSolve(sud3);
592 
593  sudokuCompareState(sud, sud1, 1, &same1);
594  sudokuCompareState(sud, sud2, 2, &same2);
595  sudokuCompareState(sud, sud3, 3, &same3);
596  *punique = (same1 && same2 && same3);
597 
598  sudokuDestroy(&sud);
599  sudokuDestroy(&sud1);
600  sudokuDestroy(&sud2);
601  sudokuDestroy(&sud3);
602  LEPT_FREE(array1);
603  LEPT_FREE(array2);
604  LEPT_FREE(array3);
605  return 0;
606 }
607 
608 
626 static l_int32
628  L_SUDOKU *sud2,
629  l_int32 quads,
630  l_int32 *psame)
631 {
632 l_int32 i, same;
633 l_int32 *array;
634 
635  PROCNAME("sudokuCompareState");
636 
637  if (!psame)
638  return ERROR_INT("&same not defined", procName, 1);
639  *psame = 0;
640  if (!sud1)
641  return ERROR_INT("sud1 not defined", procName, 1);
642  if (!sud2)
643  return ERROR_INT("sud1 not defined", procName, 1);
644  if (quads < 1 || quads > 3)
645  return ERROR_INT("valid quads in {1,2,3}", procName, 1);
646 
647  same = TRUE;
648  if ((array = sudokuRotateArray(sud1->state, quads)) == NULL)
649  return ERROR_INT("array not made", procName, 1);
650  for (i = 0; i < 81; i++) {
651  if (array[i] != sud2->state[i]) {
652  same = FALSE;
653  break;
654  }
655  }
656  *psame = same;
657  LEPT_FREE(array);
658  return 0;
659 }
660 
661 
669 static l_int32 *
670 sudokuRotateArray(l_int32 *array,
671  l_int32 quads)
672 {
673 l_int32 i, j, sindex, dindex;
674 l_int32 *rarray;
675 
676  PROCNAME("sudokuRotateArray");
677 
678  if (!array)
679  return (l_int32 *)ERROR_PTR("array not defined", procName, NULL);
680  if (quads < 1 || quads > 3)
681  return (l_int32 *)ERROR_PTR("valid quads in {1,2,3}", procName, NULL);
682 
683  rarray = (l_int32 *)LEPT_CALLOC(81, sizeof(l_int32));
684  if (quads == 1) {
685  for (j = 0, dindex = 0; j < 9; j++) {
686  for (i = 8; i >= 0; i--) {
687  sindex = 9 * i + j;
688  rarray[dindex++] = array[sindex];
689  }
690  }
691  } else if (quads == 2) {
692  for (i = 8, dindex = 0; i >= 0; i--) {
693  for (j = 8; j >= 0; j--) {
694  sindex = 9 * i + j;
695  rarray[dindex++] = array[sindex];
696  }
697  }
698  } else { /* quads == 3 */
699  for (j = 8, dindex = 0; j >= 0; j--) {
700  for (i = 0; i < 9; i++) {
701  sindex = 9 * i + j;
702  rarray[dindex++] = array[sindex];
703  }
704  }
705  }
706 
707  return rarray;
708 }
709 
710 
711 /*---------------------------------------------------------------------*
712  * Generation *
713  *---------------------------------------------------------------------*/
734 L_SUDOKU *
735 sudokuGenerate(l_int32 *array,
736  l_int32 seed,
737  l_int32 minelems,
738  l_int32 maxtries)
739 {
740 l_int32 index, sector, nzeros, removefirst, tries, val, oldval, unique;
741 L_SUDOKU *sud, *testsud;
742 
743  PROCNAME("sudokuGenerate");
744 
745  if (!array)
746  return (L_SUDOKU *)ERROR_PTR("array not defined", procName, NULL);
747  if (minelems > 80)
748  return (L_SUDOKU *)ERROR_PTR("minelems must be < 81", procName, NULL);
749 
750  /* Remove up to 30 numbers at random from the solution.
751  * Test if the solution is valid -- the initial 'solution' may
752  * have been invalid. Then test if the sudoku with 30 zeroes
753  * is unique -- it almost always will be. */
754  srand(seed);
755  nzeros = 0;
756  sector = 0;
757  removefirst = L_MIN(30, 81 - minelems);
758  while (nzeros < removefirst) {
759  genRandomIntOnInterval(0, 8, 0, &val);
760  index = 27 * (sector / 3) + 3 * (sector % 3) +
761  9 * (val / 3) + (val % 3);
762  if (array[index] == 0) continue;
763  array[index] = 0;
764  nzeros++;
765  sector++;
766  sector %= 9;
767  }
768  testsud = sudokuCreate(array);
769  sudokuSolve(testsud);
770  if (testsud->failure) {
771  sudokuDestroy(&testsud);
772  L_ERROR("invalid initial solution\n", procName);
773  return NULL;
774  }
775  sudokuTestUniqueness(testsud->init, &unique);
776  sudokuDestroy(&testsud);
777  if (!unique) {
778  L_ERROR("non-unique result with 30 zeroes\n", procName);
779  return NULL;
780  }
781 
782  /* Remove more numbers, testing at each removal for uniqueness. */
783  tries = 0;
784  sector = 0;
785  while (1) {
786  if (tries > maxtries) break;
787  if (81 - nzeros <= minelems) break;
788 
789  if (tries == 0) {
790  lept_stderr("Trying %d zeros\n", nzeros);
791  tries = 1;
792  }
793 
794  /* Choose an element to be zeroed. We choose one
795  * at random in succession from each of the nine sectors. */
796  genRandomIntOnInterval(0, 8, 0, &val);
797  index = 27 * (sector / 3) + 3 * (sector % 3) +
798  9 * (val / 3) + (val % 3);
799  sector++;
800  sector %= 9;
801  if (array[index] == 0) continue;
802 
803  /* Save the old value in case we need to revert */
804  oldval = array[index];
805 
806  /* Is there a solution? If not, try again. */
807  array[index] = 0;
808  testsud = sudokuCreate(array);
809  sudokuSolve(testsud);
810  if (testsud->failure == TRUE) {
811  sudokuDestroy(&testsud);
812  array[index] = oldval; /* revert */
813  tries++;
814  continue;
815  }
816 
817  /* Is the solution unique? If not, try again. */
818  sudokuTestUniqueness(testsud->init, &unique);
819  sudokuDestroy(&testsud);
820  if (!unique) { /* revert and try again */
821  array[index] = oldval;
822  tries++;
823  } else { /* accept this */
824  tries = 0;
825  lept_stderr("Have %d zeros\n", nzeros);
826  nzeros++;
827  }
828  }
829  lept_stderr("Final: nelems = %d\n", 81 - nzeros);
830 
831  /* Show that we can recover the solution */
832  sud = sudokuCreate(array);
833  sudokuOutput(sud, L_SUDOKU_INIT);
834  sudokuSolve(sud);
835  sudokuOutput(sud, L_SUDOKU_STATE);
836 
837  return sud;
838 }
839 
840 
841 /*---------------------------------------------------------------------*
842  * Output *
843  *---------------------------------------------------------------------*/
857 l_int32
859  l_int32 arraytype)
860 {
861 l_int32 i, j;
862 l_int32 *array;
863 
864  PROCNAME("sudokuOutput");
865 
866  if (!sud)
867  return ERROR_INT("sud not defined", procName, 1);
868  if (arraytype == L_SUDOKU_INIT)
869  array = sud->init;
870  else if (arraytype == L_SUDOKU_STATE)
871  array = sud->state;
872  else
873  return ERROR_INT("invalid arraytype", procName, 1);
874 
875  for (i = 0; i < 9; i++) {
876  for (j = 0; j < 9; j++)
877  lept_stderr("%d ", array[9 * i + j]);
878  lept_stderr("\n");
879  }
880  return 0;
881 }
@ L_COPY
Definition: pix.h:712
@ L_NOCOPY
Definition: pix.h:710
SARRAY * sarrayCreate(l_int32 n)
sarrayCreate()
Definition: sarray1.c:170
char * sarrayGetString(SARRAY *sa, l_int32 index, l_int32 copyflag)
sarrayGetString()
Definition: sarray1.c:703
l_int32 sarrayGetCount(SARRAY *sa)
sarrayGetCount()
Definition: sarray1.c:643
void sarrayDestroy(SARRAY **psa)
sarrayDestroy()
Definition: sarray1.c:362
SARRAY * sarrayCreateWordsFromString(const char *string)
sarrayCreateWordsFromString()
Definition: sarray1.c:233
SARRAY * sarrayCreateLinesFromString(const char *string, l_int32 blankflag)
sarrayCreateLinesFromString()
Definition: sarray1.c:283
l_ok sarrayAddString(SARRAY *sa, const char *string, l_int32 copyflag)
sarrayAddString()
Definition: sarray1.c:451
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
Definition: array.h:127
l_int32 * sudokuReadFile(const char *filename)
sudokuReadFile()
Definition: sudoku.c:187
static l_int32 sudokuNewGuess(L_SUDOKU *sud)
sudokuNewGuess()
Definition: sudoku.c:453
static l_int32 sudokuValidState(l_int32 *state)
sudokuValidState()
Definition: sudoku.c:416
l_int32 * sudokuReadString(const char *str)
sudokuReadString()
Definition: sudoku.c:266
L_SUDOKU * sudokuGenerate(l_int32 *array, l_int32 seed, l_int32 minelems, l_int32 maxtries)
sudokuGenerate()
Definition: sudoku.c:735
static l_int32 * sudokuRotateArray(l_int32 *array, l_int32 quads)
sudokuRotateArray()
Definition: sudoku.c:670
static l_int32 sudokuCompareState(L_SUDOKU *sud1, L_SUDOKU *sud2, l_int32 quads, l_int32 *psame)
sudokuCompareState()
Definition: sudoku.c:627
void sudokuDestroy(L_SUDOKU **psud)
sudokuDestroy()
Definition: sudoku.c:343
L_SUDOKU * sudokuCreate(l_int32 *array)
sudokuCreate()
Definition: sudoku.c:307
static l_int32 sudokuTestState(l_int32 *state, l_int32 index)
sudokuTestState()
Definition: sudoku.c:495
l_int32 sudokuOutput(L_SUDOKU *sud, l_int32 arraytype)
sudokuOutput()
Definition: sudoku.c:858
l_ok sudokuTestUniqueness(l_int32 *array, l_int32 *punique)
sudokuTestUniqueness()
Definition: sudoku.c:566
l_int32 sudokuSolve(L_SUDOKU *sud)
sudokuSolve()
Definition: sudoku.c:375
l_ok genRandomIntOnInterval(l_int32 start, l_int32 end, l_int32 seed, l_int32 *pval)
genRandomIntOnInterval()
Definition: utils1.c:659
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:1352