Chris Maunder Ответов: 4

Задача кодирования: рыцарь на шахматной доске

Сегодняшняя задача поставлена Йеруном Ландхеером.

Напишите программу, которая позволит коню перепрыгнуть через шахматную доску так, чтобы он коснулся всех квадратов, но этот конь никогда не сможет использовать одно и то же место дважды. Исходное положение должно быть задано пользователем (или предоставлено как случайное местоположение, если вы не хотите принимать пользовательский ввод), и программа должна вычислить и вывести решение в виде списка координат.

Пример:

Время начала: А1
Решение: A1 – B3-C5 и т. д.


Прошлая неделя
Отдельно стоит упомянуть ProgramFOX для его решения Polyglot. Потрясающий. Для победителя это был спор между Йоргеном Андерссоном и Грэмом, но я собираюсь отдать его Йоргену в надежде вдохновить Грэма на еще более высокие подвиги безумия.

Graeme_Grant

Итак, производительность и надежность, когда слово не найдено, не было важно? In-memory SQLite был таким же быстрым, как и мое оптимизированное словарное решение... Гораздо быстрее и надежнее, чем у Йоргена... Хммм... Стол навалился на меня. :/

Я должен признать, что Йорген сделал хороший выстрел... молодец, приятель.

Chris Maunder

Если это станет чем-то таким, что я должен буду сесть и полностью протестировать каждое решение, засечь их время, проверить их правильность, проверить на плагиат и предоставить пункт за пунктом независимо проверенный набор критериев оценки, то я боюсь, что мне придется оставить вам, ребята, решать задачи и объявлять "победителя".

Это для развлечения. Судейство намеренно произвольное, а иногда и дико предвзятое.

Как насчет того, чтобы оставить это как вызов, и я воздержусь от любых попыток объявить победителя. Я хочу, чтобы это было весело, а не то, что потенциально может расстроить участников.

Graeme_Grant

Отмечал и буду более внимательным в будущем.

PIEBALDconsult

..- и весь мир - твоя устрица.

Graeme_Grant

и как говорится...[^]

Graeme_Grant

Крис, для некоторых возникает некоторая путаница в том, что подразумевается под "касаниями всех квадратов". Не могли бы вы дать некоторые разъяснения этим людям, пожалуйста.

Graeme_Grant

"Надежда вдохновить Грэма на еще более высокие подвиги безумия."- Обновлено и готово! ;)

4 Ответов

Рейтинг:
23

Thomas Daniels

Это было весело! Мой код и ответ становились действительно большими, вот вместо этого статья:
Рыцарский тур на квадратной шахматной доске: вызов кодирования[^]
В качестве бонуса он также может нарисовать картинку или анимированный GIF рыцарского пути :)

Maciej Los

Отлично!

Thomas Daniels

Спасибо!

Рейтинг:
2

Graeme_Grant

Вот решение, использующее интерпретацию алгоритма Варнсдорфа: Рыцарский тур - Википедия[^]

Обновление: код был переработан без ущерба для производительности.

Цель


Гибкое ядро со следующими целями:

1. Повторно использовать в других настольных ориентированных головоломки, как: Задача о восьми ферзях - Википедия[^], Ладейный полином - Википедия[^], и Нет-три-в-линии проблема-Википедия[^].

2. плюс другие "бонусные" задачи, такие как:
2а. определите все разрешимые туры для заданного размера доски
2b. определите наименьший размер платы с допустимым решением
2С. дуэльные рыцари-разрешимые решения с одним или несколькими рыцарями на доске.
2d. пользователь может визуально перемещаться вперед и назад по туру и видеть, как работает процесс принятия решений, а не только сделанные шаги.
2е. Производительность - не жертва гибкость в производительности

Чтобы достичь всех вышеперечисленных целей, я решил работать с Класс Stack(T) (System.Коллекции.Общий)[^].

основной код


Код является автономным в PCL (portable class library).

