1#!/usr/bin/env python 2# -*- mode: python; coding: utf-8; -*- 3# ---------------------------------------------------------------------------## 4# 5# Copyright (C) 1998-2003 Markus Franz Xaver Johannes Oberhumer 6# Copyright (C) 2003 Mt. Hood Playing Card Co. 7# Copyright (C) 2005-2009 Skomoroh 8# 9# This program is free software: you can redistribute it and/or modify 10# it under the terms of the GNU General Public License as published by 11# the Free Software Foundation, either version 3 of the License, or 12# (at your option) any later version. 13# 14# This program is distributed in the hope that it will be useful, 15# but WITHOUT ANY WARRANTY; without even the implied warranty of 16# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17# GNU General Public License for more details. 18# 19# You should have received a copy of the GNU General Public License 20# along with this program. If not, see <http://www.gnu.org/licenses/>. 21# 22# ---------------------------------------------------------------------------## 23 24 25import os 26import re 27import subprocess 28import time 29from io import BytesIO 30 31from pysollib.mfxutil import destruct 32from pysollib.pysolrandom import construct_random 33from pysollib.settings import DEBUG, FCS_COMMAND 34from pysollib.util import KING 35 36import six 37 38FCS_VERSION = None 39 40# ************************************************************************ 41# * HintInterface is an abstract class that defines the public 42# * interface - it only consists of the constructor 43# * and the getHints() method. 44# * 45# * The whole hint system is exclusively used by Game.getHints(). 46# ************************************************************************ 47 48 49class HintInterface: 50 # level == 0: show hint (key `H') 51 # level == 1: show hint and display score value (key `Ctrl-H') 52 # level == 2: demo 53 def __init__(self, game, level): 54 pass 55 56 # Compute all hints for the current position. 57 # Subclass responsibility. 58 # 59 # Returns a list of "atomic hints" - an atomic hint is a 7-tuple 60 # (score, pos, ncards, from_stack, to_stack, text_color, forced_move). 61 # 62 # if ncards == 0: deal cards 63 # elif from_stack == to_stack: flip card 64 # else: move cards from from_stack to to_stack 65 # 66 # score, pos and text_color are only for debugging. 67 # A forced_move is the next move that must be taken after this move 68 # in order to avoid endless loops during demo play. 69 # 70 # Deal and flip may only happen if self.level >= 2 (i.e. demo). 71 # 72 # See Game.showHint() for more information. 73 def getHints(self, taken_hint=None): 74 return [] 75 76 77# ************************************************************************ 78# * AbstractHint provides a useful framework for derived hint classes. 79# * 80# * Subclasses should override computeHints() 81# ************************************************************************ 82 83class AbstractHint(HintInterface): 84 def __init__(self, game, level): 85 self.game = game 86 self.level = level 87 self.score_flatten_value = 0 88 if self.level == 0: 89 self.score_flatten_value = 10000 90 # temporaries within getHints() 91 self.bonus_color = None 92 # 93 self.__clones = [] 94 self.reset() 95 96 def __del__(self): 97 self.reset() 98 99 def reset(self): 100 self.hints = [] 101 self.max_score = 0 102 self.__destructClones() 103 self.solver_state = 'not_started' 104 105 # 106 # stack cloning 107 # 108 109 # Create a shallow copy of a stack. 110 class AClonedStack: 111 def __init__(self, stack, stackcards): 112 # copy class identity 113 self.__class__ = stack.__class__ 114 # copy model data (reference copy) 115 stack.copyModel(self) 116 # set new cards (shallow copy of the card list) 117 self.cards = stackcards[:] 118 119 def ClonedStack(self, stack, stackcards): 120 s = self.AClonedStack(stack, stackcards) 121 self.__clones.append(s) 122 return s 123 124 def __destructClones(self): 125 for s in self.__clones: 126 s.__class__ = self.AClonedStack # restore orignal class 127 destruct(s) 128 self.__clones = [] 129 130 # When computing hints for level 0, the scores are flattened 131 # (rounded down) to a multiple of score_flatten_value. 132 # 133 # The idea is that hints will appear equal within a certain score range 134 # so that the player will not get confused by the demo-intelligence. 135 # 136 # Pressing `Ctrl-H' (level 1) will preserve the score. 137 138 def addHint(self, score, ncards, from_stack, 139 to_stack, text_color=None, forced_move=None): 140 if score < 0: 141 return 142 self.max_score = max(self.max_score, score) 143 # add an atomic hint 144 if self.score_flatten_value > 0: 145 score = (score // self.score_flatten_value) * \ 146 self.score_flatten_value 147 if text_color is None: 148 text_color = self.BLACK 149 assert forced_move is None or len(forced_move) == 7 150 # pos is used for preserving the original sort order on equal scores 151 pos = -len(self.hints) 152 ah = (int(score), pos, ncards, from_stack, to_stack, 153 text_color, forced_move) 154 self.hints.append(ah) 155 156 # clean up and return hints sorted by score 157 def _returnHints(self): 158 hints = self.hints 159 self.reset() 160 hints.sort() 161 hints.reverse() 162 return hints 163 164 # 165 # getHints() default implementation: 166 # - handle forced moves 167 # - try to flip face-down cards 168 # - call computeHints() to do something useful 169 # - try to deal cards 170 # - clean up and return hints sorted by score 171 # 172 173 # Default scores for flip and deal moves. 174 SCORE_FLIP = 100000 # 0..100000 175 SCORE_DEAL = 0 # 0..100000 176 177 def getHints(self, taken_hint=None): 178 # 0) setup 179 self.reset() 180 game = self.game 181 # 1) forced moves of the prev. taken hint have absolute priority 182 if taken_hint and taken_hint[6]: 183 return [taken_hint[6]] 184 # 2) try if we can flip a card 185 if self.level >= 2: 186 for r in game.allstacks: 187 if r.canFlipCard(): 188 self.addHint(self.SCORE_FLIP, 1, r, r) 189 if self.SCORE_FLIP >= 90000: 190 return self._returnHints() 191 # 3) ask subclass to do something useful 192 self.computeHints() 193 # 4) try if we can deal cards 194 if self.level >= 2: 195 if game.canDealCards(): 196 self.addHint(self.SCORE_DEAL, 0, game.s.talon, None) 197 return self._returnHints() 198 199 # subclass 200 def computeHints(self): 201 pass 202 203 # 204 # utility shallMovePile() 205 # 206 207 # we move the pile if it is accepted by the target stack 208 def _defaultShallMovePile(self, from_stack, to_stack, pile, rpile): 209 if from_stack is to_stack or not \ 210 to_stack.acceptsCards(from_stack, pile): 211 return 0 212 return 1 213 214 # same, but check for loops 215 def _cautiousShallMovePile(self, from_stack, to_stack, pile, rpile): 216 if from_stack is to_stack or not \ 217 to_stack.acceptsCards(from_stack, pile): 218 return 0 219 # 220 if len(rpile) == 0: 221 return 1 222 # now check for loops 223 rr = self.ClonedStack(from_stack, stackcards=rpile) 224 if rr.acceptsCards(to_stack, pile): 225 # the pile we are going to move could be moved back - 226 # this is dangerous as we can create endless loops... 227 return 0 228 return 1 229 230 # same, but only check for loops only when in demo mode 231 def _cautiousDemoShallMovePile(self, from_stack, to_stack, pile, rpile): 232 if from_stack is to_stack or not \ 233 to_stack.acceptsCards(from_stack, pile): 234 return 0 235 if self.level >= 2: 236 # 237 if len(rpile) == 0: 238 return 1 239 # now check for loops 240 rr = self.ClonedStack(from_stack, stackcards=rpile) 241 if rr.acceptsCards(to_stack, pile): 242 # the pile we are going to move could be moved back - 243 # this is dangerous as we can create endless loops... 244 return 0 245 return 1 246 247 shallMovePile = _defaultShallMovePile 248 249 # 250 # other utility methods 251 # 252 253 def _canDropAllCards(self, from_stack, stacks, stackcards): 254 assert from_stack not in stacks 255 return 0 256 # FIXME: this does not account for cards which are dropped herein 257 # cards = pile[:] 258 # cards.reverse() 259 # for card in cards: 260 # for s in stacks: 261 # if s is not from_stack: 262 # if s.acceptsCards(from_stack, [card]): 263 # break 264 # else: 265 # return 0 266 # return 1 267 268 # 269 # misc. constants 270 # 271 272 # score value so that the scores look nicer 273 K = KING + 1 274 # text_color that will display the score (for debug with level 1) 275 BLACK = "black" 276 RED = "red" 277 BLUE = "blue" 278 279 280# ************************************************************************ 281# * 282# ************************************************************************ 283 284class DefaultHint(AbstractHint): 285 286 # The DefaultHint is optimized for Klondike type games 287 # and also deals quite ok with other simple variants. 288 # 289 # But it completely lacks any specific strategy about game 290 # types like Forty Thieves, FreeCell, Golf, Spider, ... 291 # 292 # BTW, we do not cheat ! 293 294 # 295 # bonus scoring used in _getXxxScore() below - subclass overrideable 296 # 297 298 def _preferHighRankMoves(self): 299 return 0 300 301 # Basic bonus for moving a card. 302 # Bonus must be in range 0..999 303 304 BONUS_DROP_CARD = 300 # 0..400 305 BONUS_SAME_SUIT_MOVE = 200 # 0..400 306 BONUS_NORMAL_MOVE = 100 # 0..400 307 308 def _getMoveCardBonus(self, r, t, pile, rpile): 309 assert pile 310 bonus = 0 311 if rpile: 312 rr = self.ClonedStack(r, stackcards=rpile) 313 if (rr.canDropCards(self.game.s.foundations))[0]: 314 # the card below the pile can be dropped 315 bonus = self.BONUS_DROP_CARD 316 if t.cards and t.cards[-1].suit == pile[0].suit: 317 # simple heuristics - prefer moving high-rank cards 318 bonus += self.BONUS_SAME_SUIT_MOVE + (1 + pile[0].rank) 319 elif self._preferHighRankMoves(): 320 # simple heuristics - prefer moving high-rank cards 321 bonus += self.BONUS_NORMAL_MOVE + (1 + pile[0].rank) 322 elif rpile: 323 # simple heuristics - prefer low-rank cards in rpile 324 bonus += self.BONUS_NORMAL_MOVE + (self.K - rpile[-1].rank) 325 else: 326 # simple heuristics - prefer moving high-rank cards 327 bonus += self.BONUS_NORMAL_MOVE + (1 + pile[0].rank) 328 return bonus 329 330 # Special bonus for facing up a card after the current move. 331 # Bonus must be in range 0..9000 332 333 BONUS_FLIP_CARD = 1500 # 0..9000 334 335 def _getFlipSpecialBonus(self, r, t, pile, rpile): 336 assert pile and rpile 337 # The card below the pile can be flipped 338 # (do not cheat and look at it !) 339 # default: prefer a short rpile 340 bonus = max(self.BONUS_FLIP_CARD - len(rpile), 0) 341 return bonus 342 343 # Special bonus for moving a pile from stack r to stack t. 344 # Bonus must be in range 0..9000 345 346 BONUS_CREATE_EMPTY_ROW = 9000 # 0..9000 347 BONUS_CAN_DROP_ALL_CARDS = 4000 # 0..4000 348 BONUS_CAN_CREATE_EMPTY_ROW = 2000 # 0..4000 349 350 def _getMoveSpecialBonus(self, r, t, pile, rpile): 351 # check if we will create an empty row 352 if not rpile: 353 return self.BONUS_CREATE_EMPTY_ROW 354 # check if the card below the pile can be flipped 355 if not rpile[-1].face_up: 356 return self._getFlipSpecialBonus(r, t, pile, rpile) 357 # check if all the cards below our pile could be dropped 358 if self._canDropAllCards(r, self.game.s.foundations, stackcards=rpile): 359 # we can drop the whole remaining pile 360 # (and will create an empty row in the next move) 361 # print "BONUS_CAN_DROP_ALL_CARDS", r, pile, rpile 362 self.bonus_color = self.RED 363 return self.BONUS_CAN_DROP_ALL_CARDS + \ 364 self.BONUS_CAN_CREATE_EMPTY_ROW 365 # check if the cards below our pile are a whole row 366 if r.canMoveCards(rpile): 367 # could we move the remaining pile ? 368 for x in self.game.s.rows: 369 # note: we allow x == r here, because the pile 370 # (currently at the top of r) will be 371 # available in the next move 372 if x is t or not x.cards: 373 continue 374 if x.acceptsCards(r, rpile): 375 # we can create an empty row in the next move 376 # print "BONUS_CAN_CREATE_EMPTY_ROW", r, x, pile, rpile 377 self.bonus_color = self.BLUE 378 return self.BONUS_CAN_CREATE_EMPTY_ROW 379 return 0 380 381 # 382 # scoring used in getHints() - subclass overrideable 383 # 384 385 # Score for moving a pile from stack r to stack t. 386 # Increased score should be in range 0..9999 387 def _getMovePileScore(self, score, color, r, t, pile, rpile): 388 assert pile 389 self.bonus_color = color 390 b1 = self._getMoveSpecialBonus(r, t, pile, rpile) 391 assert 0 <= b1 <= 9000 392 b2 = self._getMoveCardBonus(r, t, pile, rpile) 393 assert 0 <= b2 <= 999 394 return score + b1 + b2, self.bonus_color 395 396 # Score for moving a pile (usually a single card) from the WasteStack. 397 def _getMoveWasteScore(self, score, color, r, t, pile, rpile): 398 assert pile 399 self.bonus_color = color 400 score = 30000 401 if t.cards: 402 score = 31000 403 b2 = self._getMoveCardBonus(r, t, pile, rpile) 404 assert 0 <= b2 <= 999 405 return score + b2, self.bonus_color 406 407 # Score for dropping ncards from stack r to stack t. 408 def _getDropCardScore(self, score, color, r, t, ncards): 409 assert t is not r 410 if ncards > 1: 411 # drop immediately (Spider) 412 return 93000, color 413 pile = r.cards 414 c = pile[-1] 415 # compute distance to t.cap.base_rank - compare Stack.getRankDir() 416 if t.cap.base_rank < 0: 417 d = len(t.cards) 418 else: 419 d = (c.rank - t.cap.base_rank) % t.cap.mod 420 if d > t.cap.mod // 2: 421 d -= t.cap.mod 422 if abs(d) <= 1: 423 # drop Ace and 2 immediately 424 score = 92000 425 elif r in self.game.sg.talonstacks: 426 score = 25000 # less than _getMoveWasteScore() 427 elif len(pile) == 1: 428 # score = 50000 429 score = 91000 430 elif self._canDropAllCards( 431 r, self.game.s.foundations, stackcards=pile[:-1]): 432 score = 90000 433 color = self.RED 434 else: 435 # don't drop this card too eagerly - we may need it 436 # for pile moving 437 score = 50000 438 score += (self.K - c.rank) 439 return score, color 440 441 # 442 # compute hints - main hint intelligence 443 # 444 445 def computeHints(self): 446 game = self.game 447 448 # 1) check Tableau piles 449 self.step010(game.sg.dropstacks, game.s.rows) 450 451 # 2) try if we can move part of a pile within the RowStacks 452 # so that we can drop a card afterwards 453 if not self.hints and self.level >= 1: 454 self.step020(game.s.rows, game.s.foundations) 455 456 # 3) try if we should move a card from a Foundation to a RowStack 457 if not self.hints and self.level >= 1: 458 self.step030(game.s.foundations, game.s.rows, game.sg.dropstacks) 459 460 # 4) try if we can move a card from a RowStack to a ReserveStack 461 if not self.hints or self.level == 0: 462 self.step040(game.s.rows, game.sg.reservestacks) 463 464 # 5) try if we should move a card from a ReserveStack to a RowStack 465 if not self.hints or self.level == 0: 466 self.step050(game.sg.reservestacks, game.s.rows) 467 468 # Don't be too clever and give up ;-) 469 470 # 471 # implementation of the hint steps 472 # 473 474 # 1) check Tableau piles 475 476 def step010(self, dropstacks, rows): 477 # for each stack 478 for r in dropstacks: 479 # 1a) try if we can drop cards 480 t, ncards = r.canDropCards(self.game.s.foundations) 481 if t: 482 score, color = 0, None 483 score, color = self._getDropCardScore( 484 score, color, r, t, ncards) 485 self.addHint(score, ncards, r, t, color) 486 if score >= 90000 and self.level >= 1: 487 break 488 # 1b) try if we can move cards to one of the RowStacks 489 for pile in self.step010b_getPiles(r): 490 if pile: 491 self.step010_movePile(r, pile, rows) 492 493 def step010b_getPiles(self, stack): 494 # return all moveable piles for this stack, longest one first 495 return (stack.getPile(), ) 496 497 def step010_movePile(self, r, pile, rows): 498 lp = len(pile) 499 lr = len(r.cards) 500 assert 1 <= lp <= lr 501 rpile = r.cards[: (lr-lp)] # remaining pile 502 503 empty_row_seen = 0 504 r_is_waste = r in self.game.sg.talonstacks 505 506 for t in rows: 507 score, color = 0, None 508 if not self.shallMovePile(r, t, pile, rpile): 509 continue 510 if r_is_waste: 511 # moving a card from the WasteStack 512 score, color = self._getMoveWasteScore( 513 score, color, r, t, pile, rpile) 514 else: 515 if not t.cards: 516 # the target stack is empty 517 if lp == lr: 518 # do not move a whole stack from row to row 519 continue 520 if empty_row_seen: 521 # only make one hint for moving to an empty stack 522 # (in case we have multiple empty stacks) 523 continue 524 score = 60000 525 empty_row_seen = 1 526 else: 527 # the target stack is not empty 528 score = 80000 529 score, color = self._getMovePileScore( 530 score, color, r, t, pile, rpile) 531 self.addHint(score, lp, r, t, color) 532 533 # 2) try if we can move part of a pile within the RowStacks 534 # so that we can drop a card afterwards 535 # score: 40000 .. 59999 536 537 step020_getPiles = step010b_getPiles 538 539 def step020(self, rows, foundations): 540 for r in rows: 541 for pile in self.step020_getPiles(r): 542 if not pile or len(pile) < 2: 543 continue 544 # is there a card in our pile that could be dropped ? 545 drop_info = [] 546 i = 0 547 for c in pile: 548 rr = self.ClonedStack(r, stackcards=[c]) 549 stack, ncards = rr.canDropCards(foundations) 550 if stack and stack is not r: 551 assert ncards == 1 552 drop_info.append((c, stack, ncards, i)) 553 i += 1 554 # now try to make a move so that the drop-card will get free 555 for di in drop_info: 556 c = di[0] 557 sub_pile = pile[di[3]+1:] 558 # print "trying drop move", c, pile, sub_pile 559 # assert r.canMoveCards(sub_pile) 560 if not r.canMoveCards(sub_pile): 561 continue 562 for t in rows: 563 if t is r or not t.acceptsCards(r, sub_pile): 564 continue 565 # print "drop move", r, t, sub_pile 566 score = 40000 567 score += 1000 + (self.K - r.getCard().rank) 568 # force the drop (to avoid loops) 569 force = (999999, 0, di[2], r, di[1], self.BLUE, None) 570 self.addHint( 571 score, len(sub_pile), r, t, 572 self.RED, forced_move=force) 573 574 # 3) try if we should move a card from a Foundation to a RowStack 575 # score: 20000 .. 29999 576 577 def step030(self, foundations, rows, dropstacks): 578 for s in foundations: 579 card = s.getCard() 580 if not card or not s.canMoveCards([card]): 581 continue 582 # search a RowStack that would accept the card 583 for t in rows: 584 if t is s or not t.acceptsCards(s, [card]): 585 continue 586 tt = self.ClonedStack(t, stackcards=t.cards+[card]) 587 # search a Stack that would benefit from this card 588 for r in dropstacks: 589 if r is t: 590 continue 591 pile = r.getPile() 592 if not pile: 593 continue 594 if not tt.acceptsCards(r, pile): 595 continue 596 # compute remaining pile in r 597 rpile = r.cards[:(len(r.cards)-len(pile))] 598 rr = self.ClonedStack(r, stackcards=rpile) 599 if rr.acceptsCards(t, pile): 600 # the pile we are going to move from r to t 601 # could be moved back from t ro r - this is 602 # dangerous as we can create loops... 603 continue 604 score = 20000 + card.rank 605 # print score, s, t, r, pile, rpile 606 # force the move from r to t (to avoid loops) 607 force = (999999, 0, len(pile), r, t, self.BLUE, None) 608 self.addHint(score, 1, s, t, self.BLUE, forced_move=force) 609 610 # 4) try if we can move a card from a RowStack to a ReserveStack 611 # score: 10000 .. 19999 612 613 def step040(self, rows, reservestacks): 614 if not reservestacks: 615 return 616 for r in rows: 617 card = r.getCard() 618 if not card or not r.canMoveCards([card]): 619 continue 620 pile = [card] 621 # compute remaining pile in r 622 rpile = r.cards[:(len(r.cards)-len(pile))] 623 rr = self.ClonedStack(r, stackcards=rpile) 624 for t in reservestacks: 625 if t is r or not t.acceptsCards(r, pile): 626 continue 627 if rr.acceptsCards(t, pile): 628 # the pile we are going to move from r to t 629 # could be moved back from t ro r - this is 630 # dangerous as we can create loops... 631 continue 632 score = 10000 633 score, color = self._getMovePileScore( 634 score, None, r, t, pile, rpile) 635 self.addHint(score, len(pile), r, t, color) 636 break 637 638 # 5) try if we should move a card from a ReserveStack to a RowStack 639 640 def step050(self, reservestacks, rows): 641 if not reservestacks: 642 return 643 # FIXME 644 645 646# ************************************************************************ 647# * 648# ************************************************************************ 649 650class CautiousDefaultHint(DefaultHint): 651 shallMovePile = DefaultHint._cautiousShallMovePile 652 # shallMovePile = DefaultHint._cautiousDemoShallMovePile 653 654 def _preferHighRankMoves(self): 655 return 1 656 657 658# ************************************************************************ 659# * now some default hints for the various game types 660# ************************************************************************ 661 662# DefaultHint is optimized for Klondike type games anyway 663class KlondikeType_Hint(DefaultHint): 664 pass 665 666 667# this works for Yukon, but not too well for Russian Solitaire 668class YukonType_Hint(CautiousDefaultHint): 669 def step010b_getPiles(self, stack): 670 # return all moveable piles for this stack, longest one first 671 p = stack.getPile() 672 piles = [] 673 while p: 674 piles.append(p) 675 p = p[1:] # note: we need a fresh shallow copy 676 return piles 677 678 679class Yukon_Hint(YukonType_Hint): 680 BONUS_FLIP_CARD = 9000 681 BONUS_CREATE_EMPTY_ROW = 100 682 683 # FIXME: this is only a rough approximation and doesn't seem to help 684 # for Russian Solitaire 685 def _getMovePileScore(self, score, color, r, t, pile, rpile): 686 s, color = YukonType_Hint._getMovePileScore( 687 self, score, color, r, t, pile, rpile) 688 bonus = s - score 689 assert 0 <= bonus <= 9999 690 # We must take care when moving piles that we won't block cards, 691 # i.e. if there is a card in pile which would be needed 692 # for a card in stack t. 693 tpile = t.getPile() 694 if tpile: 695 for cr in pile: 696 rr = self.ClonedStack(r, stackcards=[cr]) 697 for ct in tpile: 698 if rr.acceptsCards(t, [ct]): 699 d = bonus // 1000 700 bonus = (d * 1000) + bonus % 100 701 break 702 return score + bonus, color 703 704 705class FreeCellType_Hint(CautiousDefaultHint): 706 pass 707 708 709class GolfType_Hint(DefaultHint): 710 pass 711 712 713class SpiderType_Hint(DefaultHint): 714 pass 715 716 717class PySolHintLayoutImportError(Exception): 718 719 def __init__(self, msg, cards, line_num): 720 """docstring for __init__""" 721 self.msg = msg 722 self.cards = cards 723 self.line_num = line_num 724 725 def format(self): 726 return self.msg + ":\n\n" + ', '.join(self.cards) 727 728 729class Base_Solver_Hint: 730 def __init__(self, game, dialog, **game_type): 731 self.game = game 732 self.dialog = dialog 733 self.game_type = game_type 734 self.options = { 735 'iters_step': 100, 736 'max_iters': 10000, 737 'progress': False, 738 'preset': None, 739 } 740 self.hints = [] 741 self.hints_index = 0 742 743 # correct cards rank if foundations.base_rank != 0 (Penguin, Opus) 744 if 'base_rank' in game_type: # (Simple Simon) 745 self.base_rank = game_type['base_rank'] 746 else: 747 self.base_rank = game.s.foundations[0].cap.base_rank 748 749 def _setText(self, **kw): 750 return self.dialog.setText(**kw) 751 752 def config(self, **kw): 753 self.options.update(kw) 754 755 def _card2str_format(self, fmt, rank, suit): 756 # row and reserves 757 rank = (rank-self.base_rank) % 13 758 return fmt.format(R="A23456789TJQK"[rank], S="CSHD"[suit]) 759 760 def card2str1_(self, rank, suit): 761 # row and reserves 762 return self._card2str_format('{R}{S}', rank, suit) 763 764 def card2str1(self, card): 765 return self.card2str1_(card.rank, card.suit) 766 767 def card2str2(self, card): 768 # foundations 769 return self._card2str_format('{S}-{R}', card.rank, card.suit) 770 771# hard solvable: Freecell #47038300998351211829 (65539 iters) 772 773 def getHints(self, taken_hint=None): 774 if taken_hint and taken_hint[6]: 775 return [taken_hint[6]] 776 h = self.hints[self.hints_index] 777 if h is None: 778 return None 779 ncards, src, dest = h 780 thint = None 781 if len(src.cards) > ncards and not src.cards[-ncards-1].face_up: 782 # flip card 783 thint = (999999, 0, 1, src, src, None, None) 784 skip = False 785 if dest is None: # foundation 786 if src is self.game.s.talon: 787 if not src.cards[-1].face_up: 788 self.game.flipMove(src) 789 dest = self.game.s.foundations[0] 790 else: 791 cards = src.cards[-ncards:] 792 for f in self.game.s.foundations: 793 if f.acceptsCards(src, cards): 794 dest = f 795 break 796 assert dest 797 self.hints_index += 1 798 if skip: 799 return [] 800 hint = (999999, 0, ncards, src, dest, None, thint) 801 return [hint] 802 803 def colonPrefixMatch(self, prefix, s): 804 m = re.match(prefix + ': ([0-9]+)', s) 805 if m: 806 self._v = int(m.group(1)) 807 return True 808 else: 809 self._v = None 810 return False 811 812 def run_solver(self, command, board): 813 if DEBUG: 814 print(command) 815 kw = {'shell': True, 816 'stdin': subprocess.PIPE, 817 'stdout': subprocess.PIPE, 818 'stderr': subprocess.PIPE} 819 if os.name != 'nt': 820 kw['close_fds'] = True 821 p = subprocess.Popen(command, **kw) 822 bytes_board = six.binary_type(board, 'utf-8') 823 pout, perr = p.communicate(bytes_board) 824 if p.returncode in (127, 1): 825 # Linux and Windows return codes for "command not found" error 826 raise RuntimeError('Solver exited with {}'.format(p.returncode)) 827 return BytesIO(pout), BytesIO(perr) 828 829 830use_fc_solve_lib = False 831 832try: 833 import freecell_solver 834 fc_solve_lib_obj = freecell_solver.FreecellSolver() 835 use_fc_solve_lib = True 836except BaseException: 837 pass 838 839use_bh_solve_lib = False 840 841try: 842 import black_hole_solver 843 bh_solve_lib_obj = black_hole_solver.BlackHoleSolver() 844 use_bh_solve_lib = True 845except BaseException: 846 pass 847 848 849class FreeCellSolver_Hint(Base_Solver_Hint): 850 def _determineIfSolverState(self, line): 851 if re.search('^(?:Iterations count exceeded)', line): 852 self.solver_state = 'intractable' 853 return True 854 elif re.search('^(?:I could not solve this game)', line): 855 self.solver_state = 'unsolved' 856 return True 857 else: 858 return False 859 860 def _isSimpleSimon(self): 861 game_type = self.game_type 862 return ('preset' in game_type and 863 game_type['preset'] == 'simple_simon') 864 865 def _addBoardLine(self, line): 866 self.board += line + '\n' 867 return 868 869 def _addPrefixLine(self, prefix, b): 870 if b: 871 self._addBoardLine(prefix + b) 872 return 873 874 def importFile(solver, fh, s_game, self): 875 s_game.endGame() 876 s_game.random = construct_random('Custom') 877 s_game.newGame( 878 shuffle=True, 879 random=construct_random('Custom'), 880 dealer=lambda: solver.importFileHelper(fh, s_game)) 881 s_game.random = construct_random('Custom') 882 883 def importFileHelper(solver, fh, s_game): 884 game = s_game.s 885 stack_idx = 0 886 887 RANKS_S = "A23456789TJQK" 888 RANKS0_S = '0' + RANKS_S 889 RANKS_RE = '(?:' + '[' + RANKS_S + ']' + '|10)' 890 SUITS_S = "CSHD" 891 SUITS_RE = '[' + SUITS_S + ']' 892 CARD_RE = r'(?:' + RANKS_RE + SUITS_RE + ')' 893 line_num = 0 894 895 def cards(): 896 return game.talon.cards 897 898 def put(target, suit, rank): 899 ret = [i for i, c in enumerate(cards()) 900 if c.suit == suit and c.rank == rank] 901 if len(ret) < 1: 902 raise PySolHintLayoutImportError( 903 "Duplicate cards in input", 904 [solver.card2str1_(rank, suit)], 905 line_num 906 ) 907 908 ret = ret[0] 909 game.talon.cards = \ 910 cards()[0:ret] + cards()[(ret+1):] + [cards()[ret]] 911 s_game.flipMove(game.talon) 912 s_game.moveMove(1, game.talon, target, frames=0) 913 914 def put_str(target, str_): 915 put(target, SUITS_S.index(str_[-1]), 916 (RANKS_S.index(str_[0]) if len(str_) == 2 else 9)) 917 918 def my_find_re(RE, m, msg): 919 s = m.group(1) 920 if not re.match(r'^\s*(?:' + RE + r')?(?:\s+' + RE + r')*\s*$', s): 921 raise PySolHintLayoutImportError( 922 msg, 923 [], 924 line_num 925 ) 926 return re.findall(r'\b' + RE + r'\b', s) 927 928 # Based on https://stackoverflow.com/questions/8898294 - thanks! 929 def mydecode(s): 930 for encoding in "utf-8-sig", "utf-8": 931 try: 932 return s.decode(encoding) 933 except UnicodeDecodeError: 934 continue 935 return s.decode("latin-1") # will always work 936 937 mytext = mydecode(fh.read()) 938 for line_p in mytext.splitlines(): 939 line_num += 1 940 line = line_p.rstrip('\r\n') 941 m = re.match(r'^(?:Foundations:|Founds?:)\s*(.*)', line) 942 if m: 943 for gm in my_find_re( 944 r'(' + SUITS_RE + r')-([' + RANKS0_S + r'])', m, 945 "Invalid Foundations line"): 946 for foundat in game.foundations: 947 suit = foundat.cap.suit 948 if SUITS_S[suit] == gm[0]: 949 rank = gm[1] 950 if len(rank) == 1: 951 lim = RANKS0_S.index(rank) 952 else: 953 lim = 10 954 for r in range(lim): 955 put(foundat, suit, r) 956 break 957 continue 958 m = re.match(r'^(?:FC:|Freecells:)\s*(.*)', line) 959 if m: 960 g = my_find_re(r'(' + CARD_RE + r'|\-)', m, 961 "Invalid Freecells line") 962 while len(g) < len(game.reserves): 963 g.append('-') 964 for i, gm in enumerate(g): 965 str_ = gm 966 if str_ != '-': 967 put_str(game.reserves[i], str_) 968 continue 969 m = re.match(r'^:?\s*(.*)', line) 970 for str_ in my_find_re(r'(' + CARD_RE + r')', m, 971 "Invalid column text"): 972 put_str(game.rows[stack_idx], str_) 973 974 stack_idx += 1 975 if len(cards()) > 0: 976 raise PySolHintLayoutImportError( 977 "Missing cards in input", 978 [solver.card2str1(c) for c in cards()], 979 -1 980 ) 981 982 def calcBoardString(self): 983 game = self.game 984 self.board = '' 985 is_simple_simon = self._isSimpleSimon() 986 b = '' 987 for s in game.s.foundations: 988 if s.cards: 989 b += ' ' + self.card2str2( 990 s.cards[0 if is_simple_simon else -1]) 991 self._addPrefixLine('Founds:', b) 992 993 b = '' 994 for s in game.s.reserves: 995 b += ' ' + (self.card2str1(s.cards[-1]) if s.cards else '-') 996 self._addPrefixLine('FC:', b) 997 998 for s in game.s.rows: 999 b = '' 1000 for c in s.cards: 1001 cs = self.card2str1(c) 1002 if not c.face_up: 1003 cs = '<%s>' % cs 1004 b += cs + ' ' 1005 self._addBoardLine(b.strip()) 1006 1007 return self.board 1008 1009 def computeHints(self): 1010 game = self.game 1011 game_type = self.game_type 1012 global FCS_VERSION 1013 if FCS_VERSION is None: 1014 if use_fc_solve_lib: 1015 FCS_VERSION = (5, 0, 0) 1016 else: 1017 pout, _ = self.run_solver(FCS_COMMAND + ' --version', '') 1018 s = six.text_type(pout.read(), encoding='utf-8') 1019 m = re.search(r'version ([0-9]+)\.([0-9]+)\.([0-9]+)', s) 1020 if m: 1021 FCS_VERSION = (int(m.group(1)), int(m.group(2)), 1022 int(m.group(3))) 1023 else: 1024 FCS_VERSION = (0, 0, 0) 1025 1026 progress = self.options['progress'] 1027 1028 board = self.calcBoardString() 1029 if DEBUG: 1030 print('--------------------\n', board, '--------------------') 1031 args = [] 1032 if use_fc_solve_lib: 1033 args += ['--reset', '-opt', ] 1034 else: 1035 args += ['-m', '-p', '-opt', '-sel'] 1036 if FCS_VERSION >= (4, 20, 0): 1037 args += ['-hoi'] 1038 if (not use_fc_solve_lib) and progress: 1039 args += ['--iter-output'] 1040 fcs_iter_output_step = None 1041 if FCS_VERSION >= (4, 20, 0): 1042 fcs_iter_output_step = self.options['iters_step'] 1043 args += ['--iter-output-step', str(fcs_iter_output_step)] 1044 if DEBUG: 1045 args += ['-s'] 1046 if self.options['preset'] and self.options['preset'] != 'none': 1047 args += ['--load-config', self.options['preset']] 1048 args += ['--max-iters', str(self.options['max_iters']), 1049 '--decks-num', str(game.gameinfo.decks), 1050 '--stacks-num', str(len(game.s.rows)), 1051 '--freecells-num', str(len(game.s.reserves)), 1052 ] 1053 if 'preset' in game_type: 1054 args += ['--preset', game_type['preset']] 1055 if 'sbb' in game_type: 1056 args += ['--sequences-are-built-by', game_type['sbb']] 1057 if 'sm' in game_type: 1058 args += ['--sequence-move', game_type['sm']] 1059 if 'esf' in game_type: 1060 args += ['--empty-stacks-filled-by', game_type['esf']] 1061 1062 if use_fc_solve_lib: 1063 fc_solve_lib_obj.input_cmd_line(args) 1064 status = fc_solve_lib_obj.solve_board(board) 1065 else: 1066 command = FCS_COMMAND+' '+' '.join(args) 1067 pout, perr = self.run_solver(command, board) 1068 self.solver_state = 'unknown' 1069 stack_types = { 1070 'the': game.s.foundations, 1071 'stack': game.s.rows, 1072 'freecell': game.s.reserves, 1073 } 1074 if DEBUG: 1075 start_time = time.time() 1076 if not(use_fc_solve_lib) and progress: 1077 iter_ = 0 1078 depth = 0 1079 states = 0 1080 1081 for sbytes in pout: 1082 s = six.text_type(sbytes, encoding='utf-8') 1083 if DEBUG >= 5: 1084 print(s) 1085 1086 if self.colonPrefixMatch('Iteration', s): 1087 iter_ = self._v 1088 elif self.colonPrefixMatch('Depth', s): 1089 depth = self._v 1090 elif self.colonPrefixMatch('Stored-States', s): 1091 states = self._v 1092 if iter_ % 100 == 0 or fcs_iter_output_step: 1093 self._setText(iter=iter_, depth=depth, states=states) 1094 elif re.search('^(?:-=-=)', s): 1095 break 1096 elif self._determineIfSolverState(s): 1097 break 1098 self._setText(iter=iter_, depth=depth, states=states) 1099 1100 hints = [] 1101 if use_fc_solve_lib: 1102 self._setText( 1103 iter=fc_solve_lib_obj.get_num_times(), 1104 depth=0, 1105 states=fc_solve_lib_obj.get_num_states_in_collection(), 1106 ) 1107 if status == 0: 1108 m = fc_solve_lib_obj.get_next_move() 1109 while m: 1110 type_ = ord(m.s[0]) 1111 src = ord(m.s[1]) 1112 dest = ord(m.s[2]) 1113 hints.append([ 1114 (ord(m.s[3]) if type_ == 0 1115 else (13 if type_ == 11 else 1)), 1116 (game.s.rows if (type_ in [0, 1, 4, 11, ]) 1117 else game.s.reserves)[src], 1118 (game.s.rows[dest] if (type_ in [0, 2]) 1119 else (game.s.reserves[dest] 1120 if (type_ in [1, 3]) else None))]) 1121 1122 m = fc_solve_lib_obj.get_next_move() 1123 else: 1124 self.solver_state = 'unsolved' 1125 else: 1126 for sbytes in pout: 1127 s = six.text_type(sbytes, encoding='utf-8') 1128 if DEBUG: 1129 print(s) 1130 if self._determineIfSolverState(s): 1131 break 1132 m = re.match( 1133 'Total number of states checked is ([0-9]+)\\.', s) 1134 if m: 1135 self._setText(iter=int(m.group(1))) 1136 1137 m = re.match('This scan generated ([0-9]+) states\\.', s) 1138 1139 if m: 1140 self._setText(states=int(m.group(1))) 1141 1142 m = re.match('Move (.*)', s) 1143 if not m: 1144 continue 1145 1146 move_s = m.group(1) 1147 1148 m = re.match( 1149 'the sequence on top of Stack ([0-9]+) to the foundations', 1150 move_s) 1151 1152 if m: 1153 ncards = 13 1154 st = stack_types['stack'] 1155 sn = int(m.group(1)) 1156 src = st[sn] 1157 dest = None 1158 else: 1159 m = re.match( 1160 '(?P<ncards>a card|(?P<count>[0-9]+) cards) ' 1161 'from (?P<source_type>stack|freecell) ' 1162 '(?P<source_idx>[0-9]+) to ' 1163 '(?P<dest>the foundations|' 1164 '(?P<dest_type>freecell|stack) ' 1165 '(?P<dest_idx>[0-9]+))\\s*', move_s) 1166 1167 if not m: 1168 continue 1169 1170 if m.group('ncards') == 'a card': 1171 ncards = 1 1172 else: 1173 ncards = int(m.group('count')) 1174 1175 st = stack_types[m.group('source_type')] 1176 sn = int(m.group('source_idx')) 1177 src = st[sn] 1178 1179 dest_s = m.group('dest') 1180 if dest_s == 'the foundations': 1181 dest = None 1182 else: 1183 dt = stack_types[m.group('dest_type')] 1184 dest = dt[int(m.group('dest_idx'))] 1185 1186 hints.append([ncards, src, dest]) 1187 1188 if DEBUG: 1189 print('time:', time.time()-start_time) 1190 1191 self.hints = hints 1192 if len(hints) > 0: 1193 if self.solver_state != 'intractable': 1194 self.solver_state = 'solved' 1195 self.hints.append(None) 1196 1197 if not use_fc_solve_lib: 1198 pout.close() 1199 perr.close() 1200 1201 1202class BlackHoleSolver_Hint(Base_Solver_Hint): 1203 BLACK_HOLE_SOLVER_COMMAND = 'black-hole-solve' 1204 1205 def calcBoardString(self): 1206 board = '' 1207 cards = self.game.s.talon.cards 1208 if (len(cards) > 0): 1209 board += ' '.join(['Talon:'] + 1210 [self.card2str1(x) for x in reversed(cards)]) 1211 board += '\n' 1212 cards = self.game.s.foundations[0].cards 1213 s = '-' 1214 if (len(cards) > 0): 1215 s = self.card2str1(cards[-1]) 1216 board += 'Foundations: ' + s + '\n' 1217 1218 for s in self.game.s.rows: 1219 b = '' 1220 for c in s.cards: 1221 cs = self.card2str1(c) 1222 if not c.face_up: 1223 cs = '<%s>' % cs 1224 b += cs + ' ' 1225 board += b.strip() + '\n' 1226 1227 return board 1228 1229 def computeHints(self): 1230 game = self.game 1231 game_type = self.game_type 1232 1233 board = self.calcBoardString() 1234 if DEBUG: 1235 print('--------------------\n', board, '--------------------') 1236 if use_bh_solve_lib: 1237 # global bh_solve_lib_obj 1238 # bh_solve_lib_obj = bh_solve_lib_obj.new_bhs_user_handle() 1239 bh_solve_lib_obj.recycle() 1240 bh_solve_lib_obj.read_board( 1241 board=board, 1242 game_type=game_type['preset'], 1243 place_queens_on_kings=( 1244 game_type['queens_on_kings'] 1245 if ('queens_on_kings' in game_type) else True), 1246 wrap_ranks=( 1247 game_type['wrap_ranks'] 1248 if ('wrap_ranks' in game_type) else True), 1249 ) 1250 bh_solve_lib_obj.limit_iterations(self.options['max_iters']) 1251 else: 1252 args = [] 1253 args += ['--game', game_type['preset'], '--rank-reach-prune'] 1254 args += ['--max-iters', str(self.options['max_iters'])] 1255 if 'queens_on_kings' in game_type: 1256 args += ['--queens-on-kings'] 1257 if 'wrap_ranks' in game_type: 1258 args += ['--wrap-ranks'] 1259 1260 command = self.BLACK_HOLE_SOLVER_COMMAND + ' ' + ' '.join(args) 1261 1262 if DEBUG: 1263 start_time = time.time() 1264 1265 result = '' 1266 1267 if use_bh_solve_lib: 1268 ret_code = bh_solve_lib_obj.resume_solution() 1269 else: 1270 pout, perr = self.run_solver(command, board) 1271 1272 for sbytes in pout: 1273 s = six.text_type(sbytes, encoding='utf-8') 1274 if DEBUG >= 5: 1275 print(s) 1276 1277 m = re.search('^(Intractable|Unsolved|Solved)!', s.rstrip()) 1278 if m: 1279 result = m.group(1) 1280 break 1281 1282 self._setText(iter=0, depth=0, states=0) 1283 hints = [] 1284 if use_bh_solve_lib: 1285 self.solver_state = ( 1286 'solved' if ret_code == 0 else 1287 ('intractable' 1288 if bh_solve_lib_obj.ret_code_is_suspend(ret_code) 1289 else 'unsolved')) 1290 self._setText(iter=bh_solve_lib_obj.get_num_times()) 1291 self._setText( 1292 states=bh_solve_lib_obj.get_num_states_in_collection()) 1293 if self.solver_state == 'solved': 1294 m = bh_solve_lib_obj.get_next_move() 1295 while m: 1296 found_stack_idx = m.get_column_idx() 1297 if len(game.s.rows) > found_stack_idx >= 0: 1298 src = game.s.rows[found_stack_idx] 1299 1300 hints.append([1, src, None]) 1301 else: 1302 hints.append([1, game.s.talon, None]) 1303 m = bh_solve_lib_obj.get_next_move() 1304 else: 1305 self.solver_state = result.lower() 1306 for sbytes in pout: 1307 s = six.text_type(sbytes, encoding='utf-8') 1308 if DEBUG: 1309 print(s) 1310 1311 if s.strip() == 'Deal talon': 1312 hints.append([1, game.s.talon, None]) 1313 continue 1314 1315 m = re.match( 1316 'Total number of states checked is ([0-9]+)\\.', s) 1317 if m: 1318 self._setText(iter=int(m.group(1))) 1319 continue 1320 1321 m = re.match('This scan generated ([0-9]+) states\\.', s) 1322 1323 if m: 1324 self._setText(states=int(m.group(1))) 1325 continue 1326 1327 m = re.match( 1328 'Move a card from stack ([0-9]+) to the foundations', s) 1329 if not m: 1330 continue 1331 1332 found_stack_idx = int(m.group(1)) 1333 src = game.s.rows[found_stack_idx] 1334 1335 hints.append([1, src, None]) 1336 pout.close() 1337 perr.close() 1338 1339 if DEBUG: 1340 print('time:', time.time()-start_time) 1341 1342 hints.append(None) 1343 self.hints = hints 1344 1345 1346class FreeCellSolverWrapper: 1347 1348 def __init__(self, **game_type): 1349 self.game_type = game_type 1350 1351 def __call__(self, game, dialog): 1352 hint = FreeCellSolver_Hint(game, dialog, **self.game_type) 1353 return hint 1354 1355 1356class BlackHoleSolverWrapper: 1357 1358 def __init__(self, **game_type): 1359 self.game_type = game_type 1360 1361 def __call__(self, game, dialog): 1362 hint = BlackHoleSolver_Hint(game, dialog, **self.game_type) 1363 return hint 1364