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