Для достижения цели производительности, когда Knight класс инициализируется, он сбрасывает доску и предварительно вычисляет ходы для каждой позиции.

1. Location класс:
public class Location // a Knight's move
{
    public Location(int cols, int rows, int index)
    {
        this.cols = cols;
        this.rows = rows;
        this.index = index;
    }

    public Location(int cols, int rows, int index, int moveNum)
        : this(cols, rows, index)
    {
        this.moveNum = moveNum;
    }

    int cols, rows, iRow, col, row, index, moveNum;

    public int MoveNum => moveNum;

    public int Index => index;

    public int Col
    {
        get
        {
            if (col == 0) calcCoords();
            return col;
        }
    }

    public int Row
    {
        get
        {
            if (row == 0) calcCoords();
            return row;
        }
    }

    private void calcCoords()
    {
        col = index % cols;
        row = index / cols;
        iRow = rows - row;
    }

    public override string ToString()
    {
        if (col == 0) calcCoords();
        if (col < 26) return $"{(char)(col % 26 + 'A')}-{iRow}";
        if (col < 52) return $"{new string('A', col / 26) + (char)(col % 26 + 'A')}-{iRow}";
        return $"{"AZ" + (col - 52).ToString()}-{iRow}";
    }
}
2. Board класс & интерфейс:
using System.Collections.Generic;

public interface IBoard
{
	int Columns { get; }
	List<List<int>> Locations { get; }
	IEnumerable<int> Missed { get; }
	int Rows { get; }
	IRule Rules { set; }
	bool[] Visited { get; }

	Location Init(int? cellId = default(int?));
	void ResetVisits();
	void UndoVisit(int index);
} 

public class Board : IBoard
{
    public Board(int columns, int rows)
    {
        Columns = columns;
        Rows = rows;
        Size = columns * rows;
    }

    public int Size { get; }

    public int Rows { get; } = 8;

    public int Columns { get; } = 8;

    public List<List<int>> Locations { get; private set; }
        = new List<List<int>>();

    public IEnumerable<int> Missed
        => Locations.Where((x, i) => !Visited[i]).Select((x, i) => i);

    private static bool[] visited;
    public bool[] Visited => visited;

    public IRule Rules { private get; set; }


    public Location Init(int? locationId = null)
    {
        totalLocations = Columns * Rows;
        BuildMovesTable();
        return new Location(Columns, Rows,
			locationId.HasValue && locationId.Value > -1 
				? locationId.Value : r.Next(0, totalLocations), 0);
    }

    public void ResetVisits()
    {
        visited = new bool[totalLocations];
    }

    public void UndoVisit(int index)
    {
        Visited[index] = false;
    }

    private int totalLocations;
    private Random r = new Random();

    private void BuildMovesTable()
    {
        ResetVisits();
        RebuildTable();
    }

    private void RebuildTable()
    {
        Locations = Enumerable.Range(0, totalLocations)
                                .Select(x => Rules.BuildLocation(x))
                                .ToList();
    }
}
3. Knight класс усилителя; IRule интерфейс:
using System.Collections.Generic;

public interface IRule
{
	List<int> BuildLocation(int index);
} 

public class Knight : IRule
{
	public Knight(IBoard board, int? startLocation = null)
	{
		Board = board;
		board.Rules = this;
		Init(startLocation);
	}

	public void Init(int? startLocation)
	{
		Board.ResetVisits();
		Moves = new Stack<Location>();
		Moves.Push(Board.Init(startLocation));
		CanMoveNext = true;
	}

    public IBoard Board { get; }

    public Location Start => Moves?.Last();

    public Location Current => Moves?.Peek();

    public Stack<Location> Moves { get; private set; }

    public bool CanMoveNext { get; private set; }

    public void ExecuteMoves()
    {
        while (true) { if (MoveNext() == null) break; }
    }

    public Location MovePrevious()
    {
        if (Moves.Count > 0) Board.Visited[Moves.Pop().Index] = false;
        CanMoveNext = true;
        return Moves.Count > 0 ? Moves.Peek() : null;
    }

