Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/leptonica/src/sudoku.c @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
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
28 /*!
29 * \file sudoku.c
30 * <pre>
31 *
32 * Solve a sudoku by brute force search
33 *
34 * Read input data from file or string
35 * l_int32 *sudokuReadFile()
36 * l_int32 *sudokuReadString()
37 *
38 * Create/destroy
39 * L_SUDOKU *sudokuCreate()
40 * void sudokuDestroy()
41 *
42 * Solve the puzzle
43 * l_int32 sudokuSolve()
44 * static l_int32 sudokuValidState()
45 * static l_int32 sudokuNewGuess()
46 * static l_int32 sudokuTestState()
47 *
48 * Test for uniqueness
49 * l_int32 sudokuTestUniqueness()
50 * static l_int32 sudokuCompareState()
51 * static l_int32 *sudokuRotateArray()
52 *
53 * Generation
54 * L_SUDOKU *sudokuGenerate()
55 *
56 * Output
57 * l_int32 sudokuOutput()
58 *
59 * Solving sudokus is a somewhat addictive pastime. The rules are
60 * simple but it takes just enough concentration to make it rewarding
61 * when you find a number. And you get 50 to 60 such rewards each time
62 * you complete one. The downside is that you could have been doing
63 * something more creative, like keying out a new plant, staining
64 * the deck, or even writing a computer program to discourage your
65 * wife from doing sudokus.
66 *
67 * My original plan for the sudoku solver was somewhat grandiose.
68 * The program would model the way a person solves the problem.
69 * It would examine each empty position and determine how many possible
70 * numbers could fit. The empty positions would be entered in a priority
71 * queue keyed on the number of possible numbers that could fit.
72 * If there existed a position where only a single number would work,
73 * it would greedily take it. Otherwise it would consider a
74 * positions that could accept two and make a guess, with backtracking
75 * if an impossible state were reached. And so on.
76 *
77 * Then one of my colleagues announced she had solved the problem
78 * by brute force and it was fast. At that point the original plan was
79 * dead in the water, because the two top requirements for a leptonica
80 * algorithm are (1) as simple as possible and (2) fast. The brute
81 * force approach starts at the UL corner, and in succession at each
82 * blank position it finds the first valid number (testing in
83 * sequence from 1 to 9). When no number will fit a blank position
84 * it backtracks, choosing the next valid number in the previous
85 * blank position.
86 *
87 * This is an inefficient method for pruning the space of solutions
88 * (imagine backtracking from the LR corner back to the UL corner
89 * and starting over with a new guess), but it nevertheless gets
90 * the job done quickly. I have made no effort to optimize
91 * it, because it is fast: a 5-star (highest difficulty) sudoku might
92 * require a million guesses and take 0.05 sec. (This BF implementation
93 * does about 20M guesses/sec at 3 GHz.)
94 *
95 * Proving uniqueness of a sudoku solution is tricker than finding
96 * a solution (or showing that no solution exists). A good indication
97 * that a solution is unique is if we get the same result solving
98 * by brute force when the puzzle is also rotated by 90, 180 and 270
99 * degrees. If there are multiple solutions, it seems unlikely
100 * that you would get the same solution four times in a row, using a
101 * brute force method that increments guesses and scans LR/TB.
102 * The function sudokuTestUniqueness() does this.
103 *
104 * And given a function that can determine uniqueness, it is
105 * easy to generate valid sudokus. We provide sudokuGenerate(),
106 * which starts with some valid initial solution, and randomly
107 * removes numbers, stopping either when a minimum number of non-zero
108 * elements are left, or when it becomes difficult to remove another
109 * element without destroying the uniqueness of the solution.
110 *
111 * For further reading, see the Wikipedia articles:
112 * (1) http://en.wikipedia.org/wiki/Algorithmics_of_sudoku
113 * (2) http://en.wikipedia.org/wiki/Sudoku
114 *
115 * How many 9x9 sudokus are there? Here are the numbers.
116 * ~ From ref(1), there are about 6 x 10^27 "latin squares", where
117 * each row and column has all 9 digits.
118 * ~ There are 7.2 x 10^21 actual solutions, having the added
119 * constraint in each of the 9 3x3 squares. (The constraint
120 * reduced the number by the fraction 1.2 x 10^(-6).)
121 * ~ There are a mere 5.5 billion essentially different solutions (EDS),
122 * when symmetries (rotation, reflection, permutation and relabelling)
123 * are removed.
124 * ~ Thus there are 1.3 x 10^12 solutions that can be derived by
125 * symmetry from each EDS. Can we account for these?
126 * ~ Sort-of. From an EDS, you can derive (3!)^8 = 1.7 million solutions
127 * by simply permuting rows and columns. (Do you see why it is
128 * not (3!)^6 ?)
129 * ~ Also from an EDS, you can derive 9! solutions by relabelling,
130 * and 4 solutions by rotation, for a total of 1.45 million solutions
131 * by relabelling and rotation. Then taking the product, by symmetry
132 * we can derive 1.7M x 1.45M = 2.45 trillion solutions from each EDS.
133 * (Something is off by about a factor of 2 -- close enough.)
134 *
135 * Another interesting fact is that there are apparently 48K EDS sudokus
136 * (with unique solutions) that have only 17 givens. No sudokus are known
137 * with less than 17, but there exists no proof that this is the minimum.
138 * </pre>
139 */
140
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 *---------------------------------------------------------------------*/
172 /*!
173 * \brief sudokuReadFile()
174 *
175 * \param[in] filename formatted sudoku file
176 * \return array of 81 numbers, or NULL on error
177 *
178 * <pre>
179 * Notes:
180 * (1) The file format has:
181 * * any number of comment lines beginning with '#'
182 * * a set of 9 lines, each having 9 digits (0-9) separated
183 * by a space
184 * </pre>
185 */
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
251 /*!
252 * \brief sudokuReadString()
253 *
254 * \param[in] str formatted input data
255 * \return array of 81 numbers, or NULL on error
256 *
257 * <pre>
258 * Notes:
259 * (1) The string is formatted as 81 single digits, each separated
260 * by 81 spaces.
261 * </pre>
262 */
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 *---------------------------------------------------------------------*/
288 /*!
289 * \brief sudokuCreate()
290 *
291 * \param[in] array 81 numbers, 9 rows of 9 numbers each
292 * \return l_sudoku, or NULL on error
293 *
294 * <pre>
295 * Notes:
296 * (1) The input array has 0 for the unknown values, and 1-9
297 * for the known initial values. It is generated from
298 * a file using sudokuReadInput(), which checks that the file
299 * data has 81 numbers in 9 rows.
300 * </pre>
301 */
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
330 /*!
331 * \brief sudokuDestroy()
332 *
333 * \param[in,out] psud will be set to null before returning
334 * \return void
335 */
336 void
337 sudokuDestroy(L_SUDOKU **psud)
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 *---------------------------------------------------------------------*/
359 /*!
360 * \brief sudokuSolve()
361 *
362 * \param[in] sud l_sudoku starting in initial state
363 * \return 1 on success, 0 on failure to solve note reversal of
364 * typical unix returns
365 */
366 l_int32
367 sudokuSolve(L_SUDOKU *sud)
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
392 /*!
393 * \brief sudokuValidState()
394 *
395 * \param[in] state array of size 81
396 * \return 1 if valid, 0 if invalid
397 *
398 * <pre>
399 * Notes:
400 * (1) This can be used on either the initial state (init)
401 * or on the current state (state) of the l_soduku.
402 * All values of 0 are ignored.
403 * </pre>
404 */
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
422 /*!
423 * \brief sudokuNewGuess()
424 *
425 * \param[in] sud l_sudoku
426 * \return 0 if OK; 1 if no solution is possible
427 *
428 * <pre>
429 * Notes:
430 * (1) This attempts to increment the number in the current
431 * location. If it can't, it backtracks (sets the number
432 * in the current location to zero and decrements the
433 * current location). If it can, it tests that number,
434 * and if the number is valid, moves forward to the next
435 * empty location (increments the current location).
436 * (2) If there is no solution, backtracking will eventually
437 * exhaust possibilities for the first location.
438 * </pre>
439 */
440 static l_int32
441 sudokuNewGuess(L_SUDOKU *sud)
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
475 /*!
476 * \brief sudokuTestState()
477 *
478 * \param[in] state current state: array of 81 values
479 * \param[in] index into state element that we are testing
480 * \return 1 if valid; 0 if invalid no error checking
481 */
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 *---------------------------------------------------------------------*/
537 /*!
538 * \brief sudokuTestUniqueness()
539 *
540 * \param[in] array of 81 numbers, 9 lines of 9 numbers each
541 * \param[out] punique 1 if unique, 0 if not
542 * \return 0 if OK, 1 on error
543 *
544 * <pre>
545 * Notes:
546 * (1) This applies the brute force method to all four 90 degree
547 * rotations. If there is more than one solution, it is highly
548 * unlikely that all four results will be the same;
549 * consequently, if they are the same, the solution is
550 * most likely to be unique.
551 * </pre>
552 */
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
595 /*!
596 * \brief sudokuCompareState()
597 *
598 * \param[in] sud1, sud2 two l_Sudoku states (solutions)
599 * \param[in] quads rotation of sud2 input with respect to sud1,
600 * in units of 90 degrees cw
601 * \param[out] psame 1 if all 4 results are identical; 0 otherwise
602 * \return 0 if OK, 1 on error
603 *
604 * <pre>
605 * Notes:
606 * (1) The input to sud2 has been rotated by %quads relative to the
607 * input to sud1. Therefore, we must rotate the solution to
608 * sud1 by the same amount before comparing it to the
609 * solution to sud2.
610 * </pre>
611 */
612 static l_int32
613 sudokuCompareState(L_SUDOKU *sud1,
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
646 /*!
647 * \brief sudokuRotateArray()
648 *
649 * \param[in] array 81 numbers; 9 lines of 9 numbers each
650 * \param[in] quads 1-3; number of 90 degree cw rotations
651 * \return rarray rotated array, or NULL on error
652 */
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 *---------------------------------------------------------------------*/
696 /*!
697 * \brief sudokuGenerate()
698 *
699 * \param[in] array 81 numbers, 9 rows of 9 numbers each
700 * \param[in] seed random number
701 * \param[in] minelems min non-zero elements allowed; <= 80
702 * \param[in] maxtries max tries to remove a number and get a valid sudoku
703 * \return l_sudoku, or NULL on error
704 *
705 * <pre>
706 * Notes:
707 * (1) This is a brute force generator. It starts with a completed
708 * sudoku solution and, by removing elements (setting them to 0),
709 * generates a valid (unique) sudoku initial condition.
710 * (2) The process stops when either %minelems, the minimum
711 * number of non-zero elements, is reached, or when the
712 * number of attempts to remove the next element exceeds %maxtries.
713 * (3) No sudoku is known with less than 17 nonzero elements.
714 * </pre>
715 */
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 *---------------------------------------------------------------------*/
824 /*!
825 * \brief sudokuOutput()
826 *
827 * \param[in] sud l_sudoku at any stage
828 * \param[in] arraytype L_SUDOKU_INIT, L_SUDOKU_STATE
829 * \return 0 if OK; 1 on error
830 *
831 * <pre>
832 * Notes:
833 * (1) Prints either the initial array or the current state
834 * of the solution.
835 * </pre>
836 */
837 l_int32
838 sudokuOutput(L_SUDOKU *sud,
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 }