001      /*    Author Malte Pagel    */
002      
003      var TOTAL = 81;
004                  
005      /**
006       * TOTAL will be adjusted if not square of square
007       */
008      var LINE = parseInt(Math.sqrt(TOTAL));
009      var SMALL_LINE = parseInt(Math.sqrt(LINE));
010      LINE = Math.pow(SMALL_LINE, 2);
011      TOTAL = Math.pow(LINE, 2);
012      
013      
014      /**
015       * Define what to do with found numbers
016       */
017      function show_single (riddle_index) {
018          // some code
019      }
020      /**
021       * Define what to do with unnecessary numbers
022       */
023      function hide_single (riddle_index, value) {
024          // some code
025      }
026      /**
027       * Define what to do with messages
028       */
029      function personal_debug (message) {
030          // some code
031      }
032      
033      
034      /**
035       * Takes a position inside the large square and returns
036       *        - [0]        the row number
037       *        - [1]        the column number
038       *        - [2]        the small square number
039       * where this position is situated in
040       */
041      function get_collection (index) {
042          var ret = [];
043          ret[0] = parseInt(index / LINE);
044          ret[1] = index % LINE;
045          ret[2] = SMALL_LINE * parseInt(ret[0] / SMALL_LINE)
046          + parseInt(ret[1] / SMALL_LINE);
047      
048          return ret;
049      }
050      
051      /**
052       * Is 'the_element' in 'the_array'?
053       */
054      function contains_element (the_array, the_element) {
055          for ( var i = 0; i < the_array.length; i++ )
056              if ( the_array[i] == the_element )
057                  return 1;
058          return 0;
059      }
060      
061      /**
062       * Returns all members of row 'row'
063       */
064      function get_horizontal (row) {
065          var ret = [];
066          var i;
067          var j = 0;
068      
069          for ( i = (row * LINE); i < (row * LINE) + LINE; i++ ) {
070              ret[j] = riddle[i];
071              j++;
072          }
073      
074          return ret;
075      }
076      /**
077       * Returns all members of column 'col'
078       */
079      function get_vertical (col) {
080          var ret = [];
081          var i;
082          var j = 0;
083      
084          for ( i = col; i < TOTAL; i += LINE ) {
085              ret[j] = riddle[i];
086              j++;
087          }
088      
089          return ret;
090      }
091      /**
092       * Returns all members of small square 'which'
093       */
094      function get_square (which) {
095          var ret = [];
096          var i, j;
097      
098          for ( i = 0; i < SMALL_LINE; i++ )
099              for ( j = 0; j < SMALL_LINE; j++ ) {
100                  ret[SMALL_LINE * i + j] = riddle[LINE * i + which * SMALL_LINE + j
101                  + (parseInt(which / SMALL_LINE) * (SMALL_LINE - 1) * LINE)];
102              }
103      
104          return ret;
105      }
106      
107      /**
108       * Unweighted randomization:
109       * 'raw' numbers (i.e. indices) from 0 to (limit - 1).
110       * Fetch random value from 'raw', push it to the end of 'target',
111       * clear this value in 'raw'.
112       * Repeat until 'raw' is empty
113       */
114      function randomize_unweighted (offset, limit) {
115          var raw = [];
116          var target = [];
117          var i;
118          
119          for ( i = 0; i < limit; i++ )
120              raw[i] = i + offset;
121          
122          i = 0;
123          while ( raw.length ) {
124              random = Math.floor(Math.random() * raw.length);
125              target[i] = raw[random];
126              raw.splice(random, 1);
127              i++;
128          }
129          
130          return target;
131      }
132      
133      
134      var multi_raw = [];
135      var indices = [];
136      var riddle = [];
137      var i, random, redundant, tmp, unset_count, small_rows, small_cols;
138      var tries_to_set = 0;
139      
140      /**
141       * Initialization:
142       * Fields are set to 0 ( = we dont' know the number yet)
143       */
144      for ( i = 0; i < TOTAL; i++ )
145          riddle[i] = 0;
146      
147      
148      /**
149       * Second initialization:
150       * LINE times numbers from 0 to (LINE - 1),
151       * i.e. every square
152       */
153      for ( var big_rows = 0; big_rows < SMALL_LINE; big_rows++ )
154          for ( var big_cols = 0; big_cols < SMALL_LINE; big_cols++ ) {
155              start_value = big_rows * LINE * SMALL_LINE + (big_cols * SMALL_LINE);
156              i = multi_raw.length;
157              multi_raw[i] = [];
158              for ( small_rows = 0; small_rows < SMALL_LINE; small_rows++ )
159                  for ( small_cols = 0; small_cols < SMALL_LINE; small_cols++ )
160                      multi_raw[i].push(small_rows * LINE + small_cols + start_value);
161          }
162      
163      /**
164       * Randomization for every element ('element') of multi_raw.
165       * Fetch random value from 'element', push it to the end of 'indices',
166       * clear this value in 'element'.
167       * Repeat until 'element' is empty
168       */
169      for ( i = 0; i < multi_raw.length; i++ ) {
170          while ( multi_raw[i].length ) {
171              random = Math.floor(Math.random() * multi_raw[i].length);
172              indices[indices.length] = multi_raw[i][random];
173              multi_raw[i].splice(random, 1);
174          }
175      }
176      
177      /**
178       * Recursive function:
179       * Try for each position the numbers from 1 to LINE
180       *      (except 'forbidden_number' if given).
181       * If all numbers collide with already set numbers, move is bad.
182       * If a number doesn't collide with already set numbers,
183       *        - move is bad if next move collides with the already set numbers
184       *              (including actual one)
185       *        - move is good if it's the last one
186       */
187      function set_values (index, forbidden_number) {
188                      
189          var real_index = indices[index];
190      
191          var blocks = get_collection(real_index);
192      
193          for ( var i = 1; i <= LINE; i++ ) {
194              if ( forbidden_number && i == forbidden_number )
195                  continue;
196              
197              tries_to_set++;
198              
199              if ( contains_element(get_horizontal(blocks[0]), i) )
200                  continue;
201              if ( contains_element(get_vertical(blocks[1]), i) )
202                  continue;
203              if ( contains_element(get_square(blocks[2]), i) )
204                  continue;
205      
206              riddle[real_index] = i;
207      
208              if ( index == (TOTAL - 1) || set_values((index + 1), 0) )
209                  return 1;
210          }
211      
212          riddle[real_index] = 0;
213      
214          return 0;
215      }
216      
217      /**
218       * Setting numbers, start with the first one.
219       * Variable 'redundant' is needed only for formal reasons
220       */
221      redundant = set_values(0, 0);
222      
223      
224      /**
225       * Reshuffle 'indices' (so that the user doesn't recognize
226       * the previous used randomized order)
227       */
228      indices = randomize_unweighted(0, TOTAL);
229      
230      
231      /**
232       * We probably want to see the result
233       */
234      for ( i = 0; i < TOTAL; i++ )
235          show_single(i);
236      
237      
238      personal_debug( tries_to_set + " tries to set the " + TOTAL + " numbers" );
239      
240      
241      /**
242       * Some steps:
243       *        a) Define last piece as 'special piece'
244       *        b) Remember this piece's value
245       *        c) Try to create riddle from this position on,
246       *          but forbid the value of the special piece
247       *        d) If operation fails, define the piece before the special piece
248       *          as 'special piece' and continue with b)
249       */
250      tries_to_set = 0;
251      unset_count = 1;
252      do {
253          tmp = riddle[indices[TOTAL - unset_count]];
254          redundant = set_values((TOTAL - unset_count), tmp);
255      
256          if ( !redundant )
257              hide_single(indices[TOTAL - unset_count], tmp);
258          unset_count++;
259      }
260      while ( !redundant );
261      
262      
263      personal_debug( tries_to_set + " tries to remove " + (unset_count - 2) + " numbers" );
264      
265