diff --git a/patsolve/abstract_fc_solve_solver.cpp b/patsolve/abstract_fc_solve_solver.cpp index 11e5baa..0058711 100644 --- a/patsolve/abstract_fc_solve_solver.cpp +++ b/patsolve/abstract_fc_solve_solver.cpp @@ -1,239 +1,241 @@ /* * 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; #define PRINT 0 /* These two routines make and unmake moves. */ void FcSolveSolver::make_move(MOVE *) { return; } void FcSolveSolver::undo_move(MOVE *) { return; } /* 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; init(); + int no_use = 0; + int num_moves = 0; + get_possible_moves(&no_use, &num_moves); + Q_ASSERT( m_firstMoves.count() == 0 ); + for (int j = 0; j < num_moves; ++j) + m_firstMoves.append( Possible[j] ); 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; freecell_solver_user_limit_iterations(solver_instance, current_iters_count); } if (solver_instance) { bool continue_loop = true; while (continue_loop && ( (solver_ret == FCS_STATE_NOT_BEGAN_YET) || (solver_ret == FCS_STATE_SUSPEND_PROCESS)) && (current_iters_count < MAX_ITERS_LIMIT) ) { current_iters_count += CHUNKSIZE; freecell_solver_user_limit_iterations(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; } } } } 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[]. */ -int FcSolveSolver::get_possible_moves(int *, int *) -{ - return 0; -} - 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("") { } 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 d2d072d..f75dc67 100644 --- a/patsolve/abstract_fc_solve_solver.h +++ b/patsolve/abstract_fc_solve_solver.h @@ -1,52 +1,52 @@ /* * 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<10> +struct FcSolveSolver : public Solver<12> { public: FcSolveSolver(); virtual ~FcSolveSolver(); - virtual int get_possible_moves(int *a, int *numout); + virtual int get_possible_moves(int *a, int *numout) = 0; virtual bool isWon(); virtual void make_move(MOVE *m); virtual void undo_move(MOVE *m); virtual int getOuts(); virtual unsigned int getClusterNumber(); virtual void translate_layout() = 0; virtual void unpack_cluster( unsigned int k ); virtual MoveHint translateMove(const MOVE &m) = 0; virtual SolverInterface::ExitStatus patsolve( int _max_positions = -1); virtual void setFcSolverGameParams() = 0; virtual void print_layout(); 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; 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 diff --git a/patsolve/freecellsolver.cpp b/patsolve/freecellsolver.cpp index e92000f..ebbe4e5 100644 --- a/patsolve/freecellsolver.cpp +++ b/patsolve/freecellsolver.cpp @@ -1,525 +1,569 @@ /* * Copyright (C) 1998-2002 Tom Holroyd * 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 "freecellsolver.h" #include "../freecell.h" const int CHUNKSIZE = 100; const long int MAX_ITERS_LIMIT = 200000; /* The following function implements (Same_suit ? (suit(a) == suit(b)) : (color(a) != color(b))) */ namespace { constexpr bool suitable(const card_t a, const card_t b) {return ((a ^ b) & PS_COLOR) == PS_COLOR; } } /* Statistics. */ #if 0 int FreecellSolver::Xparam[] = { 4, 1, 8, -1, 7, 11, 4, 2, 2, 1, 2 }; #endif /* These two routines make and unmake moves. */ #if 0 void FreecellSolver::make_move(MOVE *m) { int from, to; card_t card; from = m->from; to = m->to; /* Remove from pile. */ card = *Wp[from]--; Wlen[from]--; hashpile(from); /* Add to pile. */ if (m->totype == O_Type) { O[to]++; } else { *++Wp[to] = card; Wlen[to]++; hashpile(to); } } void FreecellSolver::undo_move(MOVE *m) { int from, to; card_t card; from = m->from; to = m->to; /* Remove from 'to' pile. */ if (m->totype == O_Type) { card = O[to] + Osuit[to]; O[to]--; } else { card = *Wp[to]--; Wlen[to]--; hashpile(to); } /* Add to 'from' pile. */ *++Wp[from] = card; Wlen[from]++; hashpile(from); } #endif #if 0 /* Move prioritization. Given legal, pruned moves, there are still some that are a waste of time, especially in the endgame where there are lots of possible moves, but few productive ones. Note that we also prioritize positions when they are added to the queue. */ namespace { constexpr auto NNEED = 8; } void FreecellSolver::prioritize(MOVE *mp0, int n) { int i, j, s, w, pile[NNEED], npile; card_t card, need[4]; MOVE *mp; /* There are 4 cards that we "need": the next cards to go out. We give higher priority to the moves that remove cards from the piles containing these cards. */ for (i = 0; i < NNEED; ++i) { pile[i] = -1; } npile = 0; for (s = 0; s < 4; ++s) { need[s] = NONE; if (O[s] == NONE) { need[s] = Osuit[s] + PS_ACE; } else if (O[s] != PS_KING) { need[s] = Osuit[s] + O[s] + 1; } } /* Locate the needed cards. There's room for optimization here, like maybe an array that keeps track of every card; if maintaining such an array is not too expensive. */ for (w = 0; w < Nwpiles; ++w) { j = Wlen[w]; for (i = 0; i < j; ++i) { card = W[w][i]; s = SUIT(card); /* Save the locations of the piles containing not only the card we need next, but the card after that as well. */ if (need[s] != NONE && (card == need[s] || card == need[s] + 1)) { pile[npile++] = w; if (npile == NNEED) { break; } } } if (npile == NNEED) { break; } } /* Now if any of the moves remove a card from any of the piles listed in pile[], bump their priority. Likewise, if a move covers a card we need, decrease its priority. These priority increments and decrements were determined empirically. */ for (i = 0, mp = mp0; i < n; ++i, ++mp) { if (mp->card_index != -1) { w = mp->from; for (j = 0; j < npile; ++j) { if (w == pile[j]) { mp->pri += Xparam[0]; } } if (Wlen[w] > 1) { card = W[w][Wlen[w] - 2]; for (s = 0; s < 4; ++s) { if (card == need[s]) { mp->pri += Xparam[1]; break; } } } if (mp->totype == W_Type) { for (j = 0; j < npile; ++j) { if (mp->to == pile[j]) { mp->pri -= Xparam[2]; } } } } } } #endif /* Automove logic. Freecell games must avoid certain types of automoves. */ -#if 0 +#if 1 int FreecellSolver::good_automove(int o, int r) { - int i; - if (r <= 2) { return true; } + for (int foundation_idx = 0; foundation_idx < 4; ++foundation_idx) { + KCard *c = deal->target[foundation_idx]->topCard(); + if (c) { + O[translateSuit( c->suit() ) >> 4] = c->rank(); + } + } /* Check the Out piles of opposite color. */ - for (i = 1 - (o & 1); i < 4; i += 2) { + for (int i = 1 - (o & 1); i < 4; i += 2) { if (O[i] < r - 1) { #if 1 /* Raymond's Rule */ /* Not all the N-1's of opposite color are out yet. We can still make an automove if either both N-2's are out or the other same color N-3 is out (Raymond's rule). Note the re-use of the loop variable i. We return here and never make it back to the outer loop. */ for (i = 1 - (o & 1); i < 4; i += 2) { if (O[i] < r - 2) { return false; } } if (O[(o + 2) & 3] < r - 3) { return false; } return true; #else /* Horne's Rule */ return false; #endif } } return true; } + +int FreecellSolver::get_possible_moves(int *a, int *numout) +{ + int w; + card_t card; + MOVE *mp; + + /* Check for moves from W to O. */ + + int n = 0; + mp = Possible; + for (w = 0; w < Nwpiles + Ntpiles; ++w) { + if (Wlen[w] > 0) { + card = *Wp[w]; + int out_suit = SUIT(card); + const bool empty = (O[out_suit] == NONE); + if ((empty && (RANK(card) == PS_ACE)) || + (!empty && (RANK(card) == O[out_suit] + 1))) { + mp->card_index = 0; + mp->from = w; + mp->to = out_suit; + mp->totype = O_Type; + mp->turn_index = -1; + mp->pri = 0; /* unused */ + n++; + mp++; + + /* If it's an automove, just do it. */ + + if (good_automove(out_suit, RANK(card))) { + *a = true; + mp[-1].pri = 127; + if (n != 1) { + Possible[0] = mp[-1]; + return 1; + } + *numout = n; + return n; + } + } + } + } + *numout = 0; + return 0; +} #endif #define CMD_LINE_ARGS_NUM 2 static const char * freecell_solver_cmd_line_args[CMD_LINE_ARGS_NUM] = { "--load-config", "video-editing" }; int FreecellSolver::get_cmd_line_arg_count() { return CMD_LINE_ARGS_NUM; } const char * * FreecellSolver::get_cmd_line_args() { return freecell_solver_cmd_line_args; } void FreecellSolver::setFcSolverGameParams() { /* * I'm using the more standard interface instead of the depracated * user_set_game one. I'd like that each function will have its * own dedicated purpose. * * Shlomi Fish * */ freecell_solver_user_set_num_freecells(solver_instance,4); freecell_solver_user_set_num_stacks(solver_instance,8); freecell_solver_user_set_num_decks(solver_instance,1); freecell_solver_user_set_sequences_are_built_by_type(solver_instance, FCS_SEQ_BUILT_BY_ALTERNATE_COLOR); freecell_solver_user_set_sequence_move(solver_instance, 0); freecell_solver_user_set_empty_stacks_filled_by(solver_instance, FCS_ES_FILLED_BY_ANY_CARD); } #if 0 void FreecellSolver::unpack_cluster( unsigned int k ) { /* Get the Out cells from the cluster number. */ O[0] = k & 0xF; k >>= 4; O[1] = k & 0xF; k >>= 4; O[2] = k & 0xF; k >>= 4; O[3] = k & 0xF; } #endif FreecellSolver::FreecellSolver(const Freecell *dealer) : FcSolveSolver() { #if 0 Osuit[0] = PS_DIAMOND; Osuit[1] = PS_CLUB; Osuit[2] = PS_HEART; Osuit[3] = PS_SPADE; Nwpiles = 8; Ntpiles = 4; #endif deal = dealer; } -/* Read a layout file. Format is one pile per line, bottom to top (visible -card). Temp cells and Out on the last two lines, if any. */ - -#if 0 -void FreecellSolver::translate_layout() -{ - /* Read the workspace. */ - - int total = 0; - for ( int w = 0; w < 8; ++w ) { - int i = translate_pile(deal->store[w], W[w], 52); - Wp[w] = &W[w][i - 1]; - Wlen[w] = i; - total += i; - if (w == Nwpiles) { - break; - } - } - - /* Temp cells may have some cards too. */ - - for (int w = 0; w < Ntpiles; ++w) - { - int i = translate_pile( deal->freecell[w], W[w+Nwpiles], 52 ); - Wp[w+Nwpiles] = &W[w+Nwpiles][i-1]; - Wlen[w+Nwpiles] = i; - total += i; - } - - /* Output piles, if any. */ - for (int i = 0; i < 4; ++i) { - O[i] = NONE; - } - if (total != 52) { - for (int i = 0; i < 4; ++i) { - KCard *c = deal->target[i]->topCard(); - if (c) { - O[translateSuit( c->suit() ) >> 4] = c->rank(); - total += c->rank(); - } - } - } -} -#endif - MoveHint FreecellSolver::translateMove( const MOVE &m ) { - fcs_move_t move = m.fcs; - int cards = fcs_move_get_num_cards_in_seq(move); - PatPile *from = 0; - PatPile *to = 0; - - switch(fcs_move_get_type(move)) + if (m.is_fcs) { - case FCS_MOVE_TYPE_STACK_TO_STACK: + fcs_move_t move = m.fcs; + int cards = fcs_move_get_num_cards_in_seq(move); + PatPile *from = 0; + PatPile *to = 0; + + switch(fcs_move_get_type(move)) + { + case FCS_MOVE_TYPE_STACK_TO_STACK: from = deal->store[fcs_move_get_src_stack(move)]; to = deal->store[fcs_move_get_dest_stack(move)]; break; - case FCS_MOVE_TYPE_FREECELL_TO_STACK: + case FCS_MOVE_TYPE_FREECELL_TO_STACK: from = deal->freecell[fcs_move_get_src_freecell(move)]; to = deal->store[fcs_move_get_dest_stack(move)]; cards = 1; break; - case FCS_MOVE_TYPE_FREECELL_TO_FREECELL: + case FCS_MOVE_TYPE_FREECELL_TO_FREECELL: from = deal->freecell[fcs_move_get_src_freecell(move)]; to = deal->freecell[fcs_move_get_dest_freecell(move)]; cards = 1; break; - case FCS_MOVE_TYPE_STACK_TO_FREECELL: + case FCS_MOVE_TYPE_STACK_TO_FREECELL: from = deal->store[fcs_move_get_src_stack(move)]; to = deal->freecell[fcs_move_get_dest_freecell(move)]; cards = 1; break; - case FCS_MOVE_TYPE_STACK_TO_FOUNDATION: + case FCS_MOVE_TYPE_STACK_TO_FOUNDATION: from = deal->store[fcs_move_get_src_stack(move)]; cards = 1; to = 0; break; - case FCS_MOVE_TYPE_FREECELL_TO_FOUNDATION: + case FCS_MOVE_TYPE_FREECELL_TO_FOUNDATION: from = deal->freecell[fcs_move_get_src_freecell(move)]; cards = 1; to = 0; - } - Q_ASSERT(from); - Q_ASSERT(cards <= from->cards().count()); - Q_ASSERT(to || cards == 1); - KCard *card = from->cards()[from->cards().count() - cards]; - - if (!to) - { - PatPile *target = 0; - PatPile *empty = 0; - for (int i = 0; i < 4; ++i) { - KCard *c = deal->target[i]->topCard(); - if (c) { - if ( c->suit() == card->suit() ) - { - target = deal->target[i]; - break; - } - } else if ( !empty ) - empty = deal->target[i]; } - to = target ? target : empty; - } - Q_ASSERT(to); - - return MoveHint(card, to, 0); + Q_ASSERT(from); + Q_ASSERT(cards <= from->cards().count()); + Q_ASSERT(to || cards == 1); + KCard *card = from->cards()[from->cards().count() - cards]; -#if 0 - // this is tricky as we need to want to build the "meta moves" + if (!to) + { + PatPile *target = 0; + PatPile *empty = 0; + for (int i = 0; i < 4; ++i) { + KCard *c = deal->target[i]->topCard(); + if (c) { + if ( c->suit() == card->suit() ) + { + target = deal->target[i]; + break; + } + } else if ( !empty ) + empty = deal->target[i]; + } + to = target ? target : empty; + } + Q_ASSERT(to); - PatPile *frompile = nullptr; - if ( m.from < 8 ) - frompile = deal->store[m.from]; + return MoveHint(card, to, 0); + } else - frompile = deal->freecell[m.from-8]; - KCard *card = frompile->at( frompile->count() - m.card_index - 1); - - if ( m.totype == O_Type ) { - PatPile *target = nullptr; - PatPile *empty = nullptr; - for (int i = 0; i < 4; ++i) { - KCard *c = deal->target[i]->topCard(); - if (c) { - if ( c->suit() == card->suit() ) - { - target = deal->target[i]; - break; - } - } else if ( !empty ) - empty = deal->target[i]; - } - if ( !target ) - target = empty; - return MoveHint( card, target, m.pri ); - } else { - PatPile *target = nullptr; - if ( m.to < 8 ) - target = deal->store[m.to]; + // this is tricky as we need to want to build the "meta moves" + + PatPile *frompile = nullptr; + if ( m.from < 8 ) + frompile = deal->store[m.from]; else - target = deal->freecell[m.to-8]; + frompile = deal->freecell[m.from-8]; + KCard *card = frompile->at( frompile->count() - m.card_index - 1); - return MoveHint( card, target, m.pri ); + if ( m.totype == O_Type ) + { + PatPile *target = nullptr; + PatPile *empty = nullptr; + for (int i = 0; i < 4; ++i) { + KCard *c = deal->target[i]->topCard(); + if (c) { + if ( c->suit() == card->suit() ) + { + target = deal->target[i]; + break; + } + } else if ( !empty ) + empty = deal->target[i]; + } + if ( !target ) + target = empty; + return MoveHint( card, target, m.pri ); + } else { + PatPile *target = nullptr; + if ( m.to < 8 ) + target = deal->store[m.to]; + else + target = deal->freecell[m.to-8]; + + return MoveHint( card, target, m.pri ); + } } -#endif } void FreecellSolver::translate_layout() { strcpy(board_as_string, deal->solverFormat().toLatin1()); if (solver_instance) { freecell_solver_user_recycle(solver_instance); solver_ret = FCS_STATE_NOT_BEGAN_YET; } #if 0 /* Read the workspace. */ int total = 0; for ( int w = 0; w < 10; ++w ) { int i = translate_pile(deal->store[w], W[w], 52); Wp[w] = &W[w][i - 1]; Wlen[w] = i; total += i; } for (int i = 0; i < 4; ++i) { O[i] = -1; KCard *c = deal->target[i]->top(); if (c) { total += 13; O[i] = translateSuit( c->suit() ); } } #endif + /* Read the workspace. */ + + int total = 0; + for ( int w = 0; w < 8; ++w ) { + int i = translate_pile(deal->store[w], W[w], 52); + Wp[w] = &W[w][i - 1]; + Wlen[w] = i; + total += i; + if (w == Nwpiles) { + break; + } + } + + /* Temp cells may have some cards too. */ + + for (int w = 0; w < Ntpiles; ++w) + { + int i = translate_pile( deal->freecell[w], W[w+Nwpiles], 52 ); + Wp[w+Nwpiles] = &W[w+Nwpiles][i-1]; + Wlen[w+Nwpiles] = i; + total += i; + } + + /* Output piles, if any. */ + for (int i = 0; i < 4; ++i) { + O[i] = NONE; + } + if (total != 52) { + for (int i = 0; i < 4; ++i) { + KCard *c = deal->target[i]->topCard(); + if (c) { + O[translateSuit( c->suit() ) >> 4] = c->rank(); + total += c->rank(); + } + } + } + } #if 0 unsigned int FreecellSolver::getClusterNumber() { int i = O[0] + (O[1] << 4); unsigned int k = i; i = O[2] + (O[3] << 4); k |= i << 8; return k; } #endif #if 0 void FreecellSolver::print_layout() { int i, t, w, o; fprintf(stderr, "print-layout-begin\n"); for (w = 0; w < Nwpiles; ++w) { fprintf(stderr, "W-Pile%d: ", w); for (i = 0; i < Wlen[w]; ++i) { printcard(W[w][i], stderr); } fputc('\n', stderr); } for (t = 0; t < Ntpiles; ++t) { fprintf(stderr, "T-Pile%d: ", t+Nwpiles); printcard(W[t+Nwpiles][Wlen[t+Nwpiles]], stderr); } fprintf( stderr, "\n" ); for (o = 0; o < 4; ++o) { printcard(O[o] + Osuit[o], stderr); } fprintf(stderr, "\nprint-layout-end\n"); } #endif diff --git a/patsolve/freecellsolver.h b/patsolve/freecellsolver.h index 99d1dbb..c58d380 100644 --- a/patsolve/freecellsolver.h +++ b/patsolve/freecellsolver.h @@ -1,71 +1,71 @@ /* * Copyright (C) 1998-2002 Tom Holroyd * 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 FREECELLSOLVER_H #define FREECELLSOLVER_H #include "abstract_fc_solve_solver.h" constexpr auto Nwpiles = 8; constexpr auto Ntpiles = 4; class Freecell; class FreecellSolver : public FcSolveSolver { public: explicit FreecellSolver(const Freecell *dealer); -#if 0 int good_automove(int o, int r); - int get_possible_moves(int *a, int *numout) Q_DECL_OVERRIDE; + virtual int get_possible_moves(int *a, int *numout) Q_DECL_OVERRIDE; +#if 0 bool isWon() Q_DECL_OVERRIDE; void make_move(MOVE *m) Q_DECL_OVERRIDE; void undo_move(MOVE *m) Q_DECL_OVERRIDE; void prioritize(MOVE *mp0, int n) Q_DECL_OVERRIDE; int getOuts() Q_DECL_OVERRIDE; unsigned int getClusterNumber() Q_DECL_OVERRIDE; void translate_layout() Q_DECL_OVERRIDE; void unpack_cluster( unsigned int k ) Q_DECL_OVERRIDE; MoveHint translateMove(const MOVE &m) Q_DECL_OVERRIDE; #endif virtual void translate_layout(); #if 0 virtual void unpack_cluster( unsigned int k ); #endif virtual MoveHint translateMove(const MOVE &m); virtual void setFcSolverGameParams(); virtual int get_cmd_line_arg_count(); virtual const char * * get_cmd_line_args(); #if 0 virtual void print_layout(); int Nwpiles; /* the numbers we're actually using */ int Ntpiles; /* Names of the cards. The ordering is defined in pat.h. */ - card_t O[4]; /* output piles store only the rank or NONE */ card_t Osuit[4]; static int Xparam[]; #endif + card_t O[4]; /* output piles store only the rank or NONE */ const Freecell *deal; }; #endif // FREECELLSOLVER_H diff --git a/patsolve/simonsolver.cpp b/patsolve/simonsolver.cpp index e75dcaa..f20462f 100644 --- a/patsolve/simonsolver.cpp +++ b/patsolve/simonsolver.cpp @@ -1,544 +1,549 @@ /* * 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 "simonsolver.h" #include "../simon.h" #include const int CHUNKSIZE = 100; const long int MAX_ITERS_LIMIT = 200000; #define PRINT 0 /* These two routines make and unmake moves. */ #if 0 void SimonSolver::make_move(MOVE *m) { #if PRINT //qDebug() << "\n\nmake_move\n"; if ( m->totype == O_Type ) fprintf( stderr, "move %d from %d out (at %d) Prio: %d\n\n", m->card_index, m->from, m->turn_index, m->pri ); else fprintf( stderr, "move %d from %d to %d (%d) Prio: %d\n\n", m->card_index, m->from, m->to, m->turn_index, m->pri ); print_layout(); #else //print_layout(); #endif int from, to; card_t card = NONE; from = m->from; to = m->to; if (m->totype == O_Type) { O[to] = SUIT( *Wp[from] ); Wlen[from] -= 13; Wp[from] -= 13; hashpile( from ); if ( Wlen[from] && DOWN( *Wp[from] ) ) { *Wp[from] = ( SUIT( *Wp[from] ) << 4 ) + RANK( *Wp[from] ); } #if PRINT print_layout(); #endif return; } for ( int l = m->card_index; l >= 0; --l ) { card = W[from][Wlen[from]-l-1]; Wp[from]--; if ( m->totype != O_Type ) { Wp[to]++; *Wp[to] = card; Wlen[to]++; } } Wlen[from] -= m->card_index + 1; hashpile(from); hashpile(to); #if PRINT print_layout(); #endif } void SimonSolver::undo_move(MOVE *m) { #if PRINT //qDebug() << "\n\nundo_move\n"; if ( m->totype == O_Type ) fprintf( stderr, "move %d from %d out (at %d)\n\n", m->card_index, m->from, m->turn_index ); else fprintf( stderr, "move %d from %d to %d (%d)\n\n", m->card_index, m->from, m->to, m->turn_index ); print_layout(); #endif int from, to; card_t card; from = m->from; to = m->to; if (m->totype == O_Type) { for ( int j = PS_KING; j >= PS_ACE; --j ) { Wp[from]++; *Wp[from] = O[to] + j; Wlen[from]++; } O[to] = -1; hashpile( from ); #if PRINT print_layout(); #endif return; } /* Add to 'from' pile. */ if ( m->turn_index > 0 ) { card_t card2 = *Wp[from]; if ( !DOWN( card2 ) ) card2 = ( SUIT( card2 ) << 4 ) + RANK( card2 ) + ( 1 << 7 ); *Wp[from] = card2; } for ( int l = m->card_index; l >= 0; --l ) { card = W[to][Wlen[to]-l-1]; Wp[from]++; *Wp[from] = card; Wlen[from]++; Wp[to]--; } Wlen[to] -= m->card_index + 1; hashpile(to); hashpile(from); #if PRINT print_layout(); #endif } #endif #define CMD_LINE_ARGS_NUM 4 static const char * freecell_solver_cmd_line_args[CMD_LINE_ARGS_NUM] = { "-g", "simple_simon", "--load-config", "the-last-mohican" }; int SimonSolver::get_cmd_line_arg_count() { return CMD_LINE_ARGS_NUM; } const char * * SimonSolver::get_cmd_line_args() { return freecell_solver_cmd_line_args; } void SimonSolver::setFcSolverGameParams() { freecell_solver_user_apply_preset(solver_instance, "simple_simon"); } +int SimonSolver::get_possible_moves(int *, int *) +{ + return 0; +} + #if 0 /* Get the possible moves from a position, and store them in Possible[]. */ int SimonSolver::get_possible_moves(int *a, int *numout) { MOVE *mp; int n; mp = Possible; n = 0; *a = 1; while (freecell_solver_user_get_moves_left(solver_instance)) { fcs_move_t move; fcs_move_t * move_ptr; if (!freecell_solver_user_get_next_move(solver_instance, &move)) { move_ptr = new fcs_move_t; *move_ptr = move; mp->ptr = (void *)move_ptr; mp++; n++; } else { Q_ASSERT(0); } } *numout = n; return n; #if 0 /* Check for moves from W to O. */ int n = 0; mp = Possible; for (int w = 0; w < 10; ++w) { if (Wlen[w] >= 13 && RANK( *Wp[w] ) == PS_ACE ) { int ace_suit = SUIT( *Wp[w] ); bool stroke = true; for ( int l = 0; l < 13; ++l ) { if ( RANK( W[w][Wlen[w]-l-1] ) != l+1 || SUIT( W[w][Wlen[w]-l-1] ) != ace_suit ) { stroke = false; break; } } if ( !stroke ) continue; mp->card_index = 12; mp->from = w; int o = 0; while ( O[o] != -1) o++; // TODO I need a way to tell spades off from heart off mp->to = o; mp->totype = O_Type; mp->pri = 0; /* unused */ mp->turn_index = -1; n++; mp++; return 1; } } /* No more automoves, but remember if there were any moves out. */ *a = false; *numout = n; int conti[10]; for ( int j = 0; j < 10; ++j ) { conti[j] = 0; for ( ; conti[j] < Wlen[j]-1; ++conti[j] ) { if ( SUIT( *Wp[j] ) != SUIT( W[j][Wlen[j]-conti[j]-2] ) || DOWN( W[j][Wlen[j]-conti[j]-2] )) break; if ( RANK( W[j][Wlen[j]-conti[j]-1] ) != RANK( W[j][Wlen[j]-conti[j]-2] ) - 1) break; } conti[j]++; } for(int i=0; i<10; ++i) { int len = Wlen[i]; for (int l=0; l < len; ++l ) { card_t card = W[i][Wlen[i]-1-l]; if ( DOWN( card ) ) break; if ( l > 0 ) { card_t card_on_top = W[i][Wlen[i]-l]; if ( RANK( card ) != RANK( card_on_top ) + 1 ) break; if ( SUIT( card ) != SUIT( card_on_top ) ) break; } bool wasempty = false; for (int j = 0; j < 10; ++j) { if (i == j) continue; bool allowed = false; if ( Wlen[j] > 0 && RANK(card) == RANK(*Wp[j]) - 1 ) { allowed = true; } if ( Wlen[j] == 0 && !wasempty ) { if ( l != Wlen[i]-1 ) { allowed = true; wasempty = true; } } if ( allowed && Wlen[i] >= l+2 && Wlen[i] > 1 ) { Q_ASSERT( Wlen[i]-l-2 >= 0 ); card_t card_below = W[i][Wlen[i]-l-2]; if ( SUIT( card ) == SUIT( card_below ) && !DOWN( card_below ) && RANK( card_below ) == RANK( card ) + 1 ) { if ( conti[j]+l != 13 || conti[i]>conti[j]+l || SUIT( card ) != SUIT( *Wp[j] ) ) { // fprintf( stderr, "continue\n" ); continue; } } } if ( allowed ) { mp->card_index = l; mp->from = i; mp->to = j; mp->totype = W_Type; mp->turn_index = -1; int cont = conti[j]; if ( Wlen[j] ) cont++; if ( cont ) cont += l; mp->pri = 8 * cont + qMax( 0, 10 - Wlen[i] ); if ( Wlen[j] ) { if ( SUIT( card ) != SUIT( *Wp[j] ) ) { mp->pri /= 2; } } else { mp->pri = 2; // TODO: it should depend on the actual stack's order } if ( Wlen[i] == l+1 ) mp->pri = qMin( 127, mp->pri + 20 ); else mp->pri = qMin( 127, mp->pri + 2 ); /* and now check what sequence we open */ int conti_pos = l+1; for ( ; conti_pos < Wlen[i]-1; ++conti_pos ) { card_t top = W[i][Wlen[i]-l-2]; card_t theone = W[i][Wlen[i]-conti_pos-1]; card_t below = W[i][Wlen[i]-conti_pos-2]; if ( SUIT( top ) != SUIT( below ) || DOWN( below ) ) break; if ( RANK( theone ) != RANK( below ) - 1) break; } mp->pri = qMin( 127, mp->pri + 5 * ( conti_pos - l - 1 ) ); n++; mp++; } } } } return n; #endif } #endif #if 0 void SimonSolver::unpack_cluster( unsigned int k ) { // TODO: this only works for easy for ( unsigned int i = 0; i < 4; ++i ) { if ( i < k ) O[i] = PS_SPADE; else O[i] = -1; } } #endif #if 0 bool SimonSolver::isWon() { // maybe won? for (int o = 0; o < 4; ++o) if (O[o] == -1) return false; return true; } #endif #if 0 int SimonSolver::getOuts() { int k = 0; for (int o = 0; o < 4; ++o) if (O[o]) k += 13; return k; } #endif SimonSolver::SimonSolver(const Simon *dealer) : FcSolveSolver() { deal = dealer; } /* Read a layout file. Format is one pile per line, bottom to top (visible card). Temp cells and Out on the last two lines, if any. */ void SimonSolver::translate_layout() { strcpy(board_as_string, deal->solverFormat().toLatin1()); if (solver_instance) { freecell_solver_user_recycle(solver_instance); solver_ret = FCS_STATE_NOT_BEGAN_YET; } #if 0 /* Read the workspace. */ int total = 0; for ( int w = 0; w < 10; ++w ) { int i = translate_pile(deal->store[w], W[w], 52); Wp[w] = &W[w][i - 1]; Wlen[w] = i; total += i; } for (int i = 0; i < 4; ++i) { O[i] = -1; KCard *c = deal->target[i]->topCard(); if (c) { total += 13; O[i] = translateSuit( c->suit() ); } } #endif } #if 0 unsigned int SimonSolver::getClusterNumber() { unsigned int k = 0; for ( int i = 0; i < 4; ++i ) { if ( O[i] != -1 ) k++; } return k; } #endif #if 0 void SimonSolver::print_layout() { 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 MoveHint SimonSolver::translateMove( const MOVE &m ) { fcs_move_t move = m.fcs; int cards = fcs_move_get_num_cards_in_seq(move); PatPile *from = 0; PatPile *to = 0; switch(fcs_move_get_type(move)) { case FCS_MOVE_TYPE_STACK_TO_STACK: from = deal->store[fcs_move_get_src_stack(move)]; to = deal->store[fcs_move_get_dest_stack(move)]; break; case FCS_MOVE_TYPE_SEQ_TO_FOUNDATION: from = deal->store[fcs_move_get_src_stack(move)]; cards = 13; to = deal->target[fcs_move_get_foundation(move)]; break; } Q_ASSERT(from); Q_ASSERT(cards <= from->cards().count()); Q_ASSERT(to || cards == 1); KCard *card = from->cards()[from->cards().count() - cards]; if (!to) { PatPile *target = 0; PatPile *empty = 0; for (int i = 0; i < 4; ++i) { KCard *c = deal->target[i]->topCard(); if (c) { if ( c->suit() == card->suit() ) { target = deal->target[i]; break; } } else if ( !empty ) empty = deal->target[i]; } to = target ? target : empty; } Q_ASSERT(to); return MoveHint(card, to, 0); #if 0 Q_ASSERT( m.from < 10 && m.to < 10 ); PatPile *frompile = deal->store[m.from]; KCard *card = frompile->at( frompile->count() - m.card_index - 1); if ( m.totype == O_Type ) { for ( int i = 0; i < 4; ++i ) if ( deal->target[i]->isEmpty() ) return MoveHint( card, deal->target[i], 127 ); } Q_ASSERT( m.to < 10 ); return MoveHint( card, deal->store[m.to], m.pri ); #endif } diff --git a/patsolve/simonsolver.h b/patsolve/simonsolver.h index 4a417b1..c0c1b50 100644 --- a/patsolve/simonsolver.h +++ b/patsolve/simonsolver.h @@ -1,55 +1,55 @@ /* * 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 SIMONSOLVER_H #define SIMONSOLVER_H #include "abstract_fc_solve_solver.h" #include "simon.h" class Simon; class SimonSolver : public FcSolveSolver { public: explicit SimonSolver(const Simon *dealer); -#if 0 int get_possible_moves(int *a, int *numout) Q_DECL_OVERRIDE; +#if 0 bool isWon() Q_DECL_OVERRIDE; void make_move(MOVE *m) Q_DECL_OVERRIDE; void undo_move(MOVE *m) Q_DECL_OVERRIDE; int getOuts() Q_DECL_OVERRIDE; unsigned int getClusterNumber() Q_DECL_OVERRIDE; #endif virtual void translate_layout() Q_DECL_OVERRIDE; virtual MoveHint translateMove(const MOVE &m) Q_DECL_OVERRIDE; #if 0 void unpack_cluster( unsigned int k ) Q_DECL_OVERRIDE; void print_layout() Q_DECL_OVERRIDE; #endif virtual void setFcSolverGameParams(); virtual int get_cmd_line_arg_count(); virtual const char * * get_cmd_line_args(); #if 0 /* Names of the cards. The ordering is defined in pat.h. */ int O[4]; #endif const Simon *deal; }; #endif // SIMONSOLVER_H diff --git a/patsolve/solverinterface.h b/patsolve/solverinterface.h index 77fd410..546c959 100644 --- a/patsolve/solverinterface.h +++ b/patsolve/solverinterface.h @@ -1,57 +1,60 @@ #ifndef SolverInterface_H #define SolverInterface_H #include #include "../hint.h" #include "freecell-solver/fcs_user.h" /* A card is represented as ( down << 6 ) + (suit << 4) + rank. */ typedef quint8 card_t; /* Represent a move. */ enum PileType { O_Type = 1, W_Type }; class MOVE { public: int card_index; /* the card we're moving (0 is the top)*/ quint8 from; /* from pile number */ quint8 to; /* to pile number */ PileType totype; signed char pri; /* move priority (low priority == low value) */ int turn_index; /* turn the card index */ + bool is_fcs; fcs_move_t fcs; /* A Freecell Solver move. */ bool operator<( const MOVE &m) const { return pri < m.pri; } + + MOVE() : is_fcs(false) {} }; class SolverInterface { public: enum ExitStatus { MemoryLimitReached = -3, SearchAborted = -2, UnableToDetermineSolvability = -1, NoSolutionExists = 0, SolutionExists = 1 }; virtual ~SolverInterface() {}; virtual ExitStatus patsolve( int max_positions = -1) = 0; virtual void translate_layout() = 0; virtual MoveHint translateMove(const MOVE &m ) = 0; virtual void stopExecution() = 0; virtual QList firstMoves() const = 0; virtual QList winMoves() const = 0; }; extern long all_moves; #endif