با سلام
مساله تور اسب (Knight's tour) به این شکل است:
برنامه‌ای بنویسید که در نقطه‌ای دلخواه در صفحه شطرنج، یک اسب حرکت خود را شروع کرده و بدون اینکه هیچ خانه‌ای را دوبار ملاقات کند تمام خانه‌های شطرنج را با 64 حرکت L مانند ملاقات نماید.
به عنوان مثال تصویر زیر را نگاه کنید:
تمام خانه‌های شطرنج توسط اسب با 64 حرکت ملاقات می‌شوند.
http://upload.wikimedia.org/wikipedi..._tour_anim.gif
یکی از راه‌های حل این مساله استفاده از الگوریتم واندرولف (Warnsdorff's algorithm) می‌باشد.
این الگوریتم بیان می‌دارد که برای حرکت بعدی، خانه‌ای از صفحه شطرنج باید انتخاب گردد که کمترین امکان برای حرکت بعد از آن وجود داشته باشد.
برای مثال در تصویر زیر اسب در خانه Start می‌باشد و تمام خانه‌های شماره‌دار هنوز ملاقات نشده‌اند. بنابراین بهترین خانه برای حرکت بعدی خانه شماره دو می‌باشد چون اسب پس از انتقال به خانه شماره 2، تنها 2 امکان برای حرکت خود دارد.
http://upload.wikimedia.org/wikipedi...Warnsdorff.gif
----------------------------------------------------------------------
این صورت مساله پروژه درس ساختمان داده ما بود.
من این پروژه رو با زبان C# نوشتم و تصویر اون رو در زیر مشاهده می‌کنید:
http://i41.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
