Sliding Game

You're given a 3x3 board of a tile puzzle, with 8 tiles numbered 1 to 8, and an empty spot. You can move any tile adjacent to the empty spot, to the empty spot, creating an empty spot where the tile originally was. The goal is to find a series of moves that will solve the board, i.e. get [ [1, 2, 3], [4, 5, 6], [7, 8, - ]…

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82

#pragma once #include <unordered_set> #include <queue> #include <string> #include <algorithm> using namespace std; namespace airbnb { class SlidingGame { public: SlidingGame(); ~SlidingGame(); bool IsValidStart(string& initState); private: string m_initState; const string finalState = "123456780"; }; SlidingGame::SlidingGame() { } SlidingGame::~SlidingGame() { } bool SlidingGame::IsValidStart(string& initState) { if (initState == finalState) { return true; } const vector<int> x_move = { -1, 0, 1, 0 }; const vector<int> y_move = { 0, 1, 0, -1 }; queue<string> slidingqueue; unordered_set<string> visited; slidingqueue.push(initState); visited.insert(initState); cout << initState << endl; while (!slidingqueue.empty()) { auto top = slidingqueue.front(); slidingqueue.pop(); int idx = top.find('0'); int x = idx / 3; int y = idx % 3; for (int i = 0; i < 4; i++) { int m_x = x + x_move[i]; int m_y = y + y_move[i]; if (m_x < 0 || m_x >= 3 || m_y < 0 || m_y >= 3) { continue; } int m_idx = 3 * m_x + m_y; swap(top[idx], top[m_idx]); if (top == finalState) { return true; } if (visited.find(top) == visited.end()) { visited.insert(top); slidingqueue.push(top); cout << top << endl; } // backtrack swap(top[idx], top[m_idx]); } } return false; } }