حرکات اسب در صفحه ی شطرنج

[paradise_human]

سلام ...
من میخوام این برنامه مختصات مکان اسب رو ازم بگیره و بعد تمام حرکات اسب رو توی صفخه ی شطرنج برام بنویسه .....
من این برنامه رو نوشتم ولی ارور میده ...
میتونید برام مشکلش رو حل کنید ؟

#include <stdio.h>
int horse_move(int,int);
int chess [8][8];
int main()
{
int i,j;
scanf("%d",&i);
scanf("%d",&j);
printf("%d",horse_move(i,j));

}
int horse_move(int i,int j)
{

if(i<8&&j<8&&i>=0&&j>=0)
{
horse_move(i-2,j+1);
horse_move(i-2,j-1);
horse_move(i-1,j-2);
horse_move(i+1,j-2);
horse_move(i+1,j-1);
horse_move(i+2,j+1);
horse_move(i-1,j+2);
horse_move(i+1,j+2);
}
return 0;
}

[clover]

دوست عزیز
تابع horse_move هیچ عملی انجام نمیده و فقط خودش را تا جایی که شرط برقرار باشه فراخوانی می کنه. این شرط هم بالاخره در یکی از هشت فراخوانی صحیح هست . بنابر این تابع به صورت بی پایان فراخوانی شده و Stack overflow اتفاق می افته.

فکر میکنم برنامه مورد نظر شما به این شکل باید تغییر کند:

#include <stdio.h>

int horse_move(int,int);
int chess [8][8];
int main()
{
int i,j;

scanf("%d",&i);
scanf("%d",&j);

horse_move(i-2,j+1);
horse_move(i-2,j-1);
horse_move(i-1,j-2);
horse_move(i+1,j-2);
horse_move(i+1,j-1);
horse_move(i+2,j+1);
horse_move(i-1,j+2);
horse_move(i+1,j+2);

return 0;
}

int horse_move(int i,int j)
{
if(i<8&&j<8&&i>=0&&j>=0)
{
printf("(%d, %d)", i, j);
}
return 0;
}

[paradise_human]

دوست عزیز
تابع horse_move هیچ عملی انجام نمیده و فقط خودش را تا جایی که شرط برقرار باشه فراخوانی می کنه. این شرط هم بالاخره در یکی از هشت فراخوانی صحیح هست . بنابر این تابع به صورت بی پایان فراخوانی شده و Stack overflow اتفاق می افته.

فکر میکنم برنامه مورد نظر شما به این شکل باید تغییر کند:

#include <stdio.h>

int horse_move(int,int);
int chess [8][8];
int main()
{
int i,j;

scanf("%d",&i);
scanf("%d",&j);

horse_move(i-2,j+1);
horse_move(i-2,j-1);
horse_move(i-1,j-2);
horse_move(i+1,j-2);
horse_move(i+1,j-1);
horse_move(i+2,j+1);
horse_move(i-1,j+2);
horse_move(i+1,j+2);

return 0;
}

int horse_move(int i,int j)
{
if(i<8&&j<8&&i>=0&&j>=0)
{
printf("(%d, %d)", i, j);
}
return 0;
}
ولی این فقط 8 حالت اول رو مینویسه ....
من میخوام از طریق تابع بازگشتی و فراخوانی خودش یه حلقه ایجاد کنم که خونه هایی رو که اسب میتونه توشون بره رو برام بنویسه ....
احتمالا مشکل اون برنامه ی من اینه که توی یه حلقه ی بینهایت میافته ...
چطور میشه یه کاریش کرد که توی اون حلقه ی بینهایت نیفته و یا به قول معروف اگه توی یه خونه رفت و اگه بعدا از دوباره خواست توی اون خونه ی تکراری بره جلوشو گرفت که از دوباره حلقه تکرار نشه و برنامه قاطی نکنه ؟؟

[M4st3r_4w4r3]

احتمالا مشکل اون برنامه ی من اینه که توی یه حلقه ی بینهایت میافته ...
چطور میشه یه کاریش کرد که توی اون حلقه ی بینهایت نیفته و یا به قول معروف اگه توی یه خونه رفت و اگه بعدا از دوباره خواست توی اون خونه ی تکراری بره جلوشو گرفت که از دوباره حلقه تکرار نشه و برنامه قاطی نکنه ؟؟
حلقه که نمی شه اسمشو گذاشت !
به قول دوستمون استک خورد میشه !
حالا میتونی یه متغیر از نوع اشاره گر تعریف کنی که بعد از اینکه 8 تا خانه ی کنار مهره رو پیدا کرد با عدد 8 مقایسه بشه ...
اگه کمتر از 8 بود دوباره به تابع فرستاده بشه تا همه ی خونه ها بدست بیاد ...

[qwerty11]

