Fission FSN
Loading...
Searching...
No Matches
gfCSlidaSolver.h
Go to the documentation of this file.
1/********************************************************************
2*
3* File: gfCSlidaSolver.h
4*
5* Purpose: Solves the sliding puzzle with a hole - engine free, so it can be tested alone
6*
7*********************************************************************/
8
9#ifndef gfCSlidaSolverhdr
10#define gfCSlidaSolverhdr
11
12#include <algorithm>
13#include <cstdlib>
14#include <vector>
15
16
17// Tiles are numbered by their home cell, row by row, and the hole is one of them. A move taps
18// the tile next to the hole, which then slides into it.
19class gfCSlidaSolver
20{
21public:
22
23 struct sResult
24 {
25 // False if the search gave up (too many nodes) or the position cannot be solved.
26 bool mSolved = false;
27 // The tiles to tap, in order. Empty with mSolved set means it is already done.
28 std::vector<int> mTaps;
29 };
30
31 // pCells holds the tile in each cell, row by row.
32 static sResult solve(int pWidth, int pHeight, const std::vector<int>& pCells, int pHoleId,
33 long pNodeLimit = 300000)
34 {
35 gfCSlidaSolver solver(pWidth, pHeight, pCells, pHoleId, pNodeLimit);
36 return solver.run();
37 }
38
39 // The tap that most reduces the estimate of the moves left - no promise it leads home, but it is
40 // instant. For boards too big to search in the time a hint may take. -1 if already home.
41 static int greedyTap(int pWidth, int pHeight, const std::vector<int>& pCells, int pHoleId)
42 {
43 gfCSlidaSolver solver(pWidth, pHeight, pCells, pHoleId, 0);
44 if (solver.goalReached())
45 {
46 return -1;
47 }
48
49 const int holeCell = cellOf(pCells, pHoleId);
50 int bestTile = -1;
51 int bestEstimate = 1 << 30;
52 for (int cell = 0; cell < static_cast<int>(pCells.size()); ++cell)
53 {
54 if (!adjacent(pWidth, pHeight, cell, holeCell))
55 {
56 continue;
57 }
58 std::swap(solver.mCells[cell], solver.mCells[holeCell]);
59 const int estimate = solver.heuristic();
60 std::swap(solver.mCells[cell], solver.mCells[holeCell]);
61 if (estimate < bestEstimate)
62 {
63 bestEstimate = estimate;
64 bestTile = pCells[cell];
65 }
66 }
67 return bestTile;
68 }
69
70 // The cells after the tile has been tapped, or the same cells if it is not next to the hole.
71 static std::vector<int> tapApply(int pWidth, int pHeight, std::vector<int> pCells, int pHoleId, int pTile)
72 {
73 const int tileCell = cellOf(pCells, pTile);
74 const int holeCell = cellOf(pCells, pHoleId);
75 if (adjacent(pWidth, pHeight, tileCell, holeCell))
76 {
77 std::swap(pCells[tileCell], pCells[holeCell]);
78 }
79 return pCells;
80 }
81
82private:
83
84 gfCSlidaSolver(int pWidth, int pHeight, const std::vector<int>& pCells, int pHoleId, long pNodeLimit) :
85 mWidth(pWidth),
86 mHeight(pHeight),
87 mHoleId(pHoleId),
88 mCells(pCells),
89 mNodeLimit(pNodeLimit)
90 {
91 }
92
93 static int cellOf(const std::vector<int>& pCells, int pTile)
94 {
95 return static_cast<int>(std::find(pCells.begin(), pCells.end(), pTile) - pCells.begin());
96 }
97
98 static bool adjacent(int pWidth, int, int pCellA, int pCellB)
99 {
100 const int dx = std::abs(pCellA % pWidth - pCellB % pWidth);
101 const int dy = std::abs(pCellA / pWidth - pCellB / pWidth);
102 return dx + dy == 1;
103 }
104
105 bool goalReached() const
106 {
107 for (int cell = 0; cell < static_cast<int>(mCells.size()); ++cell)
108 {
109 if (mCells[cell] != cell)
110 {
111 return false;
112 }
113 }
114 return true;
115 }
116
117 // Lower bound on the moves left: each tile's distance home, plus two for each tile that must
118 // step out of its row or column to let another past it.
119 int heuristic() const
120 {
121 int total = 0;
122 for (int cell = 0; cell < static_cast<int>(mCells.size()); ++cell)
123 {
124 const int tile = mCells[cell];
125 if (tile != mHoleId)
126 {
127 total += std::abs(cell % mWidth - tile % mWidth) + std::abs(cell / mWidth - tile / mWidth);
128 }
129 }
130 return total + lineConflicts(true) + lineConflicts(false);
131 }
132
133 int lineConflicts(bool pRows) const
134 {
135 const int lines = pRows ? mHeight : mWidth;
136 const int length = pRows ? mWidth : mHeight;
137 int total = 0;
138
139 for (int line = 0; line < lines; ++line)
140 {
141 // The tiles in this line that belong in it: their place along it now, and at home.
142 std::vector<int> now;
143 std::vector<int> home;
144 for (int along = 0; along < length; ++along)
145 {
146 const int cell = pRows ? line * mWidth + along : along * mWidth + line;
147 const int tile = mCells[cell];
148 const int tileLine = pRows ? tile / mWidth : tile % mWidth;
149 if (tile != mHoleId && tileLine == line)
150 {
151 now.push_back(along);
152 home.push_back(pRows ? tile % mWidth : tile / mWidth);
153 }
154 }
155
156 const int count = static_cast<int>(now.size());
157 std::vector<int> conflicts(count, 0);
158 for (int a = 0; a < count; ++a)
159 {
160 for (int b = a + 1; b < count; ++b)
161 {
162 if (home[a] > home[b])
163 {
164 ++conflicts[a];
165 ++conflicts[b];
166 }
167 }
168 }
169
170 // Take out the worst offender until none clash; each one costs a detour of two moves.
171 for (;;)
172 {
173 const auto worst = std::max_element(conflicts.begin(), conflicts.end());
174 if (conflicts.empty() || *worst == 0)
175 {
176 break;
177 }
178 const int out = static_cast<int>(worst - conflicts.begin());
179 for (int other = 0; other < count; ++other)
180 {
181 const bool clash = (out < other) ? home[out] > home[other] : home[other] > home[out];
182 if (other != out && clash)
183 {
184 --conflicts[other];
185 }
186 }
187 conflicts[out] = 0;
188 total += 2;
189 }
190 }
191 return total;
192 }
193
194 // Depth first up to pBound moves. Returns the smallest estimate that went over it, or
195 // -1 once solved (the path is left in mPath), or -2 when it ran out of nodes.
196 int search(int pMoves, int pBound, int pHoleCell, int pCameFrom)
197 {
198 if (++mNodes > mNodeLimit)
199 {
200 return -2;
201 }
202
203 const int estimate = pMoves + heuristic();
204 if (estimate > pBound)
205 {
206 return estimate;
207 }
208 if (goalReached())
209 {
210 return -1;
211 }
212
213 int smallestOver = 1 << 30;
214 const int dx[4] = {1, -1, 0, 0};
215 const int dy[4] = {0, 0, 1, -1};
216 for (int direction = 0; direction < 4; ++direction)
217 {
218 const int x = pHoleCell % mWidth + dx[direction];
219 const int y = pHoleCell / mWidth + dy[direction];
220 if (x < 0 || x >= mWidth || y < 0 || y >= mHeight)
221 {
222 continue;
223 }
224 const int cell = y * mWidth + x;
225 if (cell == pCameFrom)
226 {
227 continue;
228 }
229
230 const int tile = mCells[cell];
231 std::swap(mCells[cell], mCells[pHoleCell]);
232 mPath.push_back(tile);
233 const int result = search(pMoves + 1, pBound, cell, pHoleCell);
234 if (result == -1 || result == -2)
235 {
236 return result;
237 }
238 mPath.pop_back();
239 std::swap(mCells[cell], mCells[pHoleCell]);
240 smallestOver = std::min(smallestOver, result);
241 }
242 return smallestOver;
243 }
244
245 sResult run()
246 {
247 sResult result;
248 const int cells = mWidth * mHeight;
249 if (mWidth < 1 || mHeight < 1 || static_cast<int>(mCells.size()) != cells)
250 {
251 return result;
252 }
253 if (goalReached())
254 {
255 result.mSolved = true;
256 return result;
257 }
258
259 const int holeCell = cellOf(mCells, mHoleId);
260 int bound = heuristic();
261 // No solution is longer than this for the sizes in use; an unsolvable position runs it out.
262 const int deepest = 120;
263 while (bound <= deepest)
264 {
265 mPath.clear();
266 const int found = search(0, bound, holeCell, -1);
267 if (found == -1)
268 {
269 result.mSolved = true;
270 result.mTaps = mPath;
271 return result;
272 }
273 if (found == -2 || found >= (1 << 30))
274 {
275 return result;
276 }
277 bound = found;
278 }
279 return result;
280 }
281
282 const int mWidth;
283 const int mHeight;
284 const int mHoleId;
285 std::vector<int> mCells;
286 const long mNodeLimit;
287 long mNodes = 0;
288 std::vector<int> mPath;
289};
290
291#endif
Definition gfCSlidaSolver.h:20
static int greedyTap(int pWidth, int pHeight, const std::vector< int > &pCells, int pHoleId)
Definition gfCSlidaSolver.h:41
static sResult solve(int pWidth, int pHeight, const std::vector< int > &pCells, int pHoleId, long pNodeLimit=300000)
Definition gfCSlidaSolver.h:32
static std::vector< int > tapApply(int pWidth, int pHeight, std::vector< int > pCells, int pHoleId, int pTile)
Definition gfCSlidaSolver.h:71
Definition gfCSlidaSolver.h:24
std::vector< int > mTaps
Definition gfCSlidaSolver.h:28
bool mSolved
Definition gfCSlidaSolver.h:26