32 static sResult solve(
int pWidth,
int pHeight,
const std::vector<int>& pCells,
int pHoleId,
33 long pNodeLimit = 300000)
35 gfCSlidaSolver solver(pWidth, pHeight, pCells, pHoleId, pNodeLimit);
41 static int greedyTap(
int pWidth,
int pHeight,
const std::vector<int>& pCells,
int pHoleId)
43 gfCSlidaSolver solver(pWidth, pHeight, pCells, pHoleId, 0);
44 if (solver.goalReached())
49 const int holeCell = cellOf(pCells, pHoleId);
51 int bestEstimate = 1 << 30;
52 for (
int cell = 0; cell < static_cast<int>(pCells.size()); ++cell)
54 if (!adjacent(pWidth, pHeight, cell, holeCell))
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)
63 bestEstimate = estimate;
64 bestTile = pCells[cell];
71 static std::vector<int>
tapApply(
int pWidth,
int pHeight, std::vector<int> pCells,
int pHoleId,
int pTile)
73 const int tileCell = cellOf(pCells, pTile);
74 const int holeCell = cellOf(pCells, pHoleId);
75 if (adjacent(pWidth, pHeight, tileCell, holeCell))
77 std::swap(pCells[tileCell], pCells[holeCell]);
84 gfCSlidaSolver(
int pWidth,
int pHeight,
const std::vector<int>& pCells,
int pHoleId,
long pNodeLimit) :
89 mNodeLimit(pNodeLimit)
93 static int cellOf(
const std::vector<int>& pCells,
int pTile)
95 return static_cast<int>(std::find(pCells.begin(), pCells.end(), pTile) - pCells.begin());
98 static bool adjacent(
int pWidth,
int,
int pCellA,
int pCellB)
100 const int dx = std::abs(pCellA % pWidth - pCellB % pWidth);
101 const int dy = std::abs(pCellA / pWidth - pCellB / pWidth);
105 bool goalReached()
const
107 for (
int cell = 0; cell < static_cast<int>(mCells.size()); ++cell)
109 if (mCells[cell] != cell)
119 int heuristic()
const
122 for (
int cell = 0; cell < static_cast<int>(mCells.size()); ++cell)
124 const int tile = mCells[cell];
127 total += std::abs(cell % mWidth - tile % mWidth) + std::abs(cell / mWidth - tile / mWidth);
130 return total + lineConflicts(
true) + lineConflicts(
false);
133 int lineConflicts(
bool pRows)
const
135 const int lines = pRows ? mHeight : mWidth;
136 const int length = pRows ? mWidth : mHeight;
139 for (
int line = 0; line < lines; ++line)
142 std::vector<int> now;
143 std::vector<int> home;
144 for (
int along = 0; along < length; ++along)
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)
151 now.push_back(along);
152 home.push_back(pRows ? tile % mWidth : tile / mWidth);
156 const int count =
static_cast<int>(now.size());
157 std::vector<int> conflicts(count, 0);
158 for (
int a = 0; a < count; ++a)
160 for (
int b = a + 1; b < count; ++b)
162 if (home[a] > home[b])
173 const auto worst = std::max_element(conflicts.begin(), conflicts.end());
174 if (conflicts.empty() || *worst == 0)
178 const int out =
static_cast<int>(worst - conflicts.begin());
179 for (
int other = 0; other < count; ++other)
181 const bool clash = (out < other) ? home[out] > home[other] : home[other] > home[out];
182 if (other != out && clash)
196 int search(
int pMoves,
int pBound,
int pHoleCell,
int pCameFrom)
198 if (++mNodes > mNodeLimit)
203 const int estimate = pMoves + heuristic();
204 if (estimate > pBound)
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)
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)
224 const int cell = y * mWidth + x;
225 if (cell == pCameFrom)
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)
239 std::swap(mCells[cell], mCells[pHoleCell]);
240 smallestOver = std::min(smallestOver, result);
248 const int cells = mWidth * mHeight;
249 if (mWidth < 1 || mHeight < 1 ||
static_cast<int>(mCells.size()) != cells)
255 result.mSolved =
true;
259 const int holeCell = cellOf(mCells, mHoleId);
260 int bound = heuristic();
262 const int deepest = 120;
263 while (bound <= deepest)
266 const int found = search(0, bound, holeCell, -1);
269 result.mSolved =
true;
270 result.mTaps = mPath;
273 if (found == -2 || found >= (1 << 30))
285 std::vector<int> mCells;
286 const long mNodeLimit;
288 std::vector<int> mPath;
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