patsolve.h 5.18 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
 * Copyright (C) 1998-2002 Tom Holroyd <tomh@kurage.nimh.nih.gov>
 * Copyright (C) 2006-2009 Stephan Kulow <coolo@kde.org>
 *
 * 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 <http://www.gnu.org/licenses/>.
 */

19
20
21
22
23
#ifndef PATSOLVE_H
#define PATSOLVE_H

#include "../hint.h"
#include "memory.h"
Frederik Schwarzer's avatar
Frederik Schwarzer committed
24

25
26
#include "KCardPile"

Heiko Becker's avatar
Heiko Becker committed
27
28
#include <QMap>
#include <QMutex>
Frederik Schwarzer's avatar
Frederik Schwarzer committed
29

30
#include <cstdio>
31
32


Stephan Kulow's avatar
Stephan Kulow committed
33
/* A card is represented as ( down << 6 ) + (suit << 4) + rank. */
34

Stephan Kulow's avatar
Stephan Kulow committed
35
typedef quint8 card_t;
36
37
38

/* Represent a move. */

Stephan Kulow's avatar
Stephan Kulow committed
39
enum PileType { O_Type = 1, W_Type };
40

Stephan Kulow's avatar
Stephan Kulow committed
41
42
class MOVE {
public:
43
    int card_index;         /* the card we're moving (0 is the top)*/
Stephan Kulow's avatar
Stephan Kulow committed
44
45
    quint8 from;            /* from pile number */
    quint8 to;              /* to pile number */
46
47
    PileType totype;
    signed char pri;        /* move priority (low priority == low value) */
48
    int turn_index;         /* turn the card index */
Stephan Kulow's avatar
Stephan Kulow committed
49
50
51
52
53
54

    bool operator<( const MOVE &m) const
    {
	return pri < m.pri;
    }
};
55
56
57
58
59
60
61
62

struct POSITION;

struct POSITION {
        POSITION *queue;      /* next position in the queue */
	POSITION *parent;     /* point back up the move stack */
	TREE *node;             /* compact position rep.'s tree node */
	MOVE move;              /* move that got us here from the parent */
63
	quint32 cluster; /* the cluster this node is in */
64
	short depth;            /* number of moves so far */
Stephan Kulow's avatar
Stephan Kulow committed
65
66
	quint8 ntemp;           /* number of cards in T */
	quint8 nchild;          /* number of child nodes left */
67
68
69
70
71
72
73
};

class MemoryManager;

class Solver
{
public:
74
75
76
77
78
79
80
81
82
    enum ExitStatus
    {
        MemoryLimitReached = -3,
        SearchAborted = -2,
        UnableToDetermineSolvability = -1,
        NoSolutionExists = 0,
        SolutionExists = 1
    };

83
84
    Solver();
    virtual ~Solver();
85
    ExitStatus patsolve( int max_positions = -1, bool debug = false);
Stephan Kulow's avatar
Stephan Kulow committed
86
    bool recursive(POSITION *pos = 0);
Stephan Kulow's avatar
Stephan Kulow committed
87
88
    virtual void translate_layout() = 0;
    bool m_shouldEnd;
89
    QMutex endMutex;
90
    virtual MoveHint translateMove(const MOVE &m ) = 0;
Stephan Kulow's avatar
Stephan Kulow committed
91
92
    QList<MOVE> firstMoves;
    QList<MOVE> winMoves;
93
94
95
96
97
98

protected:
    MOVE *get_moves(int *nmoves);
    bool solve(POSITION *parent);
    void doit();
    void win(POSITION *pos);
Stephan Kulow's avatar
Stephan Kulow committed
99
    virtual int get_possible_moves(int *a, int *numout) = 0;
100
    int translateSuit( int s );
101
102
103
104
105
106
107
108
109
110
111

    int wcmp(int a, int b);
    void queue_position(POSITION *pos, int pri);
    void free_position(POSITION *pos, int);
    POSITION *dequeue_position();
    void hashpile(int w);
    POSITION *new_position(POSITION *parent, MOVE *m);
    TREE *pack_position(void);
    void unpack_position(POSITION *pos);
    void init_buckets(void);
    int get_pilenum(int w);
112
    MemoryManager::inscode insert(unsigned int *cluster, int d, TREE **node);
113
    void free_buckets(void);
Stephan Kulow's avatar
Stephan Kulow committed
114
    void printcard(card_t card, FILE *outfile);
115
    int translate_pile(const KCardPile *pile, card_t *w, int size);
116
    virtual void print_layout();
117
118

