حل سوال گردش اسب یا knight’s tour
مسئله گردش اسب یا سفر اسب
مقدمه و تعریف
مسئله گردش اسب یکی از سوال های محبوب و هیجان انگیز برای مبتدیان در برنامه نویسی است. می خواهیم برنامه ای بنویسیم که یک اسب را در یکی از خانه های شطرنج قرار دهد و اسب را طوری جا به جا کند که اسب از همه خانه های شطرنج عبور کند بدون این که از یک خانه بیش از یک بار عبور کند. با ما همراه باشید.
قوانین مسئله
در حرکت اسبی یا همان knight tour اسب می تواند حرکاتی به شکل L انجام دهد(دو خانه در یک جهت و سپس یک خانه در جهت عمود بر جهت اول )به این ترتیب یک اسب از خانه ای در وسط صفحه خالی شطرنج می تواند هر یک از هشت حرکت مختلف را که در شکل می بینید انجام دهد.
knight-move-chess
۱ ) یک صفحه شطرنج ۸*۸ رسم کنید و سعی کنید مساله گردش اسب را با دست حل کنید . در اولین خانه ای که قرار می گیرید عدد ۱و در دومین خانه عدد ۲ و در سومین خانه عدد ۳ و…را بنویسید . پیش از آغاز گردش مسافتی را که می تواند طی کند تخمین بزنید؟
۲) برنامه ای بنویسید که اسب را در یک صفحه شطرنج گردش دهد . این صفحه را با یک آرایه دواندیسی نمایش دهید در ابتدا تمام خانه ها را برابر ۰ قرار دهید .هر یک از هشت حرکت ممکن بر حسب هر دو جز افقی و عمودی آن ها توصیف می شوند. مثلا حرکتی از نوع صفر به صورتی که در شکل نشان داده شده شامل یک حرکت افقی به سمت راست به اندازه دو خانه ویک حرکت عمودی به بالا به اندازه یک خانه است این حرکت ها را می توان با ۲ آرایه ۸ تایی نشان داد که در شکل آمده اند.
move-of-knight
برای نمایش ردیف و ستون محل جاری اسب از متغییر های currentrow ,currentcolumn استفاده می کنیم .
شمارنده ای در نظر بگیرید که از ۱ تا ۶۴ تغییر می کند و در آن تعداد حرکاتی که اسب انجام داده ثبت کنید.
اگر توجه کرده باشید خانه هایی که در گوشه هستند دردسر ساز ترند برای همین خانه ها را در جه بندی می کنیم و برای گوشه ها اهمیت بیشتری قایل می شویم . این درجه بندی را در شکل می بینید .
امتیاز خانه های شطرنج
ابتدا سعی کنید خانه هایی که شماره کوچک تری دارند پر کنید (اهمیت بیشتری دارد)زیرا احتمال موفقیت بالا می رود .
در برنامه نوشته شده تابع reset_array ارزش های از پیش تعیین شده را درون آرایه می ریزد .
تابع show آرایه دوبعدی را نمایش می دهد.
تابع check_around خانه های اطراف خانه ای را که در آن هستیم چک می کند و خانه ای را که اهمیت بیشتری دارد انتخاب می کند و اگر از خانه هایی که ارزش یکسان دارند چند تا داشتیم به طور رندم انتخاب می کند و شماره عملی را که برای رفتن به آن خانه لازم است برمی گرداند.
تابع fill_board با استفاده از تابع reset_array نقطه ای که اسب درش است را به نقطه ای که reset_array گفته می برد.
در تابع main() تابع fill_board چند بار فراخوانی می شود تا به جواب مطلوب یعنی پر کردن تمام خانه های جدول برسیم.
این هم از کد برنامه knight tour مستقیم سراغ کد نیایید خودتان فکر کنید.
نمایی از اجرای برنامه
کد مسئله گردش اسب به زبان سی پلاس پلاس
این هم کد برنامه:
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 | #include <stdio.h> #include <stdlib.h> #include <time.h> #include <conio.h> //fill array by number that point to cost of squar void reset_array(int a[8][8]) { a[0][0]=a[0][7]=a[7][0]=a[7][7]=2; a[1][0]=a[0][1]=a[0][6]=a[1][7]=a[6][7]=a[7][6]=a[7][1]=a[6][0]=3; a[2][0]=a[3][0]=a[4][0]=a[5][0]=a[6][1]=a[7][2]=a[7][3]=a[7][4]= a[7][5]=a[6][6]=a[5][7]=a[4][7]=a[3][7]=a[2][7]=a[1][6]=a[0][5]= a[0][5]=a[0][4]=a[0][3]=a[0][2]=a[1][1]=4; a[1][2]=a[1][3]=a[1][4]=a[1][5]=a[2][1]=a[2][6]=a[3][1]=a[3][6]= a[4][1]=a[4][6]=a[5][1]=a[5][6]=a[6][2]=a[6][3]=a[6][4]=a[6][5]=6; a[2][2]=a[2][3]=a[2][4]=a[2][5]=a[3][2]=a[3][3]=a[3][4]=a[3][5]= a[4][2]=a[4][3]=a[4][4]=a[4][5]=a[5][2]=a[5][3]=a[5][4]=a[5][5]=8; } //---------------------------------------------------- //show 2D array void show(int a[8][8]) { int i,j; for(i=0;i<8;i++) { for(j=0;j<8;j++) { printf("%d\t ",a[i][j]); } printf("\n\n"); } } //----------------------------------------------------------- //check around for best squar int check_around(int a[8][8],int currentrow,int currentcolumn) { int j=0; int randbox[8]; int horizontal[8]; int vertical[8]; horizontal[0]=2; horizontal[1]=1; horizontal[2]=-1; horizontal[3]=-2; horizontal[4]=-2; horizontal[5]=-1; horizontal[6]=1; horizontal[7]=2; vertical[0]=-1; vertical[1]=-2; vertical[2]=-2; vertical[3]=-1; vertical[4]=1; vertical[5]=2; vertical[6]=2; vertical[7]=1; int i; int action[8]; for(i=0;i<8;i++) { if(currentrow+vertical[i]>=0 && currentrow+vertical[i]<=7 && currentcolumn+horizontal[i]>=0 && currentcolumn+horizontal[i]<=7 && a[currentrow+vertical[i]][currentcolumn+horizontal[i]]!=0) { action[i]=a[currentrow+vertical[i]][currentcolumn+horizontal[i]]; } else { action[i]=9; } } int min=10; int counter=0; for(i=0;i<8;i++) { if(min>=action[i]) { min=action[i]; } } if(min==9) { return -1; } j=0; for(i=0;i<8;i++) { if(min==action[i]) { randbox[j]=i; j++; counter++; } } int rnd=rand()%counter; return (randbox[rnd]); } //------------------------------------ //in this function after find best action //by check_around action do move and fill currect squar by 0 int fill_board(int a[8][8],int b[64],int c[64],int currentrow,int currentcolumn) { int p=1; int k; a[currentrow][currentcolumn]=0; b[0]=currentrow; c[0]=currentcolumn; int horizontal[8]; int vertical[8]; horizontal[0]=2; horizontal[1]=1; horizontal[2]=-1; horizontal[3]=-2; horizontal[4]=-2; horizontal[5]=-1; horizontal[6]=1; horizontal[7]=2; vertical[0]=-1; vertical[1]=-2; vertical[2]=-2; vertical[3]=-1; vertical[4]=1; vertical[5]=2; vertical[6]=2; vertical[7]=1; int u=1; for(k=0;k<64;k++) { if(k==63) { return 0; } int i=check_around(a,currentrow,currentcolumn); if(i!=-1) { currentcolumn+=horizontal[i]; currentrow+=vertical[i]; a[currentrow][currentcolumn]=0; b[p]=currentrow; c[p]=currentcolumn; p++; } else { return 1; } } return 0; } //-----------------open-mind.ir---------------- //-----------------farhad-dalirani------------- //main function .ask row and column for start int main() { system("cls"); int i,h; int a[8][8]; int b[64]={0}; int c[64]={0}; srand(time(NULL)); reset_array(a); int currentrow,currentcolumn; printf("<Enter sqare that you want start>\n "); printf("0<=Number<=7\n"); printf("Enter currentrow:"); scanf("%d",¤trow); printf("Enter currentcolumn:"); scanf("%d",¤tcolumn); printf("\n\n"); do { reset_array(a); h=fill_board(a,b,c,currentrow,currentcolumn); } while(h==1); for(i=0;i<=63;i++) { a[b[i]][c[i]]=i; } show(a); return 0; } |
مرسی فراوون ، داشتم دستی مساله رو حل میکردم و همش فک میکردم که بهتره اول خونه های وسط پر شه همش ، خیلی گیر کرده بودم . تشکر فراوون
سلام
خیلی توضیحات الگوریتم حرکت اسب خیلی واضح و قشنگ بود ممنون.
اگه میشه فقط با یک فانکشن بنویسید که اینقد تعداد خط برنامه نره بالا.
ما برنامه نویسا به تنبلی شهرت داریم :)))
ممنون از کدی که گذاشتید، کلی گشتم تا تونستم این سایت رو پیدا کنم، رو سئو بیشتر کار کنید؛ تو صفحه دوم،سوم گوگل پیداتون کردم.
بازهم ممنون از سایتتون.
تشکر از نظرتان، حتما بهترش می کنیم.
آقا دمت گرم خیلی سایت خفنی زدید . کدشو با C# بنویسید خوب می شه