ولی این فقط 8 حالت اول رو مینویسه ....
من میخوام از طریق تابع بازگشتی و فراخوانی خودش یه حلقه ایجاد کنم که خونه هایی رو که اسب میتونه توشون بره رو برام بنویسه ....
احتمالا مشکل اون برنامه ی من اینه که توی یه حلقه ی بینهایت میافته ...
چطور میشه یه کاریش کرد که توی اون حلقه ی بینهایت نیفته و یا به قول معروف اگه توی یه خونه رفت و اگه بعدا از دوباره خواست توی اون خونه ی تکراری بره جلوشو گرفت که از دوباره حلقه تکرار نشه و برنامه قاطی نکنه ؟؟
سلام،

این چیزی که شما میخواین مربوط میشه به مباحث طراحی الگوریتم و قسمت backtrack !!

اما به هر حال : برای هر خونه ی شطرنجی یه متغیر visit در نظر بگیر و هر وقت وارد اون خونه شدی visit اون خونه رو true کن . (منظور از true و false تو C همان 0و1 هست). اونوقت هر وقت که خواستی اون تابع حرکت رو صدا بزنی قبلش چک کن که ویزیت اون خونه ای که میخوای توش بری true نباشه.
اما اگه این کاریم که من گفتم کردی خیلی انتظار نداشته باش که برنامت جواب قابل انتظاری بده جون به نظر من سوال کلاً غلطه !! و اصلا معنای خاصی نداره ...

ویرایش: یه چی دیگه یادم اومد، اگه اسب رو تو یکی از خونه های صفحه ی 8*8 بزاریم حتما راهی وجود داره که از تمام خونه ها یه بار بگذره و به هیچ خونه ای هم 2 بار وارد نشه. پس اگه سوالتون واقعاً اینه که تمام خونه های reachable رو چاپ کنین میتونین تمام خونه ها رو چاپ کنین :D

ویرایش 2 : اگه اسبی رو تو خونه ی Aو1 یه صفحه شطرنج بزاریم اونوقت مسیر زیر همه ی خونه هارو طی میکنه و از هیچ خونه ای هم 2 بار رد نمیشه :
A1B3A5B7C5A4B2C4A3B1C3A2B4A6B8C6A7B5C7A8B6C8D6E4D2 F1E3C2D4E2C1D3E1G2F4D5E7G8H6F5H4G6H8F7D8E6F8D7E5G4 H2F3G1H3G5H7F6E8G7H5G3H1F2D1

[clover]

