Задача о шахматном коне (нерекурсивный алгоритм обхода)

Пока я "сочиняю" следующую тему, предлагаю рассмотреть задачу об обходе шахматным конём шахматной доски (каламбур получился :)). Для адекватного восприятия материала рекомендую предварительно просмотреть/изучить все темы до 26 включительно.

Дана шахматная доска. На ней есть только одна фигура - конь. Как известно, конь в шахматах ходит буквой "Г". Задача - посетить все клетки шахматного поля, при этом остановиться в каждой клетке конь может только один раз. Например, конь стартует из позиции B1:

     A  B  C  D  E  F  G  H   
  8  9 22  7 14 11 64 19 16  8
  7  6 13 10 21 18 15 26 63  7
  6 23  8  5 12 25 20 17 28  6
  5  4 57 24 51 30 27 62 49  5
  4 55 32  3 58 45 50 29 40  4
  3  2 35 56 31 52 41 48 61  3
  2 33 54 37 44 59 46 39 42  2
  1 36  1 34 53 38 43 60 47  1
     A  B  C  D  E  F  G  H   

Обход нерекурсивный. Старый добрый брутфорс во всей красе 🙂 Зато память не жрёт и работает шустро!

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

  6 8
5 7
X
1 3
  2 4

Реализуем эти ходы с помощью двух одномерных массивов (массивы объявлены как константы, это защитит их от случайного изменения). Один отвечает за смещение по строкам (по вертикали), а другой по столбцам (по горизонтали). Примем точку, в которой стоит конь (в таблице - X) за 0, тогда ходы из таблицы можно записать так:

Step_Row : constant array(1..8) of Integer := (-1, -2, -1, -2, 1, 2, 1, 2); --Вертикаль
Step_Col : constant array(1..8) of Integer := (-2, -1, 2, 1, -2, -1, 2, 1); --Горизонталь

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

with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
with Ada.Characters.Handling; use Ada.Characters.Handling;
with Ada.Strings.Fixed; use Ada.Strings.Fixed; --Для поиска в строке
 