    public Location MoveNext()
    {
        var index = Moves.Peek().Index;
        var c1 = Board.Locations[index];
        int ndx = 0, score = int.MaxValue;

        for (int i = 0; i < c1.Count; i++)
            if (!Board.Visited[c1[i]] && c1[i] != index)
            {
                var tscore = 0;
                var c2 = Board.Locations[c1[i]];
                for (int j = 0; j < c2.Count; j++)
                    if (!Board.Visited[c2[j]] && c2[j] != i) tscore++;

                if (tscore < score)
                {
                    ndx = c1[i];
                    score = tscore;
                }
            }

        Board.Visited[index] = true;

        CanMoveNext = score != int.MaxValue;
        if (CanMoveNext)
        {
            var newLoc = new Location(Board.Columns, Board.Rows, ndx, Moves.Count);
            Moves.Push(newLoc);
            return newLoc;
        }
        return null;
    }

    List<int> IRule.BuildLocation(int index)
    {
        var loc = new List<int>();
        int pc = index % Board.Columns, pr = index / Board.Columns;
        for (int k = 0; k < rules.GetLength(0); k++)
        {
            int nc = pc + rules[k, 0], nr = pr + rules[k, 1];
            if (nc < Board.Columns && nc > -1 && nr < Board.Rows && nr > -1)
                loc.Add(nr * Board.Columns + nc);
        }
        return loc;
    }

    private readonly int[,] rules = new int[,]
    {
    { -1, -2 }, {  1, -2 }, {  2, -1 }, {  2,  1 },
    {  1,  2 }, { -1,  2 }, { -2,  1 }, { -2, -1 }
    };
}

Доказательства Оспаривания


Этот проект тестирует основной код на нескольких различных размерах и размерах плат для a). завершение задачи; б). представление.
using System;
using System.Linq;
using System.Diagnostics;
using System.Collections.Generic;
using KnightsTour.Core;

static class Program
{
    static void Main()
    {
        ResetWindow();
        Console.WriteLine("Weekly Challenge: Knight's Tour");
        Console.WriteLine("===============================\n");

        var styles = new List<IReportStyle>
        {
            new ChessStyle(),
            new IndexedStyle(),
            new LocationStyle()
        };

        foreach (var tour in new List<Tour>
        {
            new Tour("Standard Chess Board (8 x 8)", () => Activity(8, 8, null)),
            new Tour("Smallest Viable Rectangle (4 x 3)", () => Activity(4, 3, 0)),
            new Tour("2nd Smallest Viable Rectangle (7 x 3)", () => Activity(7, 3, 0)),
            new Tour("Smallest Viable Square (5 x 5)", () => Activity(5, 5, 0)),
            new Tour("Large Square Board", () => Activity(20, 20, null)),
            new Tour("Very Large Square Board", () => Activity(300, 300, 89700)),
        })
            // choose a reporting style format...
            Report(tour.Activity(), styles[(int)ReportStyle.Chess]);

        Console.WriteLine("\n-- press any key to exit --");
        Console.ReadKey();
        Console.CursorVisible = true;
    }

