Пишем и решаем игру в 15
"Пятнашки", ошибочно приписываемые Сэмюелу Лойду - игра не менее классическая, чем "Вампус", и программки для неё, конечно, писал почти каждый действующий программист на Земле :)
Ниже показана игра в 15 для консоли C++ (проверялась в актуальной версии Visual Studio 2019), позволяющая как сыграть "вручную", так и поискать решение автоматически.
Так как изначально генерируется правильная расстановка, а затем квадратики перемешиваются, решение должно существовать всегда. Константа MIX_NUMBER
сознательно выставлена в небольшое значение, чтобы решения находились быстро. Если хотите "нерешалки", поставьте там, например, 1000
. Класс игры позволяет вводить номера передвигаемых квадратиков в качестве ходов и проверяет корректность ввода данных.
Класс решалки куда более "эзотеричен", вообще говоря, он требует, чтобы была 64-битная платформа (sizeof(unsigned long long) == 8
), а процесс решения может оказаться длинным при большом значении MIX_NUMBER
. Для краткости решалка выдаёт порядок ходов в виде цепочки символов "l
" (переместить квадратик слева от пустой клетки), "u
" (сверху), "r
" (справа) и "d
" (снизу).
Пример вывода приложения в консоли:
If this size == 8: (8) it may works correctly New game code is 0x124756039ab8defc +----+----+----+----+ | 1 | 2 | 4 | 7 | +----+----+----+----+ | 5 | 6 | | 3 | +----+----+----+----+ | 9 | 10 | 11 | 8 | +----+----+----+----+ | 13 | 14 | 15 | 12 | +----+----+----+----+ Type 1 to play manually, 2 to solve, 0 to exit: 2 Solution found in 7 moves : ruldrdd New game code is 0x123456089a7cdebf +----+----+----+----+ | 1 | 2 | 3 | 4 | +----+----+----+----+ | 5 | 6 | | 8 | +----+----+----+----+ | 9 | 10 | 7 | 12 | +----+----+----+----+ | 13 | 14 | 11 | 15 | +----+----+----+----+ Type 1 to play manually, 2 to solve, 0 to exit:
Листинг приложения:
#include <iostream> #include <string> #include <vector> #include <cstdlib> #include <ctime> using namespace std; #define MIX_NUMBER 15 /* количество перемешиваний начальной расстановки */ class game15 { public: string code; game15() { createBoard(); } void play() { bool p = true; string a; while (p) { while (!isDone()) { drawBoard(); p = getMove(); if (!p) break; } drawBoard(); cout << endl << endl << "End of game!"; p = false; } } void drawBoard() { int r; cout << endl << endl; for (int y = 0; y < 4; y++) { cout << "+----+----+----+----+" << endl; for (int x = 0; x < 4; x++) { r = brd[x + y * 4]; cout << "| "; if (r < 10) cout << " "; if (!r) cout << " "; else cout << dec << r << " "; } cout << "|" << endl; } cout << "+----+----+----+----+" << endl; } static void clearInput() { cin.clear(); cin.ignore(10000, '\n'); } private: int brd[16], x, y; void createBoard() { vector <int> v; int i; for (i = 1; i < 16; i++) { brd[i - 1] = i; } brd[15] = 0; x = y = 3; //такое вот перемешивание из начальной позиции, чтоб решалось for (i = 0; i < MIX_NUMBER; i++) { getCandidates(v); move(v[rand() % v.size()]); v.clear(); } //вычисляем код игры для решалки this->code = "0x"; string hex = "0123456789abcdef"; for (int i = 0; i < 16; i++) code += hex[this->brd[i]]; } void move (int d) { int t = x + y * 4; switch (d) { case 1: y--; break; case 2: x++; break; case 4: y++; break; case 8: x--; break; } brd[t] = brd[x + y * 4]; brd[x + y * 4] = 0; } void getCandidates (vector<int>& v) { if (x < 3) v.push_back(2); if (x > 0) v.push_back(8); if (y < 3) v.push_back(4); if (y > 0) v.push_back(1); } bool getMove() { vector <int> v; getCandidates(v); vector <int> p; getTiles(p, v); unsigned int i; while (true) { cout << endl << "Possible moves (or 0 to break): "; for (i = 0; i < p.size(); i++) cout << p[i] << " "; int z; try { cin >> z; if (cin.fail()) throw invalid_argument("You need a number here, please repeat"); } catch (invalid_argument& error) { game15::clearInput(); cerr << endl << error.what() << endl; } if (z == 0) return false; for (i = 0; i < p.size(); i++) { if (z == p[i]) { move(v[i]); return true; } } } } void getTiles(vector<int>& p, vector<int>& v) { for (unsigned int t = 0; t < v.size(); t++) { int xx = x, yy = y; switch (v[t]) { case 1: yy--; break; case 2: xx++; break; case 4: yy++; break; case 8: xx--; } p.push_back(brd[xx + yy * 4]); } } bool isDone() { for (int i = 0; i < 15; i++) if (brd[i] != i + 1) return false; return true; } }; #define BUFSIZE 128 /*размеры буферов для решалки */ class solver15 { const int Nr[16] { 3,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3 }, Nc[16] { 3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2 }; int n{}, _n{}, N0[BUFSIZE]{}, N3[BUFSIZE]{}, N4[BUFSIZE]{}; unsigned long long N2[BUFSIZE]{}; const bool fY() { if (N4[n] < _n) return fN(); if (N2[n] == 0x123456789abcdef0) { cout << "Solution found in " << dec << n << " moves :" << endl; for (int g{ 1 }; g <= n; ++g) cout << (char)N3[g]; cout << endl; return true; } if (N4[n] == _n) return fN(); else return false; } const bool fN() { if (N3[n] != 'u' && N0[n] / 4 < 3) { fI(); ++n; if (fY()) return true; --n; } if (N3[n] != 'd' && N0[n] / 4 > 0) { fG(); ++n; if (fY()) return true; --n; } if (N3[n] != 'l' && N0[n] % 4 < 3) { fE(); ++n; if (fY()) return true; --n; } if (N3[n] != 'r' && N0[n] % 4 > 0) { fL(); ++n; if (fY()) return true; --n; } return false; } void fI() { const int g = (11 - N0[n]) * 4; const unsigned long long a = N2[n] & ((unsigned long long)15 << g); N0[n + 1] = N0[n] + 4; N2[n + 1] = N2[n] - a + (a << 16); N3[n + 1] = 'd'; N4[n + 1] = N4[n] + (Nr[a >> g] <= N0[n] / 4 ? 0 : 1); } void fG() { const int g = (19 - N0[n]) * 4; const unsigned long long a = N2[n] & ((unsigned long long)15 << g); N0[n + 1] = N0[n] - 4; N2[n + 1] = N2[n] - a + (a >> 16); N3[n + 1] = 'u'; N4[n + 1] = N4[n] + (Nr[a >> g] >= N0[n] / 4 ? 0 : 1); } void fE() { const int g = (14 - N0[n]) * 4; const unsigned long long a = N2[n] & ((unsigned long long)15 << g); N0[n + 1] = N0[n] + 1; N2[n + 1] = N2[n] - a + (a << 4); N3[n + 1] = 'r'; N4[n + 1] = N4[n] + (Nc[a >> g] <= N0[n] % 4 ? 0 : 1); } void fL() { const int g = (16 - N0[n]) * 4; const unsigned long long a = N2[n] & ((unsigned long long)15 << g); N0[n + 1] = N0[n] - 1; N2[n + 1] = N2[n] - a + (a >> 4); N3[n + 1] = 'l'; N4[n + 1] = N4[n] + (Nc[a >> g] >= N0[n] % 4 ? 0 : 1); } public: solver15 (string gs) { int n = gs.substr(2).find(string("0")); char *e; unsigned long long g = strtoull(gs.c_str(), &e, 16); N0[0] = n; N2[0] = g; } void solve() { for (; not fY(); ++_n); } }; int main() { cout << "If this size == 8: (" << sizeof(unsigned long long) << ") it may works correctly" << endl; srand((unsigned)time(0)); int menu; do { game15 p; cout << endl << "New game code is " << hex << p.code << endl; p.drawBoard(); try { cout << endl << "Type 1 to play manually, 2 to solve, 0 to exit: "; cin >> menu; if (cin.fail() || menu<0 || menu>2) throw invalid_argument("Bad input, please repeat"); if (menu == 0) break; else if (menu == 1) { p.play(); //играем сами } else { solver15 s(p.code); s.solve(); //решает автоматически } } catch (invalid_argument& error) { game15::clearInput(); cerr << endl << error.what() << endl; } } while (1); return 0; }
22.10.2020, 15:44 [3272 просмотра]