Back Tacking

[blackhatgh]

یه توضیح در مورد الگوریتم Back Tacking میزارید یعنی کامل با طرز استفاده. برای حل این بازی ها میخوام که یه مسیر درست رو باید پیدا کنیم برای رسیدن به مقصد از تعدادی مسیر اگه پروژشو دارین بی ضحمت میشه بزارین ممنون میشم.یا یه توضیحی بدین.:بوس::بوس::بوس:

[hadi0x7c7]

بک ترک هیچ روش کللی و سیستماتیک نداره. باید اول با 8 وزیر شروع کنی بعد که فول شدی بری سراغ مساله 4 رنگ بعد از اون هم knights tour . در کل باید تمرین کنی .

در کل مثل DFS روی یک گراف هستش با این تفاوت که هر بار یه نود رو ویزیت میکنی در دور های بعد هم اونو دوباره ویزیت میکنی. که این باعث میشه پیچیدگی از چند جمله ای فراتر بره !

اینم یه نمونه 8 وزیر از کتاب Competetive Progeamming

/* 8 Queens Chess Problem */
#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;

int row[9], TC, a, b, lineCounter; // it is ok to use global variables in competitive programming

bool place(int col, int tryrow) {
for (int prev = 1; prev < col; prev++) // check previously placed queens
if (row[prev] == tryrow || (abs(row[prev] - tryrow) == abs(prev - col)))
return false; // an infeasible solution if share same row or same diagonal
return true;
}

void backtrack(int col) {
for (int tryrow = 1; tryrow <= 8; tryrow++) // try all possible row
if (place(col, tryrow)) { // if can place a queen at this col and row...
row[col] = tryrow; // put this queen in this col and row
if (col == 8 && row[b] == a) { // a candidate solution & (a, b) has 1 queen
printf("%2d %d", ++lineCounter, row[1]);
for (int j = 2; j <= 8; j++) printf(" %d", row[j]);
printf("\n");
}
else
backtrack(col + 1); // recursively try next column
}
}

int main() {
scanf("%d", &TC);
while (TC--) {
scanf("%d %d", &a, &b);
memset(row, 0, sizeof row); lineCounter = 0;
printf("SOLN COLUMN\n");
printf(" # 1 2 3 4 5 6 7 8\n\n");
backtrack(1); // generate all possible 8! candidate solutions
if (TC) printf("\n");
}
return 0;
}


کتاب Programming Challenges هم یه وصل کامل به اون اختصاص داده.

[مسعود اقدسی فام]

برای درک بهتر الگوریتم با حل معمای هشت وزیر این پیوند رو بخونید:


http://www.algorithmha.ir (http://www.algorithmha.ir/post-%D9%85%D8%B9%D9%85%D8%A7%DB%8C-%D9%87%D8%B4%D8%AA-%D9%88%D8%B2%DB%8C%D8%B1.aspx)