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