Меню
За съжаление алгоритъмът, който успях да измисля (долната програма на C#), е със сложност $O(8^{N^2})$ и при $N=6$ изведе схемата на ходовете след няколко минути, а при $N=7$ така и не я дочаках.
Дали няма по-бърз алгоритъм?
- Код: Избери целия код
namespace Ход_на_коня
{
public partial class Form1 : Form
{
private const int N = 6;
private Point[] numberPositions;
private bool[,] H;
private Point[][] coordinates;
bool active;
public Form1()
{
InitializeComponent();
Random random = new Random();
numberPositions = new Point[N * N];
coordinates = new Point[N * N][];
for (int i = 0; i < N * N; i++)
{
coordinates[i] = new Point[] { new Point(-2, -1), new Point(-1, -2), new Point(1, -2), new Point(2, -1), new Point(2, 1), new Point(1, 2), new Point(-1, 2), new Point(-2, 1) };
for (int c = 0; c < 12; c++)
{
int u = random.Next(8); int v = random.Next(8);
(coordinates[i][u], coordinates[i][v]) = (coordinates[i][v], coordinates[i][u]);
}
}
H = new bool[N, N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
H[i, j] = false;
active = true;
HorseMove(0, random.Next(N), random.Next(N));
}
private void HorseMove(int n, int row, int col)
{
if (active && row >= 0 && row < N && col >= 0 && col < N && !H[row, col])
{
H[row, col] = true;
numberPositions[n] = new Point(col, row);
if (n < N * N - 1)
{
int i = N * row + col;
for (int j = 0; j < 8; j++)
HorseMove(n + 1, row + coordinates[i][j].Y, col + coordinates[i][j].X);
}
else
{
int deltaX = Math.Abs(numberPositions[n].X - numberPositions[0].X);
int deltaY = Math.Abs(numberPositions[n].Y - numberPositions[0].Y);
if (deltaX == 1 && deltaY == 2 || deltaX == 2 && deltaY == 1)
{
active = false;
this.Invalidate();
}
}
H[row, col] = false;
}
}
private void Form1_Paint(object sender, PaintEventArgs e)
{
if (!active)
{
float w = ClientSize.Width, h = ClientSize.Height;
for (int i = 0; i <= N; i++)
{
e.Graphics.DrawLine(new Pen(Color.Brown, (w + h) / 270),
w / 12, h / 12 + 5 * h / 6 * i / N,
w / 12 + 5 * w / 6, h / 12 + 5 * h / 6 * i / N);
e.Graphics.DrawLine(new Pen(Color.Brown, (w + h) / 270),
w / 12 + 5 * w / 6 * i / N, h / 12,
w / 12 + 5 * w / 6 * i / N, h / 12 + 5 * h / 6);
}
PointF[] points = new PointF[N * N];
for (int num = 0; num < N * N; num++)
if (numberPositions[num].X >= 0 && numberPositions[num].Y >= 0)
{
float x = w / 12 + 5 * w / 6 / N * (numberPositions[num].X + 0.2f);
float y = h / 12 + 5 * h / 6 / N * (numberPositions[num].Y + 0.2f);
float sizeNumber = (w + h) / N;
Font font;
SizeF size;
do
{
sizeNumber -= 0.1f;
font = new Font("Arial", sizeNumber, FontStyle.Italic);
size = e.Graphics.MeasureString("" + (num + 1), font);
}
while (size.Width > 5 * w / 6 / N * 0.6f || size.Height > 5 * h / 6 / N * 0.6f);
e.Graphics.DrawString("" + (num + 1), font, Brushes.Black, x, y);
x = w / 12 + 5 * w / 6 / N * (numberPositions[num].X + 0.5f);
y = h / 12 + 5 * h / 6 / N * (numberPositions[num].Y + 0.5f);
points[num] = new PointF(x, y);
}
e.Graphics.DrawPolygon(new Pen(Color.Red, (w + h) / 290), points);
}
}
private void Form1_Resize(object sender, EventArgs e)
{
this.Invalidate();
}
}
}
Ето какво излезе при $N=6$:
- Ход на коня.png (40.25 KiB) Прегледано 261 пъти
