1 /*
2 * Copyright (C) 2006-2009 Stephan Kulow <coolo@kde.org>
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License as
6 * published by the Free Software Foundation; either version 2 of
7 * the License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program. If not, see <http://www.gnu.org/licenses/>.
16 */
17
18 #include "golfsolver.h"
19
20 // own
21 #include "../golf.h"
22 #include "../kpat_debug.h"
23
24 const int CHUNKSIZE = 10000;
25
26 #define BHS__GOLF__NUM_COLUMNS 7
27 #define BHS__GOLF__MAX_NUM_CARDS_IN_COL 5
28 #define BHS__GOLF__BITS_PER_COL 3
29
30 #define PRINT 0
31
make_move(MOVE * m)32 void GolfSolver::make_move(MOVE *m)
33 {
34 #ifndef WITH_BH_SOLVER
35 #if PRINT
36 if ( m->totype == O_Type )
37 fprintf( stderr, "\nmake move %d from %d out (at %d)\n\n", m->card_index, m->from, m->turn_index );
38 else
39 fprintf( stderr, "\nmake move %d from %d to %d (%d)\n\n", m->card_index, m->from, m->to, m->turn_index );
40 print_layout();
41 #else
42 //print_layout();
43 #endif
44
45 int from = m->from;
46 int to = m->to;
47
48 Q_ASSERT( to == 7 );
49 Q_ASSERT( from != 7 );
50
51 // move to pile
52 if ( from == 8 && to == 7 )
53 {
54 card_t card = *Wp[8];
55 Wp[8]--;
56 Wlen[8]--;
57 card = ( SUIT( card ) << 4 ) + RANK( card );
58 Wp[7]++;
59 *Wp[7] = card;
60 Wlen[7]++;
61 hashpile( 7 );
62 hashpile( 8 );
63 #if PRINT
64 print_layout();
65 #endif
66 return;
67 }
68
69 card_t card = *Wp[from];
70 Wp[from]--;
71 Wlen[from]--;
72
73 Wp[to]++;
74 *Wp[to] = card;
75 Wlen[to]++;
76
77 hashpile(from);
78 hashpile(to);
79 #if PRINT
80 print_layout();
81 #endif
82 #else
83 Q_UNUSED(m);
84 #endif
85 }
86
undo_move(MOVE * m)87 void GolfSolver::undo_move(MOVE *m)
88 {
89 #ifndef WITH_BH_SOLVER
90 #if PRINT
91 if ( m->totype == O_Type )
92 fprintf( stderr, "\nundo move %d from %d out (at %d)\n\n", m->card_index, m->from, m->turn_index );
93 else
94 fprintf( stderr, "\nundo move %d from %d to %d (%d)\n\n", m->card_index, m->from, m->to, m->turn_index );
95 print_layout();
96
97 #endif
98
99 int from = m->from;
100 int to = m->to;
101
102 Q_ASSERT( to == 7 );
103 Q_ASSERT( from != 7 );
104
105 // move to pile
106 if ( from == 8 && to == 7 )
107 {
108 card_t card = *Wp[7];
109 Wp[7]--;
110 Wlen[7]--;
111 card = ( SUIT( card ) << 4 ) + RANK( card ) + ( 1 << 7 );
112 Wp[8]++;
113 *Wp[8] = card;
114 Wlen[8]++;
115 hashpile( 7 );
116 hashpile( 8 );
117 #if PRINT
118 print_layout();
119 #endif
120 return;
121 }
122
123 card_t card = *Wp[to];
124 Wp[to]--;
125 Wlen[to]--;
126
127 Wp[from]++;
128 *Wp[from] = card;
129 Wlen[from]++;
130
131 hashpile(from);
132 hashpile(to);
133 #if PRINT
134 print_layout();
135 #endif
136 #else
137 Q_UNUSED(m);
138 #endif
139 }
140
141 /* Get the possible moves from a position, and store them in Possible[]. */
142
get_possible_moves(int * a,int * numout)143 int GolfSolver::get_possible_moves(int *a, int *numout)
144 {
145 #ifndef WITH_BH_SOLVER
146 int n = 0;
147 MOVE *mp = Possible;
148
149 *a = false;
150 *numout = 0;
151
152 card_t top = *Wp[7];
153 for (int w = 0; w < 7; w++) {
154 if (Wlen[w] > 0) {
155 card_t card = *Wp[w];
156 if (RANK(card) == RANK(top) - 1 ||
157 RANK(card) == RANK(top) + 1 )
158 {
159 mp->card_index = 0;
160 mp->from = w;
161 mp->to = 7;
162 mp->totype = W_Type;
163 mp->pri = 13;
164 if ( RANK( card ) == PS_ACE || RANK( card ) == PS_KING )
165 mp->pri = 30;
166 mp->turn_index = -1;
167 n++;
168 mp++;
169 }
170 }
171 }
172
173 /* check for deck->pile */
174 if ( !n && Wlen[8] ) {
175 mp->card_index = 1;
176 mp->from = 8;
177 mp->to = 7;
178 mp->totype = W_Type;
179 mp->pri = 5;
180 mp->turn_index = 0;
181 n++;
182 mp++;
183 }
184
185 return n;
186 #else
187 Q_UNUSED(a);
188 Q_UNUSED(numout);
189 return 0;
190 #endif
191 }
192
isWon()193 bool GolfSolver::isWon()
194 {
195 #ifndef WITH_BH_SOLVER
196 return Wlen[7] == 52 ;
197 #else
198 return false;
199 #endif
200 }
201
getOuts()202 int GolfSolver::getOuts()
203 {
204 #ifndef WITH_BH_SOLVER
205 return Wlen[7];
206 #else
207 return 0;
208 #endif
209 }
210
GolfSolver(const Golf * dealer)211 GolfSolver::GolfSolver(const Golf *dealer)
212 : Solver()
213 {
214 deal = dealer;
215 // Set default_max_positions to an initial
216 // value so it will not accidentally be used uninitialized.
217 // Note: it will be overrided by the Settings anyhow.
218 default_max_positions = 100000;
219 #ifdef WITH_BH_SOLVER
220 solver_instance = NULL;
221 solver_ret = BLACK_HOLE_SOLVER__OUT_OF_ITERS;
222 #endif
223 }
224
225 #ifdef WITH_BH_SOLVER
free_solver_instance()226 void GolfSolver::free_solver_instance()
227 {
228 if (solver_instance)
229 {
230 black_hole_solver_free(solver_instance);
231 solver_instance = NULL;
232 }
233 }
234
patsolve(int _max_positions)235 SolverInterface::ExitStatus GolfSolver::patsolve( int _max_positions )
236 {
237 int current_iters_count = 0;
238 max_positions = (_max_positions < 0) ? default_max_positions : _max_positions;
239 init();
240
241 if (solver_instance)
242 {
243 return Solver::UnableToDetermineSolvability;
244 }
245 if (black_hole_solver_create(&solver_instance))
246 {
247 fputs("Could not initialise solver_instance (out-of-memory)\n", stderr);
248 exit(-1);
249 }
250 black_hole_solver_enable_rank_reachability_prune(
251 solver_instance, true);
252 black_hole_solver_enable_wrap_ranks(solver_instance, false);
253 black_hole_solver_enable_place_queens_on_kings(
254 solver_instance, true);
255 #ifdef BLACK_HOLE_SOLVER__API__REQUIRES_SETUP_CALL
256 black_hole_solver_config_setup(solver_instance);
257 #endif
258
259 int error_line_num;
260 int num_columns = BHS__GOLF__NUM_COLUMNS;
261 if (black_hole_solver_read_board(solver_instance, board_as_string, &error_line_num,
262 num_columns,
263 BHS__GOLF__MAX_NUM_CARDS_IN_COL,
264 BHS__GOLF__BITS_PER_COL
265 ))
266 {
267 fprintf(stderr, "Error reading the board at line No. %d!\n",
268 error_line_num);
269 exit(-1);
270 }
271 #ifdef BLACK_HOLE_SOLVER__API__REQUIRES_SETUP_CALL
272 black_hole_solver_setup(solver_instance);
273 #endif
274 solver_ret = BLACK_HOLE_SOLVER__OUT_OF_ITERS;
275
276 if (solver_instance)
277 {
278 bool continue_loop = true;
279 while (continue_loop &&
280 ( (solver_ret == BLACK_HOLE_SOLVER__OUT_OF_ITERS)
281 )
282 &&
283 (current_iters_count < max_positions)
284 )
285 {
286 current_iters_count += CHUNKSIZE;
287 black_hole_solver_set_max_iters_limit(solver_instance, current_iters_count);
288
289 solver_ret = black_hole_solver_run(solver_instance);
290 {
291 // QMutexLocker lock( &endMutex );
292 if ( m_shouldEnd )
293 {
294 continue_loop = false;
295 }
296 }
297 }
298 }
299 switch (solver_ret)
300 {
301 case BLACK_HOLE_SOLVER__OUT_OF_ITERS:
302 free_solver_instance();
303 return Solver::UnableToDetermineSolvability;
304
305 case 0:
306 {
307 if (solver_instance)
308 {
309 m_winMoves.clear();
310 int col_idx, card_rank, card_suit;
311 int next_move_ret_code;
312 #ifdef BLACK_HOLE_SOLVER__API__REQUIRES_SETUP_CALL
313 black_hole_solver_init_solution_moves(solver_instance);
314 #endif
315 while ((next_move_ret_code = black_hole_solver_get_next_move(
316 solver_instance, &col_idx, &card_rank, &card_suit)) ==
317 BLACK_HOLE_SOLVER__SUCCESS)
318 {
319 MOVE new_move;
320 new_move.card_index = 0;
321 new_move.from = col_idx;
322 m_winMoves.append( new_move );
323 }
324
325 }
326 free_solver_instance();
327 return Solver::SolutionExists;
328 }
329
330 default:
331 free_solver_instance();
332 return Solver::UnableToDetermineSolvability;
333
334 case BLACK_HOLE_SOLVER__NOT_SOLVABLE:
335 free_solver_instance();
336 return Solver::NoSolutionExists;
337 }
338 }
339 #endif
340
341 /* Read a layout file. Format is one pile per line, bottom to top (visible
342 card). Temp cells and Out on the last two lines, if any. */
343
translate_layout()344 void GolfSolver::translate_layout()
345 {
346 #ifdef WITH_BH_SOLVER
347 strcpy(board_as_string, deal->solverFormat().toLatin1().constData());
348 free_solver_instance();
349 #else
350 /* Read the workspace. */
351
352 int total = 0;
353 for ( int w = 0; w < 7; ++w ) {
354 int i = translate_pile(deal->stack[w], W[w], 52);
355 Wp[w] = &W[w][i - 1];
356 Wlen[w] = i;
357 total += i;
358 }
359
360 int i = translate_pile( deal->waste, W[7], 52 );
361 Wp[7] = &W[7][i-1];
362 Wlen[7] = i;
363 total += i;
364
365 i = translate_pile( deal->talon, W[8], 52 );
366 Wp[8] = &W[8][i-1];
367 Wlen[8] = i;
368 total += i;
369
370 for ( int i = 0; i < 9; i++ )
371 {
372 for ( int l = 0; l < Wlen[i]; l++ )
373 {
374 card_t card = W[i][l];
375 if ( DOWN( card ) )
376 card = RANK( card ) + PS_SPADE + ( 1 << 7 );
377 else
378 card = RANK( card ) + PS_SPADE;
379 W[i][l] = card;
380 }
381 }
382 #endif
383 }
384
translateMove(const MOVE & m)385 MoveHint GolfSolver::translateMove( const MOVE &m )
386 {
387 if ( m.from >= 7 )
388 return MoveHint();
389 PatPile *frompile = deal->stack[m.from];
390
391 KCard *card = frompile->at( frompile->count() - m.card_index - 1);
392
393 return MoveHint( card, deal->waste, m.pri );
394 }
395
print_layout()396 void GolfSolver::print_layout()
397 {
398 #ifndef WITH_BH_SOLVER
399 fprintf(stderr, "print-layout-begin\n");
400 for (int w = 0; w < 9; w++) {
401 if ( w == 8 )
402 fprintf( stderr, "Deck: " );
403 else if ( w == 7 )
404 fprintf( stderr, "Pile: " );
405 else
406 fprintf( stderr, "Play%d: ", w );
407 for (int i = 0; i < Wlen[w]; i++) {
408 printcard(W[w][i], stderr);
409 }
410 fputc('\n', stderr);
411 }
412 fprintf(stderr, "print-layout-end\n");
413 #endif
414 }
415