| 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 complete_collection = new KnightPosition**[cols];
094 for ( i = 0; i < cols; i++ )
095 complete_collection[i] = new KnightPosition*[cols];
096 for ( i = 0; i < cols; i++ )
097 for ( j = 0; j < cols; j++ )
098 complete_collection[i][j] = NULL;
099
100
101 start_position = new KnightPosition(column, row, cols, complete_collection);
102
103
104 delete[](complete_collection);
105
106
107
108 start_position->set_knight_and_start_search(NULL);
109
110
111
112 int ** show_collection = new int*[cols];
113 for ( i = 0; i < cols; i++ ) {
114 show_collection[i] = new int[cols];
115 for ( j = 0; j < cols; j++ )
116 show_collection[i][j] = 0;
117 }
118 i = 0;
119 KnightPosition * position = start_position;
120 KnightPosition * position_to_delete;
121 do {
122 show_collection[cols - position->row - 1][position->column] = ++i;
123 position_to_delete = position;
124 if ( position->next_position )
125 position = position->next_position;
126 delete(position_to_delete);
127 }
128 while ( position->next_position );
129 delete(position);
130 show_collection[cols - position->row - 1][position->column] = ++i;
131
132
133
134 cout << endl;
135 for ( i = 0; i < cols; i++ ) {
136 printf("%2d", (cols - i));
137 cout << " |";
138 for ( j = 0; j < cols; j++ )
139 printf("%5d", show_collection[i][j]);
140 cout << endl;
141 }
142 cout << " ";
143 for ( i = 0; i < cols; i++ )
144 cout << "-----";
145 cout << endl;
146 printf("%4s", " ");
147 for ( i = 0; i < cols; i++ )
148 printf("%5c", letters[i]);
149 cout << endl;
150
151
152
153 #ifdef _WIN32
154 char c = 'n';
155 while ( c != 'y' ) {
156 cout << "Quit application [y/n]?" << endl;
157 scanf("%s", &c);
158 }
159 #endif
160
161
162 return 0;
163 }
164
KnightPosition.h
01 // File: KnightPosition.h
02
03
04
05 #ifndef KNIGHTPOSITION_H
06 #define KNIGHTPOSITION_H
07
08 #include <iostream>
09 #include <cmath>
10 #include <cstdlib>
11
12 using namespace std;
13
14
15
16 #define MEMORY_LIMIT 4096
17
18
19 class KnightPosition {
20
21 public:
22 KnightPosition(int, int, int, KnightPosition***);
23 virtual ~KnightPosition();
24
25
26 static int knight_count;
27 static int knight_number;
28 static long memory_count;
29
30
31 int has_knight;
32 int column, row;
33 int center_distance;
34
35
36 KnightPosition * next_position;
37
38
39 void set_knight_and_start_search(KnightPosition*);
40 int get_num_possibilities(void);
41 void another_try_from_above(void);
42
43 private:
44 static char letters[];
45
46
47 static int cols;
48
49
50 static int reachable_positions_offset_set;
51
52
53 KnightPosition * previous_position;
54
55
56 struct reachable_position_pointer {
57 KnightPosition * possible_position;
58 int heuristic;
59 struct reachable_position_pointer * next;
60 struct reachable_position_pointer * basic_next;
61 };
62 struct reachable_position_pointer * first_collected_position;
63 struct reachable_position_pointer * last_collected_position;
64
65 struct reachable_position_pointer * first_position_to_try;
66 struct reachable_position_pointer * last_position_to_try;
67
68
69 int lower_or_equal, reachable_positions_offset;
70
71
72 void fill_reachable_positions(KnightPosition***);
73 void add_to_reachable_positions(KnightPosition*);
74 void order_reachable_positions(void);
75 void do_search(void);
76 void go_back(void);
77 };
78
79 #endif
80
KnightPosition.cpp
001 // File: KnightPosition.cpp
002
003
004
005 #include "KnightPosition.h"
006
007
008 int KnightPosition::knight_count = 0;
009 int KnightPosition::knight_number = 0;
010 int KnightPosition::cols = 0;
011 long KnightPosition::memory_count = 0;
012 char KnightPosition::letters[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P' };
013 int KnightPosition::reachable_positions_offset_set = 0;
014
015
016 KnightPosition::KnightPosition(int column, int row, int num_cols, KnightPosition*** collection) {
017
018 collection[column][row] = this;
019
020 this->column = column;
021 this->row = row;
022
023 if ( !cols )
024 cols = num_cols;
025
026 has_knight = 0;
027
028 next_position = NULL;
029 previous_position = NULL;
030
031 first_collected_position = NULL;
032 last_collected_position = NULL;
033
034
035 center_distance = abs((cols - 1) - (2 * column) - (2 * row));
036
037 if ( !reachable_positions_offset_set ) {
038 if ( column < 4 ) {
039 if ( row < 4 )
040 reachable_positions_offset = 4;
041 else
042 reachable_positions_offset = 6;
043 }
044 else {
045 if ( row < 4 )
046 reachable_positions_offset = 2;
047 else
048 reachable_positions_offset = 0;
049 }
050 reachable_positions_offset_set = 1;
051 }
052
053 fill_reachable_positions(collection);
054
055 knight_count++;
056
057 lower_or_equal = ( rand() % (cols * cols + center_distance + 1 - knight_count) == 0 ) ? 1 : 0;
058
059 //cout << "KnightPosition number " << knight_count << " constructed at " << letters[column] << (row + 1) << endl;
060 }
061
062
063 KnightPosition::~KnightPosition() {
064
065 struct reachable_position_pointer * tmp_position, * next_tmp_position;
066
067 if ( !first_collected_position )
068 return;
069
070 tmp_position = first_collected_position->basic_next;
071 while ( tmp_position ) {
072 next_tmp_position = first_collected_position->basic_next->basic_next;
073 first_collected_position->basic_next = next_tmp_position;
074 delete(tmp_position);
075 tmp_position = next_tmp_position;
076 }
077 delete(first_collected_position->basic_next);
078 delete(first_collected_position);
079 first_collected_position = NULL;
080
081 //cout << "KnightPosition " << (cols * cols - --knight_count) << " at " << letters[column] << (row + 1) << " destroyed" << endl;
082 }
083
084
085 int KnightPosition::get_num_possibilities () {
086 int possibilities = 0;
087
088 if ( !first_collected_position )
089 return 0;
090
091 struct reachable_position_pointer * tmp_position = first_collected_position;
092 while ( tmp_position ) {
093 if ( !tmp_position->possible_position->has_knight )
094 possibilities++;
095 tmp_position = tmp_position->basic_next;
096 }
097
098 return possibilities;
099 }
100
101
102 void KnightPosition::order_reachable_positions () {
103
104 int possibilities, success;
105
106 struct reachable_position_pointer * tmp_position_to_add;
107 struct reachable_position_pointer * tmp_tmp_position;
108 struct reachable_position_pointer * tmp_tmp_tmp_position;
109
110 struct reachable_position_pointer * tmp_position = first_collected_position;
111
112 while ( tmp_position != NULL ) {
113
114 possibilities = tmp_position->possible_position->get_num_possibilities();
115
116 if ( !tmp_position->possible_position->has_knight ) {
117
118 if ( !possibilities )
119 possibilities = cols * 8;
120
121 tmp_position_to_add = tmp_position;
122 tmp_position_to_add->possible_position = tmp_position->possible_position;
123 tmp_position_to_add->heuristic = cols * possibilities + tmp_position->possible_position->center_distance;
124 tmp_position_to_add->next = NULL;
125
126 if ( !first_position_to_try ) {
127 first_position_to_try = tmp_position_to_add;
128 last_position_to_try = first_position_to_try;
129 }
130 else {
131 tmp_tmp_position = first_position_to_try;
132 success = 0;
133 while ( tmp_tmp_position && !success ) {
134 if ( tmp_position_to_add->heuristic < tmp_tmp_position->heuristic || (lower_or_equal && tmp_position_to_add->heuristic == tmp_tmp_position->heuristic) ) {
135 if ( tmp_tmp_position == first_position_to_try ) {
136 tmp_position_to_add->next = tmp_tmp_position;
137 first_position_to_try = tmp_position_to_add;
138 success = 1;
139 }
140 else {
141 tmp_tmp_tmp_position = first_position_to_try;
142 while ( tmp_tmp_tmp_position->next != tmp_tmp_position )
143 tmp_tmp_tmp_position = tmp_tmp_tmp_position->next;
144 tmp_position_to_add->next = tmp_tmp_tmp_position->next;
145 tmp_tmp_tmp_position->next = tmp_position_to_add;
146 success = 1;
147 }
148 }
149 tmp_tmp_position = tmp_tmp_position->next;
150 }
151 if ( !success ) {
152 last_position_to_try->next = tmp_position_to_add;
153 last_position_to_try = tmp_position_to_add;
154 }
155 }
156 }
157
158 tmp_position = tmp_position->basic_next;
159 }
160 }
161
162
163 void KnightPosition::do_search () {
164 struct reachable_position_pointer * position_to_try = first_position_to_try;
165
166 next_position = position_to_try->possible_position;
167
168 first_position_to_try = (first_position_to_try->next) ? first_position_to_try->next : NULL;
169
170 if ( knight_number >= (cols * cols - 1) ) {
171 cout << endl;
172 cout << "\t**********" << endl;
173 cout << "\t* SOLVED *" << endl;
174 cout << "\t**********" << endl;
175 cout << endl;
176 return;
177 }
178
179 next_position->set_knight_and_start_search(this);
180 }
181
182
183 void KnightPosition::another_try_from_above () {
184 next_position->next_position = NULL;
185
186 if ( !first_position_to_try ) {
187 go_back();
188 return;
189 }
190
191 if ( memory_count > MEMORY_LIMIT || (memory_count && knight_number == 1) ) {
192 if ( knight_number == 1 )
193 cout << "Does not seem to be solvable" << endl;
194 else
195 cout << "Too much recursion, I'm giving up; knights: " << knight_number << " / " << (cols * cols) << endl;
196 return;
197 }
198
199 cout << "I am at " << letters[column] << (row + 1) << " at step " << knight_number << " (" << memory_count << " tries)" << endl;
200 cout << "I came from " << letters[next_position->column] << (next_position->row + 1) << endl;
201 cout << "I want to try " << letters[first_position_to_try->possible_position->column] << (first_position_to_try->possible_position->row + 1) << endl;
202 cout << "---" << endl;
203
204 do_search();
205 }
206
207
208 void KnightPosition::go_back () {
209 memory_count++;
210 knight_number--;
211 has_knight = 0;
212 previous_position->another_try_from_above();
213 }
214
215
216 void KnightPosition::set_knight_and_start_search (KnightPosition* last_position) {
217 knight_number++;
218 has_knight = 1;
219 previous_position = last_position;
220
221 last_position_to_try = NULL;
222 first_position_to_try = NULL;
223
224 order_reachable_positions();
225
226 if ( !first_position_to_try ) {
227 go_back();
228 return;
229 }
230
231 do_search();
232 }
233
234
235 void KnightPosition::add_to_reachable_positions (KnightPosition* position) {
236
237 struct reachable_position_pointer * position_data = new reachable_position_pointer;
238
239 position_data->possible_position = position;
240 position_data->heuristic = 0;
241 position_data->next = NULL;
242 position_data->basic_next = NULL;
243
244 if ( !first_collected_position ) {
245 first_collected_position = position_data;
246 last_collected_position = first_collected_position;
247 }
248 else {
249 last_collected_position->basic_next = position_data;
250 last_collected_position = position_data;
251 }
252 }
253
254 void KnightPosition::fill_reachable_positions (KnightPosition*** collection) {
255 int x_move[] = { 1, 2, 2, 1, -1, -2, -2, -1, 1, 2, 2, 1, -1, -2 };
256 int y_move[] = { -2, -1, 1, 2, 2, 1, -1, -2, -2, -1, 1, 2, 2, 1 };
257 int i, x, y;
258 KnightPosition * tmp_position;
259
260 for ( i = reachable_positions_offset; i < (8 + reachable_positions_offset); i++ ) {
261 x = column + x_move[i];
262 y = row + y_move[i];
263
264 if ( x < 0 || x > (cols - 1) || y < 0 || y > (cols - 1) )
265 continue;
266 if ( !collection[x][y] ) {
267 tmp_position = new KnightPosition(x, y, cols, collection);
268 add_to_reachable_positions(tmp_position);
269 }
270 else
271 add_to_reachable_positions(collection[x][y]);
272 }
273 }
274