دوست عزیز
این مسئله ای که شما دنبال راه حلش هستید (حرکت اسب در تمام خانه های صفحه ی شطرنج بدون تکرار )به نام Knight's Tour معروف هست. با کد شما به هیچ عنوان نمیشه به جواب رسید ، در واقع شما اول باید در مورد مسئله و راه حل اون خوب مطالعه کنید و بعد شروع به کد نویسی کنید. در ضمن روش بازگشتی این مسئله بسیار نا کارامد هست اما اگر اصرار به حل به روش بازگشتی دارید این عبارت را جستجو کنید : Knight's Tour Recursive Solution (http://www.google.com/search?q=Knight%27s+Tour+Recursive+Solution)

موفق باشید

[moharramiasl]

برنامه ات خیلی ناقصه
شما باید یک آرایه 8*8 تعریف کنید.ابتدا از یک خانه شروع کنید به حرکت کردن،و تعداد حرکت ها را هم داخل یک آرایه قرار بدید،

[moharramiasl]

s1={2,1,-1,-2,-2,-1,1,2}
s2={-1,-2,-2,-1,1,2,2,1}
این تعداد حرکت هایی است که اسب در هر بار حرکت می توتند داشته باشد.
من این برنامه را به صورت بازگشتی نوشتم و 5 دقیقه طول میکشه که به جواب برسد.

[paradise_human]

از همتون ممنونم به خاطر راهنماییهاتون ...
استادمون یه سوال داده گفته ترتیب حرکاتی را بنویسید که اسب مستقر در iوj سرباز مستقر در خانه ی wوx را بزنید ...
من منظور سوالشو نفهمیدم سوال دقیقا از من چی میخواد میتونید راهنماییم کنید ؟
آیا این سوال خروجی داره یا نه ؟

[paradise_human]

از همتون ممنونم به خاطر راهنماییهاتون ...
استادمون یه سوال داده گفته ترتیب حرکاتی را بنویسید که اسب مستقر در iوj سرباز مستقر در خانه ی wوx را بزنید ...
من منظور سوالشو نفهمیدم سوال دقیقا از من چی میخواد میتونید راهنماییم کنید ؟
آیا این سوال خروجی داره یا نه ؟
من از استاد پرسیدم گفت منظورم مسیر حرکت اسبه تا رسیدن به سرباز یعنی مسیر حرکت اسب رو میخواد .
من هرطوری این برنامه رو مینویسم over flow میشه .....
کسی نمیتونه کمکی بکنه ؟؟؟

[qwerty11]

من از استاد پرسیدم گفت منظورم مسیر حرکت اسبه تا رسیدن به سرباز یعنی مسیر حرکت اسب رو میخواد .
من هرطوری این برنامه رو مینویسم over flow میشه .....
کسی نمیتونه کمکی بکنه ؟؟؟
اولاً که کدتون رو بزارین.
بعدشم اینکه مطمئنم این سوال یه جواب ریاضی داره (این سوالو قبلاً یه جایی دیدم).
سوماً اگه میشه بگین سوال درس پیشرفته هست یا نه !؟
چهارماً صف میدونین چیه یا نه !؟

[paradise_human]

اولاً که کدتون رو بزارین.
بعدشم اینکه مطمئنم این سوال یه جواب ریاضی داره (این سوالو قبلاً یه جایی دیدم).
سوماً اگه میشه بگین سوال درس پیشرفته هست یا نه !؟
چهارماً صف میدونین چیه یا نه !؟

#include <stdio.h>
void horse_move (int,int);
static int i,j,w,x;
void main()
{
scanf("%d%d%d%d",&i,&j,&w,&x);
horse_move(i,j);

}
void horse_move(int i,int j)
{
if(i<8&&j<8&&i>=0&&j>=0)
{

while(i!=w&&j!=0)
{
horse_move(i-2,j+1);
horse_move(i-2,j-1);
horse_move(i-1,j-2);
horse_move(i+1,j-2);
horse_move(i+2,j-1);
horse_move(i+2,j+1);
horse_move(i-1,j+2);
horse_move(i+1,j+2);
}

printf("%d,%d\n",i,j);
}


}
اینم برنامه ...
والا استادمون گفته از تابع بازگشتی استفاده کنید ....
منظورتونو از پیشرفته نفهیمدم ...
یعنی خود سوال پیشرفته است یا برای درس برنامه سازی پیشرفته است ؟

[paradise_human]

منتظر کمکتون هستم .....

[qwerty11]

محدوده ی صفحه کوچیکه یا بزرگ !؟

جواب بهینه میخوای یا نه؟

واسه اینکه از تو لوپ بینهایت نیفته واسه هر خونه یه مقدار bool به نام visit در نظر بگیر و هر بار که وارد خونه ای شدی visit اون خونه رو true کن. در ابتدای تابع horse_move هم چک کن که اگه خونه ای که توش هستیم visit اش true هست بیاد بیرون.

[paradise_human]

محدوده ی صفحه کوچیکه یا بزرگ !؟

جواب بهینه میخوای یا نه؟

واسه اینکه از تو لوپ بینهایت نیفته واسه هر خونه یه مقدار bool به نام visit در نظر بگیر و هر بار که وارد خونه ای شدی visit اون خونه رو true کن. در ابتدای تابع horse_move هم چک کن که اگه خونه ای که توش هستیم visit اش true هست بیاد بیرون.
محدودش همون 8 در 8 باشه دیگه ....
اگه بهینه هم باشه چه بهتر ولی اگه با تابع بازگشتی باشه بهتره .....
و در ضمن میتونید بیشتر راجع به اون مطالب توضیح بدین .....
مقدار bool جریانش چیه ؟

[paradise_human]

محدوده ی صفحه کوچیکه یا بزرگ !؟

جواب بهینه میخوای یا نه؟

واسه اینکه از تو لوپ بینهایت نیفته واسه هر خونه یه مقدار bool به نام visit در نظر بگیر و هر بار که وارد خونه ای شدی visit اون خونه رو true کن. در ابتدای تابع horse_move هم چک کن که اگه خونه ای که توش هستیم visit اش true هست بیاد بیرون.
آقا می تونید یه کمی منو راهنمایی کنید که جریان اون چیزایی که گفتید چیه ؟

[qwerty11]

امیدوارم این کمکت کنه ...


#include<stdio.h>
#include<conio.h>
int check[9][9];
int x_des,y_des;
int horse_move(int x,int y){
if(x<1 || x>8 || y<1 || y>8 || check[x][y]) return 0;
check[x][y]=1;
if(x==x_des && y==y_des){printf("%d %d\n",x,y); return 1;}
if(horse_move(x+1,y+2)){printf("%d %d\n",x,y); return 1;}
if(horse_move(x+1,y-2)){printf("%d %d\n",x,y); return 1;}
if(horse_move(x-1,y+2)){printf("%d %d\n",x,y); return 1;}
if(horse_move(x-1,y-2)){printf("%d %d\n",x,y); return 1;}
if(horse_move(x+2,y+1)){printf("%d %d\n",x,y); return 1;}
if(horse_move(x+2,y-1)){printf("%d %d\n",x,y); return 1;}
if(horse_move(x-2,y+1)){printf("%d %d\n",x,y); return 1;}
if(horse_move(x-2,y-1)){printf("%d %d\n",x,y); return 1;}
return 0;
}
int main(){
clrscr();
int x_start,y_start;
scanf("%d%d%d%d" ,&x_start ,&y_start ,&x_des ,&y_des);
for(int i=1;i<9;i++)
for(int j=1;j<9;j++)
check[i][j]=0;
horse_move(x_start,y_start);
getch();
return 0;
}

[qanewaisi]

سلام
منظورتون از حرکت اسب تو صفحه شطرنجه؟

[paradise_human]

سلام
منظورتون از حرکت اسب تو صفحه شطرنجه؟

آره .....
ولی سوال اصلیم این بود ....
مسیر حرکت اسبی مستقر در i,j رو از خروجی بگیرید که سرباز مستقر در w,x رو بزند ....