procedure main is
    Cell_Size : constant Integer := 3; --Размер ячейки (3 - для удобства вывода)
    Board_Size : constant Integer := 10; --Размер доски
    Horse_Col, Horse_Row : Integer := 0; --Координаты коня на доске
 
    --Так как недавно была пройдена тема про записи, используем для решения задачи записи,
    --хотя можно использовать пару массивов. В данном случае, если курсор при выводе массива
    --будет находится в служебных клетках (литеры A-H и т.д.), то выводить будем поле
    --типа Character, иначе - Integer;
    type Cell is Record
        Lit : Character; --Литера клетки (A-H, 1-8)
        Val : Integer; --Номер хода
        --Для запоминания хода, приведшего коня в текущую позицию (если вдруг придётся
        --делать шаг назад):
        Step_Index : Integer;
 
    end Record;
 
    --Размер шахматной доски (8х8 + по одной клетке с каждой стороны на имена клеток):
    type Chess_Board is array(1..Board_Size, 1..Board_Size) of Cell;
 
    Board : Chess_Board;
    --------------------------------------------------------------------
    procedure Show_Board(Board : in Chess_Board) is
    --Показывает шахматную доску
    begin
        for i in 1..Board'Last(1) loop
            --так как ширина ячейки - 3 символа, а клетка квадратная, то выводим в начале
            --и конце каждой строки массива по одной пустой строке
            New_Line;
            for j in 1..Board'Last(2) loop
                --Если клетка была посещена, то Val в ячейке не 0, он равен номеру хода
                if Board(i, j).Val > 0 then
                    Put(Item => Board(i, j).Val, Width => Cell_Size);
                else --Если клетка не посещена, то Val в ячейке равен 0, => проверяем литеру
                    if Board(i, j).Lit = ' ' then --Если ячейка с литерой пуста
                        for i in 1..Cell_Size loop --выводим пробелы
                            Put(' ');
                        end loop;
                    else --Если литера не пуста
                        --Выводим символ и дополняем ширину поля вывода пробелами (ширина ячейки - 3)
                        for i in 1..Cell_Size - 1 loop
                            Put(' ');
                        end loop;
                        Put(Board(i, j).Lit);
                    end if;
                end if;
            end loop;
            New_Line;
        end loop;
    end Show_Board;
    --------------------------------------------------------------------
    procedure Set_Board(Board : out Chess_Board) is
    --Первоначальное заполнение доски пустыми значениями (шагов ещё не было)
        --Буквенное обозначение клетки (Имя клетки по горизонтали)
        Alph : constant array(1..10) of Character := (' ', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', ' ');
        --Цифровое обозначение клетки (Имя клетки по вертикали)
        Num : constant array(1..10) of Integer := (0, 8, 7, 6, 5, 4, 3, 2, 1, 0);
    begin
        for i in Board'Range(1) loop
            for j in Board'Range(2) loop
                if i = 1 or else i = 10 then --Если служебные клетки (литеры A-H)
                    Board(i, j).Lit := Alph(j);
                    Board(i, j).Val := 0;
                elsif j = 1 or else j = 10 then --Если служебные клетки (цифры 1-8)
                    Board(i, j).Val := Num(i);
                    Board(i, j).Lit := ' ';
                else --Если игровые клетки 
                    Board(i, j).Val := 0;
                    Board(i, j).Lit := ' ';
                end if;
                Board(i, j).Step_Index := 0;
            end loop;
        end loop;
    end Set_Board;
    --------------------------------------------------------------------
    procedure Get_Horse_Pos(Horse_Col, Horse_Row : in out Integer) is
    --Получить от пользователя начальную позицию коня
        str : String(1..2);
        str_len : Integer;
    begin
        loop
            Put("Введите первоначальное положение коня на доске (A1, E2, D3 и т.д): ");
            Get_Line(Item => str, Last => str_Len);
            if str_len = str'Last then
                Skip_Line;
            end if;
            --Обработка пользовательского ввода:
            --Если буква-имя поля введена в нижнем регистре, то привести её к верхнему регистру
            str(1) := To_Upper(str(1));
            --Проверка вхождения введенного имени поля в допустимый диапазон
            if str(1) in 'A'..'H' and then str(2) in '1'..'8' then
                exit; --Если всё корректно, то выходим из цикла
            end if;
        end loop;
        --Итоговые координаты коня
        Horse_Col := 1 + Index("ABCDEFGH", str(1..1)); --Index - поиск подстроки в строке
        Horse_Row := Board_Size - Integer'Value(str(2..2));
    end Get_Horse_Pos;
    --------------------------------------------------------------------
    procedure Visitation(Board : in out Chess_Board; Horse_Row, Horse_Col : in out Integer) is
    --Обход доски. Основной алгоритм данной задачи.
        --Все возможные шаги по строкам и столбцам (всего 8). По одному и тому же индексу
        --берётся смещение из двух массивов. Одно значение - смещение по строкам,
        --второе - по столбцам:
        Step_Row : constant array(1..8) of Integer := (-1, -2, -1, -2, 1, 2, 1, 2);
        Step_Col : constant array(1..8) of Integer := (-2, -1, 2, 1, -2, -1, 2, 1);
        Step : Integer := 1;
        i : Integer := 0;
    begin
        loop
            i := i + 1;
            if i <= 8 then --Если не вышли за пределы массивов Step_Row и Step_Col
                --Если ход не приведёт к выходу коня за пределы поля и в предлагаемой позиции конь
                --ещё не был:
                if (Horse_Row + Step_Row(i) > 1 and then Horse_Row + Step_Row(i) < 10)
                 and then (Horse_Col + Step_Col(i) > 1 and then Horse_Col + Step_Col(i) < 10)
                 and then Board(Horse_Row + Step_Row(i), Horse_Col + Step_Col(i)).Val = 0 then
                    Step := Step + 1;
                    Horse_Row := Horse_Row + Step_Row(i);
                    Horse_Col:= Horse_Col + Step_Col(i);
                    Board(Horse_Row, Horse_Col).Val := Step;
                    --В эту позицию привел ход с номером:
                    Board(Horse_Row, Horse_Col).Step_Index := i;
                    i := 0; --Двигаемся дальше
                end if;
            else --Шаг назад
                Board(Horse_Row, Horse_Col).Val := 0;
                i := Board(Horse_Row, Horse_Col).Step_Index;
                Board(Horse_Row, Horse_Col).Step_Index := 0;
                Horse_Row := Horse_Row - Step_Row(i);
                Horse_Col:= Horse_Col - Step_Col(i);
                Step := Step - 1;
            end if;
            --Вывод промежуточного результата на каждом 32 шаге,
            --чтобы видеть работу программы (что она не зависла)
            --Можно закомментировать следующие 3 строки, тогда промежуточного вывода не будет
            --и решение будет найдено немного быстрее:
            if Step rem 32 = 0 then
                Show_Board(Board);
            end if;
 
            --Если все ячейки доски посещены (т.е. в данном случае доска 8х8, 
            --следовательно последний ход имеет номер 64), то выходим из цикла,
            --Обход завершен.
            exit when Step = (Board_Size - 2) ** 2;
            --Если обход невозможен, т.е. мы вернулись в позицию, с которой начинали
            --и при этом перепробовали все 8 ходов из данной позиции.
            if i = 8 and Step = 1 then
                Put_Line("Обход из указанной позиции невозможен!");
                exit;
            end if;
        end loop;
    end Visitation;
    --------------------------------------------------------------------
begin
    --Создать доску
    Set_Board(Board);
    --Показать пустую доску
    Show_Board(Board);
    --Получить начальную позицию коня
    Get_Horse_Pos(Horse_Col, Horse_Row);
    --Установить позицию коня
    Board(Horse_Row, Horse_Col).Val := 1;
    --Показать доску с начальной позицией коня
    --Show_Board(Board);
    --Обход доски
    Visitation(Board, Horse_Row, Horse_Col);
    --Вывод результата
    Show_Board(Board);
end main;

На процессоре i3 решение из начальных позиций, где по правилам игры изначально стоит конь заняло:

  • Из позиции B1 ~ 2.5 - 3 сек
  • Из позиции B8 ~ 10 мин
  • Из позиции G1 ~ 2 мин
  • Из позиции G8 ~ 1 сек

Из позиции D5 решение было найдено меньше, чем за секунду, а из A1 - за 5 минут.

Если кому-то интересно, то можно модифицировать задачу, например, дав пользователю возможность вводить размер доски. Но!.. При увеличении поля время поиска решения будет значительно увеличиваться.

В данном решении время обхода очень сильно зависит от заданной последовательности ходов:

Step_Row : constant array(1..8) of Integer := (-1, -2, -1, -2, 1, 2, 1, 2);
Step_Col : constant array(1..8) of Integer := (-2, -1, 2, 1, -2, -1, 2, 1);

То есть, можно так подобрать последовательность, что решение будет найдено при первом же проходе из начальной точки, т.е. в данном случае на шаге (-1, -2). А может быть найдено и на последнем (2, 1), т.е. из начальной точки будут сначала проверены 7 ходов, а это займёт очень много времени, и только ход № 8 со стартом из начальной точки (2, 1) приведёт к решению задачи.

P.S.: Решение обкатал на нескольких стартах, вроде бы всё работает. Если найдёте ошибки - пишите, всё поправлю. И ещё: результата, когда обход доски невозможен, я не дождался. Уж очень долго придётся ждать полного обхода + нужно знать, из какой клетки обход невозможен, т.к. методом научного тыка можно целый год искать эту клетку (ну или эти клетки).

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *