| Inhalt | Code | Beispiel A* | |
| Beispiel IDA* |
| C | PHP | Kommentare | Zeilennummern | Midnight |
common.h
01 /* Author Malte Pagel */
02
03
04 #ifndef Memory_Balanced_A_Star_common_h
05 #define Memory_Balanced_A_Star_common_h
06
07
08 #define ROWS 3
09 #define COLS 3
10
11 #define DEBUGGING 1
12
13 #define IDA 1
14
15 #define OFFSET 0
16 #define SPEED 0
17
18
19 /*
20 'rows', 'cols', and 'ida_usage' take
21 ROWS, COLS, and IDA as default values
22 */
23 int rows, cols;
24 int ida_usage;
25
26 /*
27 'puzzle_line' and 'solved_puzzle_line'
28 are quasi arrays, but built dynamically
29 */
30 int * puzzle_line;
31 int * solved_puzzle_line;
32 int black_piece_number;
33 int black_piece_position;
34 int solved_black_piece_position;
35 /*
36 quasi boolean
37 */
38 int solution_found;
39
40 /*
41 to store whole puzzle situation (more memory, less calculation)
42 */
43 struct puzzle_situation {
44 int * piece_numbers;
45 int black_piece_position;
46 int num_moves_made;
47 int * moves_made;
48 int last_piece_number;
49 };
50
51 /*
52 made moves to reconstruct puzzle situation (more calculation, less memory)
53 */
54 struct reduced_situation {
55 int num_moves_made;
56 int * moves_made;
57 struct reduced_situation *next;
58 };
59 /*
60 puzzle situation pointers for list
61 */
62 struct reduced_situation * first_reduced_situation;
63 struct reduced_situation * last_reduced_situation;
64
65 /*
66 debug and control only
67 */
68 long heap_count;
69 int actual_stack_count;
70 long max_stack_count;
71
72
73 #endif
74
main.c
001 //
002 // main.c
003 // Memory_Balanced_A_Star
004 //
005 // Created 2013/10 by Malte Pagel
006 // Copyright (c) 2013 Malte Pagel. All rights reserved.
007 //
008
009
010 #include <stdio.h>
011
012 #include <time.h>
013
014
015 #include "common.h"
016 #include "debug.h"
017 #include "build_basic.h"
018 #include "memory_management.h"
019 #include "algorithms.h"
020
021
022 void cleanup(void);
023
024
025 /**
026 * Should be done automatically
027 */
028 void cleanup (void) {
029 free(puzzle_line);
030 free(solved_puzzle_line);
031
032 long deleted = 0;
033 struct reduced_situation* actual_situation_pointer;
034 while ( first_reduced_situation ) {
035
036 actual_situation_pointer = first_reduced_situation;
037
038 first_reduced_situation = first_reduced_situation->next;
039
040 free(actual_situation_pointer->moves_made);
041 free(actual_situation_pointer);
042
043 deleted++;
044 }
045 if ( deleted )
046 printf( "%li momorized moves deleted \n", deleted );
047 }
048
049
050
051 /**
052 * Starting point
053 *
054 * @param <int> argc [up to 3]
055 * @param <const char*> argv [rows, columns, IDA*]
056 * @return <int> [hopefully 0]
057 */
058 int main (int argc, const char * argv[]) {
059
060 if ( argc == 2 ) {
061 printf( "\n\t" "USAGE:" "\n" );
062 printf( "\t\t" "./Memory_Balanced_A_Star" "\n" );
063 printf( "\t\t " "(same as " "'./Memory_Balanced_A_Star 3 3 1'" ")" "\n" );
064 printf( "\n\t" "OR" "\n" );
065 printf( "\t\t" "./Memory_Balanced_A_Star" "[ROWS] [COLS]" "\n" );
066 printf( "\t\t " "(where [ROWS] and [COLS] should be positive integer numbers)" "\n" );
067 printf( "\n\t" "OR" "\n" );
068 printf( "\t\t" "./Memory_Balanced_A_Star" "[ROWS] [COLS] [0]" "\n" );
069 printf( "\t\t " "(where [ROWS] and [COLS] should be positive integer numbers)" "\n" );
070 printf( "\t\t " "(and [0] switches the iterative deepening search off)" "\n" );
071 printf( "\n\n" );
072 return 0;
073 }
074
075 if ( argc > 2 ) {
076 rows = strtod(argv[1], NULL);
077 cols = strtod(argv[2], NULL);
078 }
079 else {
080 rows = ROWS;
081 cols = COLS;
082 }
083 if ( argc > 3 )
084 ida_usage = strtod(argv[3], NULL);
085 else
086 ida_usage = IDA;
087
088 first_reduced_situation = NULL;
089 last_reduced_situation = NULL;
090
091 /*
092 Begging for true random values
093 */
094 time_t t;
095 time(&t);
096 srand((unsigned int) t);
097
098
099 /*
100 Creating basic situation
101 */
102 int total_length = rows * cols;
103
104 puzzle_line = malloc(total_length * sizeof(int));
105 set_target(puzzle_line);
106 set_black_piece_position();
107 solved_black_piece_position = black_piece_position;
108
109
110 solved_puzzle_line = malloc(total_length * sizeof(int));
111 memcpy(solved_puzzle_line, puzzle_line, (total_length * sizeof(int)));
112
113
114 /*
115 Randomization
116 */
117 int is_even = is_puzzle_even();
118 shuffle_a_lot(is_even);
119
120
121 show_puzzle(puzzle_line);
122
123
124 /*
125 Basic values
126 */
127 solution_found = 0;
128 actual_stack_count = 0;
129 max_stack_count = 0;
130 heap_count = 0;
131
132 /*
133 Search for solution
134 */
135 struct puzzle_situation begin = create_puzzle_situation(puzzle_line, black_piece_position, 0, NULL);
136 explore_list(begin);
137
138
139 cleanup();
140
141
142 return 0;
143 }
144
145
algorithms.h
01 //
02 // algorithms.h
03 // Memory_Balanced_A_Star
04 //
05 // Created 2013/10 by Malte Pagel
06 // Copyright (c) 2013 Malte Pagel. All rights reserved.
07 //
08
09 #ifndef Memory_Balanced_A_Star_algorithms_h
10 #define Memory_Balanced_A_Star_algorithms_h
11
12
13 #include <stdio.h>
14 #include <stdlib.h>
15
16 #include "common.h"
17 #include "memory_management.h"
18
19
20 int test_if_solved(int*);
21 int is_a_good_move(int black_position, int moving_piece_position, int moving_piece_number);
22 struct puzzle_situation reconstruct_puzzle_situation(struct reduced_situation*);
23 void explore_list(struct puzzle_situation);
24 void add_to_list(int, int*);
25 void stack_search(struct puzzle_situation, int, int, int);
26 int eventually_continue_search(struct puzzle_situation, int, int, int, int);
27 void swap_pieces(int*, int, int);
28
29 int impossible1(int, int);
30
31
32 #endif
33
algorithms.c
001 //
002 // algorithms.c
003 // Memory_Balanced_A_Star
004 //
005 // Created 2013/10 by Malte Pagel
006 // Copyright (c) 2013 Malte Pagel. All rights reserved.
007 //
008
009
010 #include "algorithms.h"
011
012
013
014 /**
015 * Prooves a given puzzle situation against
016 * global puzzle situation 'solved_puzzle_line'
017 *
018 * @param <int*> puzzle [pointer; used as array]
019 * @return <int> [quasi boolean]
020 */
021 int test_if_solved (int* puzzle) {
022 int i;
023 int solved = 1;
024
025 for ( i = 0; i < (rows * cols); i++ ) {
026 if ( puzzle[i] && puzzle[i] != solved_puzzle_line[i] ) {
027 solved = 0;
028 break;
029 }
030 }
031
032 return solved;
033 }
034
035 /**
036 * Is black piece closer to wanted position than given piece?
037 *
038 * @param <int> black_position [inside linearized puzzle]
039 * @param <int> moving_piece_position [inside linearized puzzle]
040 * @param <int> moving_piece_number [to compare with wanted puzzle situation.
041 * Could be extended with solved_puzzle_line[moving_piece_number - 1]
042 * if other than 'common' solution is wanted.]
043 * @return int [quasi boolean]
044 */
045 int is_a_good_move (int black_position, int moving_piece_position, int moving_piece_number) {
046 int black_position_count, moving_piece_position_count;
047
048 black_position_count = abs( (black_position / cols) - ((solved_puzzle_line[moving_piece_number - 1] - 1) / cols) );
049 black_position_count += abs( (black_position % cols) - ((solved_puzzle_line[moving_piece_number - 1] - 1) % cols) );
050
051 moving_piece_position_count = abs( (moving_piece_position / cols) - ((solved_puzzle_line[moving_piece_number - 1] - 1) / cols) );
052 moving_piece_position_count += abs( (moving_piece_position % cols) - ((solved_puzzle_line[moving_piece_number - 1] - 1) % cols) );
053
054 return (black_position_count < moving_piece_position_count);
055 }
056
057 /**
058 * Constructs complete puzzle situation from start situation and made moves
059 *
060 * @param <struct reduced_situation*> reducted
061 * @return <struct puzzle_situation>
062 */
063 struct puzzle_situation reconstruct_puzzle_situation (struct reduced_situation* reducted) {
064
065 int i, j, piece_position;
066
067 struct puzzle_situation reconstructed = create_puzzle_situation(puzzle_line, black_piece_position, reducted->num_moves_made, reducted->moves_made);
068
069 for ( i = 0; i < reducted->num_moves_made; i++ ) {
070 for ( j = 0; j < (cols * rows); j++ ) {
071 if ( reconstructed.piece_numbers[j] == reducted->moves_made[i] ) {
072 piece_position = j;
073 break;
074 }
075 }
076 swap_pieces(reconstructed.piece_numbers, reconstructed.black_piece_position, piece_position);
077 reconstructed.black_piece_position = piece_position;
078 }
079
080
081 return reconstructed;
082 }
083
084 /**
085 * If IDA*:
086 * Starts 'stack_search()' with increasing failure tolerance
087 * If A*:
088 * Starts 'stack_search()' with each puzzle situation from list
089 *
090 * @param <struct puzzle_situation> begin
091 */
092 void explore_list (struct puzzle_situation begin) {
093
094 long explored_count = 0;
095 int search_deep = OFFSET;
096
097 struct reduced_situation* actual_situation_pointer;
098 struct puzzle_situation copied_begin;
099
100 if ( !ida_usage )
101 stack_search(begin, 1, 0, 0);
102 else {
103 while ( !solution_found ) {
104 copied_begin = copy_puzzle_situation(begin);
105 actual_stack_count = 0;
106 if ( DEBUGGING )
107 printf( "Allowed 'bad moves': %d \t | \t max simultaneous stack calls used: %li \n", search_deep, max_stack_count );
108 stack_search(copied_begin, 1, search_deep, 1);
109 search_deep += 1 + SPEED;
110 }
111 }
112
113
114 while ( !solution_found && first_reduced_situation ) {
115
116 actual_situation_pointer = first_reduced_situation;
117
118 struct puzzle_situation reconstructed = reconstruct_puzzle_situation(actual_situation_pointer);
119 actual_stack_count = 0;
120 stack_search(reconstructed, 0, 0, 0);
121
122 first_reduced_situation = first_reduced_situation->next;
123
124 free(actual_situation_pointer->moves_made);
125 free(actual_situation_pointer);
126
127 explored_count++;
128 heap_count--;
129 }
130
131 printf( "USED MEMORY \t heap: %li(%li), stack: %li\n", explored_count, heap_count, max_stack_count );
132 }
133
134 /**
135 * Allocates memory for given collection of moves and pushes it to end of list
136 *
137 * @param <int> num_moves_made
138 * @param <int*> moves_made
139 */
140 void add_to_list (int num_moves_made, int* moves_made) {
141
142 struct reduced_situation* situation_pointer;
143
144 if ( !(situation_pointer = malloc(sizeof(struct reduced_situation))) ) {
145 fprintf( stderr, "NOT ENOUGH MEMORY TO CONTINUE!!!\n" );
146 return;
147 }
148 situation_pointer->num_moves_made = num_moves_made;
149 situation_pointer->moves_made = moves_made;
150 situation_pointer->next = NULL;
151
152 if ( !first_reduced_situation ) {
153 first_reduced_situation = situation_pointer;
154 last_reduced_situation = first_reduced_situation;
155 }
156 else {
157 last_reduced_situation->next = situation_pointer;
158 last_reduced_situation = situation_pointer;
159 }
160
161 heap_count++;
162 }
163
164 /**
165 * Tests if move up, to right, down, or to left is possible.
166 * Tests if move would bring piece closer to target.
167 * Calls itself recursevely with respective move if
168 * - move would bring piece closer and 'good_moves' is non-zero
169 * - move would not bring piece closer and 'good_moves' is zero
170 * - 'allowed_faults' is non-zero
171 * Calls 'test_if_solved()' if situation cannot be increased directly.
172 * Calls 'add_to_list()' if good_moves is non-zero and not IDA*
173 *
174 * @param <struct puzzle_situation> situation
175 * @param <int> good_moves [quasi boolean]
176 * @param <int> allowed_faults
177 * @param <int> ida [quasi boolean]
178 */
179 void stack_search (struct puzzle_situation situation, int good_moves, int allowed_faults, int ida) {
180
181 int i, moving_piece_position;
182
183 int black_position = situation.black_piece_position;
184 int found_something_good = 0;
185
186
187 actual_stack_count++;
188 if ( actual_stack_count > max_stack_count )
189 max_stack_count = actual_stack_count;
190
191
192 // move black piece up, other piece down
193 if ( (black_position - cols) >= 0 && !solution_found ) {
194 moving_piece_position = black_position - cols;
195
196 if ( eventually_continue_search(situation, good_moves, moving_piece_position, allowed_faults, ida) )
197 found_something_good = 1;
198 }
199
200 // move black piece to right, other piece to left
201 if ( (black_position % cols) != (cols - 1) && !solution_found ) {
202 moving_piece_position = black_position + 1;
203
204 if ( eventually_continue_search(situation, good_moves, moving_piece_position, allowed_faults, ida) )
205 found_something_good = 1;
206 }
207
208 // move black piece down, other piece up
209 if ( (black_position + cols) < (cols * rows) && !solution_found ) {
210 moving_piece_position = black_position + cols;
211
212 if ( eventually_continue_search(situation, good_moves, moving_piece_position, allowed_faults, ida) )
213 found_something_good = 1;
214 }
215
216 // move black piece to left, other piece to right
217 if ( (black_position % cols) != 0 && !solution_found ) {
218 moving_piece_position = black_position - 1;
219
220 if ( eventually_continue_search(situation, good_moves, moving_piece_position, allowed_faults, ida) )
221 found_something_good = 1;
222 }
223
224
225 if ( good_moves && !found_something_good ) {
226 if ( test_if_solved(situation.piece_numbers) ) {
227 solution_found = 1;
228 printf( "THIS IS THE SOLUTION: (%d moves)\n", situation.num_moves_made );
229 //show_puzzle(situation.piece_numbers);
230 for ( i = 0; i < situation.num_moves_made; i++ )
231 printf( "%d ", situation.moves_made[i] );
232 printf( "\n\n" );
233 }
234 }
235
236
237 int* the_moves_made = destroy_puzzle_situation_content(situation);
238 if ( good_moves && !allowed_faults && !ida )
239 add_to_list(situation.num_moves_made, the_moves_made);
240 else
241 free(the_moves_made);
242 }
243
244 /**
245 * Taking back a move never leads to shortest solution
246 *
247 * @param <int> value1
248 * @param <int> value2
249 * @return <int> [quasi boolean]
250 */
251 int impossible1 (int value1, int value2) {
252 return (value1 == value2);
253 }
254
255 /**
256 * Does all the stuff that is equal for moving up, to right, down, or to left
257 *
258 * @param <struct puzzle_situation situation> situation
259 * @param <int> good_moves
260 * @param <int> moving_piece_position
261 * @param <int> allowed_faults
262 * @param <int> ida [quasi boolean]
263 * @return <int> [quasi boolean]
264 */
265 int eventually_continue_search (struct puzzle_situation situation, int good_moves, int moving_piece_position, int allowed_faults, int ida) {
266
267 int better;
268 struct puzzle_situation next_situation;
269 int found_something_good = 0;
270
271
272 if ( impossible1(situation.piece_numbers[moving_piece_position], situation.last_piece_number) )
273 return found_something_good;
274
275
276 better = is_a_good_move(situation.black_piece_position, moving_piece_position, situation.piece_numbers[moving_piece_position]);
277 if ( good_moves == better || (good_moves && allowed_faults) ) {
278 if ( good_moves && !better )
279 allowed_faults--;
280 found_something_good = 1;
281 next_situation = extended_copy(situation, moving_piece_position);
282 stack_search(next_situation, 1, allowed_faults, ida);
283 }
284
285
286 return found_something_good;
287 }
288
289 /**
290 * Swap content at position first_index with
291 * content at position second_index in referenced (linearized) puzzle
292 *
293 * @param <int*> puzzle [pointer; used as array]
294 * @param <int> first_index
295 * @param <int> second_index
296 */
297 void swap_pieces (int* puzzle, int first_index, int second_index) {
298 int tmp_value;
299
300 if ( first_index == second_index )
301 return;
302
303 tmp_value = puzzle[second_index];
304 puzzle[second_index] = puzzle[first_index];
305 puzzle[first_index] = tmp_value;
306 }
307
debug.h
01 //
02 // debug.h
03 // Memory_Balanced_A_Star
04 //
05 // Created 2013/10 by Malte Pagel
06 // Copyright (c) 2013 Malte Pagel. All rights reserved.
07 //
08
09 #ifndef Memory_Balanced_A_Star_debug_h
10 #define Memory_Balanced_A_Star_debug_h
11
12
13
14 #include <stdio.h>
15
16 #include "common.h"
17
18
19 void show_puzzle(int*);
20 void show_puzzle_line(int*);
21 void show_numeric(char[], int);
22
23
24
25 #endif
26
debug.c
01 //
02 // debug.c
03 // Memory_Balanced_A_Star
04 //
05 // Created 2013/10 by Malte Pagel
06 // Copyright (c) 2013 Malte Pagel. All rights reserved.
07 //
08
09
10 #include "debug.h"
11
12
13 /**
14 * Shows puzzle as rectangle
15 *
16 * @param <int*> puzzle [pointer; used as array]
17 */
18 void show_puzzle (int* puzzle) {
19 int i;
20 int total_length = rows * cols;
21
22 for ( i = 0; i < total_length; i++ ) {
23 printf( "\t%d", puzzle[i] );
24 if ( ((i + 1) % cols) == 0 )
25 printf( "\n" );
26 }
27 }
28 /**
29 * Shows puzzle as line
30 *
31 * @param <int*> puzzle [pointer; used as array]
32 */
33 void show_puzzle_line (int* puzzle) {
34 int i;
35 int total_length = rows * cols;
36
37 for ( i = 0; i < total_length; i++ )
38 printf( "\t%d", puzzle[i] );
39 printf( "\n" );
40 }
41 /**
42 * Easy debugging
43 *
44 * @param <char[]> message
45 * @param <int> value
46 */
47 void show_numeric (char message[], int value) {
48 printf("\t%s: %d\n", message, value);
49 }
50
build_basic.h
01 //
02 // build_basic.h
03 // Memory_Balanced_A_Star
04 //
05 // Created 2013/10 by Malte Pagel
06 // Copyright (c) 2013 Malte Pagel. All rights reserved.
07 //
08
09 #ifndef Memory_Balanced_A_Star_build_basic_h
10 #define Memory_Balanced_A_Star_build_basic_h
11
12
13
14 #include <stdlib.h>
15
16 #include "common.h"
17 #include "algorithms.h"
18
19
20 void set_target(int*);
21 void set_black_piece_position(void);
22 int is_puzzle_even(void);
23 int is_puzzle_solvable(int*, int, int);
24 void shuffle_a_lot(int);
25
26
27
28 #endif
29
build_basic.c
001 //
002 // build_basic.c
003 // Memory_Balanced_A_Star
004 //
005 // Created 2013/10 by Malte Pagel
006 // Copyright (c) 2013 Malte Pagel. All rights reserved.
007 //
008
009
010 #include "build_basic.h"
011
012
013 /**
014 * INITIAL FILL
015 * Numbers from 1 to (rows * cols)
016 *
017 * @param <int*> puzzle [pointer; used as array]
018 */
019 void set_target (int* puzzle) {
020 int i;
021 int total_length = rows * cols;
022
023 for ( i = 0; i < total_length; i++ )
024 puzzle[i] = i + 1;
025 }
026
027 /**
028 * Declaring one of the puzzle_line's pieces
029 * as empty (chosen by random)
030 */
031 void set_black_piece_position (void) {
032 black_piece_position = rand() % (rows * cols);
033 black_piece_number = puzzle_line[black_piece_position];
034 puzzle_line[black_piece_position] = 0;
035 }
036
037 /**
038 * Analyzing target situation:
039 * prooving parity
040 *
041 * @return <int> [quasi boolean]
042 */
043 int is_puzzle_even (void) {
044 int n2 = (cols % 2 == 0) ? (black_piece_position / cols + 1) : 0;
045
046 return (n2 % 2 == 0) ? 1 : 0;
047 }
048
049 /**
050 * Analyzing shuffled situation:
051 * comparing shuffled situation's parity with target situation's parity
052 *
053 * @param <int*> new_puzzle [pointer; used as array]
054 * @param <int> even [quasi boolean]
055 * @param <int> black_pos
056 * @return <int> [quasi boolean]
057 */
058 int is_puzzle_solvable (int* new_puzzle, int even, int black_pos) {
059 int i, j, n1, tmp_is_even;
060 int total_length = rows * cols;
061 int n2 = (cols % 2 == 0) ? (black_pos / cols + 1) : 0;
062
063 n1 = 0;
064 for ( i = 0; i < total_length; i++ ) {
065 for ( j = 0; j < i; j++ ) {
066 if ( new_puzzle[i] < new_puzzle[j] && new_puzzle[i] != 0 && new_puzzle[j] != 0 ) {
067 n1++;
068 }
069 }
070 }
071
072 tmp_is_even = ((n1 + n2) % 2 == 0);
073
074 return (even == tmp_is_even);
075 }
076
077 /**
078 * Completely randomization.
079 * Missing number (due to empty space) will be kept
080 *
081 * @param <int> is_even [quasi boolean]
082 */
083 void shuffle_a_lot (int is_even) {
084 int index, random_index, tmp_black_piece_position;
085 int * new_puzzle;
086 int total_length = rows * cols;
087
088 new_puzzle = malloc(total_length * sizeof(int));
089
090 set_target(new_puzzle);
091
092 new_puzzle[black_piece_position] = 0;
093
094 for ( index = 0; index < total_length; index++ ) {
095 random_index = rand() % total_length;
096 swap_pieces(new_puzzle, index, random_index);
097 }
098
099 for ( index = 0; index < total_length; index++ )
100 if ( new_puzzle[index] == 0 )
101 tmp_black_piece_position = index;
102
103 if ( !is_puzzle_solvable(new_puzzle, is_even, tmp_black_piece_position) ) {
104 free(new_puzzle);
105 shuffle_a_lot(is_even);
106 return;
107 }
108
109 black_piece_position = tmp_black_piece_position;
110
111 for ( index = 0; index < total_length; index++ )
112 puzzle_line[index] = new_puzzle[index];
113
114 free(new_puzzle);
115 }
116
memory_management.h
01 //
02 // memory_management.h
03 // Memory_Balanced_A_Star
04 //
05 // Created 2013/10 by Malte Pagel
06 // Copyright (c) 2013 Malte Pagel. All rights reserved.
07 //
08
09 #ifndef Memory_Balanced_A_Star_memory_management_h
10 #define Memory_Balanced_A_Star_memory_management_h
11
12
13
14 #include <stdlib.h>
15 #include <string.h>
16
17 #include "common.h"
18 #include "algorithms.h"
19
20
21
22
23
24 struct puzzle_situation create_puzzle_situation(int*, int, int, int*);
25 int* destroy_puzzle_situation_content(struct puzzle_situation);
26 struct puzzle_situation copy_puzzle_situation(struct puzzle_situation);
27 struct puzzle_situation extended_copy(struct puzzle_situation, int);
28
29
30
31 #endif
32
memory_management.c
01 //
02 // memory_management.c
03 // Memory_Balanced_A_Star
04 //
05 // Created 2013/10 by Malte Pagel
06 // Copyright (c) 2013 Malte Pagel. All rights reserved.
07 //
08
09
10 #include "memory_management.h"
11
12
13 /**
14 * Something like a constructor.
15 * Allocates memory for all necessary data of puzzle situation,
16 * creates it from given parameters and returns it
17 *
18 * @param <int*> pieces
19 * @param <int> black_pos
20 * @param <int> num_moves
21 * @param <int*> moves
22 * @return <struct puzzle_situation>
23 */
24 struct puzzle_situation create_puzzle_situation (int* pieces, int black_pos, int num_moves, int* moves) {
25 struct puzzle_situation new_puzzle_situation;
26 new_puzzle_situation.piece_numbers = malloc((rows * cols) * sizeof(int));
27 memcpy(new_puzzle_situation.piece_numbers, pieces, (rows * cols * sizeof(int)));
28 new_puzzle_situation.black_piece_position = black_pos;
29 new_puzzle_situation.num_moves_made = num_moves;
30 new_puzzle_situation.moves_made = malloc(num_moves * sizeof(int));
31 memcpy(new_puzzle_situation.moves_made, moves, num_moves * sizeof(int));
32 new_puzzle_situation.last_piece_number = ( num_moves ) ? new_puzzle_situation.moves_made[num_moves - 1] : -1;
33
34 return new_puzzle_situation;
35 }
36 /**
37 * (Quasi-) Destructor.
38 * Does not free the whole puzzle_situation
39 * (because puzzle_situation probably is not a pointer).
40 * Returns property 'moves_made' for later usage
41 * (must be destroyed seperately)
42 *
43 * @param <struct puzzle_situation> situation_to_destroy
44 * @return <int*> [pointer to made moves]
45 */
46 int* destroy_puzzle_situation_content (struct puzzle_situation situation_to_destroy) {
47 free(situation_to_destroy.piece_numbers);
48
49 return situation_to_destroy.moves_made;
50 }
51 /**
52 * Copy constructor (i.e. true value from pointer)
53 *
54 * @param <struct puzzle_situation> situation_to_copy
55 * @return <struct puzzle_situation>
56 */
57 struct puzzle_situation copy_puzzle_situation (struct puzzle_situation situation_to_copy) {
58 struct puzzle_situation copied_puzzle_situation = create_puzzle_situation(situation_to_copy.piece_numbers, situation_to_copy.black_piece_position, situation_to_copy.num_moves_made, situation_to_copy.moves_made);
59
60 return copied_puzzle_situation;
61 }
62
63 /**
64 * Extended copy constructor (one more move).
65 * Swapping 'swapping_position' and 'black_piece_position'
66 *
67 * @param <struct puzzle_situation> situation_to_copy
68 * @param <int> swapping_position
69 * @return <struct puzzle_situation>
70 */
71 struct puzzle_situation extended_copy (struct puzzle_situation situation_to_copy, int swapping_position) {
72 struct puzzle_situation copied_extended_puzzle_situation = create_puzzle_situation(situation_to_copy.piece_numbers, situation_to_copy.black_piece_position, (situation_to_copy.num_moves_made + 1), situation_to_copy.moves_made);
73
74 copied_extended_puzzle_situation.last_piece_number = situation_to_copy.piece_numbers[swapping_position];
75 copied_extended_puzzle_situation.black_piece_position = swapping_position;
76 copied_extended_puzzle_situation.moves_made[situation_to_copy.num_moves_made] = situation_to_copy.piece_numbers[swapping_position];
77
78 swap_pieces(copied_extended_puzzle_situation.piece_numbers, situation_to_copy.black_piece_position, swapping_position);
79
80 return copied_extended_puzzle_situation;
81 }
82