Changeset View
Changeset View
Standalone View
Standalone View
patsolve/patsolve.cpp
Show First 20 Lines • Show All 89 Lines • ▼ Show 20 Line(s) | |||||
90 | } | 90 | } | ||
91 | 91 | | |||
92 | #define MAXDEPTH 400 | 92 | #define MAXDEPTH 400 | ||
93 | 93 | | |||
94 | bool Solver::recursive(POSITION *parent) | 94 | bool Solver::recursive(POSITION *parent) | ||
95 | { | 95 | { | ||
96 | int i, alln, a, numout = 0; | 96 | int i, alln, a, numout = 0; | ||
97 | 97 | | |||
98 | if ( parent == NULL ) { | 98 | if ( parent == nullptr ) { | ||
99 | init(); | 99 | init(); | ||
100 | recu_pos.clear(); | 100 | recu_pos.clear(); | ||
101 | delete Stack; | 101 | delete Stack; | ||
102 | Stack = new POSITION[MAXDEPTH]; | 102 | Stack = new POSITION[MAXDEPTH]; | ||
103 | memset( Stack, 0, sizeof( POSITION ) * MAXDEPTH ); | 103 | memset( Stack, 0, sizeof( POSITION ) * MAXDEPTH ); | ||
104 | } | 104 | } | ||
105 | 105 | | |||
106 | /* Fill in the Possible array. */ | 106 | /* Fill in the Possible array. */ | ||
Show All 23 Lines | 128 | /* Now copy to safe storage and return. Non-auto moves out get put | |||
130 | good moves, even if they didn't pass the automove test. So we still | 130 | good moves, even if they didn't pass the automove test. So we still | ||
131 | do the recursive solve() on them, but only after queueing the other | 131 | do the recursive solve() on them, but only after queueing the other | ||
132 | moves. */ | 132 | moves. */ | ||
133 | 133 | | |||
134 | if ( parent && parent->depth >= MAXDEPTH - 2 ) | 134 | if ( parent && parent->depth >= MAXDEPTH - 2 ) | ||
135 | return false; | 135 | return false; | ||
136 | 136 | | |||
137 | MOVE *mp0 = new_array(MOVE, alln+1); | 137 | MOVE *mp0 = new_array(MOVE, alln+1); | ||
138 | if (mp0 == NULL) { | 138 | if (mp0 == nullptr) { | ||
139 | return false; | 139 | return false; | ||
140 | } | 140 | } | ||
141 | MOVE *mp = mp0; | 141 | MOVE *mp = mp0; | ||
142 | for (i = 0; i < alln; ++i) { | 142 | for (i = 0; i < alln; ++i) { | ||
143 | if (Possible[i].card_index != -1) { | 143 | if (Possible[i].card_index != -1) { | ||
144 | *mp = Possible[i]; /* struct copy */ | 144 | *mp = Possible[i]; /* struct copy */ | ||
145 | mp++; | 145 | mp++; | ||
146 | } | 146 | } | ||
147 | } | 147 | } | ||
148 | mp->card_index = -1; | 148 | mp->card_index = -1; | ||
149 | ++alln; | 149 | ++alln; | ||
150 | 150 | | |||
151 | bool fit = false; | 151 | bool fit = false; | ||
152 | for (mp = mp0; mp->card_index != -1; ++mp) { | 152 | for (mp = mp0; mp->card_index != -1; ++mp) { | ||
153 | 153 | | |||
154 | int depth = 0; | 154 | int depth = 0; | ||
155 | if (parent != NULL) | 155 | if (parent != nullptr) | ||
156 | depth = parent->depth + 1; | 156 | depth = parent->depth + 1; | ||
157 | 157 | | |||
158 | make_move(mp); | 158 | make_move(mp); | ||
159 | 159 | | |||
160 | /* Calculate indices for the new piles. */ | 160 | /* Calculate indices for the new piles. */ | ||
161 | pilesort(); | 161 | pilesort(); | ||
162 | 162 | | |||
163 | /* See if this is a new position. */ | 163 | /* See if this is a new position. */ | ||
164 | 164 | | |||
165 | Total_generated++; | 165 | Total_generated++; | ||
166 | POSITION *pos = &Stack[depth]; | 166 | POSITION *pos = &Stack[depth]; | ||
167 | pos->queue = NULL; | 167 | pos->queue = nullptr; | ||
168 | pos->parent = parent; | 168 | pos->parent = parent; | ||
169 | pos->node = pack_position(); | 169 | pos->node = pack_position(); | ||
170 | quint8 *key = (quint8 *)pos->node + sizeof(TREE); | 170 | quint8 *key = (quint8 *)pos->node + sizeof(TREE); | ||
171 | #if 0 | 171 | #if 0 | ||
172 | qint32 hash = fnv_hash_buf(key, mm->Pilebytes); | 172 | qint32 hash = fnv_hash_buf(key, mm->Pilebytes); | ||
173 | if ( recu_pos.contains( hash ) ) | 173 | if ( recu_pos.contains( hash ) ) | ||
174 | { | 174 | { | ||
175 | undo_move( mp ); | 175 | undo_move( mp ); | ||
176 | mm->give_back_block( (quint8 *)pos->node ); | 176 | mm->give_back_block( (quint8 *)pos->node ); | ||
177 | continue; | 177 | continue; | ||
178 | } | 178 | } | ||
179 | recu_pos[hash] = true; | 179 | recu_pos[hash] = true; | ||
180 | #else | 180 | #else | ||
181 | for ( int i = 0; i < depth; ++i ) | 181 | for ( int i = 0; i < depth; ++i ) | ||
182 | { | 182 | { | ||
183 | quint8 *tkey = (quint8 *)Stack[i].node + sizeof(TREE); | 183 | quint8 *tkey = (quint8 *)Stack[i].node + sizeof(TREE); | ||
184 | if ( !memcmp( key, tkey, mm->Pilebytes ) ) | 184 | if ( !memcmp( key, tkey, mm->Pilebytes ) ) | ||
185 | { | 185 | { | ||
186 | key = 0; | 186 | key = nullptr; | ||
187 | break; | 187 | break; | ||
188 | } | 188 | } | ||
189 | } | 189 | } | ||
190 | if ( !key ) | 190 | if ( !key ) | ||
191 | { | 191 | { | ||
192 | undo_move( mp ); | 192 | undo_move( mp ); | ||
193 | mm->give_back_block( (quint8 *)pos->node ); | 193 | mm->give_back_block( (quint8 *)pos->node ); | ||
194 | continue; | 194 | continue; | ||
Show All 14 Lines | 196 | #endif | |||
209 | undo_move(mp); | 209 | undo_move(mp); | ||
210 | mm->give_back_block( (quint8 *)pos->node ); | 210 | mm->give_back_block( (quint8 *)pos->node ); | ||
211 | if ( ret ) | 211 | if ( ret ) | ||
212 | break; | 212 | break; | ||
213 | } | 213 | } | ||
214 | 214 | | |||
215 | MemoryManager::free_array(mp0, alln); | 215 | MemoryManager::free_array(mp0, alln); | ||
216 | 216 | | |||
217 | if ( parent == NULL ) { | 217 | if ( parent == nullptr ) { | ||
218 | printf( "Total %ld\n", Total_generated ); | 218 | printf( "Total %ld\n", Total_generated ); | ||
219 | delete [] Stack; | 219 | delete [] Stack; | ||
220 | Stack = 0; | 220 | Stack = nullptr; | ||
221 | } | 221 | } | ||
222 | return fit; | 222 | return fit; | ||
223 | } | 223 | } | ||
224 | 224 | | |||
225 | 225 | | |||
226 | /* Generate an array of the moves we can make from this position. */ | 226 | /* Generate an array of the moves we can make from this position. */ | ||
227 | 227 | | |||
228 | MOVE *Solver::get_moves(int *nmoves) | 228 | MOVE *Solver::get_moves(int *nmoves) | ||
Show All 20 Lines | 237 | { | |||
249 | } | 249 | } | ||
250 | } | 250 | } | ||
251 | 251 | | |||
252 | /* No moves? Maybe we won. */ | 252 | /* No moves? Maybe we won. */ | ||
253 | 253 | | |||
254 | if (n == 0) { | 254 | if (n == 0) { | ||
255 | /* No more moves - won or lost */ | 255 | /* No more moves - won or lost */ | ||
256 | //print_layout(); | 256 | //print_layout(); | ||
257 | return NULL; | 257 | return nullptr; | ||
258 | } | 258 | } | ||
259 | 259 | | |||
260 | /* Prioritize these moves. Automoves don't get queued, so they | 260 | /* Prioritize these moves. Automoves don't get queued, so they | ||
261 | don't need a priority. */ | 261 | don't need a priority. */ | ||
262 | 262 | | |||
263 | if (!a) { | 263 | if (!a) { | ||
264 | prioritize(Possible, alln); | 264 | prioritize(Possible, alln); | ||
265 | } | 265 | } | ||
266 | 266 | | |||
267 | /* Now copy to safe storage and return. Non-auto moves out get put | 267 | /* Now copy to safe storage and return. Non-auto moves out get put | ||
268 | at the end. Queueing them isn't a good idea because they are still | 268 | at the end. Queueing them isn't a good idea because they are still | ||
269 | good moves, even if they didn't pass the automove test. So we still | 269 | good moves, even if they didn't pass the automove test. So we still | ||
270 | do the recursive solve() on them, but only after queueing the other | 270 | do the recursive solve() on them, but only after queueing the other | ||
271 | moves. */ | 271 | moves. */ | ||
272 | 272 | | |||
273 | mp = mp0 = new_array(MOVE, n); | 273 | mp = mp0 = new_array(MOVE, n); | ||
274 | if (mp == NULL) { | 274 | if (mp == nullptr) { | ||
275 | return NULL; | 275 | return nullptr; | ||
276 | } | 276 | } | ||
277 | *nmoves = n; | 277 | *nmoves = n; | ||
278 | i = 0; | 278 | i = 0; | ||
279 | if (a || numout == 0) { | 279 | if (a || numout == 0) { | ||
280 | for (i = 0; i < alln; ++i) { | 280 | for (i = 0; i < alln; ++i) { | ||
281 | if (Possible[i].card_index != -1) { | 281 | if (Possible[i].card_index != -1) { | ||
282 | *mp = Possible[i]; /* struct copy */ | 282 | *mp = Possible[i]; /* struct copy */ | ||
283 | mp++; | 283 | mp++; | ||
Show All 17 Lines | |||||
301 | return mp0; | 301 | return mp0; | ||
302 | } | 302 | } | ||
303 | 303 | | |||
304 | /* Test the current position to see if it's new (or better). If it is, save | 304 | /* Test the current position to see if it's new (or better). If it is, save | ||
305 | it, along with the pointer to its parent and the move we used to get here. */ | 305 | it, along with the pointer to its parent and the move we used to get here. */ | ||
306 | 306 | | |||
307 | int Posbytes; | 307 | int Posbytes; | ||
308 | 308 | | |||
309 | /* Comparison function for sorting the W piles. */ | | |||
310 | | ||||
311 | int Solver::wcmp(int a, int b) | | |||
312 | { | | |||
313 | if (m_newer_piles_first) { | | |||
314 | return Wpilenum[b] - Wpilenum[a]; /* newer piles first */ | | |||
315 | } else { | | |||
316 | return Wpilenum[a] - Wpilenum[b]; /* older piles first */ | | |||
317 | } | | |||
318 | } | | |||
319 | | ||||
320 | void Solver::pilesort(void) | 309 | void Solver::pilesort(void) | ||
321 | { | 310 | { | ||
322 | /* Make sure all the piles have id numbers. */ | 311 | /* Make sure all the piles have id numbers. */ | ||
323 | 312 | | |||
324 | for (int w = 0; w < m_number_piles; w++) { | 313 | for (int w = 0; w < m_number_piles; w++) { | ||
325 | if (Wpilenum[w] < 0) { | 314 | if (Wpilenum[w] < 0) { | ||
326 | Wpilenum[w] = get_pilenum(w); | 315 | Wpilenum[w] = get_pilenum(w); | ||
327 | if (Wpilenum[w] < 0) { | 316 | if (Wpilenum[w] < 0) { | ||
Show All 37 Lines | 353 | { | |||
365 | int j, w; | 354 | int j, w; | ||
366 | quint8 *p; | 355 | quint8 *p; | ||
367 | TREE *node; | 356 | TREE *node; | ||
368 | 357 | | |||
369 | /* Allocate space and store the pile numbers. The tree node | 358 | /* Allocate space and store the pile numbers. The tree node | ||
370 | will get filled in later, by insert_node(). */ | 359 | will get filled in later, by insert_node(). */ | ||
371 | 360 | | |||
372 | p = mm->new_from_block(Treebytes); | 361 | p = mm->new_from_block(Treebytes); | ||
373 | if (p == NULL) { | 362 | if (p == nullptr) { | ||
374 | Status = UnableToDetermineSolvability; | 363 | Status = UnableToDetermineSolvability; | ||
375 | return NULL; | 364 | return nullptr; | ||
376 | } | 365 | } | ||
377 | node = (TREE *)p; | 366 | node = (TREE *)p; | ||
378 | p += sizeof(TREE); | 367 | p += sizeof(TREE); | ||
379 | 368 | | |||
380 | /* Pack the pile numers j into bytes p. | 369 | /* Pack the pile numers j into bytes p. | ||
381 | j j | 370 | j j | ||
382 | +--------+----:----+--------+ | 371 | +--------+----:----+--------+ | ||
383 | |76543210|7654:3210|76543210| | 372 | |76543210|7654:3210|76543210| | ||
384 | +--------+----:----+--------+ | 373 | +--------+----:----+--------+ | ||
385 | p p p | 374 | p p p | ||
386 | */ | 375 | */ | ||
387 | 376 | | |||
388 | quint16 *p2 = ( quint16* ) p; | 377 | quint16 *p2 = ( quint16* ) p; | ||
389 | for (w = 0; w < m_number_piles; ++w) { | 378 | for (w = 0; w < m_number_piles; ++w) { | ||
390 | j = Wpilenum[w]; | 379 | j = Wpilenum[w]; | ||
391 | if ( j < 0 ) | 380 | if ( j < 0 ) | ||
392 | { | 381 | { | ||
393 | mm->give_back_block( p ); | 382 | mm->give_back_block( p ); | ||
394 | return NULL; | 383 | return nullptr; | ||
395 | } | 384 | } | ||
396 | *p2++ = j; | 385 | *p2++ = j; | ||
397 | } | 386 | } | ||
398 | 387 | | |||
399 | return node; | 388 | return node; | ||
400 | } | 389 | } | ||
401 | 390 | | |||
402 | /* Like strcpy() but return the length of the string. */ | 391 | /* Like strcpy() but return the length of the string. */ | ||
Show All 11 Lines | |||||
414 | } | 403 | } | ||
415 | 404 | | |||
416 | /* Unpack a compact position rep. T cells must be restored from the | 405 | /* Unpack a compact position rep. T cells must be restored from the | ||
417 | array following the POSITION struct. */ | 406 | array following the POSITION struct. */ | ||
418 | 407 | | |||
419 | void Solver::unpack_position(POSITION *pos) | 408 | void Solver::unpack_position(POSITION *pos) | ||
420 | { | 409 | { | ||
421 | int i, w; | 410 | int i, w; | ||
422 | quint8 c; | | |||
423 | BUCKETLIST *l; | 411 | BUCKETLIST *l; | ||
424 | 412 | | |||
425 | unpack_cluster(pos->cluster); | 413 | unpack_cluster(pos->cluster); | ||
426 | 414 | | |||
427 | /* Unpack bytes p into pile numbers j. | 415 | /* Unpack bytes p into pile numbers j. | ||
428 | p p p | 416 | p p p | ||
429 | +--------+----:----+--------+ | 417 | +--------+----:----+--------+ | ||
430 | |76543210|7654:3210|76543210| | 418 | |76543210|7654:3210|76543210| | ||
431 | +--------+----:----+--------+ | 419 | +--------+----:----+--------+ | ||
432 | j j | 420 | j j | ||
433 | */ | 421 | */ | ||
434 | 422 | | |||
435 | w = i = c = 0; | 423 | w = i = 0; | ||
436 | quint16 *p2 = ( quint16* )( (quint8 *)(pos->node) + sizeof(TREE) ); | 424 | quint16 *p2 = ( quint16* )( (quint8 *)(pos->node) + sizeof(TREE) ); | ||
437 | while (w < m_number_piles) { | 425 | while (w < m_number_piles) { | ||
438 | i = *p2++; | 426 | i = *p2++; | ||
439 | Wpilenum[w] = i; | 427 | Wpilenum[w] = i; | ||
440 | l = Pilebucket[i]; | 428 | l = Pilebucket[i]; | ||
441 | i = strecpy(W[w], l->pile); | 429 | i = strecpy(W[w], l->pile); | ||
442 | Wp[w] = &W[w][i - 1]; | 430 | Wp[w] = &W[w][i - 1]; | ||
443 | Wlen[w] = i; | 431 | Wlen[w] = i; | ||
Show All 32 Lines | 455 | { | |||
476 | for (p = pos; p->parent; p = p->parent) { | 464 | for (p = pos; p->parent; p = p->parent) { | ||
477 | i++; | 465 | i++; | ||
478 | } | 466 | } | ||
479 | nmoves = i; | 467 | nmoves = i; | ||
480 | 468 | | |||
481 | //printf("Winning in %d moves.\n", nmoves); | 469 | //printf("Winning in %d moves.\n", nmoves); | ||
482 | 470 | | |||
483 | mpp0 = new_array(MOVE *, nmoves); | 471 | mpp0 = new_array(MOVE *, nmoves); | ||
484 | if (mpp0 == NULL) { | 472 | if (mpp0 == nullptr) { | ||
485 | Status = UnableToDetermineSolvability; | 473 | Status = UnableToDetermineSolvability; | ||
486 | return; /* how sad, so close... */ | 474 | return; /* how sad, so close... */ | ||
487 | } | 475 | } | ||
488 | mpp = mpp0 + nmoves - 1; | 476 | mpp = mpp0 + nmoves - 1; | ||
489 | for (p = pos; p->parent; p = p->parent) { | 477 | for (p = pos; p->parent; p = p->parent) { | ||
490 | *mpp-- = &p->move; | 478 | *mpp-- = &p->move; | ||
491 | } | 479 | } | ||
492 | 480 | | |||
▲ Show 20 Lines • Show All 53 Lines • ▼ Show 20 Line(s) | 530 | { | |||
546 | /* For a given pile, get its unique pile id. If it doesn't have | 534 | /* For a given pile, get its unique pile id. If it doesn't have | ||
547 | one, add it to the appropriate list and give it one. First, get | 535 | one, add it to the appropriate list and give it one. First, get | ||
548 | the hash bucket. */ | 536 | the hash bucket. */ | ||
549 | 537 | | |||
550 | bucket = Whash[w] % NBUCKETS; | 538 | bucket = Whash[w] % NBUCKETS; | ||
551 | 539 | | |||
552 | /* Look for the pile in this bucket. */ | 540 | /* Look for the pile in this bucket. */ | ||
553 | 541 | | |||
554 | last = NULL; | 542 | last = nullptr; | ||
555 | for (l = Bucketlist[bucket]; l; l = l->next) { | 543 | for (l = Bucketlist[bucket]; l; l = l->next) { | ||
556 | if (l->hash == Whash[w] && | 544 | if (l->hash == Whash[w] && | ||
557 | strncmp((char*)l->pile, (char*)W[w], Wlen[w]) == 0) { | 545 | strncmp((char*)l->pile, (char*)W[w], Wlen[w]) == 0) { | ||
558 | break; | 546 | break; | ||
559 | } | 547 | } | ||
560 | last = l; | 548 | last = l; | ||
561 | } | 549 | } | ||
562 | 550 | | |||
563 | /* If we didn't find it, make a new one and add it to the list. */ | 551 | /* If we didn't find it, make a new one and add it to the list. */ | ||
564 | 552 | | |||
565 | if (l == NULL) { | 553 | if (l == nullptr) { | ||
566 | if (Pilenum >= NPILES ) { | 554 | if (Pilenum >= NPILES ) { | ||
567 | Status = UnableToDetermineSolvability; | 555 | Status = UnableToDetermineSolvability; | ||
568 | //qDebug() << "out of piles"; | 556 | //qDebug() << "out of piles"; | ||
569 | return -1; | 557 | return -1; | ||
570 | } | 558 | } | ||
571 | l = mm_allocate(BUCKETLIST); | 559 | l = mm_allocate(BUCKETLIST); | ||
572 | if (l == NULL) { | 560 | if (l == nullptr) { | ||
573 | Status = UnableToDetermineSolvability; | 561 | Status = UnableToDetermineSolvability; | ||
574 | //qDebug() << "out of buckets"; | 562 | //qDebug() << "out of buckets"; | ||
575 | return -1; | 563 | return -1; | ||
576 | } | 564 | } | ||
577 | l->pile = new_array(quint8, Wlen[w] + 1); | 565 | l->pile = new_array(quint8, Wlen[w] + 1); | ||
578 | if (l->pile == NULL) { | 566 | if (l->pile == nullptr) { | ||
579 | Status = UnableToDetermineSolvability; | 567 | Status = UnableToDetermineSolvability; | ||
580 | MemoryManager::free_ptr(l); | 568 | MemoryManager::free_ptr(l); | ||
581 | //qDebug() << "out of memory"; | 569 | //qDebug() << "out of memory"; | ||
582 | return -1; | 570 | return -1; | ||
583 | } | 571 | } | ||
584 | 572 | | |||
585 | /* Store the new pile along with its hash. Maintain | 573 | /* Store the new pile along with its hash. Maintain | ||
586 | a reverse mapping so we can unpack the piles swiftly. */ | 574 | a reverse mapping so we can unpack the piles swiftly. */ | ||
587 | 575 | | |||
588 | strncpy((char*)l->pile, (char*)W[w], Wlen[w] + 1); | 576 | strncpy((char*)l->pile, (char*)W[w], Wlen[w] + 1); | ||
589 | l->hash = Whash[w]; | 577 | l->hash = Whash[w]; | ||
590 | l->pilenum = pilenum = Pilenum++; | 578 | l->pilenum = pilenum = Pilenum++; | ||
591 | l->next = NULL; | 579 | l->next = nullptr; | ||
592 | if (last == NULL) { | 580 | if (last == nullptr) { | ||
593 | Bucketlist[bucket] = l; | 581 | Bucketlist[bucket] = l; | ||
594 | } else { | 582 | } else { | ||
595 | last->next = l; | 583 | last->next = l; | ||
596 | } | 584 | } | ||
597 | Pilebucket[pilenum] = l; | 585 | Pilebucket[pilenum] = l; | ||
598 | } | 586 | } | ||
599 | 587 | | |||
600 | #if 0 | 588 | #if 0 | ||
Show All 36 Lines | 624 | { | |||
637 | int i, q; | 625 | int i, q; | ||
638 | POSITION *pos; | 626 | POSITION *pos; | ||
639 | MOVE m; | 627 | MOVE m; | ||
640 | memset( &m, 0, sizeof( MOVE ) ); | 628 | memset( &m, 0, sizeof( MOVE ) ); | ||
641 | 629 | | |||
642 | /* Init the queues. */ | 630 | /* Init the queues. */ | ||
643 | 631 | | |||
644 | for (i = 0; i < NQUEUES; ++i) { | 632 | for (i = 0; i < NQUEUES; ++i) { | ||
645 | Qhead[i] = NULL; | 633 | Qhead[i] = nullptr; | ||
646 | } | 634 | } | ||
647 | Maxq = 0; | 635 | Maxq = 0; | ||
648 | 636 | | |||
649 | /* Queue the initial position to get started. */ | 637 | /* Queue the initial position to get started. */ | ||
650 | 638 | | |||
651 | hash_layout(); | 639 | hash_layout(); | ||
652 | pilesort(); | 640 | pilesort(); | ||
653 | m.card_index = -1; | 641 | m.card_index = -1; | ||
654 | m.turn_index = -1; | 642 | m.turn_index = -1; | ||
655 | pos = new_position(NULL, &m); | 643 | pos = new_position(nullptr, &m); | ||
656 | if ( pos == NULL ) | 644 | if ( pos == nullptr ) | ||
657 | { | 645 | { | ||
658 | Status = UnableToDetermineSolvability; | 646 | Status = UnableToDetermineSolvability; | ||
659 | return; | 647 | return; | ||
660 | } | 648 | } | ||
661 | queue_position(pos, 0); | 649 | queue_position(pos, 0); | ||
662 | 650 | | |||
663 | /* Solve it. */ | 651 | /* Solve it. */ | ||
664 | 652 | | |||
665 | while ((pos = dequeue_position()) != NULL) { | 653 | while ((pos = dequeue_position()) != nullptr) { | ||
666 | q = solve(pos); | 654 | q = solve(pos); | ||
667 | if (!q) { | 655 | if (!q) { | ||
668 | free_position(pos, true); | 656 | free_position(pos, true); | ||
669 | } | 657 | } | ||
670 | } | 658 | } | ||
671 | } | 659 | } | ||
672 | 660 | | |||
673 | /* Generate all the successors to a position and either queue them or | 661 | /* Generate all the successors to a position and either queue them or | ||
Show All 30 Lines | 680 | } | |||
704 | { | 692 | { | ||
705 | Status = MemoryLimitReached; | 693 | Status = MemoryLimitReached; | ||
706 | return false; | 694 | return false; | ||
707 | } | 695 | } | ||
708 | 696 | | |||
709 | 697 | | |||
710 | /* Generate an array of all the moves we can make. */ | 698 | /* Generate an array of all the moves we can make. */ | ||
711 | 699 | | |||
712 | if ((mp0 = get_moves(&nmoves)) == NULL) { | 700 | if ((mp0 = get_moves(&nmoves)) == nullptr) { | ||
713 | if ( isWon() ) { | 701 | if ( isWon() ) { | ||
714 | Status = SolutionExists; | 702 | Status = SolutionExists; | ||
715 | win( parent ); | 703 | win( parent ); | ||
716 | } | 704 | } | ||
717 | return false; | 705 | return false; | ||
718 | } | 706 | } | ||
719 | 707 | | |||
720 | if ( parent->depth == 0 ) | 708 | if ( parent->depth == 0 ) | ||
Show All 12 Lines | 720 | for (i = 0, mp = mp0; i < nmoves; ++i, ++mp) { | |||
733 | make_move(mp); | 721 | make_move(mp); | ||
734 | 722 | | |||
735 | /* Calculate indices for the new piles. */ | 723 | /* Calculate indices for the new piles. */ | ||
736 | 724 | | |||
737 | pilesort(); | 725 | pilesort(); | ||
738 | 726 | | |||
739 | /* See if this is a new position. */ | 727 | /* See if this is a new position. */ | ||
740 | 728 | | |||
741 | if ((pos = new_position(parent, mp)) == NULL) { | 729 | if ((pos = new_position(parent, mp)) == nullptr) { | ||
742 | undo_move(mp); | 730 | undo_move(mp); | ||
743 | parent->nchild--; | 731 | parent->nchild--; | ||
744 | continue; | 732 | continue; | ||
745 | } | 733 | } | ||
746 | 734 | | |||
747 | /* If this position is in a new cluster, a card went out. | 735 | /* If this position is in a new cluster, a card went out. | ||
748 | Don't queue it, just keep going. A larger cutoff can also | 736 | Don't queue it, just keep going. A larger cutoff can also | ||
749 | force a recursive call, which can help speed things up (but | 737 | force a recursive call, which can help speed things up (but | ||
Show All 35 Lines | 772 | if (!rec) { | |||
785 | pos->queue = Freepos; | 773 | pos->queue = Freepos; | ||
786 | Freepos = pos; | 774 | Freepos = pos; | ||
787 | pos->parent->nchild--; | 775 | pos->parent->nchild--; | ||
788 | } else { | 776 | } else { | ||
789 | do { | 777 | do { | ||
790 | pos->queue = Freepos; | 778 | pos->queue = Freepos; | ||
791 | Freepos = pos; | 779 | Freepos = pos; | ||
792 | pos = pos->parent; | 780 | pos = pos->parent; | ||
793 | if (pos == NULL) { | 781 | if (pos == nullptr) { | ||
794 | return; | 782 | return; | ||
795 | } | 783 | } | ||
796 | pos->nchild--; | 784 | pos->nchild--; | ||
797 | } while (pos->nchild == 0); | 785 | } while (pos->nchild == 0); | ||
798 | } | 786 | } | ||
799 | } | 787 | } | ||
800 | 788 | | |||
801 | /* Save positions for consideration later. pri is the priority of the move | 789 | /* Save positions for consideration later. pri is the priority of the move | ||
Show All 20 Lines | 794 | { | |||
822 | if (pri > Maxq) { | 810 | if (pri > Maxq) { | ||
823 | Maxq = pri; | 811 | Maxq = pri; | ||
824 | } | 812 | } | ||
825 | 813 | | |||
826 | /* We always dequeue from the head. Here we either stick the move | 814 | /* We always dequeue from the head. Here we either stick the move | ||
827 | at the head or tail of the queue, depending on whether we're | 815 | at the head or tail of the queue, depending on whether we're | ||
828 | pretending it's a stack or a queue. */ | 816 | pretending it's a stack or a queue. */ | ||
829 | 817 | | |||
830 | pos->queue = NULL; | 818 | pos->queue = nullptr; | ||
831 | if (Qhead[pri] == NULL) { | 819 | if (Qhead[pri] == nullptr) { | ||
832 | Qhead[pri] = pos; | 820 | Qhead[pri] = pos; | ||
833 | } else { | 821 | } else { | ||
834 | pos->queue = Qhead[pri]; | 822 | pos->queue = Qhead[pri]; | ||
835 | Qhead[pri] = pos; | 823 | Qhead[pri] = pos; | ||
836 | } | 824 | } | ||
837 | } | 825 | } | ||
838 | 826 | | |||
839 | /* Return the position on the head of the queue, or NULL if there isn't one. */ | 827 | /* Return the position on the head of the queue, or NULL if there isn't one. */ | ||
Show All 12 Lines | 830 | { | |||
852 | but we still get lots of low priority action (instead of | 840 | but we still get lots of low priority action (instead of | ||
853 | ignoring it completely). */ | 841 | ignoring it completely). */ | ||
854 | 842 | | |||
855 | last = false; | 843 | last = false; | ||
856 | do { | 844 | do { | ||
857 | qpos--; | 845 | qpos--; | ||
858 | if (qpos < minpos) { | 846 | if (qpos < minpos) { | ||
859 | if (last) { | 847 | if (last) { | ||
860 | return NULL; | 848 | return nullptr; | ||
861 | } | 849 | } | ||
862 | qpos = Maxq; | 850 | qpos = Maxq; | ||
863 | minpos--; | 851 | minpos--; | ||
864 | if (minpos < 0) { | 852 | if (minpos < 0) { | ||
865 | minpos = Maxq; | 853 | minpos = Maxq; | ||
866 | } | 854 | } | ||
867 | if (minpos == 0) { | 855 | if (minpos == 0) { | ||
868 | last = true; | 856 | last = true; | ||
869 | } | 857 | } | ||
870 | } | 858 | } | ||
871 | } while (Qhead[qpos] == NULL); | 859 | } while (Qhead[qpos] == nullptr); | ||
872 | 860 | | |||
873 | pos = Qhead[qpos]; | 861 | pos = Qhead[qpos]; | ||
874 | Qhead[qpos] = pos->queue; | 862 | Qhead[qpos] = pos->queue; | ||
875 | 863 | | |||
876 | /* Decrease Maxq if that queue emptied. */ | 864 | /* Decrease Maxq if that queue emptied. */ | ||
877 | 865 | | |||
878 | while (Qhead[qpos] == NULL && qpos == Maxq && Maxq > 0) { | 866 | while (Qhead[qpos] == nullptr && qpos == Maxq && Maxq > 0) { | ||
879 | Maxq--; | 867 | Maxq--; | ||
880 | qpos--; | 868 | qpos--; | ||
881 | if (qpos < minpos) { | 869 | if (qpos < minpos) { | ||
882 | minpos = qpos; | 870 | minpos = qpos; | ||
883 | } | 871 | } | ||
884 | } | 872 | } | ||
885 | 873 | | |||
886 | /* Unpack the position into the work arrays. */ | 874 | /* Unpack the position into the work arrays. */ | ||
887 | 875 | | |||
888 | unpack_position(pos); | 876 | unpack_position(pos); | ||
889 | 877 | | |||
890 | return pos; | 878 | return pos; | ||
891 | } | 879 | } | ||
892 | 880 | | |||
893 | Solver::Solver() | 881 | Solver::Solver() | ||
894 | { | 882 | { | ||
895 | mm = new MemoryManager(); | 883 | mm = new MemoryManager(); | ||
896 | Freepos = NULL; | 884 | Freepos = nullptr; | ||
897 | m_newer_piles_first = true; | | |||
898 | /* Work arrays. */ | 885 | /* Work arrays. */ | ||
899 | W = 0; | 886 | W = nullptr; | ||
900 | Wp = 0; | 887 | Wp = nullptr; | ||
901 | 888 | | |||
902 | Wlen = 0; | 889 | Wlen = nullptr; | ||
903 | 890 | | |||
904 | Whash = 0; | 891 | Whash = nullptr; | ||
905 | Wpilenum = 0; | 892 | Wpilenum = nullptr; | ||
906 | Stack = 0; | 893 | Stack = nullptr; | ||
907 | } | 894 | } | ||
908 | 895 | | |||
909 | Solver::~Solver() | 896 | Solver::~Solver() | ||
910 | { | 897 | { | ||
911 | delete mm; | 898 | delete mm; | ||
912 | 899 | | |||
913 | for ( int i = 0; i < m_number_piles; ++i ) | 900 | for ( int i = 0; i < m_number_piles; ++i ) | ||
914 | { | 901 | { | ||
Show All 24 Lines | 913 | { | |||
939 | depth_sum = 0; | 926 | depth_sum = 0; | ||
940 | } | 927 | } | ||
941 | 928 | | |||
942 | void Solver::free() | 929 | void Solver::free() | ||
943 | { | 930 | { | ||
944 | free_buckets(); | 931 | free_buckets(); | ||
945 | mm->free_clusters(); | 932 | mm->free_clusters(); | ||
946 | mm->free_blocks(); | 933 | mm->free_blocks(); | ||
947 | Freepos = NULL; | 934 | Freepos = nullptr; | ||
948 | } | 935 | } | ||
949 | 936 | | |||
950 | 937 | | |||
951 | Solver::ExitStatus Solver::patsolve( int _max_positions, bool _debug ) | 938 | Solver::ExitStatus Solver::patsolve( int _max_positions, bool _debug ) | ||
952 | { | 939 | { | ||
953 | max_positions = _max_positions; | 940 | max_positions = _max_positions; | ||
954 | debug = _debug; | 941 | debug = _debug; | ||
955 | 942 | | |||
▲ Show 20 Lines • Show All 75 Lines • ▼ Show 20 Line(s) | 1017 | { | |||
1031 | /* Get the cluster number from the Out cell contents. */ | 1018 | /* Get the cluster number from the Out cell contents. */ | ||
1032 | 1019 | | |||
1033 | unsigned int k = getClusterNumber(); | 1020 | unsigned int k = getClusterNumber(); | ||
1034 | *cluster = k; | 1021 | *cluster = k; | ||
1035 | 1022 | | |||
1036 | /* Get the tree for this cluster. */ | 1023 | /* Get the tree for this cluster. */ | ||
1037 | 1024 | | |||
1038 | TREELIST *tl = mm->cluster_tree(k); | 1025 | TREELIST *tl = mm->cluster_tree(k); | ||
1039 | if (tl == NULL) { | 1026 | if (tl == nullptr) { | ||
1040 | return MemoryManager::ERR; | 1027 | return MemoryManager::ERR; | ||
1041 | } | 1028 | } | ||
1042 | 1029 | | |||
1043 | /* Create a compact position representation. */ | 1030 | /* Create a compact position representation. */ | ||
1044 | 1031 | | |||
1045 | TREE *newtree = pack_position(); | 1032 | TREE *newtree = pack_position(); | ||
1046 | if (newtree == NULL) { | 1033 | if (newtree == nullptr) { | ||
1047 | return MemoryManager::ERR; | 1034 | return MemoryManager::ERR; | ||
1048 | } | 1035 | } | ||
1049 | Total_generated++; | 1036 | Total_generated++; | ||
1050 | 1037 | | |||
1051 | MemoryManager::inscode i2 = mm->insert_node(newtree, d, &tl->tree, node); | 1038 | MemoryManager::inscode i2 = mm->insert_node(newtree, d, &tl->tree, node); | ||
1052 | 1039 | | |||
1053 | if (i2 != MemoryManager::NEW) { | 1040 | if (i2 != MemoryManager::NEW) { | ||
1054 | mm->give_back_block((quint8 *)newtree); | 1041 | mm->give_back_block((quint8 *)newtree); | ||
1055 | } | 1042 | } | ||
1056 | 1043 | | |||
1057 | return i2; | 1044 | return i2; | ||
1058 | } | 1045 | } | ||
1059 | 1046 | | |||
1060 | 1047 | | |||
1061 | POSITION *Solver::new_position(POSITION *parent, MOVE *m) | 1048 | POSITION *Solver::new_position(POSITION *parent, MOVE *m) | ||
1062 | { | 1049 | { | ||
1063 | unsigned int depth, cluster; | 1050 | unsigned int depth, cluster; | ||
1064 | quint8 *p; | 1051 | quint8 *p; | ||
1065 | POSITION *pos; | 1052 | POSITION *pos; | ||
1066 | TREE *node; | 1053 | TREE *node; | ||
1067 | 1054 | | |||
1068 | /* Search the list of stored positions. If this position is found, | 1055 | /* Search the list of stored positions. If this position is found, | ||
1069 | then ignore it and return (unless this position is better). */ | 1056 | then ignore it and return (unless this position is better). */ | ||
1070 | 1057 | | |||
1071 | if (parent == NULL) { | 1058 | if (parent == nullptr) { | ||
1072 | depth = 0; | 1059 | depth = 0; | ||
1073 | } else { | 1060 | } else { | ||
1074 | depth = parent->depth + 1; | 1061 | depth = parent->depth + 1; | ||
1075 | } | 1062 | } | ||
1076 | MemoryManager::inscode i = insert(&cluster, depth, &node); | 1063 | MemoryManager::inscode i = insert(&cluster, depth, &node); | ||
1077 | if (i == MemoryManager::NEW) { | 1064 | if (i == MemoryManager::NEW) { | ||
1078 | Total_positions++; | 1065 | Total_positions++; | ||
1079 | depth_sum += depth; | 1066 | depth_sum += depth; | ||
1080 | } else | 1067 | } else | ||
1081 | return NULL; | 1068 | return nullptr; | ||
1082 | 1069 | | |||
1083 | 1070 | | |||
1084 | /* A new or better position. insert() already stashed it in the | 1071 | /* A new or better position. insert() already stashed it in the | ||
1085 | tree, we just have to wrap a POSITION struct around it, and link it | 1072 | tree, we just have to wrap a POSITION struct around it, and link it | ||
1086 | into the move stack. Store the temp cells after the POSITION. */ | 1073 | into the move stack. Store the temp cells after the POSITION. */ | ||
1087 | 1074 | | |||
1088 | if (Freepos) { | 1075 | if (Freepos) { | ||
1089 | p = (quint8 *)Freepos; | 1076 | p = (quint8 *)Freepos; | ||
1090 | Freepos = Freepos->queue; | 1077 | Freepos = Freepos->queue; | ||
1091 | } else { | 1078 | } else { | ||
1092 | p = mm->new_from_block(Posbytes); | 1079 | p = mm->new_from_block(Posbytes); | ||
1093 | if (p == NULL) { | 1080 | if (p == nullptr) { | ||
1094 | Status = UnableToDetermineSolvability; | 1081 | Status = UnableToDetermineSolvability; | ||
1095 | return NULL; | 1082 | return nullptr; | ||
1096 | } | 1083 | } | ||
1097 | } | 1084 | } | ||
1098 | 1085 | | |||
1099 | pos = (POSITION *)p; | 1086 | pos = (POSITION *)p; | ||
1100 | pos->queue = NULL; | 1087 | pos->queue = nullptr; | ||
1101 | pos->parent = parent; | 1088 | pos->parent = parent; | ||
1102 | pos->node = node; | 1089 | pos->node = node; | ||
1103 | pos->move = *m; /* struct copy */ | 1090 | pos->move = *m; /* struct copy */ | ||
1104 | pos->cluster = cluster; | 1091 | pos->cluster = cluster; | ||
1105 | pos->depth = depth; | 1092 | pos->depth = depth; | ||
1106 | pos->nchild = 0; | 1093 | pos->nchild = 0; | ||
1107 | #if 0 | 1094 | #if 0 | ||
1108 | QString dummy; | 1095 | QString dummy; | ||
Show All 28 Lines |