    private static Tuple<TimeSpan, Knight> 
		Activity(int cols, int rows, int? startLocation)
    {
        TimeSpan elapsed;
        var sw = new Stopwatch();

        var knight = new Knigh

Maciej Los

Ну, а что сказать о версии 13? - Ух ты!
5ед!

Graeme_Grant

Спасибо! Крис действительно просил "еще более высокие подвиги безумия"... :)

Рейтинг:
0

Arthur V. Ratz

Вот мое решение, основанное на алгоритме кратчайшего пути:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace KnightChess
{
    class KnightMove
    {
        public bool ChessToIndex(string sMove, ref int Row, ref int Col)
        {
            if ((sMove[0] >= 'A' && sMove[0] <= 'H') &&
                (sMove[1] >= '1' && sMove[1] <= '8'))
            {
                Col = System.Convert.ToInt32(sMove[0]) - 0x41;
                Row = System.Convert.ToInt32(sMove[1].ToString()) - 1;
        
                return true;
            }

            return false;
        }

        public bool IndexToChess(ref string sMove, int Row, int Col)
        {
            sMove += Convert.ToChar(Col + 0x41);
            sMove += Convert.ToString(Row + 1);

            return true;
        }
        public KnightMove(int Row, int Col)
        {
            this.Row = Row; this.Col = Col;
        }
        public KnightMove(string sMove)
        {
            int Row = -1, Col = -1;
            if (this.ChessToIndex(sMove, ref Row, ref Col) != false)
                this.Row = Row; this.Col = Col;
        }

        public int Row
        {
            get { return m_Row; }
            set { m_Row = value; }
        }
        public int Col
        {
            get { return m_Col; }
            set { m_Col = value; }
        }

        private int m_Row = -1;
        private int m_Col = -1;
    }

    class Corner
    {
        public Corner(KnightMove mv1, KnightMove mv2)
        {
            this.Move1 = mv1; this.m_Move2 = mv2;
        }

        public KnightMove Move1
        {
            get { return m_Move1; }
            set { m_Move1 = value; }
        }
        public KnightMove Move2
        {
            get { return m_Move2; }
            set { m_Move2 = value; }
        }

        private KnightMove m_Move1;
        private KnightMove m_Move2;
    }

    class KnightMoves : ICloneable
    {
        public KnightMoves() { }
        public KnightMoves(List<KnightMove> Path, int Length)
        {
            this.Path = Path; this.Length = Length;
        }

        public List<KnightMove> Path
        {
            get { return m_Path; }
            set { m_Path = value; }
        }

        public int Length
        {
            get { return m_Length; }
            set { m_Length = value; }
        }

        private int m_Length = -1;
        private List<KnightMove> m_Path = null;

        public object Clone()
        {
            KnightMoves Target_Moves = new KnightMoves();
            Target_Moves.m_Length = Length;
            Target_Moves.Path = new List<KnightMove>();
            foreach (KnightMove km in this.Path)
                Target_Moves.Path.Add(km);
            return Target_Moves;
        }
    }

    class KnightPaths : IEnumerable<KnightMoves>
    {
        private List<KnightMoves> m_PathList = null;
        public KnightPaths()
        {
            if (m_PathList == null)
                m_PathList = new List<KnightMoves>();
        }

        public KnightPaths(KnightPaths Knight_Path)
        {
            m_PathList = new List<KnightMoves>();
            foreach (KnightMoves km in Knight_Path)
                m_PathList.Add(km);
        }

        public void Add(KnightMoves Move)
        {
            m_PathList.Add(Move);
        }
        public KnightMoves this[int iIndex]
        {
            get { return m_PathList[iIndex]; }
            set { m_PathList[iIndex] = value; }
        }
        public int Count() { return m_PathList.Count(); }
        public void Clear() { m_PathList.Clear(); }

        public IEnumerator GetEnumerator()
        {
            return m_PathList.GetEnumerator();
        }
        IEnumerator<KnightMoves> IEnumerable<KnightMoves>.GetEnumerator()
        {
            return (IEnumerator<KnightMoves>)this.GetEnumerator();
        }
    }
    class Program
    {
        static bool IsValidMove(int value1, int value2, int PathID)
        {
            if ((value1 > value2) && (PathID == 0 || PathID == 1) ||
                (value1 < value2) && (PathID == 2 || PathID == 3)) return true;

            return false;
        }
        static bool IsValidPath(int Row1, int Col1, int Row2, int Col2, int PathID)
        {
            if (((((Row1 == 0 && Col1 == 5) &&
                   (Row2 == 1 && Col2 == 7)) ||
                  ((Row1 == 0 && Col1 == 6) &&
                   (Row2 == 2 && Col2 == 7))) && (PathID == 0)) ||
 
                ((((Row1 == 5 && Col1 == 7) &&
                   (Row2 == 7 && Col2 == 6)) ||
                  ((Row1 == 6 && Col1 == 7) &&
                   (Row2 == 7 && Col2 == 5))) && (PathID == 1)) ||

                ((((Row1 == 7 && Col1 == 2) &&
                   (Row2 == 6 && Col2 == 0)) ||
                  ((Row1 == 7 && Col1 == 1) &&
                   (Row2 == 5 && Col2 == 0))) && (PathID == 2)) ||

                ((((Row1 == 2 && Col1 == 0) &&
                   (Row2 == 0 && Col2 == 1)) ||
                   ((Row1 == 1 && Col1 == 0) &&
                   (Row2 == 0 && Col2 == 2))) && (PathID == 3))) return true;

            return false;
        }
        static void Main(string[] args)
        {
            string _StartMove = "";
            Console.Write("Start At: ");
            _StartMove = Console.ReadLine();

            Console.WriteLine();

            KnightPaths Knight_Paths = new KnightPaths();
            KnightMoves Knight_Moves = new KnightMoves();

            Knight_Moves.Path = new List<KnightMove>();

            Knight_Moves.Length = 1;
            Knight_Moves.Path.Add(new KnightChess.KnightMove(_StartMove));

            Knight_Paths.Add(Knight_Moves);

            KnightPaths Knight_Paths2 = new KnightPaths();

            List<Corner> Corners = new List<Corner>();
            Corners.Add(new Corner(new KnightMove(0, 5), new KnightMove(1, 7)));
            Corners.Add(new Corner(new KnightMove(0, 6), new KnightMove(2, 7)));

            Corners.Add(new Corner(new KnightMove(5, 7), new KnightMove(7, 6)));
            Corners.Add(new Corner(new KnightMove(6, 7), new KnightMove(7, 5)));

            Corners.Add(new Corner(new KnightMove(7, 2), new KnightMove(6, 0)));
            Corners.Add(new Corner(new KnightMove(7, 1), new KnightMove(5, 0)));

            Corners.Add(new Corner(new KnightMove(2, 0), new KnightMove(0, 1)));
            Corners.Add(new Corner(new KnightMove(1, 0), new KnightMove(0, 2)));

            var watch = new System.Diagnostics.Stopwatch();
            watch.Start();

            for (int PathID = 0; PathID < 4; PathID++)
            {
                for (int Route = 0; Route < Knight_Paths.Count(); Route++)
                {
                    KnightMoves CurrPath = Knight_Paths[Route];

                    if (Knight_Paths[Route].Path.Count() > 1)
                    {
                        if (IsValidPath(CurrPath.Path[Knight_Paths[Route].Path.Count() - 2].Row,
                                        CurrPath.Path[Knight_Paths[Route].Path.Count() - 2].Col,
                                        CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row,
                                        CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col, PathID))
                        {
                            Knight_Paths2.Add(new KnightMoves(CurrPath.Path, CurrPath.Path.Count()));
                        }
                    }

                    if (((CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row + 1) < 8) &&
                        ((CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col + 2) < 8))
                    {
                        bool Exists = false;
                        for (int Index = 0; Index < CurrPath.Path.Count() && !Exists; Index++)
                            if (CurrPath.Path[Index].Row == CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row + 1 &&
                                CurrPath.Path[Index].Col == CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col + 2)
                                Exists = true;

                        int value1 = 0, value2 = 0;
                        if (PathID == 0 || PathID == 2)
                        {
                            value1 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col + 2;
                            value2 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col;
                        }

                        if (PathID == 1 || PathID == 3)
                        {
                            value1 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row + 1;
                            value2 = CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row;
                        }

                        if (Exists == false && IsValidMove(value1, value2, PathID))
                        {
                            KnightMoves NewPath = (KnightMoves)CurrPath.Clone();
                            NewPath.Length = Knight_Paths[Route].Length + 1;
                            NewPath.Path.Add(new KnightMove(CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row + 1,
                                CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Col + 2));

                            Knight_Paths.Add(NewPath);
                        }
                    }

                    if (((CurrPath.Path[Knight_Paths[Route].Path.Count() - 1].Row - 1) >= 0) &&
                        ((CurrPath.Path[Knight

Thomas Daniels

"Ходы = 14" невозможны для доски 8х8, если вы хотите посетить все квадраты. Я что-то упустил?

Arthur V. Ratz

ProgramFox, все эти два пути:

0. (A;1) (C;2) (E;3) (F;1) (H;2) (G;4) (H;6) (G;8) (E;7) (C;8) (A;7) (B;5) (A;3) (B;1) Ходов = 14
1. (A;1) (B;3) (D;2) (F;1) (H;2) (G;4) (H;6) (G;8) (E;7) (C;8) (A;7) (B;5) (A;3) (B;1) Ходов = 14

* ЯВЛЯЮТСЯ * * ДЕЙСТВИТЕЛЬНЫМИ*. Первый и второй пути действительно касаются всех квадратов:

(F; 1), (H;2) - 1-й угол
(H; 6), (G; 8) - 2-й угол
(С; 8), (а;7) - 3-й угол
(А; 3), (Б;1) - 4-й угол

Это все. Если у вас есть еще какие-либо комментарии или вопросы, просто отправьте свое сообщение.

Thomas Daniels

Я этого не понимаю. Прикосновение ко всем квадратам на доске 3х3 означает, что у вас есть 63 хода, не так ли? Просто "перемещение по квадрату с конем" не считается "прикосновением", Если вы это сделали.

Arthur V. Ratz

если это не так, то что значит "прикоснуться к квадрату", если не иначе ??

Thomas Daniels

Прикосновение к квадрату означает, что квадрат используется в качестве начальной и конечной точки нового рыцарского прыжка. Посмотрите GIF-файлы на этой странице Википедии, чтобы понять, что я имею в виду: https://en.wikipedia.org/wiki/Knight ' s_tour

Graeme_Grant

Все просто, действуют шахматные правила...

Arthur V. Ratz

Кроме того, я считаю, что мое решение довольно эффективно, поскольку оно позволяет выбрать наиболее подходящий путь из множества всех возможных путей, найденных предложенным мной кодом.

Arthur V. Ratz

Разнообразие путей, создаваемых следующим кодом, также включает в себя полный путь, указанный в вопросе, например:

Пример:

Время начала: А1
Решение: A1 – B3-C5 и т. д.

Ответ: Вот что:
(A;1) (B; 3) (C; 5) (D; 3) (E; 1) (F; 3) (G; 1) (H; 3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2) (C;1) Ходов = 17

PIEBALDconsult

Рыцарь не "прикасается" к квадратам, через которые он перепрыгивает.
И если это так, я уверен, что у вас там должно быть много множественных касаний.

Arthur V. Ratz

У меня уже есть несколько касаний, например: (F; 1), (H;2) и (G;1), (H;3).

Например: (A;1) (B; 3) (D;2)(F;1)(H;2)(G;4)(H;6)(G;8)(E;7)(C;8)(A;7)(B;5)(A;3) (B;1) ходы = 14-касания (F;1), (H;2),

тогда как (A;1)(C;2)(E;1)(F;3)(G;1)(H;3)(G;5)(H;7)(F;8)(D;7)(B;8)(A;6)(B;4)(A;2) (C;1) движется = 15 - касается(G;1), (H;3).

Arthur V. Ratz

Я имею в виду, что уже есть несколько путей, которые включают верхний правый угол шахматной доски, нависая конем над любым (F;1), (H;2) или (G;1), (H;3).

PIEBALDconsult

Рыцари не"парят". Имеют значение только те места, где рыцарь отдыхает после хода.

Arthur V. Ratz

Множество мнений ? Это хорошо.

Graeme_Grant

Сетка 8 х 8 имеет фиксированное количество ходов - 8 х 8 - 1 = 63 (не считая стартового квадрата). Теперь же избранный путь - это совсем другая история... ;)

Arthur V. Ratz

Нет, это неправильно. Обычно шахматный стол 8х8 имеет около 26 534 728 821 064 направленных закрытых туров. Я имею в виду https://en.wikipedia.org/wiki/Knight ' s_tour

Thomas Daniels

Да, это и есть граф различные закрытые туры. Но один закрытый тур состоит из 1 стартовой площади и 63 хода.

Arthur V. Ratz

Извините, но Graeme_Grant заявил, что сетка 8 x 8 имеет фиксированное количество ходов - 8 x 8 - 1 = 63...

Thomas Daniels

И он прав. Но это фиксированное количество ходов для одного рыцарского тура.

Arthur V. Ratz

Согласно постановке задачи, не имеет значения, сколько ходов делает конь, но он должен касаться всех углов. Другими словами, количество ходов не может быть критерием правильности для данного конкретного случая.

Graeme_Grant

Там нет упоминания об углах, только рыцарь перепрыгивает через шахматную доску так, чтобы она касалась всех квадратов, но этот рыцарь никогда не может использовать одно и то же место дважды, не примыкает к нему.

PIEBALDconsult

Где написано "дотронься до всех углов"?

Graeme_Grant

... что является требованием вызова. ;)

Arthur V. Ratz

Количество ходов не может быть требованием вызова. Об этом не было сказано ни слова.

Graeme_Grant

Нет, но подразумевается прикосновение ко всем квадратам, а не к углам...

Arthur V. Ratz

О, Возможно, вы этого не понимаете. Если рыцарь должен коснуться квадрата в точке, где он останавливается, вы никогда не построите путь, в котором рыцарь касается всех квадратов таким образом.

Graeme_Grant

"рыцарь перепрыгивает через шахматную доску так, чтобы она касалась всех квадратов"- более подробную информацию об этом можно найти здесь: Рыцарский тур - Википедия[^]

PIEBALDconsult

Правильно, и новички должны также отметить, что рыцарь прыгает _straight_ из одного пространства в другое; _not_ в L-образной форме.

Graeme_Grant

только с наклоном, а не перпендикулярно.. ;)

Arthur V. Ratz

да, это так.

Arthur V. Ratz

В этом никто не сомневается. В моем решении конь прыгает прямо, например: (F;1) - > (H;2) и так далее.

Arthur V. Ratz

Извините, но я тоже ссылаюсь на статью Википедии, но, прочитав эту статью, я не нашел, что она была упомянута непосредственно. Я имею в виду анимированную шахматную доску, иллюстрирующую ходы коня. Он по-прежнему обычно касается всех углов, касаясь обеих сторон угла. Посмотрите на это более внимательно.

Graeme_Grant

Нарисуйте сетку 8 х 8, поставьте крестик в каждой ячейке, которую найдет ваше решение. Если какие-то клетки пусты, значит, тест не прошел.

PIEBALDconsult

"Коснуться" означает "приземлиться", а не" приземлиться рядом "или"зависнуть".

Arthur V. Ratz

да, определенно, чтобы "зависнуть".

Graeme_Grant

Мы просто пытаемся вам помочь... Сделайте это по-своему, и мы узнаем результат через несколько дней...

Arthur V. Ratz

Мне очень жаль, но это единственное решение этой проблемы, которое я нашел. У меня нет других способов решить эту проблему, кроме этого.

Graeme_Grant

На всякий случай, если вы раньше не играли в шахматы: Краткое изложение правил игры в шахматы[^]- Обратите внимание, как движется конь в отличие от слона или ферзя...

Arthur V. Ratz

Обычно он способен сделать 8 ходов. Ну и что ?

Graeme_Grant

Я попросил Криса пояснить, что именно означает слово "прикосновения". Надеюсь, он скоро обновит заметки о вызове.

Arthur V. Ratz

О'Кей. Без проблем. Я приму во внимание последнее обновление проблемы.

Arthur V. Ratz

Насколько я понимаю, согласно вашей теории, рыцарь не может коснуться всех квадратов, остановившись на отдых на каждом из четырех квадратов шахматной доски. Это невозможно.

Graeme_Grant

Нанесите на сетку шаги/ходы в моем решении, и вы увидите, что это не так.

Arthur V. Ratz

Мне очень жаль, но вы допустили ошибку D-4, E-2, G-1, H-2, G-5, H-6, F-8, G-6, H-7, F-7, H-5, G-8, E-7, C-8, A-7, B-5, A-3, B-1, C-3, A-2, C-1, B-3, A-1, C-2, E-1, G-2, H-3, F-3, H-1, F-1, F-1, F-1, F-1, F-1, F-1, F-1, F-1, F-1, F-1, F-1, F-1, F-1, F-1, F-1, F-1, F-1, F-1, F-1, F-1, F-1, F-1, F-1, F-1, F-1, F-2,-1, d-2, e-4, G-3, h-0, f-2, D-1, B-2, A-4, B-6, A-8, C-7, E-8, G-7, H-4, F-4, E-6, D-8, B-7, D-6, F-5, E-3, D-5, F-6, G-4, E-5, C-4, A-5, C-6, B-8, D-7, C-5, D-3, b-4, A-6

Рыцарь не может перейти от G-1 к H-2. Просто сверьтесь с шахматной доской. :Д

Graeme_Grant

Да, извини за это, засекли час назад. Существует ошибка в моем отображении переопределения строки для вывода решения. Однако решение правильное. У меня есть обновление, ожидающее завершения того, над чем я работаю, но я сделаю это сейчас. Дай мне пару минут, и я все обновлю...

[edit:] обновлено с поправкой на вывод...

Member 14361425

https://gamesroute.com/how-to-play-chess/

Graeme_Grant

:Д

Graeme_Grant

Эй, мы увидим решение от вас на этой неделе?

Arthur V. Ratz

Какое решение вы ожидаете увидеть ? Для этой проблемы я уже опубликовал решение (см. Решение 2).

Arthur V. Ratz

Как я уже объяснял, нет подходящего решения, в котором конь останавливается во всех четырех углах шахматной доски.

Рейтинг:
0

PIEBALDconsult

Ну, МММ, мое решение еще не завершено. Эта проблема на самом деле мне не интересна, но у меня есть исчерпывающая реализация обратного отслеживания грубой силы, которая, теоретически, может найти все туры. Учитывая доску 6х6, он нашел то, что говорит, что все туры из квадрата (0,0) примерно за час. Но, учитывая шахматную доску (8х8), она работает уже два дня и пока не сообщила никаких результатов.

Все, что я действительно готов сказать на данный момент,-это то, что я использую Граф (сеть) узлов, а не двумерное представление платы. И никакой рекурсии.

Я не заинтересован в поиске один тур или какой-нибудь тур, я ищу закрытый тур, и мне лень переписывать его из сети; я хочу найти его сам.

Закрытый рыцарский тур из какой-нибудь площадь-это закрытый рыцарский тур от каждый площадь.

Во всяком случае, мой план решения этой проблемы таков::
Учитывая (ну, не подаренный, как было сказано выше) закрытый рыцарский тур по шахматной доске...
Жесткий код этого тура и просто используйте его каждый раз.
Какой бы квадрат ни был указан в качестве стартового места, начните с него в жестко закодированном туре и совершите тур.
Сделано
(Я постараюсь держать вас в курсе.)

Сказав это и имея реализацию обхода графов, я теперь рассматриваю возможность обобщения своего кода для решения более общих вопросов обхода графов. На самом деле, есть загадка середины 80-х, которую я совершенно не смог решить, которая иногда приходит мне на ум (как белый кит), и я думаю, что смогу применить к ней эту технику.


Обновление: после работы в течение целой недели - используя 100% одного виртуального процессора - мой код вообще не нашел туров. Время убить его и найти проблему...