    void pilesort(void);
Stephan Kulow's avatar
Stephan Kulow committed
119
    void hash_layout( void );
Stephan Kulow's avatar
Stephan Kulow committed
120
121
    virtual void make_move(MOVE *m) = 0;
    virtual void undo_move(MOVE *m) = 0;
122
    virtual void prioritize(MOVE *mp0, int n);
Stephan Kulow's avatar
Stephan Kulow committed
123
124
    virtual bool isWon() = 0;
    virtual int getOuts() = 0;
125
126
    virtual unsigned int getClusterNumber() { return 0; }
    virtual void unpack_cluster( unsigned int  ) {}
Stephan Kulow's avatar
Stephan Kulow committed
127
128
129

    void setNumberPiles( int i );
    int m_number_piles;
130

131
132
133
    void init();
    void free();

134
135
    /* Work arrays. */

Stephan Kulow's avatar
Stephan Kulow committed
136
137
138
    card_t **W; /* the workspace */
    card_t **Wp;   /* point to the top card of each work pile */
    int *Wlen;     /* the number of cards in each pile */
139
140

    /* Every different pile has a hash and a unique id. */
Stephan Kulow's avatar
Stephan Kulow committed
141
    quint32 *Whash;
Stephan Kulow's avatar
Stephan Kulow committed
142
    int *Wpilenum;
143

Stephan Kulow's avatar
Stephan Kulow committed
144
145
146
147
    /* Position freelist. */

    POSITION *Freepos;

148
149
150
151
#define MAXMOVES 64             /* > max # moves from any position */
    MOVE Possible[MAXMOVES];

    MemoryManager *mm;
152
    ExitStatus Status;             /* win, lose, or fail */
Stephan Kulow's avatar
Stephan Kulow committed
153

Stephan Kulow's avatar
Stephan Kulow committed
154
#define NQUEUES 127
Stephan Kulow's avatar
Stephan Kulow committed
155
156
157
158

    POSITION *Qhead[NQUEUES]; /* separate queue for each priority */
    int Maxq;

Stephan Kulow's avatar
Stephan Kulow committed
159
    bool m_newer_piles_first;
160
    unsigned long Total_generated, Total_positions;
161
    qreal depth_sum;
Stephan Kulow's avatar
Stephan Kulow committed
162
163
164

    POSITION *Stack;
    QMap<qint32,bool> recu_pos;
Stephan Kulow's avatar
Stephan Kulow committed
165
    int max_positions;
166
    bool debug;
Stephan Kulow's avatar
Stephan Kulow committed
167
168
};

169
/* Misc. */
Stephan Kulow's avatar
Stephan Kulow committed
170

171
172
173
174
#define PS_DIAMOND 0x00         /* red */
#define PS_CLUB    0x10         /* black */
#define PS_HEART   0x20         /* red */
#define PS_SPADE   0x30         /* black */
Stephan Kulow's avatar
Stephan Kulow committed
175
#define PS_BLACK   0x10
176
177
#define PS_COLOR   0x10         /* black if set */
#define PS_SUIT    0x30         /* mask both suit bits */
Stephan Kulow's avatar
Stephan Kulow committed
178

179
180
181
#define NONE    0
#define PS_ACE  1
#define PS_KING 13
Stephan Kulow's avatar
Stephan Kulow committed
182

183
#define RANK(card) ((card) & 0xF)
Stephan Kulow's avatar
Stephan Kulow committed
184
#define SUIT(card) (( (card) >> 4 ) & 3)
185
#define COLOR(card) ((card) & PS_COLOR)
Stephan Kulow's avatar
Stephan Kulow committed
186
#define DOWN(card) ((card) & ( 1 << 7 ) )
187

Stephan Kulow's avatar
Stephan Kulow committed
188
189
extern long all_moves;

Frederik Schwarzer's avatar
Frederik Schwarzer committed
190
#endif // PATSOLVE_H