01      // Author Malte Pagel
02      
03      document.write("<sty" + "le type='text/css'>");
04      document.write(".table_cell {width: 40px;height: 40px;text-align: center;color: #FF8000;}.table_cell.empty {background-color: #EEEEEE;}.table_cell.full_dark {background-color: #282828;}.table_cell.full_light {background-color: #A5A5A5;}.table_cell.grey, .table_cell.empty.grey {color: gray;font-size: 18px;}");
05      document.write("</style>");
06      
07      function personal_debug (message) {
08          console.log(message);
09          //iD("instruction").innerHTML = message;
10      }
11      
12      document.write("<center><span id='instruction'>Klicken Sie auf ein Feld, auf dem der Springer beginnen soll</span><br><br></center>");
13                      
14      var upper_array = [ 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H',
15                          'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P'];
16      var table_cols = 8;
17      
18      document.write("<center><table border='1' rules='none' style='color: #FF8000; font-size: 24px; border: thin ridge #F2F2F2'>");
19      
20      for ( var table_count = 0; table_count < table_cols; table_count++ ) {
21          document.write("<tr>");
22          document.write("<td class='table_cell' style='padding-right: 8px; color: silver; background-color: #F6F6F6'>" + (table_cols - table_count) + "</td>");
23          for ( var inner_count = 0; inner_count < table_cols; inner_count ++ ) {
24              document.write("<td id='cell_" + upper_array[inner_count] + (table_cols - table_count) + "' class='table_cell");
25              if ( (table_count + inner_count) % 2 != 0 )
26                  document.write(" empty");
27              document.write("' style='cursor: pointer' onclick='set_start(" + inner_count + ", " + (table_cols - table_count - 1) + ")'>");
28              document.write("</td>");
29          }
30          document.write("</tr>");
31      }
32      document.write("<tr><td class='table_cell' style='padding-right: 8px; background-color: #F6F6F6'></td>");
33      for ( table_count = 0; table_count < table_cols; table_count++ ) {
34          document.write("<td class='table_cell' style='padding-top: 8px; color: silver; background-color: #F6F6F6'>");
35          document.write(upper_array[table_count]);
36          document.write("</td>");
37      }
38      document.write("</tr>");
39      document.write("</table></center>");
40       

