1 // This file is part of Freecell Solver. It is subject to the license terms in
2 // the COPYING.txt file found in the top-level directory of this distribution
3 // and at http://fc-solve.shlomifish.org/docs/distro/COPYING.html . No part of
4 // Freecell Solver, including this file, may be copied, modified, propagated,
5 // or distributed except according to the terms contained in the COPYING file.
6 //
7 // Copyright (c) 2000 Shlomi Fish
8 // freecell.c - a module that contains moves of the Freecell-games family.
9
10 #include "scans.h"
11 #include "freecell.h"
12 #include "meta_move_funcs_helpers.h"
13
14 // Throughout this code the following local variables are used to quickly
15 // access the instance's members:
16 //
17 // LOCAL_STACKS_NUM - the number of stacks in the state
18 // LOCAL_FREECELLS_NUM - the number of freecells in the state
19 // sequences_are_built_by - the type of sequences of this board.
20
21 #if MAX_NUM_FREECELLS == 0
DECLARE_PURE_MOVE_FUNCTION(fc_solve_sfs_null_move_func)22 DECLARE_PURE_MOVE_FUNCTION(fc_solve_sfs_null_move_func) {}
23 #endif
24
25 #ifndef FCS_ZERO_FREECELLS_MODE
26 #define CALC_POSITIONS_BY_RANK() \
27 const int8_t *const positions_by_rank = \
28 fc_solve_calc_positions_by_rank_location(soft_thread); \
29 const int suit_positions_by_rank_step = POS_BY_RANK_MAP(POS_BY_RANK_STEP)
30
31 #define POS_BY_RANK_MAP(x) ((x) << 1)
32
33 #ifdef FCS_BREAK_BACKWARD_COMPAT_2
34 #define RAR
35 #endif
36
find_empty_stack(fcs_kv_state raw_state_raw,const int start_from,const int local_stacks_num)37 static inline int find_empty_stack(fcs_kv_state raw_state_raw,
38 const int start_from, const int local_stacks_num)
39 {
40 for (int ret = start_from; ret < local_stacks_num; ret++)
41 {
42 if (fcs_state_col_is_empty(state_key, ret))
43 {
44 return ret;
45 }
46 }
47 return -1;
48 }
49
sort_derived_states(fcs_derived_states_list * const d,const size_t derived_start_idx)50 static inline void sort_derived_states(
51 fcs_derived_states_list *const d, const size_t derived_start_idx)
52 {
53 var_AUTO(start, d->states + derived_start_idx);
54 const_AUTO(limit, d->states + d->num_states);
55
56 for (var_AUTO(b, start + 1); b < limit; b++)
57 {
58 for (var_AUTO(c, b); (c > start) && (c[0].context.i < c[-1].context.i);
59 c--)
60 {
61 const_AUTO(swap_temp, c[-1]);
62 c[-1] = c[0];
63 c[0] = swap_temp;
64 }
65 }
66 }
67 // This function tries to move stack cards that are present at the
68 // top of stacks to the foundations.
DECLARE_MOVE_FUNCTION(fc_solve_sfs_move_top_stack_cards_to_founds)69 DECLARE_MOVE_FUNCTION(fc_solve_sfs_move_top_stack_cards_to_founds)
70 {
71 tests_define_accessors();
72 STACKS__SET_PARAMS();
73
74 for (stack_i stack_idx = 0; stack_idx < LOCAL_STACKS_NUM; stack_idx++)
75 {
76 var_AUTO(col, fcs_state_get_col(state_key, stack_idx));
77 const size_t cards_num = fcs_col_len(col);
78 if (!cards_num)
79 {
80 continue;
81 }
82 // Get the top card in the stack
83 const fcs_card card = fcs_col_get_card(col, cards_num - 1);
84 for (size_t deck = 0; deck < INSTANCE_DECKS_NUM; deck++)
85 {
86 if (fcs_foundation_value(state_key,
87 deck * 4 + fcs_card_suit(card)) != fcs_card_rank(card) - 1)
88 {
89 continue;
90 }
91 sfs_check_state_begin();
92
93 my_copy_stack(stack_idx);
94 fcs_state_pop_col_top(&new_state_key, stack_idx);
95 fcs_increment_foundation(
96 new_state_key, deck * 4 + fcs_card_suit(card));
97
98 fcs_move_stack_non_seq_push(moves,
99 FCS_MOVE_TYPE_STACK_TO_FOUNDATION, stack_idx,
100 deck * 4 + fcs_card_suit(card));
101
102 sfs_check_state_end();
103 break;
104 }
105 }
106 }
107
108 #if MAX_NUM_FREECELLS > 0
109 #ifdef FCS_BREAK_BACKWARD_COMPAT_2
110 #define RAR2
111 #endif
112 // This test moves single cards that are present in the freecells to
113 // the foundations.
DECLARE_MOVE_FUNCTION(fc_solve_sfs_move_freecell_cards_to_founds)114 DECLARE_MOVE_FUNCTION(fc_solve_sfs_move_freecell_cards_to_founds)
115 {
116 tests_define_accessors_no_stacks(tests_state_context_val);
117
118 #ifndef HARD_CODED_NUM_FREECELLS
119 SET_GAME_PARAMS();
120 #endif
121
122 #ifdef RAR2
123 for (int fc = LOCAL_FREECELLS_NUM - 1; fc >= 0; --fc)
124 #else
125 for (int fc = 0; fc < LOCAL_FREECELLS_NUM; ++fc)
126 #endif
127 {
128 const fcs_card card = fcs_freecell_card(state_key, fc);
129
130 if (fcs_card_is_empty(card))
131 {
132 continue;
133 }
134 for (stack_i deck = 0; deck < INSTANCE_DECKS_NUM; deck++)
135 {
136 if (fcs_foundation_value(state_key,
137 deck * 4 + fcs_card_suit(card)) != fcs_card_rank(card) - 1)
138 {
139 continue;
140 }
141 sfs_check_state_begin();
142
143 fcs_empty_freecell(new_state_key, fc);
144 fcs_increment_foundation(
145 new_state_key, deck * 4 + fcs_card_suit(card));
146 fcs_move_stack_non_seq_push(moves,
147 FCS_MOVE_TYPE_FREECELL_TO_FOUNDATION, (size_t)fc,
148 deck * 4 + fcs_card_suit(card));
149
150 sfs_check_state_end();
151 break;
152 }
153 }
154 }
155 #endif
156
157 typedef struct
158 {
159 int src_idx;
160 bool is_col;
161 } empty_two_cols_ret;
162
163 // This function empties two stacks from the new state into freeeclls and empty
164 // columns
empty_two_cols_from_new_state(const fcs_soft_thread * const soft_thread GCC_UNUSED,fcs_kv_state * const kv_ptr_new_state SFS__PASS_MOVE_STACK (fcs_move_stack * const moves_ptr),const int cols_indexes[3],const int_fast16_t num_cards_1,const int_fast16_t num_cards_2)165 static inline empty_two_cols_ret empty_two_cols_from_new_state(
166 const fcs_soft_thread *const soft_thread GCC_UNUSED,
167 fcs_kv_state *const kv_ptr_new_state SFS__PASS_MOVE_STACK(
168 fcs_move_stack *const moves_ptr),
169 const int cols_indexes[3], const int_fast16_t num_cards_1,
170 const int_fast16_t num_cards_2)
171 {
172 empty_two_cols_ret ret = {.src_idx = -1, .is_col = false};
173
174 int_fast16_t num_cards_to_move_from_columns[3] = {
175 num_cards_1, num_cards_2, -1};
176
177 const int *col_idx = cols_indexes;
178 int_fast16_t *col_num_cards = num_cards_to_move_from_columns;
179
180 #if ((!defined(HARD_CODED_NUM_FREECELLS)) || (!defined(HARD_CODED_NUM_STACKS)))
181 SET_INSTANCE_GAME_PARAMS(fcs_st_instance(soft_thread));
182 #endif
183
184 #ifdef INDIRECT_STACK_STATES
185 fcs_card *const indirect_stacks_buffer =
186 HT_FIELD(soft_thread->hard_thread, indirect_stacks_buffer);
187 #endif
188
189 const_AUTO(new_key, kv_ptr_new_state->key);
190 #if MAX_NUM_FREECELLS > 0
191 {
192 size_t dest_fc_idx = 0;
193
194 while (1)
195 {
196 while ((*col_num_cards) == 0)
197 {
198 ++col_num_cards;
199 if (*(++col_idx) == -1)
200 {
201 return ret;
202 }
203 }
204
205 // Find a vacant freecell
206 for (; dest_fc_idx < LOCAL_FREECELLS_NUM; ++dest_fc_idx)
207 {
208 if (fcs_freecell_is_empty(*new_key, dest_fc_idx))
209 {
210 break;
211 }
212 }
213 if (dest_fc_idx == LOCAL_FREECELLS_NUM)
214 {
215 // Move on to the stacks.
216 break;
217 }
218
219 const_AUTO(
220 top_card, fcs_state_pop_col_card(new_key, (stack_i)*col_idx));
221 fcs_put_card_in_freecell(*new_key, dest_fc_idx, top_card);
222
223 fcs_move_stack_non_seq_push(moves_ptr,
224 FCS_MOVE_TYPE_STACK_TO_FREECELL, (size_t)*col_idx, dest_fc_idx);
225
226 ret = (empty_two_cols_ret){
227 .src_idx = (int)dest_fc_idx, .is_col = false};
228 --(*col_num_cards);
229 ++dest_fc_idx;
230 }
231 }
232 #endif
233
234 while ((*col_num_cards) == 0)
235 {
236 ++col_num_cards;
237 if (*(++col_idx) == -1)
238 {
239 return ret;
240 }
241 }
242
243 int put_cards_in_col_idx = 0;
244 // Fill the free stacks with the cards below them
245 while (1)
246 {
247 while ((*col_num_cards) == 0)
248 {
249 ++col_num_cards;
250 if (*(++col_idx) == -1)
251 {
252 return ret;
253 }
254 }
255
256 put_cards_in_col_idx = find_empty_stack(
257 *kv_ptr_new_state, put_cards_in_col_idx, LOCAL_STACKS_NUM);
258
259 fcs_copy_stack(*new_key, *(kv_ptr_new_state->val), put_cards_in_col_idx,
260 indirect_stacks_buffer);
261
262 const size_t col_idx_val = (size_t)*col_idx;
263 const_AUTO(top_card, fcs_state_pop_col_card(new_key, col_idx_val));
264 fcs_state_push(new_key, (size_t)put_cards_in_col_idx, top_card);
265
266 fcs_push_1card_seq(
267 moves_ptr, col_idx_val, (size_t)put_cards_in_col_idx);
268
269 ret = (empty_two_cols_ret){
270 .src_idx = put_cards_in_col_idx, .is_col = true};
271 --(*col_num_cards);
272 ++put_cards_in_col_idx;
273 }
274 }
275
calc_num_vacant_slots(const fcs_soft_thread * const soft_thread,const bool is_filled_by_any_card)276 static inline fcs_game_limit calc_num_vacant_slots(
277 const fcs_soft_thread *const soft_thread, const bool is_filled_by_any_card)
278 {
279 return (soft_thread->num_vacant_freecells +
280 (is_filled_by_any_card ? soft_thread->num_vacant_stacks : 0));
281 }
282
283 #if MAX_NUM_FREECELLS > 0
284 #ifndef FCS_BREAK_BACKWARD_COMPAT_2
285 #define FLUT
286 #endif
DECLARE_MOVE_FUNCTION(fc_solve_sfs_move_freecell_cards_on_top_of_stacks)287 DECLARE_MOVE_FUNCTION(fc_solve_sfs_move_freecell_cards_on_top_of_stacks)
288 {
289 MOVE_FUNCS__define_common();
290 HARD__SET_GAME_PARAMS();
291
292 const fcs_game_limit num_vacant_slots =
293 calc_num_vacant_slots(soft_thread, tests__is_filled_by_any_card());
294
295 #ifdef FLUT
296 const size_t derived_start_idx = derived_states_list->num_states;
297 #endif
298
299 CALC_POSITIONS_BY_RANK();
300 // Let's try to put cards in the freecells on top of stacks
301
302 for (stack_i fc = 0; fc < LOCAL_FREECELLS_NUM; fc++)
303 {
304 const fcs_card src_card = fcs_freecell_card(state_key, fc);
305
306 if (!(fcs_card_is_valid(src_card) && (!fcs_card_is_king(src_card))))
307 {
308 continue;
309 }
310 FCS_POS_IDX_TO_CHECK_START_LOOP(src_card)
311 {
312 const int_fast32_t ds = pos_idx_to_check[0];
313 if (ds == -1)
314 {
315 continue;
316 }
317 const int_fast32_t dc = pos_idx_to_check[1];
318
319 const_AUTO(dest_col, fcs_state_get_col(state_key, ds));
320 const int dest_cards_num = fcs_col_len(dest_col);
321 // Let's check if we can put it there
322
323 // Check if the destination card is already below a suitable card
324 const int_fast32_t next_dc = dc + 1;
325 // If dest_cards_num == next_dc then dest_cards_num - next_dc == 0 <= 0 so the
326 // other check can be skipped.
327
328 // We don't need this check because the positions_by_rank
329 // already filters the fcs_is_parent_card check for us.
330 #ifdef FCS_POS_BY_RANK__ENABLE_PARENT_CHECK
331 const fcs_card dest_card = fcs_col_get_card(dest_col, dc);
332 if (!((dest_cards_num == next_dc) ||
333 ((!fcs_is_parent_card(
334 fcs_col_get_card(dest_col, next_dc), dest_card)) &&
335 (dest_cards_num <= next_dc + num_vacant_slots)
336
337 )))
338 #else
339 if (!(dest_cards_num <= next_dc + num_vacant_slots))
340 #endif
341 {
342 continue;
343 }
344 sfs_check_state_begin();
345
346 // Fill the freecells with the top cards
347 my_copy_stack(ds);
348 const int cols_indexes[3] = {(int)ds, -1, -1};
349 empty_two_cols_from_new_state(soft_thread,
350 ptr_new_state SFS__PASS_MOVE_STACK(moves), cols_indexes,
351 (int)(dest_cards_num - dc - 1), 0);
352
353 // Now put the freecell card on top of the stack
354 fcs_state_push(&new_state_key, (stack_i)ds, src_card);
355 fcs_empty_freecell(new_state_key, fc);
356 fcs_move_stack_non_seq_push(
357 moves, FCS_MOVE_TYPE_FREECELL_TO_STACK, fc, (stack_i)ds);
358
359 #ifdef FLUT
360 // This is to preserve the order that the initial (non-optimized)
361 // version of the function used - for backwards-compatibility and
362 // consistency.
363 state_context_value =
364 (int)(((stack_i)ds << 16U) | ((255 - (stack_i)dc) << 8U) | fc);
365 #endif
366
367 sfs_check_state_end();
368 }
369 }
370
371 #ifdef FLUT
372 sort_derived_states(derived_states_list, derived_start_idx);
373 #endif
374 }
375 #endif
376
DECLARE_MOVE_FUNCTION(fc_solve_sfs_move_non_top_stack_cards_to_founds)377 DECLARE_MOVE_FUNCTION(fc_solve_sfs_move_non_top_stack_cards_to_founds)
378 {
379 tests_define_accessors();
380 MOVE_FUNCS__define_empty_stacks_fill();
381 FC__STACKS__SET_PARAMS();
382 const fcs_game_limit num_vacant_slots =
383 calc_num_vacant_slots(soft_thread, tests__is_filled_by_any_card());
384 #ifdef RAR
385 const size_t derived_start_idx = derived_states_list->num_states;
386 #endif
387
388 // Now let's check if a card that is under some other cards can be placed in
389 // the foundations.
390 const_AUTO(num_vacant_slots_plus_1, num_vacant_slots + 1);
391
392 for (stack_i stack_idx = 0; stack_idx < LOCAL_STACKS_NUM; stack_idx++)
393 {
394 var_AUTO(col, fcs_state_get_col(state_key, stack_idx));
395 const int cards_num = fcs_col_len(col);
396 // We start from cards_num-2 because the top card is already covered
397 // by move_top_stack_cards_to_founds.
398 //
399 // Some math:
400 // num_vacant_slots >= cards_num - (c + 1)
401 // c >= cards_num - num_vacant_slots - 1
402 const int c_bottom = max0(cards_num - num_vacant_slots_plus_1);
403 for (int c = cards_num - 2; c >= c_bottom; c--)
404 {
405 const fcs_card card = fcs_col_get_card(col, c);
406
407 for (stack_i deck = 0; deck < INSTANCE_DECKS_NUM; deck++)
408 {
409 const stack_i dest_found = deck * 4 + fcs_card_suit(card);
410 if (fcs_foundation_value(state_key, dest_found) !=
411 fcs_card_rank(card) - 1)
412 {
413 continue;
414 }
415 sfs_check_state_begin();
416 my_copy_stack(stack_idx);
417 const int cols_indexes[3] = {(int)stack_idx, -1, -1};
418
419 empty_two_cols_from_new_state(soft_thread,
420 ptr_new_state SFS__PASS_MOVE_STACK(moves), cols_indexes,
421 cards_num - (c + 1), 0);
422 fcs_state_pop_col_top(&new_state_key, stack_idx);
423 fcs_increment_foundation(new_state_key, dest_found);
424 fcs_move_stack_non_seq_push(moves,
425 FCS_MOVE_TYPE_STACK_TO_FOUNDATION, stack_idx, dest_found);
426 #ifdef RAR
427 #if 1
428 state_context_value =
429 (int)(((size_t)(fcs_card_rank(card)) << 8U) |
430 fcs_card_suit(card));
431 #else
432 state_context_value = card;
433 #endif
434 #endif
435 sfs_check_state_end();
436 #ifdef FCS_BREAK_BACKWARD_COMPAT_2
437 goto end_loop;
438 #else
439 break;
440 #endif
441 }
442 }
443 #ifdef FCS_BREAK_BACKWARD_COMPAT_2
444 end_loop:;
445 #endif
446 }
447 #ifdef RAR
448 sort_derived_states(derived_states_list, derived_start_idx);
449 #endif
450 }
451
DECLARE_MOVE_FUNCTION(fc_solve_sfs_move_stack_cards_to_a_parent_on_the_same_stack)452 DECLARE_MOVE_FUNCTION(
453 fc_solve_sfs_move_stack_cards_to_a_parent_on_the_same_stack)
454 {
455 MOVE_FUNCS__define_common();
456 FC__STACKS__SET_PARAMS();
457 const fcs_game_limit num_vacant_slots_plus_1 =
458 calc_num_vacant_slots(soft_thread, tests__is_filled_by_any_card()) + 1;
459
460 // Now let's try to move a stack card to a parent card which is found
461 // on the same stack.
462 for (stack_i stack_idx = 0; stack_idx < LOCAL_STACKS_NUM; stack_idx++)
463 {
464 var_AUTO(col, fcs_state_get_col(state_key, stack_idx));
465 const int cards_num = fcs_col_len(col);
466 const int start_dc = max0(cards_num - num_vacant_slots_plus_1);
467
468 for (int c = start_dc + 2; c < cards_num; c++)
469 {
470 // Find a card which this card can be put on
471 const fcs_card card = fcs_col_get_card(col, c);
472
473 // Do not move cards that are already found above a suitable parent
474 const int below_c = c - 1;
475 if (fcs_is_parent_card(card, fcs_col_get_card(col, below_c)))
476 {
477 continue;
478 }
479 // Some math:
480 // (dest_cards_num - next_dc <= num_vacant_slots)
481 // dest_cards_num - dc - 1 <= num_vacant_slots
482 // dc >= dest_cards_num - num_vacant_slots - 1
483 #define ds stack_idx
484 // Check if it can be moved to a target on the same stack
485 for (int dc = start_dc; dc < below_c; dc++)
486 {
487 const fcs_card dest_card = fcs_col_get_card(col, dc);
488 const int next_dc = dc + 1;
489 if ((!fcs_is_parent_card(card, dest_card)) ||
490 fcs_is_parent_card(
491 fcs_col_get_card(col, next_dc), dest_card))
492 {
493 continue;
494 }
495 sfs_check_state_begin();
496
497 my_copy_stack(ds);
498 const int cols_indexes[3] = {(int)ds, -1, -1};
499 const empty_two_cols_ret last_dest =
500 empty_two_cols_from_new_state(soft_thread,
501 ptr_new_state SFS__PASS_MOVE_STACK(moves), cols_indexes,
502 // We're moving one extra card
503 cards_num - c, 0);
504
505 empty_two_cols_from_new_state(soft_thread,
506 ptr_new_state SFS__PASS_MOVE_STACK(moves), cols_indexes,
507 below_c - dc, 0);
508
509 fcs_card moved_card;
510 #define s_idx ((stack_i)last_dest.src_idx)
511 #if MAX_NUM_FREECELLS > 0
512 if (last_dest.is_col)
513 #endif
514 {
515 var_AUTO(new_source_col,
516 fcs_state_get_col(new_state_key, s_idx));
517 fcs_col_pop_card(new_source_col, moved_card);
518 fcs_push_1card_seq(moves, s_idx, ds);
519 }
520 #if MAX_NUM_FREECELLS > 0
521 else
522 {
523 moved_card = fcs_freecell_card(new_state_key, s_idx);
524 fcs_empty_freecell(new_state_key, s_idx);
525 fcs_move_stack_non_seq_push(
526 moves, FCS_MOVE_TYPE_FREECELL_TO_STACK, s_idx, ds);
527 }
528 #endif
529 #undef s_idx
530 fcs_state_push(&new_state_key, ds, moved_card);
531
532 sfs_check_state_end();
533 }
534 }
535 }
536 }
537 #undef ds
538
539 #define CALC_num_virtual_vacant_stacks() \
540 (tests__is_filled_by_any_card() ? num_vacant_stacks : 0)
541
542 typedef struct
543 {
544 fcs_cards_column col;
545 int_fast16_t col_len, col_len_minus_1, c, seq_end;
546 FCS_ON_NOT_FC_ONLY(int sequences_are_built_by;)
547 } col_seqs_iter;
548
col_seqs_iter__calc_end(col_seqs_iter * const iter)549 static inline void col_seqs_iter__calc_end(col_seqs_iter *const iter)
550 {
551 FCS_ON_NOT_FC_ONLY(const_SLOT(sequences_are_built_by, iter));
552 const_SLOT(col, iter);
553 for ((*iter).seq_end = (*iter).c; (*iter).seq_end < (*iter).col_len_minus_1;
554 ++((*iter).seq_end))
555 {
556 if (!fcs_is_parent_card(fcs_col_get_card(col, (*iter).seq_end + 1),
557 fcs_col_get_card(col, (*iter).seq_end)))
558 {
559 break;
560 }
561 }
562 }
563
col_seqs_iter__create(fcs_state * const s,const stack_i stack_idx PASS_sequences_are_built_by (const int sequences_are_built_by))564 static inline col_seqs_iter col_seqs_iter__create(
565 fcs_state *const s, const stack_i stack_idx PASS_sequences_are_built_by(
566 const int sequences_are_built_by))
567 {
568 col_seqs_iter ret;
569 FCS_ON_NOT_FC_ONLY(ret.sequences_are_built_by = sequences_are_built_by);
570 ret.col = fcs_state_get_col(*s, stack_idx);
571 ret.col_len_minus_1 = (ret.col_len = fcs_col_len(ret.col)) - 1;
572 ret.c = 0;
573 col_seqs_iter__calc_end(&ret);
574 return ret;
575 }
576
col_seqs_iter__advance(col_seqs_iter * const iter)577 static inline void col_seqs_iter__advance(col_seqs_iter *const iter)
578 {
579 iter->c = iter->seq_end + 1;
580 col_seqs_iter__calc_end(iter);
581 }
582
check_if_can_relocate(const fcs_game_limit start,const fcs_game_limit num_virtual_vacant_freecells,const fcs_game_limit num_virtual_vacant_stacks,const col_seqs_iter * const iter PASS_sequences_are_built_by (const fcs_instance * const instance))583 static inline bool check_if_can_relocate(const fcs_game_limit start,
584 const fcs_game_limit num_virtual_vacant_freecells,
585 const fcs_game_limit num_virtual_vacant_stacks,
586 const col_seqs_iter *const iter PASS_sequences_are_built_by(
587 const fcs_instance *const instance))
588 {
589 MOVE_FUNCS__define_empty_stacks_fill();
590 fcs_game_limit num_cards_to_relocate = start;
591 const fcs_game_limit freecells_to_fill =
592 min(num_cards_to_relocate, num_virtual_vacant_freecells);
593
594 num_cards_to_relocate -= freecells_to_fill;
595
596 const fcs_game_limit freestacks_to_fill =
597 min(num_cards_to_relocate, num_virtual_vacant_stacks);
598 num_cards_to_relocate -= freestacks_to_fill;
599
600 return ((num_cards_to_relocate == 0) &&
601 (calc_max_sequence_move(
602 num_virtual_vacant_freecells - freecells_to_fill,
603 num_virtual_vacant_stacks - freestacks_to_fill) >=
604 iter->seq_end - iter->c + 1));
605 }
606
607 #ifdef FCS_BREAK_BACKWARD_COMPAT_2
608 #define CLAP
609 #endif
DECLARE_MOVE_FUNCTION(fc_solve_sfs_move_stack_cards_to_different_stacks)610 DECLARE_MOVE_FUNCTION(fc_solve_sfs_move_stack_cards_to_different_stacks)
611 {
612 MOVE_FUNCS__define_common();
613 HARD__SET_GAME_PARAMS();
614 const_SLOT(num_vacant_freecells, soft_thread);
615 const_SLOT(num_vacant_stacks, soft_thread);
616 const fcs_game_limit num_virtual_vacant_stacks =
617 CALC_num_virtual_vacant_stacks();
618 #ifndef CLAP
619 const size_t derived_start_idx = derived_states_list->num_states;
620 #endif
621
622 CALC_POSITIONS_BY_RANK();
623 // Now let's try to move a card from one stack to the other
624 // Note that it does not involve moving cards lower than king
625 // to empty stacks
626
627 for (stack_i stack_idx = 0; stack_idx < LOCAL_STACKS_NUM; ++stack_idx)
628 {
629 col_seqs_iter iter = col_seqs_iter__create(&state_key,
630 stack_idx PASS_sequences_are_built_by(sequences_are_built_by));
631 for (; iter.c < iter.col_len; col_seqs_iter__advance(&iter))
632 {
633 if (MOVE_FUNCS__should_not_empty_columns() && (iter.c == 0))
634 {
635 continue;
636 }
637 const int_fast16_t col_num_cards =
638 iter.col_len_minus_1 - iter.seq_end;
639 // Find a card which this card can be put on
640
641 const fcs_card card = fcs_col_get_card(iter.col, iter.c);
642 // Skip if it's a King - nothing to put it on.
643 if (unlikely(fcs_card_is_king(card)))
644 {
645 continue;
646 }
647
648 FCS_POS_IDX_TO_CHECK_START_LOOP(card)
649 {
650 const int_fast32_t ds = pos_idx_to_check[0];
651
652 if ((ds < 0) || ((stack_i)ds == stack_idx))
653 {
654 continue;
655 }
656 const int_fast32_t dc = pos_idx_to_check[1];
657 const stack_i dest_cards_num =
658 fcs_state_col_len(state_key, ds) - (stack_i)dc - 1;
659 if (!unlikely(check_if_can_relocate(
660 (fcs_game_limit)(
661 dest_cards_num + (stack_i)col_num_cards),
662 num_vacant_freecells, num_virtual_vacant_stacks,
663 &iter PASS_sequences_are_built_by(instance))))
664 {
665 continue;
666 }
667 sfs_check_state_begin();
668 copy_two_stacks(stack_idx, ds);
669 const int cols_indexes[3] = {(int)ds, (int)stack_idx, -1};
670 empty_two_cols_from_new_state(soft_thread,
671 ptr_new_state SFS__PASS_MOVE_STACK(moves), cols_indexes,
672 (int)dest_cards_num, col_num_cards);
673 fcs_move_sequence((stack_i)ds, stack_idx,
674 (stack_i)(iter.seq_end - iter.c + 1));
675 // This is to preserve the order that the initial
676 // (non-optimized) version of the function used - for
677 // backwards-compatibility and consistency.
678 #ifndef CLAP
679 state_context_value =
680 (int)((((((stack_idx << 8) | (stack_i)iter.c) << 8) |
681 (stack_i)ds)
682 << 8) |
683 (stack_i)dc);
684 #endif
685
686 sfs_check_state_end();
687 }
688 }
689 }
690 #ifndef CLAP
691 sort_derived_states(derived_states_list, derived_start_idx);
692 #endif
693 }
694
DECLARE_MOVE_FUNCTION(fc_solve_sfs_move_sequences_to_free_stacks)695 DECLARE_MOVE_FUNCTION(fc_solve_sfs_move_sequences_to_free_stacks)
696 {
697 MOVE_FUNCS__define_common();
698 if (IS_FILLED_BY_NONE())
699 {
700 return;
701 }
702 FC__STACKS__SET_PARAMS();
703 const fcs_game_limit num_vacant_stacks = soft_thread->num_vacant_stacks;
704 if (num_vacant_stacks == 0)
705 {
706 return;
707 }
708 const fcs_game_limit num_vacant_freecells =
709 soft_thread->num_vacant_freecells;
710 const fcs_game_limit num_virtual_vacant_stacks =
711 CALC_num_virtual_vacant_stacks();
712 const size_t max_sequence_len = (size_t)calc_max_sequence_move(
713 num_vacant_freecells, num_vacant_stacks - 1);
714
715 // Now try to move sequences to empty stacks
716 const int ds = find_empty_stack(raw_state_raw, 0, LOCAL_STACKS_NUM);
717 for (stack_i stack_idx = 0; stack_idx < LOCAL_STACKS_NUM; stack_idx++)
718 {
719 col_seqs_iter iter = col_seqs_iter__create(&state_key,
720 stack_idx PASS_sequences_are_built_by(sequences_are_built_by));
721 for (; iter.c < iter.col_len; col_seqs_iter__advance(&iter))
722 {
723 if (IS_FILLED_BY_KINGS_ONLY() &&
724 (!fcs_col_is_king(iter.col, (stack_i)iter.c)))
725 {
726 continue;
727 }
728
729 if (iter.seq_end == iter.col_len_minus_1)
730 {
731 stack_i c = (stack_i)iter.c;
732 // One stack is the destination stack, so we have one less stack
733 // in that case
734 while (
735 (max_sequence_len < (stack_i)iter.col_len - c) && (c > 0))
736 {
737 c--;
738 }
739
740 if (!((c > 0) && ((IS_FILLED_BY_KINGS_ONLY())
741 ? fcs_col_is_king(iter.col, c)
742 : true)))
743 {
744 continue;
745 }
746 sfs_check_state_begin();
747 copy_two_stacks(stack_idx, ds);
748 fcs_move_sequence(
749 (stack_i)ds, stack_idx, (stack_i)iter.col_len - c);
750
751 sfs_check_state_end();
752 }
753 else
754 {
755 long num_cards_to_relocate =
756 iter.col_len_minus_1 - iter.seq_end;
757
758 const long freecells_to_fill =
759 min(num_cards_to_relocate, (long)num_vacant_freecells);
760
761 num_cards_to_relocate -= freecells_to_fill;
762
763 const long freestacks_to_fill =
764 min(num_cards_to_relocate, num_virtual_vacant_stacks);
765 num_cards_to_relocate -= freestacks_to_fill;
766
767 if (!((num_cards_to_relocate == 0) &&
768 (num_vacant_stacks - freestacks_to_fill > 0)))
769 {
770 continue;
771 }
772 // We can move it
773 const long seq_start = ({
774 const long max_seq_move = (long)calc_max_sequence_move(
775 num_vacant_freecells - freecells_to_fill,
776 num_vacant_stacks - freestacks_to_fill - 1);
777 const long m = iter.seq_end + 1 - max_seq_move;
778 max(m, iter.c);
779 });
780 if (!((seq_start <= iter.seq_end) &&
781 ((IS_FILLED_BY_KINGS_ONLY())
782 ? fcs_col_is_king(iter.col, (stack_i)seq_start)
783 : true)))
784 {
785 continue;
786 }
787 sfs_check_state_begin();
788
789 // Fill the freecells with the top cards
790 my_copy_stack(stack_idx);
791 const int cols_indexes[3] = {(int)stack_idx, -1, -1};
792 const empty_two_cols_ret empty_ret =
793 empty_two_cols_from_new_state(soft_thread,
794 ptr_new_state SFS__PASS_MOVE_STACK(moves), cols_indexes,
795 freecells_to_fill + freestacks_to_fill, 0);
796
797 const stack_i b = (stack_i)find_empty_stack(raw_state_raw,
798 (empty_ret.is_col ? empty_ret.src_idx + 1 : 0),
799 LOCAL_STACKS_NUM);
800 my_copy_stack(b);
801
802 fcs_move_sequence(
803 b, stack_idx, (stack_i)(iter.seq_end - seq_start + 1));
804
805 sfs_check_state_end();
806 }
807 }
808 }
809 }
810
811 #if MAX_NUM_FREECELLS > 0
DECLARE_MOVE_FUNCTION(fc_solve_sfs_move_freecell_cards_to_empty_stack)812 DECLARE_MOVE_FUNCTION(fc_solve_sfs_move_freecell_cards_to_empty_stack)
813 {
814 tests_define_accessors();
815 MOVE_FUNCS__define_empty_stacks_fill();
816 if (IS_FILLED_BY_NONE())
817 {
818 return;
819 }
820 FC__STACKS__SET_PARAMS();
821 if (!soft_thread->num_vacant_stacks)
822 {
823 return;
824 }
825 SET_empty_stack_idx(empty_stack_idx);
826
827 for (int fc = 0; fc < LOCAL_FREECELLS_NUM; fc++)
828 {
829 const fcs_card card = fcs_freecell_card(state_key, fc);
830 #define SHOULD_SKIP_FC_CARD(card) \
831 (fcs_card_is_empty(card) || \
832 (IS_FILLED_BY_KINGS_ONLY() && !fcs_card_is_king(card)))
833 if (SHOULD_SKIP_FC_CARD(card))
834 {
835 continue;
836 }
837 sfs_check_state_begin();
838
839 my_copy_stack(empty_stack_idx);
840
841 fcs_state_push(&new_state_key, (stack_i)empty_stack_idx, card);
842 fcs_empty_freecell(new_state_key, fc);
843 fcs_move_stack_non_seq_push(moves, FCS_MOVE_TYPE_FREECELL_TO_STACK,
844 (stack_i)fc, (stack_i)empty_stack_idx);
845 sfs_check_state_end();
846 }
847 }
848
849 // Let's try to put cards that occupy freecells on an empty stack and
850 // immediately put a child card on top. See:
851 // https://groups.yahoo.com/neo/groups/fc-solve-discuss/conversations/messages/584
DECLARE_MOVE_FUNCTION(fc_solve_sfs_move_fc_to_empty_and_put_on_top)852 DECLARE_MOVE_FUNCTION(fc_solve_sfs_move_fc_to_empty_and_put_on_top)
853 {
854 MOVE_FUNCS__define_common();
855 if (IS_FILLED_BY_NONE())
856 {
857 return;
858 }
859 FC__STACKS__SET_PARAMS();
860 const fcs_game_limit num_vacant_freecells =
861 soft_thread->num_vacant_freecells;
862 const fcs_game_limit num_virtual_vacant_freecells =
863 num_vacant_freecells + 1;
864 const fcs_game_limit num_vacant_stacks = soft_thread->num_vacant_stacks;
865 const fcs_game_limit num_virtual_vacant_stacks = num_vacant_stacks - 1;
866 if (!num_vacant_stacks)
867 {
868 return;
869 }
870 SET_empty_stack_idx(empty_stack_idx);
871
872 #ifdef RAR2
873 for (int fc = LOCAL_FREECELLS_NUM - 1; fc >= 0; --fc)
874 #else
875 for (int fc = 0; fc < LOCAL_FREECELLS_NUM; ++fc)
876 #endif
877 {
878 const fcs_card src_card = fcs_freecell_card(state_key, fc);
879 if (SHOULD_SKIP_FC_CARD(src_card))
880 {
881 continue;
882 }
883 for (int dest_fc = 0; dest_fc < LOCAL_FREECELLS_NUM; ++dest_fc)
884 {
885 if (dest_fc == fc)
886 {
887 continue;
888 }
889 const fcs_card dest_card = fcs_freecell_card(state_key, dest_fc);
890 if (fcs_card_is_empty(dest_card))
891 {
892 continue;
893 }
894 if (!unlikely(fcs_is_parent_card(dest_card, src_card)))
895 {
896 continue;
897 }
898 sfs_check_state_begin();
899
900 my_copy_stack(empty_stack_idx);
901
902 fcs_state_push(&new_state_key, (stack_i)empty_stack_idx, src_card);
903 fcs_state_push(&new_state_key, (stack_i)empty_stack_idx, dest_card);
904 fcs_empty_freecell(new_state_key, fc);
905 fcs_empty_freecell(new_state_key, dest_fc);
906 fcs_move_stack_non_seq_push(moves, FCS_MOVE_TYPE_FREECELL_TO_STACK,
907 (stack_i)fc, (stack_i)empty_stack_idx);
908 fcs_move_stack_non_seq_push(moves, FCS_MOVE_TYPE_FREECELL_TO_STACK,
909 (stack_i)dest_fc, (stack_i)empty_stack_idx);
910 sfs_check_state_end();
911 }
912 for (stack_i stack_idx = 0; stack_idx < LOCAL_STACKS_NUM; ++stack_idx)
913 {
914 col_seqs_iter iter = col_seqs_iter__create(&state_key,
915 stack_idx PASS_sequences_are_built_by(sequences_are_built_by));
916 for (; iter.c < iter.col_len; col_seqs_iter__advance(&iter))
917 {
918 if (MOVE_FUNCS__should_not_empty_columns() && (iter.c == 0))
919 {
920 continue;
921 }
922 const long col_num_cards = iter.col_len_minus_1 - iter.seq_end;
923 // Find a card which this card can be put on
924
925 const fcs_card card = fcs_col_get_card(iter.col, iter.c);
926 if (!unlikely(fcs_is_parent_card(card, src_card)))
927 {
928 continue;
929 }
930 if (!unlikely(check_if_can_relocate(
931 (fcs_game_limit)col_num_cards,
932 num_virtual_vacant_freecells, num_virtual_vacant_stacks,
933 &iter PASS_sequences_are_built_by(instance))))
934 {
935 continue;
936 }
937 sfs_check_state_begin();
938 copy_two_stacks(stack_idx, empty_stack_idx);
939 fcs_state_push(
940 &new_state_key, (stack_i)empty_stack_idx, src_card);
941 fcs_empty_freecell(new_state_key, fc);
942 fcs_move_stack_non_seq_push(moves,
943 FCS_MOVE_TYPE_FREECELL_TO_STACK, (stack_i)fc,
944 (stack_i)empty_stack_idx);
945 const int cols_indexes[3] = {(int)stack_idx, -1, -1};
946 empty_two_cols_from_new_state(soft_thread,
947 ptr_new_state SFS__PASS_MOVE_STACK(moves), cols_indexes,
948 col_num_cards, 0);
949 fcs_move_sequence((stack_i)empty_stack_idx, stack_idx,
950 (stack_i)(iter.seq_end - iter.c + 1));
951 sfs_check_state_end();
952 }
953 }
954 }
955 }
956 #endif
957
DECLARE_MOVE_FUNCTION(fc_solve_sfs_move_cards_to_a_different_parent)958 DECLARE_MOVE_FUNCTION(fc_solve_sfs_move_cards_to_a_different_parent)
959 {
960 MOVE_FUNCS__define_common();
961 HARD__SET_GAME_PARAMS();
962 const fcs_game_limit num_vacant_freecells =
963 soft_thread->num_vacant_freecells;
964 const fcs_game_limit num_vacant_stacks = soft_thread->num_vacant_stacks;
965 const fcs_game_limit num_virtual_vacant_stacks =
966 CALC_num_virtual_vacant_stacks();
967 #ifndef FCS_BREAK_BACKWARD_COMPAT_2
968 #define BUTTER
969 #endif
970 #ifndef BUTTER
971 const size_t derived_start_idx = derived_states_list->num_states;
972 #endif
973
974 CALC_POSITIONS_BY_RANK();
975 // This time try to move cards that are already on top of a parent to a
976 // different parent
977
978 for (stack_i stack_idx = 0; stack_idx < LOCAL_STACKS_NUM; stack_idx++)
979 {
980 var_AUTO(col, fcs_state_get_col(state_key, stack_idx));
981 const int cards_num = fcs_col_len(col);
982
983 // If there's only one card in the column, then it won't be above a
984 // parent, so there's no sense in moving it.
985 //
986 // If there are no cards in the column, then there's nothing to do
987 // here, and the algorithm will be confused
988 if (cards_num < 2)
989 {
990 continue;
991 }
992
993 fcs_card upper_card = fcs_col_get_card(col, cards_num - 1);
994
995 int min_card_height;
996 fcs_card lower_card;
997 for (min_card_height = cards_num - 2; min_card_height >= 0;
998 upper_card = lower_card, --min_card_height)
999 {
1000 lower_card = fcs_col_get_card(col, min_card_height);
1001 if (!fcs_is_parent_card(upper_card, lower_card))
1002 {
1003 break;
1004 }
1005 }
1006 min_card_height += 2;
1007
1008 for (int c = min_card_height; c < cards_num; ++c)
1009 {
1010 const fcs_card card = fcs_col_get_card(col, c);
1011 FCS_POS_IDX_TO_CHECK_START_LOOP(card)
1012 {
1013 const int_fast32_t ds = pos_idx_to_check[0];
1014 if ((ds == -1) || ((typeof(stack_idx))ds == stack_idx))
1015 {
1016 continue;
1017 }
1018 const int_fast32_t dc = pos_idx_to_check[1];
1019
1020 var_AUTO(dest_col, fcs_state_get_col(state_key, ds));
1021 const int dest_cards_num = fcs_col_len(dest_col);
1022
1023 // Corresponding cards - see if it is feasible to move the
1024 // source to the destination.
1025
1026 #ifdef FCS_POS_BY_RANK__ENABLE_PARENT_CHECK
1027 const_AUTO(dest_card, fcs_col_get_card(dest_col, dc));
1028 // Don't move if there's a sequence of cards in the destination.
1029 if ((dc + 1 < dest_cards_num) &&
1030 fcs_is_parent_card(
1031 fcs_col_get_card(dest_col, dc + 1), dest_card))
1032 {
1033 continue;
1034 }
1035 #endif
1036
1037 long num_cards_to_relocate = dest_cards_num - dc - 1;
1038
1039 const long freecells_to_fill =
1040 min(num_cards_to_relocate, num_vacant_freecells);
1041
1042 num_cards_to_relocate -= freecells_to_fill;
1043
1044 const long freestacks_to_fill =
1045 min(num_cards_to_relocate, num_virtual_vacant_stacks);
1046 num_cards_to_relocate -= freestacks_to_fill;
1047
1048 if (!((num_cards_to_relocate == 0) &&
1049 (calc_max_sequence_move(
1050 num_vacant_freecells - freecells_to_fill,
1051 num_vacant_stacks - freestacks_to_fill) >=
1052 cards_num - c)))
1053 {
1054 continue;
1055 }
1056
1057 sfs_check_state_begin();
1058 // Fill the freecells with the top cards
1059 copy_two_stacks(stack_idx, ds);
1060 const int cols_indexes[3] = {(int)ds, -1, -1};
1061 empty_two_cols_from_new_state(soft_thread,
1062 ptr_new_state SFS__PASS_MOVE_STACK(moves), cols_indexes,
1063 freestacks_to_fill + freecells_to_fill, 0);
1064 fcs_move_sequence(
1065 (stack_i)ds, stack_idx, (stack_i)(cards_num - c));
1066
1067 #ifndef BUTTER
1068 state_context_value =
1069 (int)((((((stack_idx << 8) | (size_t)c) << 8) | (size_t)ds)
1070 << 8) |
1071 (size_t)dc);
1072 #endif
1073
1074 sfs_check_state_end();
1075 }
1076 }
1077 }
1078
1079 #ifndef BUTTER
1080 sort_derived_states(derived_states_list, derived_start_idx);
1081 #endif
1082 }
1083
1084 #if MAX_NUM_FREECELLS > 0
DECLARE_MOVE_FUNCTION(fc_solve_sfs_empty_stack_into_freecells)1085 DECLARE_MOVE_FUNCTION(fc_solve_sfs_empty_stack_into_freecells)
1086 {
1087 tests_define_accessors();
1088 MOVE_FUNCS__define_empty_stacks_fill();
1089 if (IS_FILLED_BY_NONE())
1090 {
1091 return;
1092 }
1093 FC__STACKS__SET_PARAMS();
1094 const fcs_game_limit num_vacant_freecells =
1095 soft_thread->num_vacant_freecells;
1096
1097 // Now, let's try to empty an entire col into the freecells, so other
1098 // cards can inhabit it
1099 if ((!num_vacant_freecells) || soft_thread->num_vacant_stacks)
1100 {
1101 return;
1102 }
1103 for (stack_i stack_idx = 0; stack_idx < LOCAL_STACKS_NUM; stack_idx++)
1104 {
1105 var_AUTO(col, fcs_state_get_col(state_key, stack_idx));
1106 const int cards_num = fcs_col_len(col);
1107
1108 if ((!cards_num) || (cards_num > num_vacant_freecells))
1109 {
1110 continue;
1111 }
1112 sfs_check_state_begin();
1113
1114 my_copy_stack(stack_idx);
1115
1116 const_AUTO(new_src_col, fcs_state_get_col(new_state_key, stack_idx));
1117
1118 stack_i fc_idx = 0;
1119 for (int c = 0; c < cards_num; ++c, ++fc_idx)
1120 {
1121 for (; fc_idx < LOCAL_FREECELLS_NUM; ++fc_idx)
1122 {
1123 if (fcs_freecell_is_empty(new_state_key, fc_idx))
1124 {
1125 break;
1126 }
1127 }
1128 fcs_card top_card;
1129 fcs_col_pop_card(new_src_col, top_card);
1130
1131 fcs_put_card_in_freecell(new_state_key, fc_idx, top_card);
1132
1133 fcs_move_stack_non_seq_push(
1134 moves, FCS_MOVE_TYPE_STACK_TO_FREECELL, stack_idx, fc_idx);
1135 }
1136
1137 sfs_check_state_end();
1138 }
1139 }
1140 #endif
1141
DECLARE_MOVE_FUNCTION(fc_solve_sfs_atomic_move_card_to_empty_stack)1142 DECLARE_MOVE_FUNCTION(fc_solve_sfs_atomic_move_card_to_empty_stack)
1143 {
1144 tests_define_accessors();
1145 MOVE_FUNCS__define_empty_stacks_fill();
1146 if (IS_FILLED_BY_NONE())
1147 {
1148 return;
1149 }
1150 if (soft_thread->num_vacant_stacks == 0)
1151 {
1152 return;
1153 }
1154 STACKS__SET_PARAMS();
1155 SET_empty_stack_idx(empty_stack_idx);
1156
1157 for (stack_i stack_idx = 0; stack_idx < LOCAL_STACKS_NUM; stack_idx++)
1158 {
1159 var_AUTO(col, fcs_state_get_col(state_key, stack_idx));
1160 const int cards_num = fcs_col_len(col);
1161
1162 // Bug fix: if there's only one card in a column, there's no
1163 // point moving it to a new empty column.
1164 if (cards_num <= 1)
1165 {
1166 continue;
1167 }
1168 const fcs_card card = fcs_col_get_card(col, cards_num - 1);
1169
1170 if (IS_FILLED_BY_KINGS_ONLY() && (!fcs_card_is_king(card)))
1171 {
1172 continue;
1173 }
1174 sfs_check_state_begin();
1175 copy_two_stacks(stack_idx, empty_stack_idx);
1176 fcs_state_pop_col_top(&new_state_key, stack_idx);
1177 fcs_state_push(&new_state_key, empty_stack_idx, card);
1178 fcs_push_1card_seq(moves, stack_idx, empty_stack_idx);
1179
1180 sfs_check_state_end();
1181 }
1182 }
1183
DECLARE_MOVE_FUNCTION(fc_solve_sfs_atomic_move_card_to_parent)1184 DECLARE_MOVE_FUNCTION(fc_solve_sfs_atomic_move_card_to_parent)
1185 {
1186 MOVE_FUNCS__define_common();
1187 STACKS__SET_PARAMS();
1188 const int num_cards_in_col_threshold = CALC_num_cards_in_col_threshold();
1189
1190 for (stack_i stack_idx = 0; stack_idx < LOCAL_STACKS_NUM; stack_idx++)
1191 {
1192 var_AUTO(col, fcs_state_get_col(state_key, stack_idx));
1193 const int cards_num = fcs_col_len(col);
1194
1195 if (cards_num <= num_cards_in_col_threshold)
1196 {
1197 continue;
1198 }
1199 const fcs_card card = fcs_col_get_card(col, cards_num - 1);
1200
1201 for (int ds = 0; ds < LOCAL_STACKS_NUM; ds++)
1202 {
1203 if ((stack_i)ds == stack_idx)
1204 {
1205 continue;
1206 }
1207
1208 var_AUTO(dest_col, fcs_state_get_col(state_key, ds));
1209 const int dest_cards_num = fcs_col_len(dest_col);
1210
1211 if (!dest_cards_num)
1212 {
1213 continue;
1214 }
1215 const fcs_card dest_card =
1216 fcs_col_get_card(dest_col, fcs_col_len(dest_col) - 1);
1217 if (!fcs_is_parent_card(card, dest_card))
1218 {
1219 continue;
1220 }
1221 sfs_check_state_begin();
1222 copy_two_stacks(stack_idx, ds);
1223 fcs_state_pop_col_top(&new_state_key, stack_idx);
1224 fcs_state_push(&new_state_key, (stack_i)ds, card);
1225 fcs_push_1card_seq(moves, stack_idx, (stack_i)ds);
1226
1227 sfs_check_state_end();
1228 }
1229 }
1230 }
1231
1232 #if MAX_NUM_FREECELLS > 0
DECLARE_MOVE_FUNCTION(fc_solve_sfs_atomic_move_card_to_freecell)1233 DECLARE_MOVE_FUNCTION(fc_solve_sfs_atomic_move_card_to_freecell)
1234 {
1235 tests_define_accessors();
1236 MOVE_FUNCS__define_empty_stacks_fill();
1237 FC__STACKS__SET_PARAMS();
1238 const fcs_game_limit num_vacant_freecells =
1239 soft_thread->num_vacant_freecells;
1240
1241 if (num_vacant_freecells == 0)
1242 {
1243 return;
1244 }
1245
1246 const int num_cards_in_col_threshold = CALC_num_cards_in_col_threshold();
1247
1248 int ds;
1249 for (ds = 0; ds < LOCAL_FREECELLS_NUM; ds++)
1250 {
1251 if (fcs_freecell_is_empty(state_key, ds))
1252 {
1253 break;
1254 }
1255 }
1256
1257 for (stack_i stack_idx = 0; stack_idx < LOCAL_STACKS_NUM; stack_idx++)
1258 {
1259 var_AUTO(col, fcs_state_get_col(state_key, stack_idx));
1260 const int cards_num = fcs_col_len(col);
1261 if (cards_num <= num_cards_in_col_threshold)
1262 {
1263 continue;
1264 }
1265 const fcs_card card = fcs_col_get_card(col, cards_num - 1);
1266
1267 sfs_check_state_begin();
1268
1269 my_copy_stack(stack_idx);
1270 fcs_state_pop_col_top(&new_state_key, stack_idx);
1271 fcs_put_card_in_freecell(new_state_key, ds, card);
1272
1273 fcs_move_stack_non_seq_push(
1274 moves, FCS_MOVE_TYPE_STACK_TO_FREECELL, stack_idx, (stack_i)ds);
1275
1276 sfs_check_state_end();
1277 }
1278 }
1279
DECLARE_MOVE_FUNCTION(fc_solve_sfs_atomic_move_freecell_card_to_parent)1280 DECLARE_MOVE_FUNCTION(fc_solve_sfs_atomic_move_freecell_card_to_parent)
1281 {
1282 tests_define_accessors();
1283 MOVE_FUNCS__define_seqs_built_by();
1284 FC__STACKS__SET_PARAMS();
1285 for (int fc = 0; fc < LOCAL_FREECELLS_NUM; fc++)
1286 {
1287 const fcs_card card = fcs_freecell_card(state_key, fc);
1288
1289 if (fcs_card_is_empty(card))
1290 {
1291 continue;
1292 }
1293
1294 for (int ds = 0; ds < LOCAL_STACKS_NUM; ds++)
1295 {
1296 var_AUTO(dest_col, fcs_state_get_col(state_key, ds));
1297 const_AUTO(l, fcs_col_len(dest_col));
1298 if (!l)
1299 {
1300 continue;
1301 }
1302 const fcs_card dest_card = fcs_col_get_card(dest_col, l - 1);
1303 if (!fcs_is_parent_card(card, dest_card))
1304 {
1305 continue;
1306 }
1307 sfs_check_state_begin();
1308
1309 my_copy_stack(ds);
1310 fcs_empty_freecell(new_state_key, fc);
1311 fcs_state_push(&new_state_key, (stack_i)ds, card);
1312 fcs_move_stack_non_seq_push(moves, FCS_MOVE_TYPE_FREECELL_TO_STACK,
1313 (stack_i)fc, (stack_i)ds);
1314
1315 sfs_check_state_end();
1316 }
1317 }
1318 }
1319
DECLARE_MOVE_FUNCTION(fc_solve_sfs_atomic_move_freecell_card_to_empty_stack)1320 DECLARE_MOVE_FUNCTION(fc_solve_sfs_atomic_move_freecell_card_to_empty_stack)
1321 {
1322 tests_define_accessors();
1323 MOVE_FUNCS__define_empty_stacks_fill();
1324 FC__STACKS__SET_PARAMS();
1325 if (IS_FILLED_BY_NONE())
1326 {
1327 return;
1328 }
1329 if (soft_thread->num_vacant_stacks == 0)
1330 {
1331 return;
1332 }
1333
1334 const int ds = find_empty_stack(raw_state_raw, 0, LOCAL_STACKS_NUM);
1335
1336 for (int fc = 0; fc < LOCAL_FREECELLS_NUM; fc++)
1337 {
1338 const fcs_card card = fcs_freecell_card(state_key, fc);
1339
1340 if (fcs_card_is_empty(card) ||
1341 (IS_FILLED_BY_KINGS_ONLY() && (!fcs_card_is_king(card))))
1342 {
1343 continue;
1344 }
1345
1346 sfs_check_state_begin();
1347
1348 my_copy_stack(ds);
1349 fcs_empty_freecell(new_state_key, fc);
1350 fcs_state_push(&new_state_key, (stack_i)ds, card);
1351 fcs_move_stack_non_seq_push(
1352 moves, FCS_MOVE_TYPE_FREECELL_TO_STACK, (stack_i)fc, (stack_i)ds);
1353
1354 sfs_check_state_end();
1355 }
1356 }
1357 #endif
1358
1359 #endif // FCS_ZERO_FREECELLS_MODE
1360
1361 #define CALC_FOUNDATION_TO_PUT_CARD_ON() \
1362 calc_foundation_to_put_card_on(soft_thread, pass_new_state.key, card)
1363
1364 #define CALC_FOUNDATION_ARG() \
1365 const fcs_soft_thread *const soft_thread GCC_UNUSED
1366 #define CALC_FOUNDATION__calc_sequences_are_built_by() \
1367 FCS_ON_NOT_FC_ONLY(const_AUTO(instance, fcs_st_instance(soft_thread))); \
1368 MOVE_FUNCS__define_seqs_built_by()
1369 #include "calc_foundation.h"
1370
fc_solve_sfs_raymond_prune(fcs_soft_thread * const soft_thread,fcs_kv_state raw_state_raw)1371 extern fcs_collectible_state *fc_solve_sfs_raymond_prune(
1372 fcs_soft_thread *const soft_thread, fcs_kv_state raw_state_raw)
1373 {
1374 #define EMPTY
1375 tests_define_accessors__generic(EMPTY);
1376 STACKS__SET_PARAMS();
1377
1378 sfs_check_state_begin();
1379 bool cards_were_moved = false;
1380 bool num_cards_moved;
1381 do
1382 {
1383 num_cards_moved = false;
1384 for (stack_i stack_idx = 0; stack_idx < LOCAL_STACKS_NUM; stack_idx++)
1385 {
1386 const_AUTO(col, fcs_state_get_col(new_state_key, stack_idx));
1387 const int cards_num = fcs_col_len(col);
1388
1389 if (!cards_num)
1390 {
1391 continue;
1392 }
1393 const fcs_card card = fcs_col_get_card(col, cards_num - 1);
1394
1395 const_AUTO(dest_foundation, CALC_FOUNDATION_TO_PUT_CARD_ON());
1396 if (dest_foundation < 0)
1397 {
1398 continue;
1399 }
1400 num_cards_moved = true;
1401
1402 my_copy_stack(stack_idx);
1403 fcs_state_pop_col_top(&new_state_key, stack_idx);
1404 fcs_increment_foundation(new_state_key, dest_foundation);
1405 fcs_move_stack_non_seq_push(moves,
1406 FCS_MOVE_TYPE_STACK_TO_FOUNDATION, stack_idx,
1407 (stack_i)dest_foundation);
1408 }
1409
1410 #if MAX_NUM_FREECELLS > 0
1411 for (int fc = 0; fc < LOCAL_FREECELLS_NUM; ++fc)
1412 {
1413 const fcs_card card = fcs_freecell_card(new_state_key, fc);
1414 if (fcs_card_is_empty(card))
1415 {
1416 continue;
1417 }
1418 const_AUTO(dest_foundation, CALC_FOUNDATION_TO_PUT_CARD_ON());
1419 if (dest_foundation < 0)
1420 {
1421 continue;
1422 }
1423 num_cards_moved = true;
1424
1425 fcs_empty_freecell(new_state_key, fc);
1426 fcs_increment_foundation(new_state_key, dest_foundation);
1427 fcs_move_stack_non_seq_push(moves,
1428 FCS_MOVE_TYPE_FREECELL_TO_FOUNDATION, (stack_i)fc,
1429 (stack_i)dest_foundation);
1430 }
1431 #endif
1432 if (num_cards_moved)
1433 {
1434 cards_were_moved = true;
1435 }
1436 } while (num_cards_moved);
1437
1438 if (!cards_were_moved)
1439 {
1440 return NULL;
1441 }
1442 register const_AUTO(ptr_next_state,
1443 fc_solve_sfs_check_state_end(soft_thread,
1444 sfs_check_state_end__arg & pass_new_state FCS__pass_moves(moves)));
1445 // Set the GENERATED_BY_PRUNING flag unconditionally. It won't
1446 // hurt if it's already there, and if it's a state that was
1447 // found by other means, we still shouldn't prune it, because
1448 // it is already "prune-perfect".
1449 FCS_S_VISITED(ptr_next_state) |= FCS_VISITED_GENERATED_BY_PRUNING;
1450 return ptr_next_state;
1451 }
1452