assignments/archive/sudoku/index.shtml

   1 <!--#set var="root_directory" value="../../.." --><!--#include virtual="$root_directory/shared/header.shtml"-->
   2
   3 <h1>Assignment #1</h1>
   4 <p><em>Due Friday, October 8, 2010</em></p>
   5
   6 <h2>Purpose</h2>
   7
   8 <p>Remind ourselves of the C or C ++ syntax, in particular: arrays,
   9 loop, conditional, functions, ...</p>
  10
  11 <p>Note: Please identify all your work.</p>
  12
  13 <p>Write a C or C ++ code to
  14 solve <a href="http://en.wikipedia.org/wiki/Sudoku">sudoku
  15 puzzles</a>.</p>
  16
  17 <p>Sudoku is a one player board puzzle in which the player fills in
  18 the empty cells on a 9x9 board with digits 1 to 9. The rules are
  19 simple:</p>
  20
  21 <ul>
  22   <li>The digits 1 to 9 must be on every row with no repetition.</li>
  23   <li>The digits 1 to 9 must be on every column with no repetition.</li>
  24   <li>The digits 1 to 9 must be on every tile with no repetition.</li>
  25 </ul>
  26
  27 <p>The <em>tiles</em> in the rules refer to 3x3 sub-regions that cover
  28 the 9x9 board with no overlap.  A game is seeded by having some digits
  29 1 to 9 placed on the board (satisfying the rules above).  The player
  30 needs to complete the filling the board with digits 1 to 9 while
  31 respecting the rules above.</p>
  32
  33 <h2>Algorithm — key steps</h2>
  34
  35 <ol>
  36   <li>Set the geometry of the board, i.e., the tiles.</li>
  37   <li>Read in the starting configuration on the board.</li>
  38   <li>Initialize in a trial array all the candidate digits for every
  39     unfilled cell, i.e., digits 1 to 9.</li>
  40   <li>For an unfilled cell on the board and for one of the digits in
  41     the trial array corresponding to this cell, scan the row, column
  42     and block for digit repetition.</li>
  43   <li>If a repetition is found, eliminate this trial digit.</li>
  44   <li>Repeat the two steps above for every unfilled cell on the board
  45     and for every digit left in the trial array corresponding to these
  46     unfilled cell 1.<li>
  47   <li>If at any time the trial array contains only one (1) trial digit
  48     for an unfilled cell on the board, this digit is part of the solution
  49     of the sudoku puzzle and marked as such.</li>
  50   <li>Accumulate the number of events in the steps above. An event
  51     could be removing a digit from the trial array or selecting a
  52     digit as part of the solution.</li>
  53   <li>Repeat the scans above until the number of events is zero (0),
  54     i.e., a steady state is reached, at which time the solution of the
  55     sudoku puzzle is either obtained or the puzzle is too hard to
  56     solve by this simple algorithm.</li>
  57 </ul>
  58
  59 <h2>I/O</h2>
  60
  61 <p>A simple file interface should prove sufficient to check your
  62 code. Namely, the initial configuration of digits on the board could
  63 be typed in a file with an obvious format</p>
  64
  65 <pre>
  66 - - 1   3 - -   - 6 -
  67 - 5 -   - - 1   - - 3
  68 ...
  69 </pre>
  70
  71 <p>The output of any configuration could follow the same format.</p>
  72
  73 <p>A run would then be</p>
  74
  75 <pre>
  76 cat initialboard | ./sudoku
  77 </pre>
  78
  79 <h2>Suggested functions</h2>
  80
  81 <p>Please write a modular code.  Functions could be</p>
  82
  83 <dl>
  84   <dt><code>geometry()</code></dt>
  85   <dd>set the geometry of the board (rows, column, tiles)</dd>
  86   <dt><code>read_config()</code></dt>
  87   <dd>read in a board configuration</dd>
  88   <dt><code>print_config()</code></dt>
  89   <dd>print a board configuration</dd>
  90   <dt><code>is_forbiden()</code></dt>
  91   <dd>check if a trial digit is forbidden in a cell</dd>
  92   <dt><code>check_cell()</code></dt>
  93   <dd>finds and removes forbidden digits in a cell</dd>
  94   <dt><code>check_all_cells()</code></dt>
  95   <dd>scans over all cells to remove forbidden trial digits</dd>
  96 </dl>
  97
  98 <h2>Sample puzzles</h2>
  99
 100 <pre>
 101 5 3 -   - 7 -   - - -
 102 6 - -   1 9 5   - - -
 103 - 9 8   - - -   - 6 -
 104
 105 8 - -   - 6 -   - - 3
 106 4 - -   8 - 3   - - 1
 107 7 - -   - 2 -   - - 6
 108
 109 - 6 -   - - -   2 8 -
 110 - - -   4 1 9   - - 5
 111 - - -   - 8 -   - 7 9
 112 </pre>
 113
 114 <pre>
 115 5 3 4   6 7 8   9 1 2
 116 6 7 2   1 9 5   3 4 8
 117 1 9 8   3 4 2   5 6 7
 118
 119 8 5 9   7 6 1   4 2 3
 120 4 2 6   8 5 3   7 9 1
 121 7 1 3   9 2 4   8 5 6
 122
 123 9 6 1   5 3 7   2 8 4
 124 2 8 7   4 1 9   6 3 5
 125 3 4 5   2 8 6   1 7 9
 126 </pre>
 127
 128 <ul>
 129   <li><a href="1.cfg">1.cfg</a></li>
 130   <li><a href="2.cfg">2.cfg</a></li>
 131   <li><a href="3.cfg">3.cfg</a></li>
 132 </ul>
 133
 134 <!--#include virtual="$root_directory/shared/footer.shtml"-->