001      //
002      //  KnightPosition: example.js
003      //
004      //  Created 2013/11 by Malte Pagel
005      //  Copyright (c) 2013 Malte Pagel. All rights reserved.
006      //
007      
008      
009      var letters = [ 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P' ];
010      var column = -1;
011      var row = -1;
012      var cols = 8;
013      var start_position = null;
014      
015      var knight_count = 0;
016      var knight_number = 0;
017      var memory_count = 0;
018      var x_move = [ 1, 2, 2, 1, -1, -2, -2, -1, 1, 2, 2, 1, -1, -2 ];
019      var y_move = [ -2, -1, 1, 2, 2, 1, -1, -2, -2, -1, 1, 2, 2, 1 ];
020      var reachable_positions_offset = 0;
021      var reachable_positions_offset_set = 0;
022      
023      var MEMORY_LIMIT = 4096;
024      
025      function show_cell_content (col, row, content) {
026          if ( content )
027              iD("cell_" + letters[col] + (row + 1)).innerHTML = content;
028          else
029              iD("cell_" + letters[col] + (row + 1)).innerHTML = "";
030      }
031      
032      
033      function KnightPosition (column, row, num_cols, collection) {
034          
035          
036          //this.column, this.row, this.has_knight, this.center_distance;
037          //this.next_position;
038          
039          
040          var lower_or_equal;
041          var previous_position;
042          var first_collected_position, last_collected_position, first_position_to_try, last_position_to_try;
043          var myself = this;
044          
045          
046          
047          this.set_knight_and_start_search = function (last_position) {
048              knight_number++;
049              this.has_knight = 1;
050              previous_position = last_position;
051              
052              show_cell_content(this.column, this.row, knight_number);
053              
054              last_position_to_try = null;
055              first_position_to_try = null;
056              
057              order_reachable_positions();
058              
059              if ( !first_position_to_try ) {
060                  go_back();
061                  return;
062              }
063              
064              do_search();
065          };
066          
067          this.get_num_possibilities = function () {
068              var possibilities = 0;
069      
070              if ( !first_collected_position )
071                  return 0;
072              
073              tmp_position = first_collected_position;
074              while ( tmp_position ) {
075                  if ( !tmp_position.possible_position.has_knight )
076                      possibilities++;
077                  tmp_position = tmp_position.basic_next;
078              }
079      
080              return possibilities;
081          };
082          
083          this.another_try_from_above = function () {
084              myself.next_position.next_position = null;
085              
086              if ( !first_position_to_try ) {
087                  show_cell_content(myself.column, myself.row, 0);
088                  go_back();
089                  return;
090              }
091              
092              if ( memory_count > MEMORY_LIMIT || (memory_count && knight_number == 1) ) {
093                  if ( knight_number == 1 )
094                      personal_debug( "Does not seem to be solvable" );
095                  else
096                      personal_debug( "Too much recursion, I'm giving up; knights: " + knight_number + " / " + (cols * cols) );
097                  return;
098              }
099              
100              personal_debug( "I am at " + letters[myself.column] + (myself.row + 1) + " (try " + memory_count + "); "
101                  + letters[myself.next_position.column] + (myself.next_position.row + 1) + " was bad; trying "
102                  + letters[first_position_to_try.possible_position.column]
103                  + (first_position_to_try.possible_position.row + 1) );
104              
105              do_search();
106          };
107          
108          
109          
110          function do_search () {
111              var position_to_try = first_position_to_try;
112              
113              myself.next_position = position_to_try.possible_position;
114              
115              first_position_to_try = (first_position_to_try.next) ? first_position_to_try.next : null;
116              
117              if ( knight_number >= (cols * cols - 1) ) {
118                  make_grey();
119                  show_cell_content(myself.next_position.column, myself.next_position.row, (cols * cols));
120                  if ( memory_count )
121                      personal_debug( "\t* SOLVED *" );
122                  show_solution(start_position);
123                  return;
124              }
125              
126              myself.next_position.set_knight_and_start_search(myself);
127          }
128          
129          function order_reachable_positions () {
130              var possibilities, success;
131              
132              var tmp_position_to_add, tmp_tmp_position, tmp_tmp_tmp_position;
133              
134              var tmp_position = first_collected_position;
135              
136              while ( tmp_position != null ) {
137                  
138                  possibilities = tmp_position.possible_position.get_num_possibilities();
139                  
140                  if ( !tmp_position.possible_position.has_knight ) {
141      
142                      if ( !possibilities )
143                          possibilities = cols * 8;
144      
145                      tmp_position_to_add = tmp_position;
146                      tmp_position_to_add.heuristic = (cols * possibilities + tmp_position.possible_position.center_distance);
147                      tmp_position_to_add.next = null;
148      
149                      if ( !first_position_to_try ) {
150                          first_position_to_try = tmp_position_to_add;
151                          last_position_to_try = first_position_to_try;
152                      }
153                      else {
154                          tmp_tmp_position = first_position_to_try;
155                          success = 0;
156                          while ( tmp_tmp_position && !success ) {
157                              if ( tmp_position_to_add.heuristic < tmp_tmp_position.heuristic || (lower_or_equal && tmp_position_to_add.heuristic == tmp_tmp_position.heuristic) ) {
158                                  if ( tmp_tmp_position == first_position_to_try ) {
159                                      tmp_position_to_add.next = tmp_tmp_position;
160                                      first_position_to_try = tmp_position_to_add;
161                                      success = 1;
162                                  }
163                                  else {
164                                      tmp_tmp_tmp_position = first_position_to_try;
165                                      while ( tmp_tmp_tmp_position.next != tmp_tmp_position )
166                                          tmp_tmp_tmp_position = tmp_tmp_tmp_position.next;
167                                      tmp_position_to_add.next = tmp_tmp_tmp_position.next;
168                                      tmp_tmp_tmp_position.next = tmp_position_to_add;
169                                      success = 1;
170                                  }
171                              }
172                              tmp_tmp_position = tmp_tmp_position.next;
173                          }
174                          if ( !success ) {
175                              last_position_to_try.next = tmp_position_to_add;
176                              last_position_to_try = tmp_position_to_add;
177                          }
178                      }
179                  }
180                  
181                  tmp_position = tmp_position.basic_next;
182              }
183          }
184          
185          function go_back () {
186              memory_count++;
187              knight_number--;
188              myself.has_knight = 0;
189              
190              setTimeout(previous_position.another_try_from_above, 21);
191          }
192          
193          function add_to_reachable_positions (position) {
194              var position_data = {};
195              
196              position_data.possible_position = position;
197              position_data.heuristic = 0;
198              position_data.next = null;
199              position_data.basic_next = null;
200              
201              if ( !first_collected_position ) {
202                  first_collected_position = position_data;
203                  last_collected_position = first_collected_position;
204              }
205              else {
206                  last_collected_position.basic_next = position_data;
207                  last_collected_position = position_data;
208              }
209          }
210          
211          function fill_reachable_positions () {
212              var i, x, y;
213              var tmp_position = null;
214              
215              for ( i = reachable_positions_offset; i < (8 + reachable_positions_offset); i++ ) {
216                  x = column + x_move[i];
217                  y = row + y_move[i];
218                  
219                  if ( x < 0 || x > (cols - 1) || y < 0 || y > (cols - 1) )
220                      continue;
221                  if ( !collection[x][y] ) {
222                      tmp_position = new KnightPosition(x, y, cols, collection);
223                      add_to_reachable_positions(tmp_position);
224                  }
225                  else
226                      add_to_reachable_positions(collection[x][y]);
227              }
228          }
229          
230          
231          
232          collection[column][row] = this;
233          
234          this.column = column;
235          this.row = row;
236          this.has_knight = 0;
237          
238          this.next_position = null;
239          previous_position = null;
240          
241          first_collected_position = null;
242          last_collected_position = null;
243          
244          this.center_distance = Math.abs((cols - 1) - (2 * column) - (2 * row));
245          
246          if ( !reachable_positions_offset_set ) {
247              if ( column < 4 ) {
248                  if ( row < 4 )
249                      reachable_positions_offset = 4;
250                  else
251                      reachable_positions_offset = 6;
252              }
253              else
254                  if ( row < 4 )
255                      reachable_positions_offset = 2;
256              reachable_positions_offset_set = 1;
257          }
258          
259          fill_reachable_positions();
260          
261          knight_count++;
262          
263          lower_or_equal = ( Math.floor(Math.random() * (cols * cols + this.center_distance + 1 - knight_count)) == 0 ) ? 1 : 0;
264          
265          //personal_debug( "KnightPosition number " + knight_count + " constructed at " + letters[column] + (row + 1) );
266      }
267      
268      
269      
270      function make_grey () {
271          for ( var i = 0; i < cols; i++ )
272              for ( var j = 0; j < cols; j++ ) {
273                  iD("cell_" + letters[i] + (j + 1)).style.cursor = "help";
274                  iD("cell_" + letters[i] + (j + 1)).className = ((i + j) % 2 != 0) ? "table_cell grey" : "table_cell empty grey";
275              }
276      }
277      
278      function show_solution (position) {
279          var c = position.column;
280          var r = position.row;
281          
282          iD("cell_" + letters[c] + (r + 1)).className = ((c + r) % 2 != 0) ? "table_cell full_light" : "table_cell full_dark";
283          
284          if ( position.next_position )
285              setTimeout(show_solution, 333, position.next_position);
286          else {
287              personal_debug( "\t************" );
288              personal_debug( "\t* FINISHED *" );
289              personal_debug( "\t************" );
290              
291              for ( var i = 0; i < cols; i++ )
292                  for ( var j = 0; j < cols; j++ )
293                      iD("cell_" + letters[i] + (j + 1)).style.cursor = "default";
294          }
295      }
296      
297      function quasi_main () {
298          var i, j;
299          
300          var complete_collection = [];
301          for ( i = 0; i < cols; i++ ) {
302              complete_collection[i] = [];
303              for ( j = 0; j < cols; j++ )
304                  complete_collection[i][j] = null;
305          }
306          
307          start_position = new KnightPosition(column, row, cols, complete_collection);
308          
309          complete_collection = null;
310          
311          start_position.set_knight_and_start_search(null);
312      }
313      
314      function set_start (c, r) {
315          if ( column >= 0 )
316              return;
317          
318          column = c;
319          row = r;
320          
321          for ( var i = 0; i < cols; i++ )
322              for ( var j = 0; j < cols; j++ )
323                  iD("cell_" + letters[i] + (j + 1)).style.cursor = "wait";
324          
325          iD("instruction").innerHTML = "";
326          
327          quasi_main();
328      }
329      
330      //set_start(Math.floor(Math.random() * cols), Math.floor(Math.random() * cols));
331