| Inhalt | Code | Beispiel |
| C++ | Javascript | Kommentare | Zeilennummern | Midnight |
main.cpp
001 /* Author Malte Pagel */
002
003
004 #include <cstdlib>
005 #include <cstdio>
006 #include <iostream>
007 #include <stdio.h>
008 #include <time.h>
009
010 using namespace std;
011
012 #include "KnightPosition.h"
013
014
015 #define ASK_USER 1
016
017 #define COL_MIN 5
018 #define COL_MAX 16
019 #define DEFAULT_COLS 8
020
021
022 void ask_user(void);
023
024 char letters[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P' };
025
026 int cols;
027 int column;
028 int row;
029
030
031 void ask_user () {
032 int i;
033 char c;
034
035 cout << endl;
036
037 cout << "How many rows resp. columns (" << COL_MIN << " - " << COL_MAX << ")?" << endl;
038 scanf("%d", &i);
039 if ( i < COL_MIN || i > COL_MAX ) {
040 cout << "Invalid value! Taking " << DEFAULT_COLS << endl;
041 cols = DEFAULT_COLS;
042 }
043 else
044 cols = i;
045
046
047 cout << "Start in which column ('A' to '" << (letters[cols - 1]) << "')?" << endl;
048 scanf("%s", &c);
049 i = (int) c - 97;
050 if ( i >= 0 && i < cols )
051 column = i;
052 else {
053 i = (int) c - 65;
054 if ( i >= 0 && i < cols )
055 column = i;
056 else {
057 column = rand() % cols;
058 cout << "Invalid value! Taking " << letters[column] << endl;
059 }
060 }
061
062
063 cout << "Start in which row (1 to " << cols << ")?" << endl;
064 scanf("%d", &i);
065 if ( i > 0 && i <= cols )
066 row = i - 1;
067 else {
068 row = rand() % cols;
069 cout << "Invalid value! Taking " << (row + 1) << endl;
070 }
071 }
072
073
074 int main (int argc, char** argv) {
075
076 KnightPosition * start_position;
077 KnightPosition *** complete_collection;
078 int i, j;
079
080 time_t t;
081 time(&t);
082 srand((unsigned int) t);
083
084 if ( ASK_USER )
085 ask_user();
086 else {
087 cols = DEFAULT_COLS;
088 column = rand() % cols;
089 row = rand() % cols;
090 }
091
092 /**
093 * Matrix of pointers needed for a moment
094 */
095 complete_collection = new KnightPosition**[cols];
096 for ( i = 0; i < cols; i++ )
097 complete_collection[i] = new KnightPosition*[cols];
098 for ( i = 0; i < cols; i++ )
099 for ( j = 0; j < cols; j++ )
100 complete_collection[i][j] = NULL;
101
102 /**
103 * 'start_position' is - no one would ever guess this - the field where to start,
104 * temporarily stored at [column][row] in 'complete_collection'
105 */
106 start_position = new KnightPosition(column, row, cols, complete_collection);
107
108 /**
109 * All fields should be initialized; matrix not needed any longer
110 */
111 delete[](complete_collection);
112
113
114 /**
115 * Setting a knight on 'start_position' and invoking path search
116 */
117 start_position->set_knight_and_start_search(NULL);
118
119
120 /**
121 * Preparing show,
122 * cleaning memory
123 */
124 int ** show_collection = new int*[cols];
125 for ( i = 0; i < cols; i++ ) {
126 show_collection[i] = new int[cols];
127 for ( j = 0; j < cols; j++ )
128 show_collection[i][j] = 0;
129 }
130 i = 0;
131 KnightPosition * position = start_position;
132 KnightPosition * position_to_delete;
133 do {
134 show_collection[cols - position->row - 1][position->column] = ++i;
135 position_to_delete = position;
136 if ( position->next_position )
137 position = position->next_position;
138 delete(position_to_delete);
139 }
140 while ( position->next_position );
141 delete(position);
142 show_collection[cols - position->row - 1][position->column] = ++i;
143
144
145 /**
146 * Dont' blame me for not using 'cout' consequently -
147 * formatted output is much more readable
148 */
149 cout << endl;
150 for ( i = 0; i < cols; i++ ) {
151 printf("%2d", (cols - i));
152 cout << " |";
153 for ( j = 0; j < cols; j++ )
154 printf("%5d", show_collection[i][j]);
155 cout << endl;
156 }
157 cout << " ";
158 for ( i = 0; i < cols; i++ )
159 cout << "-----";
160 cout << endl;
161 printf("%4s", " ");
162 for ( i = 0; i < cols; i++ )
163 printf("%5c", letters[i]);
164 cout << endl;
165
166
167 /**
168 * The result should be visible also on windows systems
169 */
170 #ifdef _WIN32
171 char c = 'n';
172 while ( c != 'y' ) {
173 cout << "Quit application [y/n]?" << endl;
174 scanf("%s", &c);
175 }
176 #endif
177
178
179 return 0;
180 }
181
KnightPosition.h
01 // File: KnightPosition.h
02
03 /*
04 * Author: maltepagel
05 *
06 * Created November 2013
07 */
08
09 #ifndef KNIGHTPOSITION_H
10 #define KNIGHTPOSITION_H
11
12 #include <iostream>
13 #include <cmath>
14 #include <cstdlib>
15
16 using namespace std;
17
18
19 /*
20 IMPORTANT: HIGHER VALUES MIGHT BREAK THE STACK
21 */
22 #define MEMORY_LIMIT 4096
23
24
25 class KnightPosition {
26
27 public:
28 KnightPosition(int, int, int, KnightPosition***);
29 virtual ~KnightPosition();
30
31
32 static int knight_count;
33 static int knight_number;
34 static long memory_count;
35
36
37 int has_knight;
38 int column, row;
39 int center_distance;
40
41
42 KnightPosition * next_position;
43
44
45 void set_knight_and_start_search(KnightPosition*);
46 int get_num_possibilities(void);
47 void another_try_from_above(void);
48
49 private:
50 static char letters[];
51
52
53 static int cols;
54
55
56 static int reachable_positions_offset_set;
57
58
59 KnightPosition * previous_position;
60
61
62 struct reachable_position_pointer {
63 KnightPosition * possible_position;
64 int heuristic;
65 struct reachable_position_pointer * next;
66 struct reachable_position_pointer * basic_next;
67 };
68 struct reachable_position_pointer * first_collected_position;
69 struct reachable_position_pointer * last_collected_position;
70
71 struct reachable_position_pointer * first_position_to_try;
72 struct reachable_position_pointer * last_position_to_try;
73
74
75 int lower_or_equal, reachable_positions_offset;
76
77
78 void fill_reachable_positions(KnightPosition***);
79 void add_to_reachable_positions(KnightPosition*);
80 void order_reachable_positions(void);
81 void do_search(void);
82 void go_back(void);
83 };
84
85 #endif /* KNIGHTPOSITION_H */
86
KnightPosition.cpp
001 // File: KnightPosition.cpp
002
003 /*
004 * Author: maltepagel
005 *
006 * Created November 2013
007 */
008
009 #include "KnightPosition.h"
010
011
012 int KnightPosition::knight_count = 0;
013 int KnightPosition::knight_number = 0;
014 int KnightPosition::cols = 0;
015 long KnightPosition::memory_count = 0;
016 char KnightPosition::letters[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P' };
017 int KnightPosition::reachable_positions_offset_set = 0;
018
019 /**
020 * Constructor.
021 * Takes basic values,
022 * invokes building of other knight positions,
023 * memorizes reachable knight positions
024 *
025 * @param <int> column, row [where are we?]
026 * @param <int> num_cols [number rows resp. columns of play table]
027 * @param <KnightPosition***> collection [matrix to temporarily store knight positions]
028 */
029 KnightPosition::KnightPosition(int column, int row, int num_cols, KnightPosition*** collection) {
030
031 collection[column][row] = this;
032
033 this->column = column;
034 this->row = row;
035
036 if ( !cols )
037 cols = num_cols;
038
039 has_knight = 0;
040
041 next_position = NULL;
042 previous_position = NULL;
043
044 first_collected_position = NULL;
045 last_collected_position = NULL;
046
047 /**
048 * Maybe you have to write 'center_distance = abs((float) ((cols - 1) - (2 * column) - (2 * row)));'
049 */
050 center_distance = abs((cols - 1) - (2 * column) - (2 * row));
051
052 if ( !reachable_positions_offset_set ) {
053 if ( column < 4 ) {
054 if ( row < 4 )
055 reachable_positions_offset = 4;
056 else
057 reachable_positions_offset = 6;
058 }
059 else {
060 if ( row < 4 )
061 reachable_positions_offset = 2;
062 else
063 reachable_positions_offset = 0;
064 }
065 reachable_positions_offset_set = 1;
066 }
067
068 fill_reachable_positions(collection);
069
070 knight_count++;
071
072 lower_or_equal = ( rand() % (cols * cols + center_distance + 1 - knight_count) == 0 ) ? 1 : 0;
073
074 //cout << "KnightPosition number " << knight_count << " constructed at " << letters[column] << (row + 1) << endl;
075 }
076
077 /**
078 * Clears all allocated memory
079 */
080 KnightPosition::~KnightPosition() {
081
082 struct reachable_position_pointer * tmp_position, * next_tmp_position;
083
084 if ( !first_collected_position )
085 return;
086
087 tmp_position = first_collected_position->basic_next;
088 while ( tmp_position ) {
089 next_tmp_position = first_collected_position->basic_next->basic_next;
090 first_collected_position->basic_next = next_tmp_position;
091 delete(tmp_position);
092 tmp_position = next_tmp_position;
093 }
094 delete(first_collected_position->basic_next);
095 delete(first_collected_position);
096 first_collected_position = NULL;
097
098 //cout << "KnightPosition " << (cols * cols - --knight_count) << " at " << letters[column] << (row + 1) << " destroyed" << endl;
099 }
100
101 /**
102 * Counts number of possible jumps to free field (i.e. without knight)
103 *
104 * @return <int> [number of possible jumps]
105 */
106 int KnightPosition::get_num_possibilities () {
107 int possibilities = 0;
108
109 if ( !first_collected_position )
110 return 0;
111
112 struct reachable_position_pointer * tmp_position = first_collected_position;
113 while ( tmp_position ) {
114 if ( !tmp_position->possible_position->has_knight )
115 possibilities++;
116 tmp_position = tmp_position->basic_next;
117 }
118
119 return possibilities;
120 }
121
122 /**
123 * Important heuristic: positions with more possible moves are worse
124 * Less important heuristic: positions near the center are worse
125 */
126 void KnightPosition::order_reachable_positions () {
127
128 int possibilities, success;
129
130 struct reachable_position_pointer * tmp_position_to_add;
131 struct reachable_position_pointer * tmp_tmp_position;
132 struct reachable_position_pointer * tmp_tmp_tmp_position;
133
134 struct reachable_position_pointer * 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->possible_position = tmp_position->possible_position;
147 tmp_position_to_add->heuristic = cols * possibilities + tmp_position->possible_position->center_distance;
148 tmp_position_to_add->next = NULL;
149
150 if ( !first_position_to_try ) {
151 first_position_to_try = tmp_position_to_add;
152 last_position_to_try = first_position_to_try;
153 }
154 else {
155 tmp_tmp_position = first_position_to_try;
156 success = 0;
157 while ( tmp_tmp_position && !success ) {
158 if ( tmp_position_to_add->heuristic < tmp_tmp_position->heuristic || (lower_or_equal && tmp_position_to_add->heuristic == tmp_tmp_position->heuristic) ) {
159 if ( tmp_tmp_position == first_position_to_try ) {
160 tmp_position_to_add->next = tmp_tmp_position;
161 first_position_to_try = tmp_position_to_add;
162 success = 1;
163 }
164 else {
165 tmp_tmp_tmp_position = first_position_to_try;
166 while ( tmp_tmp_tmp_position->next != tmp_tmp_position )
167 tmp_tmp_tmp_position = tmp_tmp_tmp_position->next;
168 tmp_position_to_add->next = tmp_tmp_tmp_position->next;
169 tmp_tmp_tmp_position->next = tmp_position_to_add;
170 success = 1;
171 }
172 }
173 tmp_tmp_position = tmp_tmp_position->next;
174 }
175 if ( !success ) {
176 last_position_to_try->next = tmp_position_to_add;
177 last_position_to_try = tmp_position_to_add;
178 }
179 }
180 }
181
182 tmp_position = tmp_position->basic_next;
183 }
184 }
185
186 /**
187 * Jumps to probably best position.
188 * Clears this position from list.
189 * Stops if play table is full
190 */
191 void KnightPosition::do_search () {
192 struct reachable_position_pointer * position_to_try = first_position_to_try;
193
194 next_position = position_to_try->possible_position;
195
196 first_position_to_try = (first_position_to_try->next) ? first_position_to_try->next : NULL;
197
198 if ( knight_number >= (cols * cols - 1) ) {
199 cout << endl;
200 cout << "\t**********" << endl;
201 cout << "\t* SOLVED *" << endl;
202 cout << "\t**********" << endl;
203 cout << endl;
204 return;
205 }
206
207 next_position->set_knight_and_start_search(this);
208 }
209
210 /**
211 * Last jump was bad - try the next best or, if there is none, go back
212 */
213 void KnightPosition::another_try_from_above () {
214 next_position->next_position = NULL;
215
216 if ( !first_position_to_try ) {
217 go_back();
218 return;
219 }
220
221 if ( memory_count > MEMORY_LIMIT || (memory_count && knight_number == 1) ) {
222 if ( knight_number == 1 )
223 cout << "Does not seem to be solvable" << endl;
224 else
225 cout << "Too much recursion, I'm giving up; knights: " << knight_number << " / " << (cols * cols) << endl;
226 return;
227 }
228
229 cout << "I am at " << letters[column] << (row + 1) << " at step " << knight_number << " (" << memory_count << " tries)" << endl;
230 cout << "I came from " << letters[next_position->column] << (next_position->row + 1) << endl;
231 cout << "I want to try " << letters[first_position_to_try->possible_position->column] << (first_position_to_try->possible_position->row + 1) << endl;
232 cout << "---" << endl;
233
234 do_search();
235 }
236
237 /**
238 * Delete this position from list of jumps and go back
239 */
240 void KnightPosition::go_back () {
241 memory_count++;
242 knight_number--;
243 has_knight = 0;
244 previous_position->another_try_from_above();
245 }
246
247 /**
248 * Remembers previous position,
249 * estimates quality of possible jumps,
250 * invokes jumping (if possible)
251 *
252 * @param <KnightPosition*> last_position [position where we came from,
253 * i.e. previous position in list of jumps]
254 */
255 void KnightPosition::set_knight_and_start_search (KnightPosition* last_position) {
256 knight_number++;
257 has_knight = 1;
258 previous_position = last_position;
259
260 last_position_to_try = NULL;
261 first_position_to_try = NULL;
262
263 order_reachable_positions();
264
265 if ( !first_position_to_try ) {
266 go_back();
267 return;
268 }
269
270 do_search();
271 }
272
273 /**
274 * Creates a data collection for each reachable position
275 *
276 * @param <KnightPosition*> position [to add]
277 */
278 void KnightPosition::add_to_reachable_positions (KnightPosition* position) {
279
280 struct reachable_position_pointer * position_data = new reachable_position_pointer;
281
282 position_data->possible_position = position;
283 position_data->heuristic = 0;
284 position_data->next = NULL;
285 position_data->basic_next = NULL;
286
287 if ( !first_collected_position ) {
288 first_collected_position = position_data;
289 last_collected_position = first_collected_position;
290 }
291 else {
292 last_collected_position->basic_next = position_data;
293 last_collected_position = position_data;
294 }
295 }
296 /**
297 * Evaluates possible positions for jumping.
298 * Adds - if not already there - position to 'collection',
299 * invokes putting it to list of reachable positions
300 *
301 * @param <KnightPosition***> collection [matrix to temporarily store knight positions]
302 */
303 void KnightPosition::fill_reachable_positions (KnightPosition*** collection) {
304 int x_move[] = { 1, 2, 2, 1, -1, -2, -2, -1, 1, 2, 2, 1, -1, -2 };
305 int y_move[] = { -2, -1, 1, 2, 2, 1, -1, -2, -2, -1, 1, 2, 2, 1 };
306 int i, x, y;
307 KnightPosition * tmp_position;
308
309 for ( i = reachable_positions_offset; i < (8 + reachable_positions_offset); i++ ) {
310 x = column + x_move[i];
311 y = row + y_move[i];
312
313 if ( x < 0 || x > (cols - 1) || y < 0 || y > (cols - 1) )
314 continue;
315 if ( !collection[x][y] ) {
316 tmp_position = new KnightPosition(x, y, cols, collection);
317 add_to_reachable_positions(tmp_position);
318 }
319 else
320 add_to_reachable_positions(collection[x][y]);
321 }
322 }
323