- This topic has 14 תגובות, 4 משתתפים, and was last updated לפני 16 שנים, 11 חודשים by
.
-
תגובות
-
למי שפספס את הקטע על קודגורו ששודר בתוכנית ג'יגהבית היום, רצ"ב ניסוח מדויק של השאלה:
מהו המספר המזערי של פרשים הנחוץ על מנת לאיים על כל 64 המשבצות של לוח שחמט?
פרש נחשב כמאיים על שמונה משבצות המרוחקות מהלך פרש ממנו, וכמובן על המשבצת עליה הוא נמצא.
מהלך פרש – מהמשבצת בקורדינטות
X,Y
אל המשבצת בקורדינטות
X+a, Y+b
כאשר אחד מבין
a,b
הוא פלוס או מינוס אחד והשני הוא פלוס או מינוס שתים.
אני גם אלך על ניחוש פרוע שזה שמונה.
אפשר לכתוב אלגוריתם ברקורסיית Backtracking כדי למצוא פתרונות לחידה אבל אין לי זמן כרגע.
מתנצל, פתרון שרשמתי אינו נכון.
אני באמצע בניית תוכנה שתחשב, מחר אפרסם פתרון מלומד, נא לא להתייחס לתשובה קודמת!
יואב
התשובה היא 18 .
האם זה נכון?
להלן תוכנית המחשב שמחשבת את המבוקש:
import java.util.*;
public class chess
{
static Scanner yoav=new Scanner(System.in);
static boolean peula(char[][]matrix)
{
int mone=0;
for(int i=0;i<=matrix.length-1;i++)
{
for(int j=0;j<=matrix.length-1;j++)
{
if(matrix[j]!=' ')
{
mone++;
}
}
}
if(mone==Math.pow(matrix.length,2))
{
return true;
}
else
{
return false;
}
}
public static void main(String[]args)
{
int mone=9,currentmone=0;
int x=0;
char[][]matrix=new char[8][8];
for(int i=0;i<=7;i++)
{
for(int j=0;j<=7;j++)
{
matrix[j]=' ';
}
}
while(peula(matrix)==false)
{
for(int i=0;i<=7;i++)
{
for(int j=0;j<=7;j++)
{
if(matrix[j]!='a')
{
if(matrix[j]==' ')
{
currentmone++;
}
if(j-1>=0 && i-2>=0 )
{
if(matrix[i-2][j-1]==' ')
{
currentmone++;
}
}
if(j+1<=7 && i-2>=0)
{
if(matrix[i-2][j+1]==' ')
{
currentmone++;
}
}
if(i+2<=7 && j-1>=0)
{
if(matrix[i+2][j-1]==' ')
{
currentmone++;
}
}
if(i+2<=7 && j+1<=7)
{
if(matrix[i+2][j+1]==' ')
{
currentmone++;
}
}
if(j+2<=7 && i-1>=0)
{
if(matrix[i-1][j+2]==' ')
{
currentmone++;
}
}
if(j-2>=0 && i-1>=0)
{
if(matrix[i-1][j-2]==' ')
{
currentmone++;
}
}
if(j+2<=7 && i+1<=7)
{
if(matrix[i+1][j+2]==' ')
{
currentmone++;
}
}
if(j-2>=0 && i+1<=7)
{
if(matrix[i+1][j-2]==' ')
{
currentmone++;
}
}
}
if(currentmone==mone)
{
matrix[j]='a';
if(i+1<=7 && j-2>=0)
matrix[i+1][j-2]='*';
if(i+1<=0 && j+2<=7)
matrix[i+1][j+2]='*';
if(i-1>=0 && j-2>=0)
matrix[i-1][j-2]='*';
if(i-1>=0 && j+2<=7)
matrix[i-1][j+2]='*';
if(i+2<=7 && j+1<=7)
matrix[i+2][j+1]='*';
if(i+2<=7 && j-1>=0)
matrix[i+2][j-1]='*';
if(i-2>=0 && j+1<=7)
matrix[i-2][j+1]='*';
x++;
}
currentmone=0;
}
}
mone–;
}
System.out.println(x);
}
}תוכנית נחמדה, אבל היא עובדת באופן חמדני – שמה פרש במשבצת פנויה – אפשר לעשות זאת טוב יותר: פחות מ18 פרשים יכולים לכסות את כל הלוח.
אממ החסם המינימלי הטריוויאלי הוא 9, אבל אני לא מצאתי משהו בסביבה…מצאתי פתרון יפה (ויזואלית) עם 16:
oooooooo
oooooooo
oxxooxxo
ooxxxxoo
ooxxxxoo
oxxooxxo
oooooooo
oooooooo
מצאתי עם 9
oooooooo
ooxooooo
ooxxoxxo
oooooxoo
ooxooooo
oxxoxxoo
oooooxoo
oooooooo
לא ייתכן פיתרון טוב יותר, מכיוון שכדי לתקוף את הפינות ארבע פרשים צריכים להיות במרחק שורה בדיוק מהקצה, ולכן הם מאבדים 2 משבצות שבהם יכלו לתקוף
כלומר 8 משבצות סה"F
אז דרוש עוד פרש
כלומר סה"F 9 פרשים
חידה יפה מאוד, גם הפיתרון הזה סיטרי ויפה (כמצופה) כשמציירים את זה נורמלית
עוד ארבע פרשים בריבוע ה2 על 2 שבמרכז הלוח פותרים את הבעיה בפיתרון הקודם….
סה"כ 13…אבל זה יותר מדי, לדעתי. אני בטוח שיש פיתרון ב9
- יש להתחבר למערכת על מנת להגיב.