أقصر مسار نايت على لوح الشطرنج
https://stackoverflow.com/questions/2339101
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
لقد كنت أتدرب على مسابقة البرمجة القادمة وقد تعثرت في سؤال أشعر بالحيرة تمامًا. ومع ذلك ، أشعر كما لو أنه مفهوم يجب أن أتعلمه الآن بدلاً من عبور أصابعي أنه لا يظهر أبدًا.
في الأساس ، فإنه يتعامل مع قطعة فارس على لوحة الشطرنج. يتم إعطاؤك اثنين من المدخلات: موقع البدء وموقع النهاية. الهدف من ذلك هو حساب وطباعة أقصر المسار الذي يمكن أن يتخذه الفارس للوصول إلى الموقع المستهدف.
لم أتعامل مع أقصر الأشياء ، ولا أعرف حتى من أين أبدأ. ما هو المنطق الذي أستخدمه في معالجة هذا؟
ملاحظة: إذا كانت ذات صلة ، فإنهم يريدون منك أن تكمل تحركات الفارس العادية من خلال السماح لها أيضًا بالانتقال إلى الزوايا الأربعة للمربع التي تشكلها (محتمل) ثمانية تحركات يمكن أن يقوم بها الفارس ، بالنظر إلى أن مركز المربع موقع الفارس.
المحلول
لديك رسم بياني هنا ، حيث يتم توصيل جميع التحركات المتاحة (القيمة = 1) ، ويتم فصل التحركات غير المتوفرة (القيمة = 0) ، ستكون المصفوفة المتفرقة مثل:
(a1,b3)=1,
(a1,c2)=1,
.....
ويمكن العثور على أقصر مسار لنقطتين في الرسم البياني باستخدام http://en.wikipedia.org/wiki/Dijkstra's_algorithm
الكود الزائف من ويكيبيديا صفحة:
function Dijkstra(Graph, source):
for each vertex v in Graph: // Initializations
dist[v] := infinity // Unknown distance function from source to v
previous[v] := undefined // Previous node in optimal path from source
dist[source] := 0 // Distance from source to source
Q := the set of all nodes in Graph
// All nodes in the graph are unoptimized - thus are in Q
while Q is not empty: // The main loop
u := vertex in Q with smallest dist[]
if dist[u] = infinity:
break // all remaining vertices are inaccessible from source
remove u from Q
for each neighbor v of u: // where v has not yet been removed from Q.
alt := dist[u] + dist_between(u, v)
if alt < dist[v]: // Relax (u,v,a)
dist[v] := alt
previous[v] := u
return dist[]
تعديل:
- كما المعتوه ، قال باستخدامhttp://en.wikipedia.org/wiki/a*_algorithmيمكن أن يكون أسرع.
- الأسرع طريقة ، هي التخلص من جميع المسافات وإنقاذه إلى مصفوفة كاملة 8 × 8. حسنًا ، أود أن أسمي هذا الغش ، وأعمل فقط لأن المشكلة صغيرة. ولكن في بعض الأحيان ستتحقق المسابقات من سرعة تشغيل البرنامج.
- النقطة الرئيسية هي أنه إذا كنت تستعد لمسابقة البرمجة ، فيجب أن تعرف خوارزميات مشتركة بما في ذلك Dijkstra's. نقطة انطلاق جيدة هي القراءة
Introduction to AlgorithmsISBN 0-262-03384-4. أو يمكنك تجربة ويكيبيديا ، http://en.wikipedia.org/wiki/list_of_algorithms
نصائح أخرى
تعديل: انظر إجابة سيمون, ، حيث أصلح الصيغة المقدمة هنا.
في الواقع هناك صيغة O (1)
هذه صورة صنعتها لتصورها (يمكن للمربعات الوصول إلى الفارس على nذ يتم رسم الحركة بنفس اللون).
هل يمكنك ملاحظة النمط هنا؟
على الرغم من أننا نستطيع رؤية النمط ، من الصعب حقًا العثور على الوظيفة f( x , y ) هذا يعيد عدد التحركات المطلوبة للذهاب من المربع ( 0 , 0 ) للتربيع ( x , y )
ولكن هنا هي الصيغة التي تعمل عندما 0 <= y <= x
int f( int x , int y )
{
int delta = x - y;
if( y > delta )
return 2 * ( ( y - delta ) / 3 ) + delta;
else
return delta - 2 * ( ( delta - y ) / 4 );
}
ملاحظة: تم طرح هذا السؤال على ساكو 2007 اليوم 1
والحلول هنا
إليك حل O (1) الصحيح ، ولكن بالنسبة للحالة التي يتحرك فيها الفارس مثل فارس الشطرنج فقط ، وعلى لوحة الشطرنج اللانهائية:
https://jsfiddle.net/graemian/5qgvr1ba/11/
مفتاح العثور على هذا هو ملاحظة الأنماط التي تظهر عند رسم اللوحة. في الرسم البياني أدناه ، يكون الرقم الموجود في المربع هو الحد الأدنى لعدد التحركات اللازمة للوصول إلى هذا المربع (يمكنك استخدام البحث الأول للعثور على هذا):
نظرًا لأن المحلول متماثل عبر المحاور والأقطار ، فقد رسمت فقط حالة x> = 0 و y> = x.
كتلة اليسار السفلية هي موضع البداية والأرقام الموجودة في الكتل تمثل الحد الأدنى لعدد التحركات للوصول إلى تلك الكتل.
هناك 3 أنماط يجب ملاحظة:
- زيادة المجموعات الرأسية الأزرق من 4
- الأقطار الحمراء "الأساسية" (وهي تعمل من أعلى اليسار إلى أسفل اليمين ، مثل الانزلاق الخلفي)
- الأقطار الخضراء "الثانوية" (نفس الاتجاه مثل الأحمر)
(تأكد من رؤية كلتا المجموعتين من الأقطار كأعلى اليسار إلى أسفل اليمين. لديهم خطوة مستمرة. الأقطار اليمنى من أعلى اليسار السفلي أكثر تعقيدًا.)
يمكنك اشتقاق الصيغ لكل. الكتل الصفراء هي حالات خاصة. لذلك يصبح الحل:
function getMoveCountO1(x, y) {
var newXY = simplifyBySymmetry(x, y);
x = newXY.x;
y = newXY.y;
var specialMoveCount = getSpecialCaseMoveCount(x ,y);
if (specialMoveCount !== undefined)
return specialMoveCount;
else if (isVerticalCase(x, y))
return getVerticalCaseMoveCount(x ,y);
else if (isPrimaryDiagonalCase(x, y))
return getPrimaryDiagonalCaseMoveCount(x ,y);
else if (isSecondaryDiagonalCase(x, y))
return getSecondaryDiagonalCaseMoveCount(x ,y);
}
مع أصعب كونها المجموعات الرأسية:
function isVerticalCase(x, y) {
return y >= 2 * x;
}
function getVerticalCaseMoveCount(x, y) {
var normalizedHeight = getNormalizedHeightForVerticalGroupCase(x, y);
var groupIndex = Math.floor( normalizedHeight / 4);
var groupStartMoveCount = groupIndex * 2 + x;
return groupStartMoveCount + getIndexInVerticalGroup(x, y);
}
function getIndexInVerticalGroup(x, y) {
return getNormalizedHeightForVerticalGroupCase(x, y) % 4;
}
function getYOffsetForVerticalGroupCase(x) {
return x * 2;
}
function getNormalizedHeightForVerticalGroupCase(x, y) {
return y - getYOffsetForVerticalGroupCase(x);
}
انظر كمان للحالات الأخرى.
ربما هناك أنماط أبسط أو أكثر أناقة فاتني؟ إذا كان الأمر كذلك ، أحب أن أراهم. على وجه الخصوص ، لاحظت بعض الأنماط القطرية في الحالات العمودية الزرقاء ، لكنني لم أستكشفها. بغض النظر ، لا يزال هذا الحل يرضي القيد O (1).
مشكلة مثيرة للاهتمام للغاية التي واجهتها مؤخرًا. بعد البحث عن بعض الحلول ، حاولت استعادة الصيغة التحليلية (O(1) time and space complexity) نظرا ل ساكو 2007 اليوم 1 حلول.
بادئ ذي بدء ، أريد أن أقدر غرايم بايل لتصور لطيف للغاية مما ساعدني على إصلاح الصيغة.
لسبب ما (ربما للتبسيط أو الجمال أو مجرد خطأ) انتقلوا minus تسجيل الدخول floor المشغل ، ونتيجة لذلك لديهم صيغة خاطئة floor(-a) != -floor(a) for any a.
هنا هي الصيغة التحليلية الصحيحة:
var delta = x-y;
if (y > delta) {
return delta - 2*Math.floor((delta-y)/3);
} else {
return delta - 2*Math.floor((delta-y)/4);
}
تعمل الصيغة لجميع أزواج (x ، y) (بعد تطبيق المحاور والتماثل القطري) باستثناء (1،0) و (2،2) حالات الزاوية ، والتي لا ترضي النمط والمتشددين في المقتطف التالي:
function distance(x,y){
// axes symmetry
x = Math.abs(x);
y = Math.abs(y);
// diagonal symmetry
if (x < y) {
t = x;x = y; y = t;
}
// 2 corner cases
if(x==1 && y == 0){
return 3;
}
if(x==2 && y == 2){
return 4;
}
// main formula
var delta = x-y;
if(y>delta){
return delta - 2*Math.floor((delta-y)/3);
}
else{
return delta - 2*Math.floor((delta-y)/4);
}
}
$body = $("body");
var html = "";
for (var y = 20; y >= 0; y--){
html += '<tr>';
for (var x = 0; x <= 20; x++){
html += '<td style="width:20px; border: 1px solid #cecece" id="'+x+'_'+y+'">'+distance(x,y)+'</td>';
}
html += '</tr>';
}
html = '<table>'+html+'</table>';
$body.append(html);<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>ملاحظة: jQuery المستخدمة في التوضيح فقط ، لمشاهدة الرمز distance وظيفة.
نعم ، ستحصل لك Dijkstra و BFS على الإجابة ، لكنني أعتقد أن سياق الشطرنج لهذه المشكلة يوفر المعرفة التي يمكن أن تسفر عن حل أسرع بكثير من خوارزمية عامة أقصر مسار ، وخاصة على لوحة شطرنج لا حصر لها.
من أجل البساطة ، دعنا نصف لوحة الشطرنج بأنها الطائرة (x ، y). الهدف هو العثور على أقصر مسار من (x0 ، y0) إلى (x1 ، y1) باستخدام خطوات المرشح فقط (+-1 ،+-2) ، (+-2 ،+-1) ، و (+-2 ، +-2) ، كما هو موضح في PS السؤال
فيما يلي الملاحظة الجديدة: ارسم مربعًا مع الزوايا (X-4 ، Y-4) ، (X-4 ، Y+4) ، (X+4 ، Y-4) ، (X+4 ، Y+4) . تحتوي هذه المجموعة (تسميها S4) على 32 نقطة. أقصر مسار من أي من هذه النقاط 32 إلى (x ، y) يتطلب بالضبط حركتان.
أقصر مسار من أي من الـ 24 نقطة في المجموعة S3 (المحددة بالمثل) إلى (x ، y) يتطلب حركتان على الأقل.
لذلك ، إذا | x1-x0 |> 4 أو | y1-y0 |> 4 ، فإن أقصر مسار من (x0 ، y0) 4 س. ويمكن حل المشكلة الأخيرة بسرعة مع التكرار المباشر.
دع n = max (| x1-x0 | ، | y1-y0 |). إذا n> = 4 ، فإن أقصر مسار من (x0 ، y0) إلى (x1 ، y1) السقف (N/2) خطوات.
الإجابة O (1) أعلاه [https://stackoverflow.com/a/8778592/4288232 بقلم مصطفى سيردار şanlı] لا يعمل حقًا. (تحقق (1،1) أو (3،2) أو (4،4) ، بصرف النظر عن حالات الحافة الواضحة (1،0) أو (2،2)).
فيما يلي حل أكثر قبيحًا (Python) ، والذي يعمل (مع "اختبارات" مضافة):
def solve(x,y):
x = abs(x)
y = abs(y)
if y > x:
temp=y
y=x
x=temp
if (x==2 and y==2):
return 4
if (x==1 and y==0):
return 3
if(y == 0 or float(y) / float(x) <= 0.5):
xClass = x % 4
if (xClass == 0):
initX = x/2
elif(xClass == 1):
initX = 1 + (x/2)
elif(xClass == 2):
initX = 1 + (x/2)
else:
initX = 1 + ((x+1)/2)
if (xClass > 1):
return initX - (y%2)
else:
return initX + (y%2)
else:
diagonal = x - ((x-y)/2)
if((x-y)%2 == 0):
if (diagonal % 3 == 0):
return (diagonal/3)*2
if (diagonal % 3 == 1):
return ((diagonal/3)*2)+2
else:
return ((diagonal/3)*2)+2
else:
return ((diagonal/3)*2)+1
def test():
real=[
[0,3,2,3,2,3,4,5,4,5,6,7,6,7],
[3,2,1,2,3,4,3,4,5,6,5,6,7,8],
[2,1,4,3,2,3,4,5,4,5,6,7,6,7],
[3,2,3,2,3,4,3,4,5,6,5,6,7,8],
[2,3,2,3,4,3,4,5,4,5,6,7,6,7],
[3,4,3,4,3,4,5,4,5,6,5,6,7,8],
[4,3,4,3,4,5,4,5,6,5,6,7,6,7],
[5,4,5,4,5,4,5,6,5,6,7,6,7,8],
[4,5,4,5,4,5,6,5,6,7,6,7,8,7],
[5,6,5,6,5,6,5,6,7,6,7,8,7,8],
[6,5,6,5,6,5,6,7,6,7,8,7,8,9],
[7,6,7,6,7,6,7,6,7,8,7,8,9,8]]
for x in range(12):
for y in range(12):
res = solve(x,y)
if res!= real[x][y]:
print (x, y), "failed, and returned", res, "rather than", real[x][y]
else:
print (x, y), "worked. Cool!"
test()
ما عليك القيام به هو التفكير في التحركات الممكنة للفارس كرسوم بيانية ، حيث يكون كل موقف على اللوحة عقدة والتحرك الممكنة إلى وضع آخر كحافة. ليست هناك حاجة لخوارزمية Dijkstra ، لأن كل حافة لها نفس الوزن أو المسافة (كلها سهلة أو قصيرة). يمكنك فقط إجراء بحث BFS من نقطة البداية حتى تصل إلى الموضع النهائي.
الحل من المبادئ الأولى في بيثون
واجهت هذه المشكلة لأول مرة في اختبار الترميز. لقد أعطوني 30 دقيقة لحلها - استغرق الأمر وقتًا أطول بكثير من ذلك للوصول إلى هذه النتيجة! كانت المشكلة هي: كم عدد التحركات التي يستغرقها الفارس للانتقال من 0،0 إلى x ، y باستخدام تحركات Knight Legal فقط. كان X و Y أكثر أو أقل من غير محدود (لذلك نحن لا نتحدث هنا عن لوحة شطرنج 8 × 8 بسيطة).
أرادوا حل O (1). كنت أرغب في حل حيث كان البرنامج يحل المشكلة بوضوح (أي أردت شيئًا أكثر وضوحًا من نمط Graeme - فإن الأنماط لديها عادة الانهيار حيث لا تبحث) ، وأردت حقًا ألا أضطر إلى الاعتماد على صيغة غير مصابة ، كما في حل مصطفى
لذلك ، هذا هو الحل الخاص بي ، لما يستحق. ابدأ ، كما فعل الآخرون ، من خلال الإشارة إلى أن الحل متماثل حول المحاور والقطر ، لذلك نحن بحاجة إلى حل فقط لـ 0> = y> = x. من أجل بساطة التفسير (والرمز) سأعكس المشكلة: يبدأ الفارس من x ، y ، ويهدف إلى 0،0.
لنفترض أننا نقلص المشكلة وصولاً إلى محيط الأصل. سنصل إلى ما يعنيه "Vicinty" فعليًا في الوقت المناسب ، ولكن في الوقت الحالي ، دعنا نكتب بعض الحلول في ورقة غش (أصل في أسفل اليسار):
2 1 4 3
3 2 1 2
0 3 2 3
لذلك ، بالنظر إلى x ، y على الشبكة ، يمكننا فقط قراءة عدد التحركات إلى الأصل.
إذا بدأنا خارج الشبكة ، فعلينا أن نعود إلى ذلك. نقدم "خط الوسط" ، وهو الخط الذي يمثله y = x/2. يمكن لأي فارس في x ، y على هذا الخط أن يعود إلى ورقة الغش باستخدام سلسلة من تحركات الساعة 8 (أي: (-2 ، -1) تحركات). إذا كانت X ، Y فوق خط الوسط ، سنحتاج إلى سلسلة من الساعة 8 و 7 صباحًا ، وإذا كانت تقل عن خط الوسط ، فسوف نحتاج إلى سلسلة من الساعة 8 و 10 س تحركات الساعة. شيئان يجب ملاحظته هنا:
- هذه التسلسلات هي أقصر مسارات. (تريد مني أن أثبت ذلك ، أم أنها واضحة؟)
- نحن نهتم فقط بعدد مثل هذه التحركات. يمكننا خلط التحركات في أي ترتيب.
لذلك ، دعونا نلقي نظرة على تحركات الخطوط المذكورة أعلاه. ما ندعيه هو:
(DX ؛ DY) = (2،1 ؛ 1،2) (N8 ؛ N7) (تدوين المصفوفة ، بدون أنواع الرياضيات - متجه العمود (DX ؛ DY) يساوي المصفوفة المربعة المضروبة بواسطة متجه العمود (N8 ؛ N7) - The The COMP عدد تحركات الساعة 8 وعدد تحركات الساعة 7) ، وبالمثل ؛
(dx ؛ dy) = (2،2 ؛ 1 ، -1) (n8 ؛ n10)
أنا أدعي أن DX ، سيكون DY تقريبًا (x ، y) ، لذلك (x-dx ، y-dy) سيكون في محيط الأصل (أيا كان "المنطقة المجاورة").
السطران في الكود اللذين يحسبان هذه المصطلحات هما الحل لها ، لكنهما تم اختيارهما للحصول على بعض الخصائص المفيدة:
- تتحرك الصيغة المذكورة أعلاه (x ، y) إلى واحد من (0،0) ، (1،1) ، أو (2،2).
- تتحرك صيغة أسفل الخط (x ، y) إلى واحد من (0،0) ، (1،0) ، (2،0) ، أو (1،1).
(هل ترغب في أن تكون أدلة هذه؟) لذا ، فإن مسافة الفارس ستكون بمجموع N7 و N8 و N10 و Cheatsheet [X-DX ، Y-DY] ، وتقلل Cheatsheet الخاص بنا إلى هذا:
. . 4
. 2 .
0 3 2
الآن ، هذه ليست نهاية القصة. انظر إلى 3 في الصف السفلي. الطرق الوحيدة التي يمكننا من خلالها الوصول إلى هذا هي:
- بدأنا هناك ، أو
- انتقلنا إلى هناك ، بتسلسل من الساعة 8 و 10 صباحًا. ولكن إذا كانت الخطوة الأخيرة هي الساعة الثامنة (التي يحق لها أن تكون ، حيث يمكننا القيام بحركاتنا بأي ترتيب) ، فيجب أن نمر عبر (3،1) ، والتي تكون المسافة في الواقع 2 (كما تستطيع انظر من ورقة الغش الأصلية). لذا فإن ما يجب أن نفعله هو خطوة واحدة في الساعة 8 صباحًا ، مما ينقذ تحركتين في المجموع.
هناك تحسين مماثل مع 4 في أعلى اليمين. بصرف النظر عن البدء هناك ، فإن الطريقة الوحيدة للوصول إليها هي بحلول الساعة الثامنة من (4،3). هذا ليس على ورقة الغش ، ولكن إذا كان هناك ، فستكون المسافة 3 ، لأننا قد نتعرض الساعة السابعة إلى (3،1) بدلاً من ذلك ، والتي تبلغ مسافة 2. فقط ، لذلك ، يجب علينا أن نتعامل مع واحد 8-O'clock Move ، ثم تقدم إلى الأمام 7-O'Clock.
لذلك ، نحتاج إلى إضافة رقم واحد إلى ورقة الغش:
. . 4
. 2 . 2
0 3 2
(ملاحظة: هناك حمولة كاملة من تحسينات التتبع الخلفي من (0،1) و (0،2) ولكن بما أن المحاليل لن يأخذنا أبدًا إلى هناك ، لا نحتاج إلى القلق بشأنهم.)
إذن هنا ، إذن ، هو رمز بيثون لتقييم هذا:
def knightDistance (x, y):
# normalise the coordinates
x, y = abs(x), abs(y)
if (x<y): x, y = y, x
# now 0 <= y <= x
# n8 means (-2,-1) (8 o'clock), n7 means (-1,-2) (7 o'clock), n10 means (-2,+1) (10 o'clock)
if (x>2*y):
# we're below the midline. Using 8- & 10-o'clock moves
n7, n8, n10 = 0, (x + 2*y)//4, (x - 2*y + 1)//4
else:
# we're above the midline. Using 7- and 8-o'clock moves
n7, n8, n10 = (2*y - x)//3, (2*x - y)//3, 0
x -= 2*n8 + n7 + 2*n10
y -= n8 + 2*n7 - n10
# now 0<=x<=2, and y <= x. Also (x,y) != (2,1)
# Try to optimise the paths.
if (x, y)==(1, 0): # hit the 3. Did we need to?
if (n8>0): # could have passed through the 2 at 3,1. Back-up
x, y = 3, 1; n8-=1;
if (x, y)==(2, 2): # hit the 4. Did we need to?
if (n8>0): # could have passed through a 3 at 4,3. Back-up, and take 7 o'clock to 2 at 3,1
x, y = 3, 1; n8-=1; n7+=1
# Almost there. Now look up the final leg
cheatsheet = [[0, 3, 2], [2, None, 2], [4]]
return n7 + n8 + n10 + cheatsheet [y][x-y]
بالمناسبة ، إذا كنت تريد معرفة مسار فعلي ، فإن هذه الخوارزمية تنص على ذلك أيضًا: إنها مجرد سلسلة من تحركات N7 7-O'Clock ، تليها (أو تتخللها) N8 8-O'Clock Moves ، N10 10- يتحرك O'Clock ، وأيًا كان رقصًا تمليه ورقة الغش (التي يمكن أن تكون في نفسها في ورقة غش).
الآن: كيف تثبت هذا صحيح. لا يكفي فقط مقارنة هذه النتائج بجدول من الإجابات الصحيحة ، لأن المشكلة نفسها غير محدودة. ولكن يمكننا أن نقول ذلك ، إذا كانت مسافة الفارس من مربع S هي D ، فعندئذ ، إذا كانت {m} هي مجموعة من الحركات القانونية من S ، فيجب أن تكون مسافة Knight (S+M) إما D-1 أو D+1 لجميع م. (هل تحتاج إلى دليل على ذلك؟) علاوة على ذلك ، يجب أن يكون هناك مربع واحد على الأقل من هذا القبيل مسافة D-1 ، ما لم تكن S هي الأصل. لذلك ، يمكننا إثبات الصواب من خلال إظهار هذا العقار الذي يحمل لكل مربع. هكذا:
def validate (n):
def isSquareReasonable (x, y):
d, downhills = knightDistance (x, y), 0
moves = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]
for dx, dy in moves:
dd = knightDistance (x+dx, y+dy)
if (dd == d+1): pass
elif (dd== d-1): downhills += 1
else: return False;
return (downhills>0) or (d==0)
for x in range (0, n+1):
for y in range (0, n+1):
if not isSquareReasonable (x, y): raise RuntimeError ("Validation failed")
بدلاً من ذلك ، يمكننا إثبات صحة أي مربع واحد من خلال مطاردة المسار من S إلى أسفل إلى الأصل. أولاً ، تحقق من المعقولية على النحو الوارد أعلاه ، ثم حدد أي S+M مثل هذه المسافة (S+M) == D-1. كرر حتى نصل إلى الأصل.
Howzat؟
/*
This program takes two sets of cordinates on a 8*8 chessboard, representing the
starting and ending points of a knight's path.
The problem is to print the cordinates that the knight traverses in between, following
the shortest path it can take.
Normally this program is to be implemented using the Djikstra's algorithm(using graphs)
but can also be implemented using the array method.
NOTE:Between 2 points there may be more than one shortest path. This program prints
only one of them.
*/
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
int m1=0,m2=0;
/*
This array contains three columns and 37 rows:
The rows signify the possible coordinate differences.
The columns 1 and 2 contains the possible permutations of the row and column difference
between two positions on a chess board;
The column 3 contains the minimum number of steps involved in traversing the knight's
path with the given permutation*/
int arr[37][3]={{0,0,0},{0,1,3},{0,2,2},{0,3,3},{0,4,2},{0,5,3},{0,6,4},{0,7,5}, {1,1,2},{1,2,1},{1,3,2},{1,4,3},{1,5,4},{1,6,3},{1,7,4},{2,2,4},{2,3,3},{2,4,2},
{2,5,3},{2,6,3},{2,7,5},{3,3,2},{3,4,3},{3,5,4},{3,6,3},{3,7,4},{4,4,4},{4,5,3},{4,6,4},{4,7,5},{5,5,4},{5,6,5},{5,7,4},{6,6,5},{6,7,5},{7,7,6}};
void printMoves(int,int,int,int,int,int);
void futrLegalMove(int,int,int,int);
main()
{
printf("KNIGHT'S SHORTEST PATH ON A 8*8 CHESSBOARD :\n");
printf("------------------------------------------");
printf("\nThe chessboard may be treated as a 8*8 array here i.e. the (1,1) ");
printf("\non chessboard is to be referred as (0,0) here and same for (8,8) ");
printf("\nwhich is to be referred as (7,7) and likewise.\n");
int ix,iy,fx,fy;
printf("\nEnter the initial position of the knight :\n");
scanf("%d%d",&ix,&iy);
printf("\nEnter the final position to be reached :\n");
scanf("%d%d",&fx,&fy);
int px=ix,py=iy;
int temp;
int tx,ty;
printf("\nThe Knight's shortest path is given by :\n\n");
printf("(%d, %d)",ix,iy);
futrLegalMove(px,py,m1,m2);
printMoves(px,py,fx,fy,m1,m2);
getch();
}
/*
This method checkSteps() checks the minimum number of steps involved from current
position(a & b) to final position(c & d) by looking up in the array arr[][].
*/
int checkSteps(int a,int b,int c,int d)
{
int xdiff, ydiff;
int i, j;
if(c>a)
xdiff=c-a;
else
xdiff=a-c;
if(d>b)
ydiff=d-b;
else
ydiff=b-d;
for(i=0;i<37;i++)
{
if(((xdiff==arr[i][0])&&(ydiff==arr[i][1])) || ((xdiff==arr[i][1])&& (ydiff==arr[i] [0])))
{
j=arr[i][2];break;
}
}
return j;
}
/*
This method printMoves() prints all the moves involved.
*/
void printMoves(int px,int py, int fx, int fy,int a,int b)
{
int temp;
int tx,ty;
int t1,t2;
while(!((px==fx) && (py==fy)))
{
printf(" --> ");
temp=checkSteps(px+a,py+b,fx,fy);
tx=px+a;
ty=py+b;
if(!(a==2 && b==1))
{if((checkSteps(px+2,py+1,fx,fy)<temp) && checkMove(px+2,py+1))
{temp=checkSteps(px+2,py+1,fx,fy);
tx=px+2;ty=py+1;}}
if(!(a==2 && b==-1))
{if((checkSteps(px+2,py-1,fx,fy)<temp) && checkMove(px+2,py-1))
{temp=checkSteps(px+2,py-1,fx,fy);
tx=px+2;ty=py-1;}}
if(!(a==-2 && b==1))
{if((checkSteps(px-2,py+1,fx,fy)<temp) && checkMove(px-2,py+1))
{temp=checkSteps(px-2,py+1,fx,fy);
tx=px-2;ty=py+1;}}
if(!(a==-2 && b==-1))
{if((checkSteps(px-2,py-1,fx,fy)<temp) && checkMove(px-2,py-1))
{temp=checkSteps(px-2,py-1,fx,fy);
tx=px-2;ty=py-1;}}
if(!(a==1 && b==2))
{if((checkSteps(px+1,py+2,fx,fy)<temp) && checkMove(px+1,py+2))
{temp=checkSteps(px+1,py+2,fx,fy);
tx=px+1;ty=py+2;}}
if(!(a==1 && b==-2))
{if((checkSteps(px+1,py-2,fx,fy)<temp) && checkMove(px+1,py-2))
{temp=checkSteps(px+1,py-2,fx,fy);
tx=px+1;ty=py-2;}}
if(!(a==-1 && b==2))
{if((checkSteps(px-1,py+2,fx,fy)<temp) && checkMove(px-1,py+2))
{temp=checkSteps(px-1,py+2,fx,fy);
tx=px-1;ty=py+2;}}
if(!(a==-1 && b==-2))
{if((checkSteps(px-1,py-2,fx,fy)<temp) && checkMove(px-1,py-2))
{temp=checkSteps(px-1,py-2,fx,fy);
tx=px-1;ty=py-2;}}
t1=tx-px;//the step taken in the current move in the x direction.
t2=ty-py;//" " " " " " " " " " " " " " " " " " " " " y " " " " ".
px=tx;
py=ty;
printf("(%d, %d)",px,py);
futrLegalMove(px,py,t1,t2);
a=m1;
b=m2;
}
}
/*
The method checkMove() checks whether the move in consideration is beyond the scope of
board or not.
*/
int checkMove(int a, int b)
{
if(a>7 || b>7 || a<0 || b<0)
return 0;
else
return 1;
}
/*Out of the 8 possible moves, this function futrLegalMove() sets the valid move by
applying the following constraints
1. The next move should not be beyond the scope of the board.
2. The next move should not be the exact opposite of the previous move.
The 1st constraint is checked by sending all possible moves to the checkMove()
method;
The 2nd constraint is checked by passing as parameters(i.e. a and b) the steps of the
previous move and checking whether or not it is the exact opposite of the current move.
*/
void futrLegalMove(int px,int py,int a,int b)
{
if(checkMove(px+2,py+1) && (a!=-2 && b!=-1))
m1=2,m2=1;
else
{
if(checkMove(px+2,py-1)&& (a!=-2 && b!=1))
m1=2,m2=-1;
else
{
if(checkMove(px-2,py+1)&& (a!=2 && b!=-1))
m1=-2,m2=1;
else
{
if(checkMove(px-2,py-1)&& (a!=2 && b!=1))
m1=-2,m2=-1;
else
{
if(checkMove(px+1,py+2)&& (b!=-2 && a!=-1))
m2=2,m1=1;
else
{
if(checkMove(px+1,py-2)&& (a!=-1 && b!=2))
m2=-2,m1=1;
else
{
if(checkMove(px-1,py+2)&& (a!=1 && b!=-2))
m2=2,m1=-1;
else
{
if(checkMove(px-1,py-2)&& (a!=1 && b!=2))
m2=-2,m1=-1;
}}}}}}}
}
//End of Program.
لم أدرس الرسوم البيانية حتى الآن .. مثل مشكلة تنفيذها من خلال صفائف ببساطة ، لم أستطع استخلاص أي حل بخلاف ذلك. لقد تعاملت مع المواقف ليس كصفوف وملفات (تدوين الشطرنج المعتاد) ، ولكن كمؤشرات صفيف. لمعلوماتك ، هذا هو لوح الشطرنج 8*8 فقط. أي نصيحة تحسين دائما موضع ترحيب.
*يجب أن تكون التعليقات كافية لفهمك للمنطق. ومع ذلك ، قد تسأل دائما.
*فحص على برنامج التحويل البرمجي DEV-C ++ 4.9.9.2 (برنامج سفك الدم).
أعتقد أن هذا قد يساعدك أيضًا ..
NumWays(x,y)=1+min(NumWays(x+-2,y-+1),NumWays(x+-1,y+-2));
واستخدام البرمجة الديناميكية للحصول على الحل.
ملاحظة: إنه يستخدم BFS دون الحاجة إلى تولي مشكلة إعلان العقد وحواف الرسم البياني.
فيما يلي حل لهذه المشكلة المعينة التي تم تنفيذها في Perl. سيظهر أحد أقصر المسارات - قد يكون هناك أكثر من واحد في بعض الحالات.
لم أستخدم أي من الخوارزميات الموضحة أعلاه - ولكن سيكون من الجيد مقارنتها بالحلول الأخرى.
#!/usr/local/bin/perl -w
use strict;
my $from = [0,0];
my $to = [7,7];
my $f_from = flat($from);
my $f_to = flat($to);
my $max_x = 7;
my $max_y = 7;
my @moves = ([-1,2],[1,2],[2,1],[2,-1],[1,-2],[-1,-2],[-2,-1],[-2,1]);
my %squares = ();
my $i = 0;
my $min = -1;
my @s = ( $from );
while ( @s ) {
my @n = ();
$i++;
foreach my $s ( @s ) {
unless ( $squares{ flat($s) } ) {
my @m = moves( $s );
push @n, @m;
$squares{ flat($s) } = { i=>$i, n=>{ map {flat($_)=>1} @m }, };
$min = $i if $squares{ flat($s) }->{n}->{$f_to};
}
}
last if $min > -1;
@s = @n;
}
show_path( $f_to, $min );
sub show_path {
my ($s,$i) = @_;
return if $s eq $f_from;
print "$i => $f_to\n" if $i == $min;
foreach my $k ( keys %squares ) {
if ( $squares{$k}->{i} == $i && $squares{$k}->{n}->{$s} ) {
$i--;
print "$i => $k\n";
show_path( $k, $i );
last;
}
}
}
sub flat { "$_[0]->[0],$_[0]->[1]" }
sub moves {
my $c = shift;
my @s = ();
foreach my $m ( @moves ) {
my $x = $c->[0] + $m->[0];
my $y = $c->[1] + $m->[1];
if ( $x >= 0 && $x <=$max_x && $y >=0 && $y <=$max_y) {
push @s, [$x, $y];
}
}
return @s;
}
__END__
public class Horse {
private int[][] board;
private int[] xer = { 2, 1, -1, -2, -2, -1, 1, 2 };
private int[] yer = { 1, 2, 2, 1, -1, -2, -2, -1 };
private final static int A_BIG_NUMBER = 10000;
private final static int UPPER_BOUND = 64;
public Horse() {
board = new int[8][8];
}
private int solution(int x, int y, int destx, int desty, int move) {
if(move == UPPER_BOUND) {
/* lets put an upper bound to avoid stack overflow */
return A_BIG_NUMBER;
}
if(x == 6 && y ==5) {
board[6][5] = 1;
return 1;
}
int min = A_BIG_NUMBER;
for (int i = 0 ; i < xer.length; i++) {
if (isMoveGood(x + xer[i], y + yer[i])) {
if(board[x + xer[i]][y + yer[i]] != 0) {
min = Integer.min(min, 1 + board[x +xer[i]] [y +yer[i]]);
} else {
min = Integer.min(min, 1 + solution(x + xer[i], y + yer[i], destx, desty, move + 1));
}
}
}
board[x][y] = min;
return min;
}
private boolean isMoveGood(int x, int y) {
if (x >= 0 && x < board.length && y >= 0 && y < board.length)
return true;
return false;
}
public static void main(String[] args) {
int destX = 6;
int destY = 7;
final Horse h = new Horse();
System.out.println(h.solution(0, 0, destX, destY, 0));
}
}
فقط رمز الياقوت من إجابة Graeme Pyle's Jsfiddle أعلاه, ، مخطط جميع التعليمات البرمجية الإضافية وتحويله إلى روبي لمجرد الحصول على حل بواسطة خوارزميةه ، يبدو أنه يعمل. لا يزال الاختبار على الرغم من:
def getBoardOffset(board)
return board.length / 2
end
def setMoveCount(x, y, count, board)
offset = getBoardOffset(board)
board[y + offset][x + offset] = count
end
def getMoveCount(x, y, board)
offset = getBoardOffset(board)
row = board[y + offset]
return row[x + offset]
end
def isBottomOfVerticalCase(x, y)
return (y - 2 * x) % 4 == 0
end
def isPrimaryDiagonalCase(x, y)
return (x + y) % 2 == 0
end
def isSecondaryDiagonalCase(x, y)
return (x + y) % 2 == 1
end
def simplifyBySymmetry(x, y)
x = x.abs
y = y.abs
if (y < x)
t = x
x = y
y = t
end
return {x: x, y: y}
end
def getPrimaryDiagonalCaseMoveCount(x, y)
var diagonalOffset = y + x
var diagonalIntersect = diagonalOffset / 2
return ((diagonalIntersect + 2) / 3).floor * 2
end
def getSpecialCaseMoveCount(x, y)
specials = [{
x: 0,
y: 0,
d: 0
},
{
x: 0,
y: 1,
d: 3
},
{
x: 0,
y: 2,
d: 2
},
{
x: 0,
y: 3,
d: 3
},
{
x: 2,
y: 2,
d: 4
},
{
x: 1,
y: 1,
d: 2
},
{
x: 3,
y: 3,
d: 2
}
];
matchingSpecial=nil
specials.each do |special|
if (special[:x] == x && special[:y] == y)
matchingSpecial = special
end
end
if (matchingSpecial)
return matchingSpecial[:d]
end
end
def isVerticalCase(x, y)
return y >= 2 * x
end
def getVerticalCaseMoveCount(x, y)
normalizedHeight = getNormalizedHeightForVerticalGroupCase(x, y)
groupIndex = (normalizedHeight/4).floor
groupStartMoveCount = groupIndex * 2 + x
return groupStartMoveCount + getIndexInVerticalGroup(x, y)
end
def getIndexInVerticalGroup(x, y)
return getNormalizedHeightForVerticalGroupCase(x, y) % 4
end
def getYOffsetForVerticalGroupCase(x)
return x * 2
end
def getNormalizedHeightForVerticalGroupCase(x, y)
return y - getYOffsetForVerticalGroupCase(x)
end
def getSecondaryDiagonalCaseMoveCount(x, y)
diagonalOffset = y + x
diagonalIntersect = diagonalOffset / 2 - 1
return ((diagonalIntersect + 2) / 3).floor * 2 + 1
end
def getMoveCountO1(x, y)
newXY = simplifyBySymmetry(x, y)
x = newXY[:x]
y = newXY[:y]
specialMoveCount = getSpecialCaseMoveCount(x ,y)
if (specialMoveCount != nil)
return specialMoveCount
elsif (isVerticalCase(x, y))
return getVerticalCaseMoveCount(x ,y)
elsif (isPrimaryDiagonalCase(x, y))
return getPrimaryDiagonalCaseMoveCount(x ,y)
elsif (isSecondaryDiagonalCase(x, y))
return getSecondaryDiagonalCaseMoveCount(x ,y)
end
end
def solution(x ,y)
return getMoveCountO1(x, y)
end
puts solution(0,0)
النية الوحيدة هي حفظ شخص ما في بعض الوقت تحويل التعليمات البرمجية إذا كان أي شخص يحتاج إلى رمز كامل.
إليك إصدار PHP من وظيفة Jules May
function knightDistance($x, $y)
{
$x = abs($x);
$y = abs($y);
if($x < $y)
{
$tmp = $x;
$x = $y;
$y = $tmp;
}
if($x > 2 * $y)
{
$n7 = 0;
$n8 = floor(($x + 2*$y) / 4);
$n10 = floor(($x - 2*$y +1) / 4);
}
else
{
$n7 = floor((2*$y - $x) / 3);
$n8 = floor((2*$x - $y) / 3);
$n10 = 0;
}
$x -= 2 * $n8 + $n7 + 2 * $n10;
$y -= $n8 + 2 * $n7 - $n10;
if($x == 1 && $y == 0)
{
if($n8 > 0)
{
$x = 3;
$y = 1;
$n8--;
}
}
if($x == 2 && $y == 2)
{
if($n8 > 0)
{
$x = 3;
$y = 1;
$n8--;
$n7++;
}
}
$cheatsheet = [[0, 3, 2], [2, 0, 2], [4]];
return $n7 + $n8 + $n10 + $cheatsheet [$y][$x-$y];
}
ها هو برنامجي. هذا ليس حلًا مثاليًا. هناك الكثير من التغييرات التي يمكنك إجراؤها في وظيفة العودية. لكن هذه النتيجة النهائية مثالية. حاولت تحسين قليلا.
public class KnightKing2 {
private static int tempCount = 0;
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
int ip1 = Integer.parseInt(in.nextLine().trim());
int ip2 = Integer.parseInt(in.nextLine().trim());
int ip3 = Integer.parseInt(in.nextLine().trim());
int ip4 = Integer.parseInt(in.nextLine().trim());
in.close();
int output = getStepCount(ip1, ip2, ip3, ip4);
System.out.println("Shortest Path :" + tempCount);
}
// 2 1 6 5 -> 4
// 6 6 5 5 -> 2
public static int getStepCount(int input1, int input2, int input3, int input4) {
return recurse(0, input1, input2, input3, input4);
}
private static int recurse(int count, int tx, int ty, int kx, int ky) {
if (isSolved(tx, ty, kx, ky)) {
int ccount = count+1;
System.out.println("COUNT: "+count+"--"+tx+","+ty+","+ccount);
if((tempCount==0) || (ccount<=tempCount)){
tempCount = ccount;
}
return ccount;
}
if ((tempCount==0 || count < tempCount) && ((tx < kx+2) && (ty < ky+2))) {
if (!(tx + 2 > 8) && !(ty + 1 > 8)) {
rightTop(count, tx, ty, kx, ky);
}
if (!(tx + 2 > 8) && !(ty - 1 < 0)) {
rightBottom(count, tx, ty, kx, ky);
}
if (!(tx + 1 > 8) && !(ty + 2 > 8)) {
topRight(count, tx, ty, kx, ky);
}
if (!(tx - 1 < 0) && !(ty + 2 > 8)) {
topLeft(count, tx, ty, kx, ky);
}
if (!(tx + 1 > 8) && !(ty - 2 < 0)) {
bottomRight(count, tx, ty, kx, ky);
}
if (!(tx - 1 < 0) && !(ty - 2 < 0)) {
bottomLeft(count, tx, ty, kx, ky);
}
if (!(tx - 2 < 0) && !(ty + 1 > 8)) {
leftTop(count, tx, ty, kx, ky);
}
if (!(tx - 2 < 0) && !(ty - 1 < 0)) {
leftBottom(count, tx, ty, kx, ky);
}
}
return count;
}
private static int rightTop(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx + 2, ty + 1, kx, ky);
}
private static int topRight(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx + 1, ty + 2, kx, ky);
}
private static int rightBottom(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx + 2, ty - 1, kx, ky);
}
private static int bottomRight(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx + 1, ty - 2, kx, ky);
}
private static int topLeft(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx - 1, ty + 2, kx, ky);
}
private static int bottomLeft(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx - 1, ty - 2, kx, ky);
}
private static int leftTop(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx - 2, ty + 1, kx, ky);
}
private static int leftBottom(int count, int tx, int ty, int kx, int ky) {
return count + recurse(count + 1, tx - 2, ty - 1, kx, ky);
}
private static boolean isSolved(int tx, int ty, int kx, int ky) {
boolean solved = false;
if ((tx == kx) && (ty == ky)) {
solved = true;
} else if ((tx + 2 == kx) && (ty + 1 == ky)) { // right top
solved = true;
} else if ((tx + 2 == kx) && (ty - 1 == ky)) { // right bottom
solved = true;
} else if ((ty + 2 == ky) && (tx + 1 == kx)) {// top right
solved = true;
} else if ((ty + 2 == ky) && (tx - 1 == kx)) {// top left
solved = true;
} else if ((tx - 2 == kx) && (ty + 1 == ky)) { // left top
solved = true;
} else if ((tx - 2 == kx) && (ty - 1 == ky)) {// left bottom
solved = true;
} else if ((ty - 2 == ky) && (tx + 1 == kx)) { // bottom right
solved = true;
} else if ((ty - 2 == ky) && (tx - 1 == kx)) { // bottom left
solved = true;
}
return solved;
}
}
فيما يلي نسخة C تعتمد على رمز مصطفى سيردار şanlı الذي يعمل مع لوحة مخصصة:
#include <stdio.h>
#include <math.h>
#define test(x1, y1, x2, y2) (sx == x1 && sy == y1 &&tx == x2 &&ty == y2) || (sx == x2 && sy == y2 && tx == x1 && ty==y1)
int distance(int sx, int sy, int tx, int ty) {
int x, y, t;
double delta;
// special corner cases
if (test(1, 1, 2, 2) ||
test(7, 7, 8, 8) ||
test(7, 2, 8, 1) ||
test(1, 8, 2, 7))
return 4;
// axes symmetry
x = abs(sx - tx);
y = abs(sy - ty);
// diagonal symmetry
if (x < y) {
t = x;
x = y;
y = t;
}
// 2 corner cases
if (x == 1 && y == 0)
return 3;
if (x == 2 && y == 2)
return 4;
// main
delta = x - y;
if (y > delta) {
return (int)(delta - 2 * floor((delta - y) / 3));
}
else {
return (int)(delta - 2 * floor((delta - y) / 4));
}
}
اختباره هنا بإثبات ضد الحل العودية
