کد و حل معمای eight puzzle (پازل هشت) با روش Back tracking
معرفی مسئله پازل هشت یا eight puzzle
بازی معمای هشت ( ۸-puzzle ) یکی از بازی های فکری است که احتمالا در دوران بچگی همه ی ما با آن خود را سرگرم می کردیم.
در شکل زیر بازی معمای هشت را می بینید:
همین طور که می بینید ما یک صفحه ی ۳ در ۳ داریم که با ۸ کاشی با شماره های یک تا هشت پر شده اند. در این بازی شما می توانید کاشی های مجاور خانه ی خالی را هول دهید و به جای خانه ی خالی بیاورید مثالا فرض کنید کاشی شماره ی شش را به پایین هول دهیم. شکل زیر ظاهر می شود:
با این کار ما می توانیم جای کاشی ها رو عوض کنیم.
هدف از این بازی این است که کاشی ها را با جابه جایی به شکل زیر برسانیم و مسیری را که منتهی به جواب می شود را بدست بیاوریم:
ما این سوال را با استفاده از روش عقبگرد ( Back Tracking) که نوعی روش جست و جو است حل می کنیم.
برای اینکه بتوانیم از روش عقبگرد استفاده باید با درخت حالات استفاده کنیم.
فرض کنید به ما این پازل را داده اند حل کنیم:
ما اینجا در این وضعیت سه کار می توانیم بکنیم:
یک :
شش را به پایین حل بدهیم :
دو:
یا ۵ را به چپ هل بدهیم:
سه :
یا هفت را به راست هول بدهیم:
خوب الان تمام سه حالت ممکن را برای آن حالت تولید کردیم.حالا فرض کنید که برای این سه حالت جدید به دست آمده تمام حالتاشونو تولید کنیم ، درخت زیر به دست می آید که به آن گراف حالات می گویند.(با کلیک روی آن آن را در اندازه ی واقعی ببینید)
حالا ما با جست و جوی درخت بالا می توانیم به جواب برسیم
جست و جوی عقبگرد درخت را به صورت عمقی جست و جو می کند.یعنی از ریشه ی درخت شروع می کنیم و به پایین می رویم اگر به جواب رسیدیم جست و جو را متوقف می کنیم در غیر این صورت به پایین می رویم تا به برگ های درخت (نود هایی که بچه ندارند برسیم) بعد از اینکه به برگ رسیدیم دوباره از مسیری که پایین آمدیم بالا می رویم تا به نودی در مسیر برسیم که امکان پایین رفتن را به ما بدهد ،وقتی به آن نود رسیدیم دوباره شروع می کنیم به پایین رفتن از درخت . این کار را تا زمانی که به جواب برسیم دنبال می کنیم.
در شکل بالا گره ها شماره گذاری شده است ، جست و جو به روش عقبگرد در دخت بالا به شکل زیر است:
۱ ,۲ ,۵,۱۰,۲۰
به ته درخت رسیدیم آن قدر بالا می رویم تا به نودی برسیم که بتوانیم از آن پایین بیاییم که اگر از مسیری که آمده ایم به عقب برگردیم اولین نودی که می توانیم از آن پایین برویم گره ی ۵ است که اگر از آن پایین برویم به مسیر زیر به دست می آید:
۱,۲,۵,۱۱,۲۱
به جواب نرسیدیم دوباره کار قبل را تکرار می کنیم تا به جواب برسیم مسیر های زیر مسیرهایی است که تا رسیدن به جواب تولید می شود
۱,۲,۵,۱۱,۲۲
۱,۲,۵,۱۱,۲۳
۱,۳,۶,۱۲,۲۴
۱,۳,۶,۱۳,۲۵
۱,۳,۷,۱۴,۲۶,۲۷
مسیر (۱,۳,۷,۱۴,۲۶,۲۷) به حل سوال منتهی می شود پس به جواب رسیده ایم و جست و جوی درخت را متوقف می کنیم. مسیر به دست آمده با خط پر رنگ در شکل مشخص شده است.
آیا قبل از حل مساله باید درخت حالات را تولید کرد و بعد در آن جست و جو کنیم؟
خیر ، اگر بخواهیم کل درخت را بسازیم و بعد در آن جست و جو کنیم حافظه خیلی زیادی را باید مصرف کنیم ، بهمین خاطر در حین حل مسیله درخت را می سازیم.
شاید یک سوال برای شما پیش آمده باشد و آن این است که چرا ما درخت حالت را تا عمق خاصی ساخته ایم در حالی که تا بی نهایت ممکن است عمق درخ ادامه داشته باشد؟
خوب دلیلش این است که حافظه ی کامپیوتر محدود است و ما نمی توانیم از یک عمقی به بعد را در نظر بگیریم و به همین دلیل درخت حالات را تا یک عمق مشخص پیمایش می کنیم
پیاده سازی کد مسئله پازل هشت
حالا بریم سراغ کد برنامه :
تابع مقایسه ی دو آرایه دو بعدی :
a و b دو آرایه ای هستند که قرار است مقایسه شوند و به صورت اشاره گر به تابع فرستاده شده اند.
n هم طول و عرض آرایه است.
خروجی به صورت bool است که یا مقدار True را دارد یا False.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | bool compareToArray(int **a, int **b, int n) { bool equality = true; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (a[i][j] != b[i][j]) { equality = false; } } } return equality; } |
تابع حل سوال n puzzle :
این تابع n را می گیرد و مشخص می کند پازل شما چند در چند است و فقط مختص به هشت پازل نیست مثلا ما اگر بخواهیم هشت پازل را حل کنیم پازل را در یک آرایه ی سه در سه می ریزیم بنابر این n برابر سه می شود.
این تابع به صورت بازگشتی است.
int **current_status : آرایه ی دو بعدی است که حالتی از پازل است که باید آن را حل کنیم
int **goal_status : آرایه ای دو بعدی است که هدف بازی است و باید به آن برسیم
در آرایه پازل خانه ی خالی را با صفر نمایش می دهیم.
vector <int> *path : وکتوری از جنس اعداد صحیح است که مسیری را طی کرده ایم در آن قرار دارد که اعداد در آن به شرح زیر است:
۰: یعنی خانه ی خالی در پازل را به سمت بالا برده ایم
۱: یعنی خانه ی خالی در پازل را به سمت چپ برده ایم
۲: یعنی خانه ی خالی در پازل را به سمت پایین برده ایم
۳: یعنی خانه ی خالی در پازل را به سمت راست برده ایم
int deep: حداکثر عمق درختی است که ما می توانیم به در درخت پیش برویم. اولین بار هنگام فراخوانی به deep مقدار ۱- را می دهیم.
int i_zeroPoint : مختصات i کاشی خالی است.
int j_zeroPoint : مختصات j کاشی خالی است.
int lastMove: حرکت قبلی مان در آن است تا دوباره آن را تکرار نکنیم و به مرحله ی قبل برویم. چون اگر به مرحله قبل برویم ممکن است توی حلقه هایی بیفتیم که مدت حل سوال را زیاد می کند. البته از vector <int> *path هم می توانستیم جای lastMove استفاده کنیم!
این تابع بازگشتی است و درخت را در خودش می سازد.
تابع حل مسئله puzzle , Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square , هشت پازل , شانزده پازل , پازل , n پازل ، معمای هشت
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 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 | bool eightPuzzle(int **current_status, int **goal_status, vector <int> *path, int n, int deep, int i_zeroPoint, int j_zeroPoint, int lastMove) { if (compareToArray(current_status, goal_status, n)) { return true; } // if (deep > maxDepth && path->size() == 0) { return false; } // if (deep > maxDepth) { path->pop_back(); return false; } for (int i = 0; i < 4; i++) { if ((lastMove == 0 && i == 2) || (lastMove == 2 && i == 0)) { continue; } if ((lastMove == 1 && i == 3) || (lastMove == 3 && i == 1)) { continue; } switch (i) { case 0: { //Up if (i_zeroPoint - 1 >= 0 ) { current_status[i_zeroPoint][j_zeroPoint] = current_status[i_zeroPoint - 1][j_zeroPoint]; current_status[i_zeroPoint - 1][j_zeroPoint] = 0; path->push_back(i); if (eightPuzzle(current_status, goal_status, path, n, deep + 1, i_zeroPoint - 1, j_zeroPoint, i)) { current_status[i_zeroPoint - 1][j_zeroPoint] = current_status[i_zeroPoint][j_zeroPoint]; current_status[i_zeroPoint][j_zeroPoint] = 0; return true; } current_status[i_zeroPoint - 1][j_zeroPoint] = current_status[i_zeroPoint][j_zeroPoint]; current_status[i_zeroPoint][j_zeroPoint] = 0; } break; } case 1: { //Left if (j_zeroPoint - 1 >= 0) { current_status[i_zeroPoint][j_zeroPoint] = current_status[i_zeroPoint][j_zeroPoint - 1]; current_status[i_zeroPoint][j_zeroPoint - 1] = 0; path->push_back(i); if (eightPuzzle(current_status, goal_status, path, n, deep + 1, i_zeroPoint, j_zeroPoint - 1, i)) { current_status[i_zeroPoint][j_zeroPoint - 1] = current_status[i_zeroPoint][j_zeroPoint]; current_status[i_zeroPoint][j_zeroPoint] = 0; return true; } current_status[i_zeroPoint][j_zeroPoint - 1] = current_status[i_zeroPoint][j_zeroPoint]; current_status[i_zeroPoint][j_zeroPoint] = 0; } break; } case 2: { //Down if (i_zeroPoint + 1 < n) { current_status[i_zeroPoint][j_zeroPoint] = current_status[i_zeroPoint + 1][j_zeroPoint]; current_status[i_zeroPoint + 1][j_zeroPoint] = 0; path->push_back(i); if (eightPuzzle(current_status, goal_status, path, n, deep + 1, i_zeroPoint + 1, j_zeroPoint, i)) { current_status[i_zeroPoint + 1][j_zeroPoint] = current_status[i_zeroPoint][j_zeroPoint]; current_status[i_zeroPoint][j_zeroPoint] = 0; return true; } current_status[i_zeroPoint + 1][j_zeroPoint] = current_status[i_zeroPoint][j_zeroPoint]; current_status[i_zeroPoint][j_zeroPoint] = 0; } break; } case 3: { //Right if (j_zeroPoint + 1 < n) { current_status[i_zeroPoint][j_zeroPoint] = current_status[i_zeroPoint][j_zeroPoint + 1]; current_status[i_zeroPoint][j_zeroPoint + 1] = 0; path->push_back(i); if (eightPuzzle(current_status, goal_status, path, n, deep + 1, i_zeroPoint, j_zeroPoint + 1, i)) { current_status[i_zeroPoint][j_zeroPoint + 1] = current_status[i_zeroPoint][j_zeroPoint]; current_status[i_zeroPoint][j_zeroPoint] = 0; return true; } current_status[i_zeroPoint][j_zeroPoint + 1] = current_status[i_zeroPoint][j_zeroPoint]; current_status[i_zeroPoint][j_zeroPoint] = 0; } break; } default: break; } } path->pop_back(); return false; } |
تابع showPath
این تابع حرکاتی را که باید روی خانه ی خالی انجام دهیم را که در وکتور vector <int>* path قرار دارد روی حالت اولیه انجام می دهد و قدم به قدم پازل حل شده را نمایش می دهد.
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 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 | void showPath(int **current_status, int **goal_status, vector <int> *path, int n,int i_zeroPoint, int j_zeroPoint) { int lasti; int lastj; std::cout << "goal state:" << endl; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (goal_status[i][j] == 0) { std::cout << " " << " "; continue; } std::cout << goal_status[i][j] << " "; } std::cout << endl; } std::cout << endl; std::cout << "start state:" << endl; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (current_status[i][j] == 0) { std::cout << " " << " "; continue; } std::cout << current_status[i][j] << " "; } std::cout << endl; } std::cout << endl; int **temp = new int*[3]; for (int i = 0; i < 3; i++) { temp[i] = new int[3]; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { temp[i][j] = current_status[i][j]; if (temp[i][j] == 0) { lasti = i; lastj = j; } } } std::cout << "Number of total Step " << path->size() << "." << endl << endl; for (int i = 0; i < path->size(); i++) { std::cout << "Step " << i + 1 << ":"<< endl; switch (path->at(i)) { case 0: { temp[lasti][lastj] = temp[lasti - 1][lastj]; temp[lasti - 1][lastj] = 0; lasti = lasti - 1; break; } case 1: { temp[lasti][lastj] = temp[lasti][lastj - 1]; temp[lasti][lastj - 1] = 0; lastj = lastj - 1; break; } case 2: { temp[lasti][lastj] = temp[lasti + 1][lastj]; temp[lasti + 1][lastj] = 0; lasti = lasti + 1; break; } case 3: { temp[lasti][lastj] = temp[lasti][lastj + 1]; temp[lasti][lastj + 1] = 0; lastj = lastj + 1; break; } default: break; } // for (int p = 0; p < n; p++) { for (int q = 0; q < n; q++) { if (temp[p][q] == 0) { std::cout << " " << " "; continue; } std::cout << temp[p][q] << " "; } std::cout << endl; } std::cout << endl; // } std::cout << endl; } |
کد کامل
در زیر کد کلی برنامه هشت پازل (معمای هشت) را با سی پلاس پلاس می بینید که در Main آن یک مثال به به تابع فرستاده شده:
(قبل از نوشتن کد یک عکس از خروجی را قرار داده ام)
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 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 | // 8-puzzle-back tracking.cpp : Defines the entry point for the console application. // #include <iostream> #include <vector> #define maxDepth 20 // maximum depth of tree using namespace std; bool compareToArray(int **a, int **b, int n) { bool equality = true; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (a[i][j] != b[i][j]) { equality = false; } } } return equality; } bool eightPuzzle(int **current_status, int **goal_status, vector <int> *path, int n, int deep, int i_zeroPoint, int j_zeroPoint, int lastMove) { if (compareToArray(current_status, goal_status, n)) { return true; } // if (deep > maxDepth && path->size() == 0) { return false; } // if (deep > maxDepth) { path->pop_back(); return false; } for (int i = 0; i < 4; i++) { if ((lastMove == 0 && i == 2) || (lastMove == 2 && i == 0)) { continue; } if ((lastMove == 1 && i == 3) || (lastMove == 3 && i == 1)) { continue; } switch (i) { case 0: { //Up if (i_zeroPoint - 1 >= 0 ) { current_status[i_zeroPoint][j_zeroPoint] = current_status[i_zeroPoint - 1][j_zeroPoint]; current_status[i_zeroPoint - 1][j_zeroPoint] = 0; path->push_back(i); if (eightPuzzle(current_status, goal_status, path, n, deep + 1, i_zeroPoint - 1, j_zeroPoint, i)) { current_status[i_zeroPoint - 1][j_zeroPoint] = current_status[i_zeroPoint][j_zeroPoint]; current_status[i_zeroPoint][j_zeroPoint] = 0; return true; } current_status[i_zeroPoint - 1][j_zeroPoint] = current_status[i_zeroPoint][j_zeroPoint]; current_status[i_zeroPoint][j_zeroPoint] = 0; } break; } case 1: { //Left if (j_zeroPoint - 1 >= 0) { current_status[i_zeroPoint][j_zeroPoint] = current_status[i_zeroPoint][j_zeroPoint - 1]; current_status[i_zeroPoint][j_zeroPoint - 1] = 0; path->push_back(i); if (eightPuzzle(current_status, goal_status, path, n, deep + 1, i_zeroPoint, j_zeroPoint - 1, i)) { current_status[i_zeroPoint][j_zeroPoint - 1] = current_status[i_zeroPoint][j_zeroPoint]; current_status[i_zeroPoint][j_zeroPoint] = 0; return true; } current_status[i_zeroPoint][j_zeroPoint - 1] = current_status[i_zeroPoint][j_zeroPoint]; current_status[i_zeroPoint][j_zeroPoint] = 0; } break; } case 2: { //Down if (i_zeroPoint + 1 < n) { current_status[i_zeroPoint][j_zeroPoint] = current_status[i_zeroPoint + 1][j_zeroPoint]; current_status[i_zeroPoint + 1][j_zeroPoint] = 0; path->push_back(i); if (eightPuzzle(current_status, goal_status, path, n, deep + 1, i_zeroPoint + 1, j_zeroPoint, i)) { current_status[i_zeroPoint + 1][j_zeroPoint] = current_status[i_zeroPoint][j_zeroPoint]; current_status[i_zeroPoint][j_zeroPoint] = 0; return true; } current_status[i_zeroPoint + 1][j_zeroPoint] = current_status[i_zeroPoint][j_zeroPoint]; current_status[i_zeroPoint][j_zeroPoint] = 0; } break; } case 3: { //Right if (j_zeroPoint + 1 < n) { current_status[i_zeroPoint][j_zeroPoint] = current_status[i_zeroPoint][j_zeroPoint + 1]; current_status[i_zeroPoint][j_zeroPoint + 1] = 0; path->push_back(i); if (eightPuzzle(current_status, goal_status, path, n, deep + 1, i_zeroPoint, j_zeroPoint + 1, i)) { current_status[i_zeroPoint][j_zeroPoint + 1] = current_status[i_zeroPoint][j_zeroPoint]; current_status[i_zeroPoint][j_zeroPoint] = 0; return true; } current_status[i_zeroPoint][j_zeroPoint + 1] = current_status[i_zeroPoint][j_zeroPoint]; current_status[i_zeroPoint][j_zeroPoint] = 0; } break; } default: break; } } path->pop_back(); return false; } void showPath(int **current_status, int **goal_status, vector <int> *path, int n,int i_zeroPoint, int j_zeroPoint) { int lasti; int lastj; std::cout << "goal state:" << endl; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (goal_status[i][j] == 0) { std::cout << " " << " "; continue; } std::cout << goal_status[i][j] << " "; } std::cout << endl; } std::cout << endl; std::cout << "start state:" << endl; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (current_status[i][j] == 0) { std::cout << " " << " "; continue; } std::cout << current_status[i][j] << " "; } std::cout << endl; } std::cout << endl; int **temp = new int*[3]; for (int i = 0; i < 3; i++) { temp[i] = new int[3]; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { temp[i][j] = current_status[i][j]; if (temp[i][j] == 0) { lasti = i; lastj = j; } } } std::cout << "Number of total Step " << path->size() << "." << endl << endl; for (int i = 0; i < path->size(); i++) { std::cout << "Step " << i + 1 << ":"<< endl; switch (path->at(i)) { case 0: { temp[lasti][lastj] = temp[lasti - 1][lastj]; temp[lasti - 1][lastj] = 0; lasti = lasti - 1; break; } case 1: { temp[lasti][lastj] = temp[lasti][lastj - 1]; temp[lasti][lastj - 1] = 0; lastj = lastj - 1; break; } case 2: { temp[lasti][lastj] = temp[lasti + 1][lastj]; temp[lasti + 1][lastj] = 0; lasti = lasti + 1; break; } case 3: { temp[lasti][lastj] = temp[lasti][lastj + 1]; temp[lasti][lastj + 1] = 0; lastj = lastj + 1; break; } default: break; } // for (int p = 0; p < n; p++) { for (int q = 0; q < n; q++) { if (temp[p][q] == 0) { std::cout << " " << " "; continue; } std::cout << temp[p][q] << " "; } std::cout << endl; } std::cout << endl; //open-mind.ir } std::cout << endl; } int main() { vector<int> *path = new vector<int>; int **current_status = new int*[3]; for (int i = 0; i < 3; i++) { current_status[i] = new int[3]; } int **goal_status = new int*[3]; for (int i = 0; i < 3; i++) { goal_status[i] = new int[3]; } current_status[0][0] = 2; current_status[0][1] = 8; current_status[0][2] = 3; current_status[1][0] = 1; current_status[1][1] = 6; current_status[1][2] = 4; current_status[2][0] = 7; current_status[2][1] = 0; current_status[2][2] = 5; goal_status[0][0] = 1; goal_status[0][1] = 2; goal_status[0][2] = 3; goal_status[1][0] = 8; goal_status[1][1] = 0; goal_status[1][2] = 4; goal_status[2][0] = 7; goal_status[2][1] = 6; goal_status[2][2] = 5; if (eightPuzzle(current_status, goal_status, path, 3, 0, 2, 1, -1)) { showPath(current_status, goal_status, path, 3, 2, 1); } else { cout << "Problem dosen't have solution by max tree depth " << maxDepth << "." << endl << endl; } return 0; } |
سلام
یه سوال داشتم
معمای هشت به روش اول سطح هم به جواب میرسه یا چون حافظه زیادی میطلبه تو کامپیوترهای معمولی قابل اجرا نیست؟
سلام. به جواب می رسه. اما همون طور که اشاره کردید حافظه و زمان زیادی (نسبت به *A و یا RBFS) مصرف می کنه.
سلام سال نو مبارک
میخواستم ببینم شما این کد برنامه معمای هشت را به زبان جاوا ندارید؟
فعلاً نه. البته ار سرچ کنید در وب هم کدهای آماده این مسئله با تکنیک های مختلف (مثل همین بک ترک) وجود دارن
سلام این الگوریتم A star هست؟
نه
سلام کسی رو هم نمیشناسین که بتونه اینو به زبان جاوا پیاده سازی کنه
نه متاسفانه ، جاوا کار نیستم و جاوا کارها هم دوست ندارم 😀 😉
سلام و خسته نباشید
ممنونم بابت این قطعه کد
ولی ظاهرا این کد فقط با همون اعدادی که مثال زدین جواب درست میده !
من اعداد دیگه میذارم ارور میده
چیکارش باید کرد واسه رفع ارور ؟
مطمینی ؟! یکی دوتا از از اون تست کیسات رو که موجب ارور شدن بده تا ببینم مشکل چی
فرض کن پازل مرتب است و ما بهمش می زنیم و یک حالت نامرتب به دست می آید ! این حالت نامرتب را می توان حل کرد و به جواب رسید . حالا فرض کن مهره ها را از جای خود دربیاوریم و جایشان را عوض کنیم ! یک حالت نامرتب به دست می آید ولی الزاما به جواب نمی رسد و ممکن است جوابی نداشته باشد! همین طور ممکن است جواب ما مثلا با انجام ۲۰۰ حرکت به دست بیاید که سرچ چنین درختی بسیار سنگین خواهد بود و با این کامپیوتر های ما یکم سخته !به همین خاطر ما توی کد یک عمق تعریف می کنیم که من مقدار ۲۰ را مشخص کرده ام که می گوید تا عمق بیست توی درخت پایین برو اگر جواب پیدا نکردی دیگه ادامه نده و به بالا برگرد و یک شاخه دیگر از درخت را امتحان کن! خطای برنامه هم به خاطر این بود که وقتی تمام درخت را سرچ می کرد و جوابی پیدا نمی کرد در آخر یکی از وکتورمان پاپ می کرد که موجب خطا می شد! که با اضافه کردن یک دوتا if به کد درستش کردم و کد را آپدیت کردم!
و در بالای کد یک ماکرو تعری کردم به اسم
که عمق حداکثر درخت را مشخص می کند که می تونی دستی کم یا زیادش کنی ولی هرچه زیاد تر باشد مدت زمان بیشتری برنامه طول می کشد و ممکن است حافظه ی کامپیوترت آور فلا کند!
یا ممکن است مثالی که داده ای در بیش از مثلا ۲۰۰ حرکت حل شود یا اصلا حلی نداشته باشد!
و تشکر بابت نظر خوبت.
اینو در نظر نگرفته بودم 😀
کاملا درسته . . .
مرسی که اینقد با حوصله و کامل جواب دادین 🙂
با این مثال هم ارور داد
با اینکه ۱ مرحله واسه حلش بیشتر نیاز نیست
چک کردم درست بود می دونی مشکلت از کجاست ؟!
هر دو تابع توی برنامه دو آرگومان دارند به نام
که مختصات نقطه صفر را مشخص می کنند در حالی که تو تست کیس ها رو مرتب عوض می کنی ولی اون دوتا آرگومان را عوض نکردی به همین خاطر اشتباه جواب می ده 🙂 با این تست کیسی که تو دادی آرگومان ها دو تابع به این شکل می شود ، صفر تو در حالت فراخوانی برنامه در نقطه یک و صفر است :
البته دفعه ی قبل که کد جدید رو روی سایت گذاشتم یک بخشی از آن را کپی پیست نکردم و فراموش کردم آپدیت کنم که دوباره الان آپدیت کردم!
سلام
ببخشید این به چه زبانی هست
و برای اینکه اجرا کنیم باید چه نرم افزاری رو نصب کنیم؟
کدهای برنامه به زبان ++C نوشته شده و برای اجرای این کدها یکی از کامپایلرهای ++C لازم است.
این لینک شما را به خوبی راهنمایی خواهد کرد:
راهنمای جامع کامپایل برنامه‌های C و ++C
http://lincafe.wordpress.com/2009/03/16/how-to-compile-c-and-c-programs-with-gnu-gcc-and-mingw
ویژوال استادیو ۲۰۱۳
میشه این پازل رو بصورت ۱۵تایی و به زبان جاوا بنویسید؟
پازل با استفاده از فاصله منهتن میتونه حل بشه.کد این روشو اگر بذارید یا برام ایمیل کنید خیلی ممنون میشم
سلام ، اگر توجه کرده باشید کد را به صورت پارامتری نوشته ام و می توانید با تغییرات کوچک آن را برای پانزده تایی در آورید. متاسفانه زیاد به جاوا مسلط نیستم
سلام
نوشتن این برنامه با زبان جاوا همین قدر طولانی میشه؟
روش دیگه ای برای نوشتنش نیست؟
(عکس درخت- گراف حالات- نمایش داده نمیشه)
بستگی به روش پیاده سازی داره ، مثلا می شد با سی پلاس پلاس همین رو توی برنامه ی کوچک تری نوشت ، تقریبا با جاوا هم همین قدر می شه، عکس رو هم دوباره می ذارم