diff --git a/freecell.cpp b/freecell.cpp index d890a13..4c17864 100644 --- a/freecell.cpp +++ b/freecell.cpp @@ -1,304 +1,307 @@ /* * Copyright (C) 1997 Rodolfo Borges * Copyright (C) 1998-2009 Stephan Kulow * Copyright (C) 2010 Parker Coates * * License of original code: * ------------------------------------------------------------------------- * Permission to use, copy, modify, and distribute this software and its * documentation for any purpose and without fee is hereby granted, * provided that the above copyright notice appear in all copies and that * both that copyright notice and this permission notice appear in * supporting documentation. * * This file is provided AS IS with no warranties of any kind. The author * shall have no liability with respect to the infringement of copyrights, * trade secrets or any patents by this file or any part thereof. In no * event will the author be liable for any lost revenue or profits or * other special, indirect and consequential damages. * ------------------------------------------------------------------------- * * License of modifications/additions made after 2009-01-01: * ------------------------------------------------------------------------- * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License as * published by the Free Software Foundation; either version 2 of * the License, or (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program. If not, see . * ------------------------------------------------------------------------- */ #include "freecell.h" #include "dealerinfo.h" #include "kpat_debug.h" #include "pileutils.h" +#include "settings.h" #include "speeds.h" #include "patsolve/freecellsolver.h" #include Freecell::Freecell( const DealerInfo * di ) : DealerScene( di ) { } void Freecell::initialize() { setDeckContents(); const qreal topRowDist = 1.08; const qreal bottomRowDist = 1.13; const qreal targetOffsetDist = ( 7 * bottomRowDist + 1 ) - ( 3 * topRowDist + 1 ); for ( int i = 0; i < 4; ++i ) { freecell[i] = new PatPile ( this, 1 + 8 + i, QStringLiteral( "freecell%1" ).arg( i ) ); freecell[i]->setPileRole(PatPile::Cell); freecell[i]->setLayoutPos(topRowDist * i, 0); freecell[i]->setKeyboardSelectHint( KCardPile::AutoFocusTop ); freecell[i]->setKeyboardDropHint( KCardPile::AutoFocusTop ); } for ( int i = 0; i < 8; ++i ) { store[i] = new PatPile( this, 1 + i, QStringLiteral( "store%1" ).arg( i ) ); store[i]->setPileRole(PatPile::Tableau); store[i]->setLayoutPos( bottomRowDist * i, 1.3 ); store[i]->setBottomPadding( 2.5 ); store[i]->setHeightPolicy( KCardPile::GrowDown ); store[i]->setKeyboardSelectHint( KCardPile::AutoFocusDeepestRemovable ); store[i]->setKeyboardDropHint( KCardPile::AutoFocusTop ); } for ( int i = 0; i < 4; ++i ) { target[i] = new PatPile(this, 1 + 8 + 4 + i, QStringLiteral( "target%1" ).arg( i )); target[i]->setPileRole(PatPile::Foundation); target[i]->setLayoutPos(targetOffsetDist + topRowDist * i, 0); target[i]->setSpread(0, 0); target[i]->setKeyboardSelectHint( KCardPile::NeverFocus ); target[i]->setKeyboardDropHint( KCardPile::ForceFocusTop ); } setActions(DealerScene::Demo | DealerScene::Hint); - setSolver( new FreecellSolver( this ) ); + auto solver = new FreecellSolver( this ); + solver->default_max_positions = Settings::freecellSolverIterationsLimit(); + setSolver( solver ); setNeededFutureMoves( 4 ); // reserve some } void Freecell::restart( const QList & cards ) { QList cardList = cards; int column = 0; while ( !cardList.isEmpty() ) { addCardForDeal( store[column], cardList.takeLast(), true, store[0]->pos() ); column = (column + 1) % 8; } startDealAnimation(); } QString Freecell::solverFormat() const { QString output; QString tmp; for (int i = 0; i < 4 ; i++) { if (target[i]->isEmpty()) continue; tmp += suitToString(target[i]->topCard()->suit()) + '-' + rankToString(target[i]->topCard()->rank()) + ' '; } if (!tmp.isEmpty()) output += QStringLiteral("Foundations: %1\n").arg(tmp); tmp.truncate(0); for (int i = 0; i < 4 ; i++) { const auto fc = freecell[i]; tmp += (fc->isEmpty() ? QStringLiteral("-") : cardToRankSuitString(fc->topCard())) + ' '; } if (!tmp.isEmpty()) { QString a = QStringLiteral("Freecells: %1\n"); output += a.arg(tmp); } for (int i = 0; i < 8 ; i++) cardsListToLine(output, store[i]->cards()); return output; } void Freecell::cardsDroppedOnPile( const QList & cards, KCardPile * pile ) { if ( cards.size() <= 1 ) { DealerScene::moveCardsToPile( cards, pile, DURATION_MOVE ); return; } QList freeCells; for ( int i = 0; i < 4; ++i ) if ( freecell[i]->isEmpty() ) freeCells << freecell[i]; QList freeStores; for ( int i = 0; i < 8; ++i ) if ( store[i]->isEmpty() && store[i] != pile ) freeStores << store[i]; multiStepMove( cards, pile, freeStores, freeCells, DURATION_MOVE ); } bool Freecell::tryAutomaticMove(KCard *c) { // target move if (DealerScene::tryAutomaticMove(c)) return true; if (c->isAnimated()) return false; if (allowedToRemove(c->pile(), c) && c == c->pile()->topCard()) { for (int i = 0; i < 4; i++) { if (allowedToAdd( freecell[i], {c} )) { moveCardToPile( c, freecell[i], DURATION_MOVE ); return true; } } } return false; } bool Freecell::canPutStore( const KCardPile * pile, const QList & cards ) const { int freeCells = 0; for ( int i = 0; i < 4; ++i ) if ( freecell[i]->isEmpty() ) ++freeCells; int freeStores = 0; for ( int i = 0; i < 8; ++i ) if ( store[i]->isEmpty() && store[i] != pile ) ++freeStores; return cards.size() <= (freeCells + 1) << freeStores && ( pile->isEmpty() || ( pile->topCard()->rank() == cards.first()->rank() + 1 && pile->topCard()->color() != cards.first()->color() ) ); } bool Freecell::checkAdd(const PatPile * pile, const QList & oldCards, const QList & newCards) const { switch (pile->pileRole()) { case PatPile::Tableau: return canPutStore(pile, newCards); case PatPile::Cell: return oldCards.isEmpty() && newCards.size() == 1; case PatPile::Foundation: return checkAddSameSuitAscendingFromAce(oldCards, newCards); default: return false; } } bool Freecell::checkRemove(const PatPile * pile, const QList & cards) const { switch (pile->pileRole()) { case PatPile::Tableau: return isAlternateColorDescending(cards); case PatPile::Cell: return cards.first() == pile->topCard(); case PatPile::Foundation: default: return false; } } QList Freecell::getHints() { QList hintList = getSolverHints(); if ( isDemoActive() ) return hintList; foreach (PatPile * store, patPiles()) { if (store->isEmpty()) continue; QList cards = store->cards(); while (cards.count() && !cards.first()->isFaceUp()) cards.erase(cards.begin()); QList::Iterator iti = cards.begin(); while (iti != cards.end()) { if (allowedToRemove(store, (*iti))) { foreach (PatPile * dest, patPiles()) { int cardIndex = store->indexOf(*iti); if (cardIndex == 0 && dest->isEmpty() && !dest->isFoundation()) continue; if (!checkAdd(dest, dest->cards(), cards)) continue; if ( dest->isFoundation() ) // taken care by solver continue; QList cardsBelow = cards.mid(0, cardIndex); // if it could be here as well, then it's no use if ((cardsBelow.isEmpty() && !dest->isEmpty()) || !checkAdd(store, cardsBelow, cards)) { hintList << MoveHint( *iti, dest, 0 ); } else if (checkPrefering( dest, dest->cards(), cards ) && !checkPrefering( store, cardsBelow, cards )) { // if checkPrefers says so, we add it nonetheless hintList << MoveHint( *iti, dest, 0 ); } } } cards.erase(iti); iti = cards.begin(); } } return hintList; } static class FreecellDealerInfo : public DealerInfo { public: FreecellDealerInfo() : DealerInfo(I18N_NOOP("Freecell"), FreecellId) {} DealerScene *createGame() const Q_DECL_OVERRIDE { return new Freecell( this ); } } freecellDealerInfo; diff --git a/kpat.kcfg b/kpat.kcfg index 6f43b0a..8afb181 100644 --- a/kpat.kcfg +++ b/kpat.kcfg @@ -1,36 +1,39 @@ true true false false svg-oxygen-air true 2 0 1000000 + + 200000 + diff --git a/patsolve/abstract_fc_solve_solver.cpp b/patsolve/abstract_fc_solve_solver.cpp index d69a096..78a7e52 100644 --- a/patsolve/abstract_fc_solve_solver.cpp +++ b/patsolve/abstract_fc_solve_solver.cpp @@ -1,268 +1,269 @@ /* * Copyright (C) 2006-2009 Stephan Kulow * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License as * published by the Free Software Foundation; either version 2 of * the License, or (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program. If not, see . */ #include #include #include "freecell-solver/fcs_user.h" #include "freecell-solver/fcs_cl.h" #include "abstract_fc_solve_solver.h" const int CHUNKSIZE = 100; -const long int MAX_ITERS_LIMIT = 200000; +const long int INITIAL_MAX_ITERS_LIMIT = 200000; #define PRINT 0 /* These two routines make and unmake moves. */ void FcSolveSolver::make_move(MOVE *) { return; } void FcSolveSolver::undo_move(MOVE *) { return; } #ifdef WITH_FCS_SOFT_SUSPEND const auto SOFT_SUSPEND = FCS_STATE_SOFT_SUSPEND_PROCESS; #define set_soft_limit(u, limit) freecell_solver_user_soft_limit_iterations_long(u, limit) #else const auto SOFT_SUSPEND = FCS_STATE_SUSPEND_PROCESS; #define set_soft_limit(u, limit) freecell_solver_user_limit_iterations(u, limit) #endif /* Get the possible moves from a position, and store them in Possible[]. */ SolverInterface::ExitStatus FcSolveSolver::patsolve( int _max_positions ) { int current_iters_count; - max_positions = (_max_positions < 0) ? MAX_ITERS_LIMIT : _max_positions; + max_positions = (_max_positions < 0) ? default_max_positions : _max_positions; init(); int no_use = 0; int num_moves = 0; const auto get_possible_moves__ret = get_possible_moves(&no_use, &num_moves); Q_ASSERT( num_moves == get_possible_moves__ret ); Q_ASSERT( m_firstMoves.count() == 0 ); for (int j = 0; j < num_moves; ++j) m_firstMoves.append( Possible[j] ); // Sometimes the solver is invoked with a small maximal iterations // quota/limit (e.g: when loading a saved game or checking for autodrop // moves) and it is done frequently, so we return prematurely without // invoking freecell_solver_user_alloc() and friends which incur extra // overhead. // // The m_firstMoves should be good enough in that case. if (max_positions < 20) { return Solver::UnableToDetermineSolvability; } if (!solver_instance) { { solver_instance = freecell_solver_user_alloc(); solver_ret = FCS_STATE_NOT_BEGAN_YET; char * error_string; int error_arg; const char * known_parameters[1] = {NULL}; /* A "char *" copy instead of "const char *". */ int parse_args_ret_code = freecell_solver_user_cmd_line_parse_args( solver_instance, get_cmd_line_arg_count() , get_cmd_line_args(), 0, known_parameters, NULL, NULL, &error_string, &error_arg ); Q_ASSERT(!parse_args_ret_code); } /* Not needed for Simple Simon because it's already specified in * freecell_solver_cmd_line_args. TODO : abstract . * * Shlomi Fish * */ setFcSolverGameParams(); current_iters_count = CHUNKSIZE; set_soft_limit(solver_instance, current_iters_count); #ifdef WITH_FCS_SOFT_SUSPEND - freecell_solver_user_limit_iterations(solver_instance, MAX_ITERS_LIMIT); + freecell_solver_user_limit_iterations(solver_instance, max_positions); #endif } if (solver_instance) { bool continue_loop = true; while (continue_loop && ( (solver_ret == FCS_STATE_NOT_BEGAN_YET) || (solver_ret == SOFT_SUSPEND)) && - (current_iters_count < MAX_ITERS_LIMIT) + (current_iters_count < max_positions) ) { current_iters_count += CHUNKSIZE; set_soft_limit(solver_instance, current_iters_count); if (solver_ret == FCS_STATE_NOT_BEGAN_YET) { solver_ret = freecell_solver_user_solve_board( solver_instance, board_as_string ); } else { solver_ret = freecell_solver_user_resume_solution(solver_instance); } { // QMutexLocker lock( &endMutex ); if ( m_shouldEnd ) { continue_loop = false; } } } } const long reached_iters = freecell_solver_user_get_num_times_long(solver_instance); - Q_ASSERT(reached_iters <= MAX_ITERS_LIMIT); + Q_ASSERT(reached_iters <= default_max_positions); #if 0 fprintf(stderr, "iters = %ld\n", reached_iters); #endif switch (solver_ret) { case FCS_STATE_IS_NOT_SOLVEABLE: if (solver_instance) { freecell_solver_user_free(solver_instance); solver_instance = NULL; } return Solver::NoSolutionExists; case FCS_STATE_WAS_SOLVED: { if (solver_instance) { m_winMoves.clear(); while (freecell_solver_user_get_moves_left(solver_instance)) { fcs_move_t move; MOVE new_move; const int verdict = !freecell_solver_user_get_next_move( solver_instance, &move) ; Q_ASSERT (verdict); new_move.is_fcs = true; new_move.fcs = move; m_winMoves.append( new_move ); } freecell_solver_user_free(solver_instance); solver_instance = NULL; } return Solver::SolutionExists; } case FCS_STATE_SUSPEND_PROCESS: return Solver::UnableToDetermineSolvability; default: if (solver_instance) { freecell_solver_user_free(solver_instance); solver_instance = NULL; } return Solver::NoSolutionExists; } } /* Get the possible moves from a position, and store them in Possible[]. */ bool FcSolveSolver::isWon() { return true; } int FcSolveSolver::getOuts() { return 0; } FcSolveSolver::FcSolveSolver() : Solver() , solver_instance(NULL) , solver_ret(FCS_STATE_NOT_BEGAN_YET) , board_as_string("") + , default_max_positions(INITIAL_MAX_ITERS_LIMIT) { } unsigned int FcSolveSolver::getClusterNumber() { return 0; } void FcSolveSolver::print_layout() { #if 0 int i, w, o; fprintf(stderr, "print-layout-begin\n"); for (w = 0; w < 10; ++w) { Q_ASSERT( Wp[w] == &W[w][Wlen[w]-1] ); fprintf( stderr, "Play%d: ", w ); for (i = 0; i < Wlen[w]; ++i) { printcard(W[w][i], stderr); } fputc('\n', stderr); } fprintf( stderr, "Off: " ); for (o = 0; o < 4; ++o) { if ( O[o] != -1 ) printcard( O[o] + PS_KING, stderr); } fprintf(stderr, "\nprint-layout-end\n"); #endif } void FcSolveSolver::unpack_cluster( unsigned int) { return; } FcSolveSolver::~FcSolveSolver() { if (solver_instance) { freecell_solver_user_free(solver_instance); solver_instance = NULL; } } diff --git a/patsolve/abstract_fc_solve_solver.h b/patsolve/abstract_fc_solve_solver.h index a5e8952..fc4e2ee 100644 --- a/patsolve/abstract_fc_solve_solver.h +++ b/patsolve/abstract_fc_solve_solver.h @@ -1,52 +1,53 @@ /* * Copyright (C) 2006-2009 Stephan Kulow * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License as * published by the Free Software Foundation; either version 2 of * the License, or (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program. If not, see . */ #ifndef ABSTRACT_FC_SOLVE_SOLVER_H #define ABSTRACT_FC_SOLVE_SOLVER_H #include "patsolve.h" struct FcSolveSolver : public Solver<12> { public: FcSolveSolver(); virtual ~FcSolveSolver(); int get_possible_moves(int *a, int *numout) override = 0; bool isWon() override; void make_move(MOVE *m) override; void undo_move(MOVE *m) override; int getOuts() override; unsigned int getClusterNumber() override; void translate_layout() override = 0; void unpack_cluster( unsigned int k ) override; MoveHint translateMove(const MOVE &m) override = 0; SolverInterface::ExitStatus patsolve( int _max_positions = -1) override; virtual void setFcSolverGameParams() = 0; void print_layout() override; virtual int get_cmd_line_arg_count() = 0; virtual const char * * get_cmd_line_args() = 0; /* Names of the cards. The ordering is defined in pat.h. */ void * solver_instance; + long default_max_positions; int solver_ret; // More than enough space for two decks. char board_as_string[4 * 13 * 2 * 4 * 3]; }; #endif // ABSTRACT_FC_SOLVE_SOLVER_H