source: liacs/ai/sudoku/latex/sudoku.tex@ 212

Last change on this file since 212 was 2, checked in by Rick van der Zwet, 15 years ago

Initial import of data of old repository ('data') worth keeping (e.g. tracking
means of URL access statistics)
File size: 38.1 KB
RevLine 
[2]1%
2% verslag.tex 9.2.2006
3% Sudoku verslag
4%
5
6\documentclass[12pt]{article}
7
8\frenchspacing
9\usepackage[english]{babel}
10\selectlanguage{english}
11\usepackage{graphicx}
12\usepackage{wrapfig}
13
14\author{Rick van der Zwet, Leiden University \\ Leiden Institute of Advanced Computer Science}
15\title{Creating and solving sudoku's}
16
17\begin{document}
18\maketitle
19\section{Introduction}
20\subsection{History}
21\begin{quote}
22The name Sudoku is the Japanese abbreviation of a longer phrase, ''suuji wa dokushin ni kagiru'' meaning ''the digits must remain single''; it is a trademark of puzzle publisher Nikoli Co. Ltd in Japan.
23
24The numerals in Sudoku puzzles are used for convenience; arithmetic relationships between numerals are absolutely irrelevant. Any set of distinct symbols will do; letters, shapes, or colours may be used without altering the rules (Penny Press' Scramblets and Knight Features Syndicate's Sudoku Word both use letters). Dell Magazines, the puzzle's originator, has been using numerals for Number Place in its magazines since they first published it in 1979. Numerals are used throughout this article.
25
26The attraction of the puzzle is that the completion rules are simple, yet the line of reasoning required to reach the completion may be complex. Sudoku is recommended by some teachers as an exercise in logical reasoning. The level of difficulty of the puzzles can be selected to suit the audience. The puzzles are often available free from published sources and also may be custom-generated using software.\cite{wikipedia}
27\end{quote}
28
29\newpage
30\subsection{Gameplay}
31\begin{wrapfigure}{r}{50mm}
32 \includegraphics[scale=0.5]{sudoku.eps}
33 \caption{Sample sudoku}
34\end{wrapfigure}
35The puzzle is most frequently a 9×9 grid, made up of 3×3 subgrids called ''regions'' (other terms include ''boxes'', ''blocks'', and the like when referring to the standard variation; even ''quadrant'' is sometimes used, despite this being an inaccurate term for a 9×9 grid). Some cells already contain numerals, known as ''givens'' (or sometimes as ''clues''). The goal is to fill in the empty cells, one numeral in each, so that each column, row, and region contains the numerals 1–9 exactly once. Each numeral in the solution therefore occurs only once in each of three ''directions'' or ''scopes'', hence the ''single numbers'' implied by the puzzle's name.\cite{wikipedia}
36
37\section{Problem}
38
39Not every combination of a board, is going to be succesfull and there is no algoritm who can predict whether a generated board is valid without completely solving the puzzle. So there has to be some other way to generate valid puzzles. First, there need to be a perfect solver writtento test whether a puzzle has got only one solution.
40The second way to generate a valid puzzle is by creating a completely solved valid puzzle and delete a ew spots, by checking if the puzzle still has got 1 unique solution. We are able to generate soduku's too.
41
42\newpage
43\section{Solution finding theories}
44
45There are currently 3 solutions know (by me) about solving the soduku somehow.
46
47\subsection{Marking up}
48By deleting the non-available spots at every location, the remaining possibilities will become clear, you will notice at certain points only one option will be left, so this will be the number to be filled in. As can be showed by figure \ref{marking_up}.
49
50\begin{figure}[!ht]
51\begin{center}
52 \includegraphics{marking_up.eps}
53\end{center}
54 \caption{Candidates for each empty cell have been entered. Some cells have only one candidate once obvious invalids have been excluded. Also, some mark with dots instead of numbers, simply using the position of the dot within the cell to distinguish them.\cite{wikipedia}}
55 \label{marking_up}
56\end{figure}
57
58
59\newpage
60\subsection{Scanning}
61Scanning will be a easy solution too to be used by humans, computers however need slight more code to accomplish the same result. With scanning you can "force" certain numbers into their spot. See figure \ref{scanning} for a example.
62
63\begin{figure}[!ht]
64 \begin{center}
65 \includegraphics{scanning.eps}
66 \end{center}
67 \caption{The 3×3 region in the top-left corner. The solver can eliminate all of the empty cells in the top-right corner which cannot contain a 5. This leaves only one possible cell (highlighted in green).\cite{wikipedia}}
68 \label{scanning}
69\end{figure}
70
71\newpage
72\subsection{Analysis}
73Analysis will be even more complex. It can consist many methods to logically gain a solution. There is one pointed out (and implemented). Let's pretend we have a row in which are 3 spot's still to be filled.
74
75Options to spot A: 1, 2 ,3
76Options to spot B: 2, 3
77Options to spot C: 2, 3
78
79B and C together will use number 2 and 3, so A has to be 1. It's just an other ''simple solution'', but implementing it it's a bit hard.
80\begin{figure}[!ht]
81 \begin{center}
82 \includegraphics{cplusplus.eps}
83 \end{center}
84 \label{cplusplus}
85\end{figure}
86
87\section{Implementation}
88
89The solver and create program are both written in C$\stackrel{++}{}$. It uses a 2d array to impement the sudoku board and a 3d array to implement the current available choices at the board.
90
91\newpage
92\section{Creating soduku's}
93
94There are 3 main ways to create sudoku's
95\begin{enumerate}
96\item Randomizing stupid, just push for example 17 random numbers inside the sudoku and hope none of them will interference.
97\item Randoming smart, push for example 17 random numbers inside the sudoku and be sure none of them will be a violation of the structure.
98\item ''Cleaning'' first generate a complete sudoku. Then get your wiper\/cleaner and delete some numbers. This solution is a bit difficult and will use a lot of math to generate a full puzzle and you are not sure if the puzzle has got only one solution.
99\end{enumerate}
100
101\section{Experiments}
102
103\subsection{Solver}
104First we will test the solver. The website of G.~Royle\cite{gordon} has got plenty solveble 17 sudoku's. A few of them are placed at Appendix C. There is a small shell script written (Appendix B) to test the result. By trying to solve 1000 puzzles, the program managed to complete 547, the other puzzles requires some more logic implemented to solve them.
105
106
107\subsection{Generator}
108The generator will generate of puzzle of class 2 (Random and not very stupid), the solver will try to fix this puzzle. No checks for unique solutions will be made. Table below will point out the results by running the test 10000 times.
109
110\begin{center}
111\begin{tabular}{l|l|l}
112Percent sudoku filled initially & Solutions found 1st round & Solutions found 2nd round\\
113\hline
11410\% &0 &0\\
11520\% &0 &0\\
11630\% &160 &0\\
11740\% &0 &0\\
11850\% &0 &0\\
119\end{tabular}
120\end{center}
121
122
123\section{Conclusion}
124
125The solver ain't good enough yet, he should fix every puzzle and not 50\%, need to program some aditional logic. The creator isn't very good either, only 30\% will generate some solveble puzzles, It properly have something to do with the very bad random generator, the random seed if filled with the unix time in which in 100 occured process will be the same. The creator needs method 3 to be implemented to validate this assumption or a rewrite of the code.
126
127\begin{thebibliography}{1}
128\bibitem{wikipedia}
129Wikipedia Foundation Inc,
130http://en.wikipedia.org/wiki/Sudoku
131\bibitem{gordon}
132G.~Royle, Minimum Sudoku
133http://www.csse.uwa.edu.au/\~{}gordon/sudokumin.php
134\end{thebibliography}
135
136\newpage
137\section*{Appendix A: sudoku.cpp}
138The following C$\stackrel{++}{}$ has been used to solve the puzzles
139
140\begin{small}
141\begin{verbatim}
142
143/* file: sudoku.c
144 * author: rick van der Zwet 0433373, 2006
145 * University Leiden, LIACS
146 */
147
148#include <stdio.h>
149#include <stdlib.h>
150#include <string.h>
151#include <time.h>
152#include <signal.h>
153
154#define MAX_XYZ 9
155#define EMPTY_SPOT '_'
156
157
158#define bold "[1m"
159#define normal "[0m"
160
161#define DEBUGPLACE stderr
162const char esc = 27; /* escape character */
163
164
165int debug(const int level = 0)
166{
167#if DEBUG
168 if (level <= DEBUG)
169 {
170 return(1);
171 }
172 else
173 {
174 return(0);
175 }
176#else
177 return(0);
178#endif
179}
180
181class Sudoku {
182 public:
183 Sudoku();
184 void printNice(const int boldRow = -1, const int boldCol = -1, const char emptcolSpace = EMPTY_SPOT);
185 void printRaw();
186 void printPossible();
187 void printPossibleAtNumber(const int row, const int col);
188 void reset();
189 int randomNumbers(const double chance);
190 int fromFile(FILE *handle);
191 int insert(const int row, const int col, const int number);
192 int solutionFinder();
193 private:
194 int _sudoku[MAX_XYZ][MAX_XYZ];
195 bool _possible[MAX_XYZ][MAX_XYZ][MAX_XYZ];
196 int _numbersFilled;
197 void _updatePossibleList(const int row, const int col, const int number);
198 bool _solution1(int &row, int &col, int &number);
199 bool _solution2(int &row, int &col, int &number);
200 bool _solution3a(int &row, int &col, int &number);
201 bool _solution3b(int &row, int &col, int &number);
202};
203
204Sudoku::Sudoku()
205{
206 reset();
207}
208
209
210void Sudoku::printRaw()
211{
212 int row,col;
213 for (row = 0; row < MAX_XYZ ; row++)
214 {
215 for (col = 0; col < MAX_XYZ; col++)
216 {
217 printf("%i ", _sudoku[row][col]);
218 }
219 printf("\n");
220 }
221}
222void Sudoku::printNice(const int boldRow, const int boldCol,
223 const char emptcolSpace)
224{
225 int row,col;
226 int tmpRow;
227 const int maxRow = (MAX_XYZ + (MAX_XYZ / 3)) * 2 + 1;
228 for(tmpRow = 0; tmpRow < maxRow; tmpRow++)
229 {
230 if ((tmpRow%8) == 0) { printf("+"); }else {printf("-");}
231 }
232 printf("\n");
233 for (row = 0; row < MAX_XYZ ; row++)
234 {
235 printf("| ");
236 for (col = 0; col < MAX_XYZ; col++)
237 {
238 if ( _sudoku[row][col] == 0)
239 {
240 printf("%c ",emptcolSpace);
241 }
242 else
243 {
244 if (row == boldRow && col == boldCol)
245 {
246 printf("%c%s%i%c%s ",esc, bold, _sudoku[row][col],
247 esc, normal);
248 }
249 else
250 {
251 printf("%i ", _sudoku[row][col]);
252 }
253 }
254 if ( ((col - 2) % 3) == 0 )
255 {
256 printf("| ");
257 }
258 }
259 printf("\n");
260 if ( ((row - 2) % 3) == 0 )
261 {
262 for(tmpRow = 0; tmpRow < maxRow; tmpRow++)
263 {
264 if ((tmpRow%8) == 0)
265 {
266 printf("+");
267 }
268 else
269 {
270 printf("-");
271 }
272 }
273 printf("\n");
274 }
275 }
276 printf("\n\n");
277}
278
279void Sudoku::printPossibleAtNumber(const int row, const int col)
280{
281 if (debug(3))
282 {
283 int tmpPossible;
284 fprintf(DEBUGPLACE, "Possible at [%i,%i]: ", row, col);
285 for (tmpPossible = 0; tmpPossible < MAX_XYZ; tmpPossible++)
286 {
287 if (_possible[row][col][tmpPossible] == true)
288 {
289 fprintf(DEBUGPLACE,"%i ", tmpPossible + 1);
290 }
291 }
292 fprintf(DEBUGPLACE, "\n");
293 }
294}
295
296void Sudoku::printPossible()
297{
298 int row,col;
299 if (debug(3))
300 {
301 for (row = 0; row < MAX_XYZ ; row++)
302 {
303 for (col = 0; col < MAX_XYZ; col++)
304 {
305 if(_sudoku[row][col] == 0)
306 {
307 printPossibleAtNumber(row,col);
308 }
309 }
310 }
311 }
312}
313
314
315void Sudoku::_updatePossibleList(const int row, const int col, const int number)
316{
317 int tmpRow;
318 int tmpCol;
319 int blockRow;
320 int blockCol;
321 int c;
322
323
324 /* Row and Col and Number own */
325 for (c = 0; c < MAX_XYZ; c++)
326 {
327 _possible[row][col][c] = false;
328 _possible[row][c][number - 1] = false;
329 _possible[c][col][number - 1] = false;
330 }
331
332 /* Block */
333 tmpRow = row - (row % (MAX_XYZ / 3));
334 tmpCol = col - (col % (MAX_XYZ / 3));
335 for (blockRow = tmpRow; blockRow < (tmpRow + 3); blockRow++)
336 {
337 for (blockCol = tmpCol; blockCol < (tmpCol + 3); blockCol++)
338 {
339 _possible[blockRow][blockCol][number - 1] = false;
340 }
341 }
342}
343
344int Sudoku::insert(const int row, const int col, const int number)
345{
346 if (debug(1)) { fprintf(DEBUGPLACE, "Will insert %i at [%i,%i]: %i\n",
347 number, row, col, _possible[row][col][number - 1]); }
348
349 if (_possible[row][col][number - 1] == true)
350 {
351 _updatePossibleList(row, col, number);
352 _sudoku[row][col] = number;
353 _numbersFilled++;
354 return(0);
355 }
356 else
357 {
358 return(1);
359 }
360}
361
362int Sudoku::randomNumbers(const double chance)
363{
364 if (debug(1)) { fprintf(DEBUGPLACE, "Running createsudoku\n"); }
365 int row;
366 int col;
367 int c;
368 int randomnumber;
369 int numberdone[MAX_XYZ];
370 int numbertried;
371
372 srand( (unsigned)time( NULL ) );
373
374 for (row = 0; row < MAX_XYZ; row++)
375 {
376 for (col = 0; col < MAX_XYZ; col++)
377 {
378 if (rand() < (RAND_MAX * (chance / 100)))
379 {
380 numbertried = 0;
381 for (c = 0; c < MAX_XYZ; c++ ) { numberdone[c] = 0; }
382 do
383 {
384 if (numbertried == 9)
385 {
386 return(1);
387 }
388 else
389 {
390 numbertried++;
391 }
392 do
393 {
394 randomnumber = 1 + (int) ( (double)MAX_XYZ * (random() / (RAND_MAX + 1.0)));
395 } while (numberdone[randomnumber - 1] == 1);
396 numberdone[randomnumber - 1] = 1;
397 if (debug(2)) { fprintf(DEBUGPLACE, "Random check number %i at [%i,%i]\n",
398 randomnumber, row,col); }
399 } while ( insert(row, col, randomnumber) == 1);
400 }
401 else
402 {
403 _sudoku[row][col] = 0;
404 }
405 }
406 }
407 return(0);
408}
409
410void Sudoku::reset()
411{
412 //temp counters
413 int row;
414 int col;
415 int z;
416
417 _numbersFilled = 0;
418 for (row = 0; row < MAX_XYZ; row++)
419 {
420 for (col = 0; col < MAX_XYZ; col++)
421 {
422 _sudoku[row][col] = 0;
423 for (z = 0; z < MAX_XYZ; z++)
424 {
425 _possible[row][col][z] = true;
426 }
427 }
428 }
429}
430
431int Sudoku::fromFile(FILE *handle)
432{
433 int row;
434 int col;
435 int tmpInt;
436 for (row = 0; row < MAX_XYZ; row++)
437 {
438 for (col = 0; col < MAX_XYZ; col++)
439 {
440 fscanf(handle, "%1i", &tmpInt);
441 if (tmpInt != 0)
442 {
443 insert(row, col, tmpInt);
444 }
445 }
446 }
447 fclose(handle);
448 return(0);
449}
450
451/* Use Basic technique of finding places with just one number left to place */
452bool Sudoku::_solution1(int &row, int &col, int &number)
453{
454 #define NOTHING_FOUND 0
455 #define ONE_FOUND 1
456 #define MORE_THEN_ONE_FOUND 2
457 int tmpRow;
458 int tmpCol;
459 int tmpPossible;
460 int tmpNumber;
461 int searchState;
462
463 for (tmpRow = 0; tmpRow < MAX_XYZ; tmpRow++)
464 {
465 for (tmpCol = 0; tmpCol < MAX_XYZ; tmpCol++)
466 {
467 if (_sudoku[tmpRow][tmpCol] == 0)
468 {
469 tmpNumber = 0;
470 searchState = NOTHING_FOUND;
471 for (tmpPossible = 0; tmpPossible < MAX_XYZ; tmpPossible++)
472 {
473 if (_possible[tmpRow][tmpCol][tmpPossible] == true &&
474 searchState == ONE_FOUND)
475 {
476 searchState = MORE_THEN_ONE_FOUND;
477 break;
478 }
479 else if (_possible[tmpRow][tmpCol][tmpPossible] == true &&
480 searchState == NOTHING_FOUND)
481 {
482 tmpNumber = tmpPossible + 1;
483 searchState = ONE_FOUND;
484 }
485 }
486 if (searchState == ONE_FOUND)
487 {
488 row = tmpRow;
489 col = tmpCol;
490 number = tmpNumber;
491 return(true);
492 }
493 }
494 }
495 }
496
497 return(false);
498}
499
500/* Check if number can onlcol be placed somewhere, if not able to place anywhere else */
501/* FIXME: Should be more modular, to reduce line length and readabilitcol */
502/* FIXME: find nice solution for goto's */
503bool Sudoku::_solution2(int &row, int &col, int &number)
504{
505 int tmpRow;
506 int tmpCol;
507 int tmpPossible;
508 int tmpNumber;
509
510 int blockRow;
511 int blockTmpRow;
512 int blockCol;
513 int blockTmpCol;
514 bool result;
515
516 for (tmpRow = 0; tmpRow < MAX_XYZ; tmpRow++)
517 {
518 for (tmpCol = 0; tmpCol < MAX_XYZ; tmpCol++)
519 {
520 if (_sudoku[tmpRow][tmpCol] == 0)
521 {
522 for (tmpPossible = 0; tmpPossible < MAX_XYZ; tmpPossible++)
523 {
524 if (_possible[tmpRow][tmpCol][tmpPossible] == true)
525 {
526 if (debug(3))
527 {
528 fprintf(DEBUGPLACE,
529 "DEBUG SOL 2: Checking [%i,%i], number: %i...\n",
530 tmpRow,tmpCol,(tmpPossible +1));
531 }
532 /* checkRow */
533 result = true;
534 for (tmpNumber = 0; tmpNumber < MAX_XYZ; tmpNumber++)
535 {
536 if (_possible[tmpNumber][tmpCol][tmpPossible] == true &&
537 tmpRow != tmpNumber)
538 {
539 if (debug(3))
540 {
541 fprintf(DEBUGPLACE,
542 "DEBUG SOL 2: ..failed at Rowcheck bcol [%i,%i]\n",
543 tmpNumber,tmpCol);
544 }
545 result = false;
546 break;
547 }
548 }
549 if (result == true)
550 {
551 if (debug(3)) { fprintf(DEBUGPLACE,"DEBUG SOL 2: ..succesfull at Rowcheck\n"); }
552 goto solutionFound;
553 }
554
555 /* checkCol */
556 result = true;
557 for (tmpNumber = 0; tmpNumber < MAX_XYZ; tmpNumber++)
558 {
559 if (_possible[tmpRow][tmpNumber][tmpPossible] == true &&
560 tmpCol != tmpNumber)
561 {
562 if (debug(3))
563 {
564 fprintf(
565 DEBUGPLACE,
566 "DEBUG SOL 2: ..failed at Cowcheck bcol [%i,%i]\n",
567 tmpRow,tmpNumber);
568 }
569 result = false;
570 break;
571 }
572 }
573 if (result == true)
574 {
575 if (debug(3)) { fprintf(DEBUGPLACE,"DEBUG SOL 2: ..succesfull at Cowcheck\n"); }
576 goto solutionFound;
577 }
578
579 /* checkBlock */
580 result = true;
581 blockTmpRow = tmpRow - (tmpRow % (MAX_XYZ / 3));
582 blockTmpCol = tmpCol - (tmpCol % (MAX_XYZ / 3));
583 for (blockRow = blockTmpRow; blockRow < (blockTmpRow + 3); blockRow++)
584 {
585 for (blockCol = blockTmpCol; blockCol < (blockTmpCol + 3); blockCol++)
586 {
587 if (debug(4))
588 {
589 fprintf(DEBUGPLACE,"DEBUG SOL 2: ..checking [%i,%i]\n",blockRow,blockCol);
590 }
591 if(_possible[blockRow][blockCol][tmpPossible] == true &&
592 (not (tmpRow == blockRow && tmpCol == blockCol)) )
593 {
594 if (debug(4)) { fprintf(DEBUGPLACE,"DEBUG SOL 2: ...will cause failure\n"); }
595 result = false;
596 goto blockCheckFailed;
597 }
598 else
599 {
600 if (debug(4)) { fprintf(DEBUGPLACE,"DEBUG SOL 2: ...will be no harm\n"); }
601 }
602 }
603 }
604blockCheckFailed:
605 if (result == true)
606 {
607 if (debug(3)) { fprintf(DEBUGPLACE,"DEBUG SOL 2: ..succesfull at Blockcheck\n"); }
608 goto solutionFound;
609 }
610 }
611 }
612 }
613 }
614 }
615
616 return(false);
617
618solutionFound:
619 row = tmpRow;
620 col = tmpCol;
621 number = tmpPossible + 1;
622 return(true);
623}
624
625/* available striper, row based */
626/* FIXME: Should be more modular, to reduce line length and readabilitcol */
627bool Sudoku::_solution3a(int &row, int &col, int &number)
628{
629 int tmpRow;
630 int tmpCol;
631 int tmpPossible;
632 int tmpPossible2;
633 int tmpColNumber;
634 int tmpNumber[MAX_XYZ];
635 int tmpAllNumbers;
636 int tmpAllNumbersFound;
637
638 bool result;
639
640 for (tmpRow = 0; tmpRow < MAX_XYZ; tmpRow++)
641 {
642 for (tmpCol = 0; tmpCol < MAX_XYZ; tmpCol++)
643 {
644 if (_sudoku[tmpRow][tmpCol] == 0)
645 {
646 if (debug(3)) { fprintf(DEBUGPLACE,"SOL 3a DEBUG Checking [%i,%i]...\n",tmpRow,tmpCol); }
647 /* Set all numbers */
648 tmpAllNumbers = 0;
649 for (tmpPossible = 0; tmpPossible < MAX_XYZ; tmpPossible++)
650 {
651 if (_possible[tmpRow][tmpCol][tmpPossible] == true)
652 {
653 tmpNumber[tmpPossible] = 1;
654 tmpAllNumbers++;
655 }
656 else
657 {
658 tmpNumber[tmpPossible] = 0;
659 }
660 }
661 if (debug(3)) { fprintf(DEBUGPLACE,"SOL 3a DEBUG %i\n", tmpAllNumbers); }
662 if (tmpAllNumbers != 0)
663 {
664 for (tmpColNumber = 0; tmpColNumber < MAX_XYZ; tmpColNumber++)
665 {
666 if (_sudoku[tmpRow][tmpColNumber] == 0 && tmpColNumber != tmpCol)
667 {
668 result = true;
669 for (tmpPossible2 = 0; tmpPossible2 < MAX_XYZ; tmpPossible2++)
670 {
671 if ( _possible[tmpRow][tmpColNumber][tmpPossible2] == true &&
672 _possible[tmpRow][tmpCol][tmpPossible2] == false)
673 {
674 if (debug(3))
675 {
676 fprintf(DEBUGPLACE,"SOL 3a DEBUG [%i,%i] failed at %i\n",
677 tmpRow, tmpColNumber,tmpPossible2+1);
678 }
679 result = false;
680 break;
681 }
682 }
683 if (result == true)
684 {
685 if (debug(3))
686 {
687 fprintf(DEBUGPLACE,"SOL 3a DEBUG [%i,%i] will increase\n",
688 tmpRow, tmpColNumber);
689 }
690 for (tmpPossible2 = 0; tmpPossible2 < MAX_XYZ; tmpPossible2++)
691 {
692 if (_possible[tmpRow][tmpColNumber][tmpPossible2] == true)
693 {
694 if (debug(3)) { fprintf(DEBUGPLACE,
695 "SOL 3a DEBUG [%i,%i] will increase possible %i to %i\n",
696 tmpRow, tmpColNumber, tmpPossible2 + 1, tmpNumber[tmpPossible2] + 1);
697 }
698
699 if (tmpNumber[tmpPossible2] == tmpAllNumbers)
700 {
701 goto colCheckFailed;
702 }
703 else
704 {
705 tmpNumber[tmpPossible2]++;
706 }
707 }
708 }
709 }
710 }
711 }
712
713 /* calculate if result found */
714 tmpAllNumbersFound = 1;
715 for (tmpPossible = 0; tmpPossible < MAX_XYZ; tmpPossible++)
716 {
717 if (tmpNumber[tmpPossible] == tmpAllNumbers)
718 {
719 tmpAllNumbersFound++;
720 if (debug(3))
721 {
722 fprintf(DEBUGPLACE,
723 "SOL 3b DEBUG %i reduced tmpAllNumbers to %i\n",
724 tmpPossible + 1, tmpAllNumbers);
725 }
726 }
727 }
728
729 if (tmpAllNumbersFound == tmpAllNumbers)
730 {
731 for (tmpPossible = 0; tmpPossible < MAX_XYZ; tmpPossible++)
732 {
733 if (tmpNumber[tmpPossible] == 1)
734 {
735 row = tmpRow;
736 col = tmpCol;
737 number = tmpPossible + 1;
738 return(true);
739 }
740 }
741 }
742 }
743 } //end if
744colCheckFailed:
745 if (debug(3)) { fprintf(DEBUGPLACE,"SOL 3c DEBUG no failed solution found\n"); }
746 }
747 }
748 return(false);
749}
750
751/* available striper, col based, note row number will change ;-) */
752/* FIXME: Should be more modular, to reduce line length and readabilitcol */
753bool Sudoku::_solution3b(int &row, int &col, int &number)
754{
755 int tmpRow;
756 int tmpCol;
757 int tmpPossible;
758 int tmpPossible2;
759 int tmpRowNumber;
760 int tmpNumber[MAX_XYZ];
761 int tmpAllNumbers;
762 int tmpAllNumbersFound;
763
764 bool result;
765
766 for (tmpRow = 0; tmpRow < MAX_XYZ; tmpRow++)
767 {
768 for (tmpCol = 0; tmpCol < MAX_XYZ; tmpCol++)
769 {
770 if (_sudoku[tmpRow][tmpCol] == 0)
771 {
772 if (debug(3)) { fprintf(DEBUGPLACE,"SOL 3b DEBUG Checking [%i,%i]...\n",tmpRow,tmpCol); }
773 /* Set all numbers */
774 tmpAllNumbers = 0;
775 for (tmpPossible = 0; tmpPossible < MAX_XYZ; tmpPossible++)
776 {
777 if (_possible[tmpRow][tmpCol][tmpPossible] == true)
778 {
779 tmpNumber[tmpPossible] = 1;
780 tmpAllNumbers++;
781 }
782 else
783 {
784 tmpNumber[tmpPossible] = 0;
785 }
786 }
787 if (debug(3)) { fprintf(DEBUGPLACE,"SOL 3b DEBUG %i\n", tmpAllNumbers); }
788 if (tmpAllNumbers != 0)
789 {
790 for (tmpRowNumber = 0; tmpRowNumber < MAX_XYZ; tmpRowNumber++)
791 {
792 if (_sudoku[tmpRowNumber][tmpCol] == 0 && tmpRowNumber != tmpRow)
793 {
794 result = true;
795 for (tmpPossible2 = 0; tmpPossible2 < MAX_XYZ; tmpPossible2++)
796 {
797 if ( _possible[tmpRowNumber][tmpCol][tmpPossible2] == true &&
798 _possible[tmpRow][tmpCol][tmpPossible2] == false)
799 {
800 if (debug(3))
801 {
802 fprintf(DEBUGPLACE,
803 "SOL 3b DEBUG [%i,%i] failed at %i\n",
804 tmpRowNumber, tmpCol,tmpPossible2+1);
805 }
806 result = false;
807 break;
808 }
809 }
810 if (result == true)
811 {
812 if (debug(3)) { fprintf(DEBUGPLACE,
813 "SOL 3b DEBUG [%i,%i] will increase\n",
814 tmpRowNumber, tmpCol);
815 }
816 for (tmpPossible2 = 0; tmpPossible2 < MAX_XYZ; tmpPossible2++)
817 {
818 if (_possible[tmpRowNumber][tmpCol][tmpPossible2] == true)
819 {
820 if (debug(3))
821 {
822 fprintf(DEBUGPLACE,
823 "SOL 3b DEBUG [%i,%i] will increase possible %i to %i\n",
824 tmpRowNumber, tmpCol, tmpPossible2 + 1,
825 tmpNumber[tmpPossible2] + 1);
826 }
827
828 if (tmpNumber[tmpPossible2] == tmpAllNumbers)
829 {
830 goto rowCheckFailed;
831 }
832 else
833 {
834 tmpNumber[tmpPossible2]++;
835 }
836 }
837 }
838 }
839 }
840 }
841
842 /* calculate if result found */
843 tmpAllNumbersFound = 1;
844 for (tmpPossible = 0; tmpPossible < MAX_XYZ; tmpPossible++)
845 {
846 if (tmpNumber[tmpPossible] == tmpAllNumbers)
847 {
848 tmpAllNumbersFound++;
849 if (debug(3))
850 {
851 fprintf(DEBUGPLACE,
852 "SOL 3b DEBUG %i reduced tmpAllNumbers to %i\n",
853 tmpPossible + 1, tmpAllNumbers);
854 }
855 }
856 }
857
858 if (tmpAllNumbersFound == tmpAllNumbers)
859 {
860 for (tmpPossible = 0; tmpPossible < MAX_XYZ; tmpPossible++)
861 {
862 if (tmpNumber[tmpPossible] == 1)
863 {
864 row = tmpRow;
865 col = tmpCol;
866 number = tmpPossible + 1;
867 return(true);
868 }
869 }
870 }
871 }
872 } //end if
873rowCheckFailed:
874 if (debug(3)) { fprintf(DEBUGPLACE,"SOL 3b DEBUG no failed solution found\n"); }
875 }
876 }
877 return(false);
878}
879int Sudoku::solutionFinder()
880{
881 #define NO_SOLUTION 0
882 #define SOLUTION_1 1
883 #define SOLUTION_2 2
884 #define SOLUTION_3a 3
885 #define SOLUTION_3b 4
886 #define SOLUTION_3c 5
887 int row;
888 int col;
889 int number;
890
891 bool gameAnalcolzed;
892 int returnCode;
893 int solutionNumber;
894
895 gameAnalcolzed = false;
896
897 while( gameAnalcolzed == false )
898 {
899 solutionNumber = NO_SOLUTION;
900 if (_numbersFilled == MAX_XYZ * MAX_XYZ)
901 {
902 gameAnalcolzed = true;
903 returnCode = 0;
904 }
905 else
906 {
907 if (_solution1(row, col, number) == true)
908 {
909 solutionNumber = SOLUTION_1;
910 }
911 else if(_solution2(row, col, number) == true)
912 {
913 solutionNumber = SOLUTION_2;
914 }
915 else if(_solution3a(row, col, number) == true)
916 {
917 solutionNumber = SOLUTION_3a;
918 }
919 else if(_solution3b(row, col, number) == true)
920 {
921 solutionNumber = SOLUTION_3b;
922 }
923 else
924 {
925 gameAnalcolzed = true;
926 returnCode = 1;
927 }
928 }
929
930 if (solutionNumber != NO_SOLUTION)
931 {
932 insert(row, col, number);
933 printf("Filled in %i at [%i,%i] found with finder %i\n", number, row, col, solutionNumber);
934 printf("Total Numbers filled %i\n", _numbersFilled);
935 printNice(row, col);
936 getchar();
937 }
938
939 }
940 return(returnCode);
941}
942
943int main(int argc, char *argv[])
944{
945 Sudoku puzzel;
946 int timesFailed;
947 int returnCode;
948
949 returnCode = 0;
950
951 if (argc == 3 && strcmp(argv[1], "-f") == 0)
952 {
953 if (strcmp(argv[2], "-") == 0)
954 {
955 if (debug(1)) { fprintf(DEBUGPLACE, "Reading from 'stdin'\n"); }
956 puzzel.fromFile(stdin);
957 }
958 else
959 {
960 if (debug(1)) { fprintf(DEBUGPLACE, "Reading from %s\n",argv[2]); }
961 puzzel.fromFile(fopen(argv[2], "r"));
962 }
963 printf("I have read this puzzle\n");
964 puzzel.printNice();
965 returnCode = puzzel.solutionFinder();
966 if (returnCode == 0)
967 {
968 printf("I Guess this will be the final solution\n");
969 puzzel.printNice();
970 }
971 else
972 {
973 printf("Finding Solution failed, error code: %i\n", returnCode);
974 printf("Failed at puzzle\n");
975 puzzel.printNice();
976 puzzel.printPossible();
977 }
978 }
979 else if (argc == 3 && strcmp(argv[1], "-c") == 0)
980 {
981 fprintf(DEBUGPLACE,"Please wait will generating puzzle");
982 timesFailed = 0;
983 while (puzzel.randomNumbers(strtod(argv[2], NULL)) == 1 )
984 {
985 timesFailed++;
986 if (debug(1))
987 {
988 fprintf(DEBUGPLACE, "Failed to created the puzzel at the %i round\n", timesFailed);
989 }
990 else
991 {
992 fprintf(DEBUGPLACE,".");
993 }
994 puzzel.reset();
995 }
996 fprintf(DEBUGPLACE, "\nResult, (NOTE(!): puzzle might not be solveble)\n");
997 puzzel.printRaw();
998 }
999 else
1000 {
1001 printf("Usage %s -f <filename>\n",argv[0]);
1002 printf("NOTE 1: No error checking done, valid input puzzel will be ");
1003 printf("generated the -c flags\n");
1004 printf("NOTE 2: if <filename> = -, stdin will be used as input");
1005 printf("Usage %s -c <percent filled> To create a new puzzle\n",argv[0]);
1006 printf("NOTE 1: Above 60%% it will be a bit hard to create ");
1007 printf("a puzzle\n");
1008 printf("NOTE 2: Puzzle generated will not always be solveble\n");
1009 returnCode = 128;
1010 }
1011 return(returnCode);
1012}
1013
1014
1015\end{verbatim}
1016\end{small}
1017
1018\newpage
1019\section*{Appendix B: sudoku.cpp}
1020Sample of 17-clue puzzles found at Minimum Sudoku\cite{gordon}. Input Row based.
1021
1022\begin{small}
1023\begin{verbatim}
1024000000010400000000020000000000050407008000300001090000300400200050100000000806000
1025000000010400000000020000000000050604008000300001090000300400200050100000000807000
1026000000012000035000000600070700000300000400800100000000000120000080000040050000600
1027000000012003600000000007000410020000000500300700000600280000040000300500000000000
1028000000012008030000000000040120500000000004700060000000507000300000620000000100000
1029000000012040050000000009000070600400000100000000000050000087500601000300200000000
1030000000012050400000000000030700600400001000000000080000920000800000510700000003000
1031000000012300000060000040000900000500000001070020000000000350400001400800060000000
1032000000012400090000000000050070200000600000400000108000018000000000030700502000000
1033000000012500008000000700000600120000700000450000030000030000800000500700020000000
1034000000012700060000000000050080200000600000400000109000019000000000030800502000000
1035000000012800040000000000060090200000700000400000501000015000000000030900602000000
1036000000013000500070000802000000400900107000000000000200890000050040000600000010000
1037000000013000700060000508000000400800106000000000000200740000050020000400000010000
1038000000013000700060000509000000400900106000000000000200740000050080000400000010000
1039000000013000800070000502000000400900107000000000000200890000050040000600000010000
1040000000013020500000000000000103000070000802000004000000000340500670000200000010000
1041000000013040000080200060000609000400000800000000300000030100500000040706000000000
1042000000013040000080200060000906000400000800000000300000030100500000040706000000000
1043000000013040000090200070000607000400000300000000900000030100500000060807000000000
1044...
1045\end{verbatim}
1046\end{small}
1047
1048\newpage
1049\section*{Appendix C: sudoku.cpp}
1050The following Shell code has been used to generate the test results
1051
1052\begin{small}
1053\begin{verbatim}
1054#!/bin/sh
1055# file: testcase.sh
1056# author: Rick van der Zwet, 0433373
1057# University Leiden, LIACS
1058timesPlayed=0
1059timesWon=0
1060timesLost=0
1061if [ "x$1" == "x" ]; then
1062 totalNumber=100
1063else
1064 totalNumber=$1
1065fi
1066
1067for puzzle in `cat puzzles17`
1068do
1069 let "timesPlayed+=1"
1070 echo "${puzzle}" | ./sudoku -f - >/dev/null
1071 if [ "x$?" == "x0" ]; then
1072 let "timesWon+=1"
1073 else
1074 let "timesLost+=1"
1075 fi
1076 echo "Played: ${timesPlayed}"
1077 echo "won : ${timesWon}"
1078 echo "lost : ${timesLost}"
1079 if [ "x${timesPlayed}" == "x${totalNumber}" ]; then
1080 break
1081 fi
1082done
1083\end{verbatim}
1084\end{small}
1085
1086\end{document}
Note: See TracBrowser for help on using the repository browser.