הבלוג של גרי רשף

20/06/2010

בעיית הפּרש (שחמט)

Filed under: Uncategorized — תגיות: , , , — גרי רשף @ 08:55

אבי אבי רכב ישראל ופרשיו: לפרש עצמו אין בעייה, אלא לנו- כיצד ניתן לעבור עם הפרש על כל משבצות לוח השחמט ב-63 מהלכים חוקיים.
בעייה זו בדומה לבעיית שמונה המלכות (לאיציק בן-גן יש פתרון פשוט ויעיל)– מהווה אתגר תכנותי מעניין מתחום השחמט.
ניצור טבלת לוח שחמט בת 64 משבצות, ונציין ליד כל אחת את העמודה והשורה שלה:

With Luah As

(Select    1 Mishbezet,

        '01' MishbezetS,

        1/8+1 Shura,

        1%8 Amuda

Union All

Select    Mishbezet+1 Mishbezet,

        Right('0'+Cast(Mishbezet+1 As Varchar(2)),2) Mishbezet,

        Mishbezet/8+1 Shura,

        Mishbezet%8+1 Amuda

From    Luah

Where    Mishbezet<64)

Select    *

Into    T_Luah

From    Luah;

ולשליפה עצמה: בכל צעד הפרש נע שני צעדים בכיוון אחד, ועוד צעד בכיוון המאונך לראשון; ומכאן שמכפלת השינוי בעמודות בשינוי בשורות צריך להיות שווה ל-2 (בערך מוחלט),

ויש לבחור במשבצת שטרם היינו בה (המסלול נאגר ב-Maslul ובכל צעד נעשית בדיקה האם המשבצת כבר נמצאת בו).

לשלוף את כל הפתרונות האפשריים- יקח כנראה כמה דורות, ולכן נסתפק בפתרון אחד (ולכן- Top 1):

With T1 As

(Select    1 Zaad,

        Cast(','+MishbezetS+',' As Varchar(193)) Maslul,

        Shura,

        Amuda

From    T_Luah

Union All

Select    T.Zaad+1 Zaad,

        Cast(T.Maslul+L.MishbezetS+',' As Varchar(193)) Maslul,

        L.Shura,

        L.Amuda

From    T1 T

Inner Join T_Luah L

        On (T.Shura-L.Shura)*(T.Amuda-L.Amuda) In (-2,2)

        And T.Maslul Not Like '%,'+L.MishbezetS+',%'

Where    T.Zaad<64)

Select    Top 1 *

From    T1

Where    Zaad=64;

לתוכנית לקח כארבעים וחמש דקות לרוץ, ויש פתרון לדוגמה:

,64,54,60,50,44,61,55,45,62,56,46,63,53,59,49,43,58,52,42,57,51,41,35,29,39,24,30,47,37,31,48,38,

32,15,21,36,26,09,03,20,05,11,01,18,33,27,17,34,28,13,07,22,16,06,12,02,19,25,10,04,14,08,23,40,

image

מודעות פרסומת

להגיב »

עדיין אין תגובות.

RSS feed for comments on this post. TrackBack URI

כתיבת תגובה

הזינו את פרטיכם בטופס, או לחצו על אחד מהאייקונים כדי להשתמש בחשבון קיים:

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s

יצירה של אתר חינמי או בלוג ב־WordPress.com.

%d בלוגרים אהבו את זה: