حل مساله تور اسب

[amir_saniyan]

با سلام

مساله تور اسب (Knight's tour) به این شکل است:

برنامه‌ای بنویسید که در نقطه‌ای دلخواه در صفحه شطرنج، یک اسب حرکت خود را شروع کرده و بدون اینکه هیچ خانه‌ای را دوبار ملاقات کند تمام خانه‌های شطرنج را با 64 حرکت L مانند ملاقات نماید.

به عنوان مثال تصویر زیر را نگاه کنید:
تمام خانه‌های شطرنج توسط اسب با 64 حرکت ملاقات می‌شوند.

http://upload.wikimedia.org/wikipedia/commons/0/0f/Knight%27s_tour_anim.gif (http://en.wikipedia.org/wiki/File:Knight%27s_tour_anim.gif)

یکی از راه‌های حل این مساله استفاده از الگوریتم واندرولف (Warnsdorff's algorithm) می‌باشد.

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

برای مثال در تصویر زیر اسب در خانه Start می‌باشد و تمام خانه‌های شماره‌دار هنوز ملاقات نشده‌اند. بنابراین بهترین خانه برای حرکت بعدی خانه شماره دو می‌باشد چون اسب پس از انتقال به خانه شماره 2، تنها 2 امکان برای حرکت خود دارد.

http://upload.wikimedia.org/wikipedia/commons/5/58/Warnsdorff.gif (http://en.wikipedia.org/wiki/File:Warnsdorff.gif)

----------------------------------------------------------------------

این صورت مساله پروژه درس ساختمان داده ما بود.
من این پروژه رو با زبان C# نوشتم و تصویر اون رو در زیر مشاهده می‌کنید:

http://i41.tinypic.com/ivlkx3.jpg (http://s5.tinypic.com/ivlkx3.jpg)

من برای حل این مساله یک کلاس به نام WarnsdorffAlgorithm نوشتم.
این کلاس یک متد داره به نام Solve که جواب مساله رو برمی‌گردونه.
این متد دو آرگومان داره که مکان اسب روی صفحه شطرنج رو مشخص می‌کنه (x و y) و باید عددی بین 0 تا 7 باشه.
مقدار برگشتی این متد هم یک آرایه از اعداد صحیح (8 در 8) است که در واقع همون صفحه شطرنجه که با اعداد 1 تا 64 پر شده‌اند.
خونه‌ای از آرایه که حاوی عدد 1 است همون نقطه شروعه و عدد 2 در آرایه نشان دهنده خونه بعدی و به همین ترتیب می‌باشد.
اگر این متد نتونه مساله رو حل کنه، مقدار null برمی‌گردونه.
بقیه قسمت‌های برنامه هم مربوط به کارهای گرافیکی می‌شه.
این برنامه با سورس رو به عنوان آموزش توی این سایت ضمیمه کردم و مي‌تونید دریافتش کنید.
امیدوارم مفید واقع بشه...


using System;
namespace KnightTour
{
publicclassWarnsdorffAlgorithm
{
public WarnsdorffAlgorithm()
{
// Create board.
board = newint[8][];
for (int i = 0; i < 8; i++)
{
board[i] = newint[8];
}
}
publicint[][] Solve(int positionX, int positionY)
{
// Check argument(s).
if ((positionX < 0) || (positionX >= 8))
{
thrownewArgumentOutOfRangeException("positionX");
}
if ((positionY < 0) || (positionY >= 8))
{
thrownewArgumentOutOfRangeException("positionY");
}
ClearBoard();
int moveNumber = 1;
board[positionX][positionY] = moveNumber;
moveNumber++;
for (int i = 1; i < 64; i++)
{
bool moved = GetNextMoves(ref positionX, ref positionY);
if (!moved)
{
returnnull;
}
board[positionX][positionY] = moveNumber;
moveNumber++;
}
return (int[][])board.Clone();
}
privateint[][] board;
privatevoid ClearBoard()
{
for (int positionX = 0; positionX < 8; positionX++)
{
for (int positionY = 0; positionY < 8; positionY++)
{
board[positionX][positionY] = 0;
}
}
return;
}
privatebool GetNextMoves(refint positionX, refint positionY)
{
int moveX = -1;
int moveY = -1;
bool moved = false;
int accessibility = 8;
// (X + 2, Y + 1)
if (((positionX + 2) < 8) && ((positionY + 1) < 8) && (board[positionX + 2][positionY + 1] == 0))
{
if ((GetAccessibility((positionX + 2), (positionY + 1)) < accessibility))
{
accessibility = GetAccessibility((positionX + 2), (positionY + 1));
moveX = positionX + 2;
moveY = positionY + 1;
moved = true;
}
}
// (X + 2, Y - 1)
if (((positionX + 2) < 8) && ((positionY - 1) >= 0) && (board[positionX + 2][positionY - 1] == 0))
{
if ((GetAccessibility((positionX + 2), (positionY - 1)) < accessibility))
{
accessibility = GetAccessibility((positionX + 2), (positionY - 1));
moveX = positionX + 2;
moveY = positionY - 1;
moved = true;
}
}
// (X + 1, Y + 2)
if (((positionX + 1) < 8) && ((positionY + 2) < 8) && (board[positionX + 1][positionY + 2] == 0))
{
if ((GetAccessibility((positionX + 1), (positionY + 2)) < accessibility))
{
accessibility = GetAccessibility((positionX + 1), (positionY + 2));
moveX = positionX + 1;
moveY = positionY + 2;
moved = true;
}
}
// (X + 1, Y - 2)
if (((positionX + 1) < 8) && ((positionY - 2) >= 0) && (board[positionX + 1][positionY - 2] == 0))
{
if ((GetAccessibility((positionX + 1), (positionY - 2)) < accessibility))
{
accessibility = GetAccessibility((positionX + 1), (positionY - 2));
moveX = positionX + 1;
moveY = positionY - 2;
moved = true;
}
}
// (X - 1, Y + 2)
if (((positionX - 1) >= 0) && ((positionY + 2) < 8) && (board[positionX - 1][positionY + 2] == 0))
{
if ((GetAccessibility((positionX - 1), (positionY + 2)) < accessibility))
{
accessibility = GetAccessibility((positionX - 1), (positionY + 2));
moveX = positionX - 1;
moveY = positionY + 2;
moved = true;
}
}
// (X - 1, Y - 2)
if (((positionX - 1) >= 0) && ((positionY - 2) >= 0) && (board[positionX - 1][positionY - 2] == 0))
{
if ((GetAccessibility((positionX - 1), (positionY - 2)) < accessibility))
{
accessibility = GetAccessibility((positionX - 1), (positionY - 2));
moveX = positionX - 1;
moveY = positionY - 2;
moved = true;
}
}
// (X - 2, Y + 1)
if (((positionX - 2) >= 0) && ((positionY + 1) < 8) && (board[positionX - 2][positionY + 1] == 0))
{
if ((GetAccessibility((positionX - 2), (positionY + 1)) < accessibility))
{
accessibility = GetAccessibility((positionX - 2), (positionY + 1));
moveX = positionX - 2;
moveY = positionY + 1;
moved = true;
}
}
// (X - 2, Y - 1)
if (((positionX - 2) >= 0) && ((positionY - 1) >= 0) && (board[positionX - 2][positionY - 1] == 0))
{
if ((GetAccessibility((positionX - 2), (positionY - 1)) < accessibility))
{
accessibility = GetAccessibility((positionX - 2), (positionY - 1));
moveX = positionX - 2;
moveY = positionY - 1;
moved = true;
}
}
positionX = moveX;
positionY = moveY;
return moved;
}
privateint GetAccessibility(int positionX, int positionY)
{
int accessibility = 0;
// (X + 2, Y + 1)
if (((positionX + 2) < 8) && ((positionY + 1) < 8) && (board[positionX + 2][positionY + 1] == 0))
{
accessibility++;
}
// (X + 2, Y - 1)
if (((positionX + 2) < 8) && ((positionY - 1) >= 0) && (board[positionX + 2][positionY - 1] == 0))
{
accessibility++;
}
// (X + 1, Y + 2)
if (((positionX + 1) < 8) && ((positionY + 2) < 8) && (board[positionX + 1][positionY + 2] == 0))
{
accessibility++;
}
// (X + 1, Y - 2)
if (((positionX + 1) < 8) && ((positionY - 2) >= 0) && (board[positionX + 1][positionY - 2] == 0))
{
accessibility++;
}
// (X - 1, Y + 2)
if (((positionX - 1) >= 0) && ((positionY + 2) < 8) && (board[positionX - 1][positionY + 2] == 0))
{
accessibility++;
}
// (X - 1, Y - 2)
if (((positionX - 1) >= 0) && ((positionY - 2) >= 0) && (board[positionX - 1][positionY - 2] == 0))
{
accessibility++;
}
// (X - 2, Y + 1)
if (((positionX - 2) >= 0) && ((positionY + 1) < 8) && (board[positionX - 2][positionY + 1] == 0))
{
accessibility++;
}
// (X - 2, Y - 1)
if (((positionX - 2) >= 0) && ((positionY - 1) >= 0) && (board[positionX - 2][positionY - 1] == 0))
{
accessibility++;
}
return accessibility;
}
}
}


موفق باشید.

----------------------------------------------------------------------

برای کسب اطلاعات بیشتر در مورد مساله تور اسب به پیوندهای زیر مراجعه کنید:
http://en.wikipedia.org/wiki/Knight%27s_tour
http://en.wikipedia.org/wiki/Warnsdorff%27s_algorithm

[amir_saniyan]

سلام دوباره

این هم نسخه تحت موبایلش (ضمیمه شده)،

البته برای استفاده ار پرونده jar (توی پوشه dist) باید موبالتون از جاوا پشتیبانی کنه و برای استفاده از سورس اون هم باید NetBeans نصب باشه

موفق باشید

[saeid99]

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

[amir_saniyan]

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

با سلام

در این حالت من اولین خونه‌ای که پیدا کنم رو انتخاب کردم چون هیچ فرقی ندارند. (تو متد GetNextMoves به if که GetAccessibility داره دقت کنید.)