Классические задачи программирования. Путешествие коня.

Владимир | | C++.

Эта интересная головоломка была предложена математиком Эйлером. Задание, на первый взгляд, достаточно простое – нужно шахматным конём, находящимся на произвольной клетке шахматной доски, обойти все остальные клетки доски. При этом на одну клетку можно походить только один раз.

Конь, как известно, ходит Г-образно. Т.е. на две клетки в каком-либо направлении (вверх, вниз, вправо, влево) и на одну клетку в перпендикулярном. Таким образом, конем, можно сделать максимум восемь различных ходов из заданной клетки (или меньше, если конь находится у края доски).

Для решения этой задачи на компьютере необходимо разработать правила, в соответствии с которыми компьютер будет выбирать ход. В принципе, очередной ход можно выбирать случайным образом. Но ожидать при этом хороших результатов может только большой оптимист. Интересный вариант выбора ходов предложен в книге «Как программировать на С++» Х.Дейтел, П.Дейтел.

Для его реализации нужны два двумерных массива (размер 8х8). В первый массив (board) записываем данные о том, ходили ли мы на какую-то клетку. Например, в начале все элементы массива равны нулю. Как только мы ставим коня на какую-либо клетку соответствующему элементу массива нужно присвоить единицу. Здесь все просто. Заполнение второго массива (accessibility — доступность) немного сложнее. Каждый его элемент, также как и в массиве board, соответствует клетке на доске, но здесь мы записываем информацию о том, со скольких клеток можно походить на заданную. Например, на клетку а1 можно походить из двух клеток (с2 и b3). Массив accessibility перед началом решения задачи имеет следующий вид:

2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2

Рис.1

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

Имея эти два массива выбрать ход не сложно. Нужно ходить на те клетки, для которых элементы массива accessibility имеют минимальное значение, а элементы массива board равны нулю.

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

Кроме этого, я хотел бы пояснить, как выполняется ход. Мы уже говорили, что существует восемь возможных ходов. Все они закодированы цифрами от 0 до 7. На рис. 2 показаны все возможные варианты ходов.

               
    2   1      
  3       0    
      K        
  4       7    
    5   6      
               
               

Рис.2

Каждый ход можно представить как перемещение на заданное количество клеток по горизонтали и по вертикали. Например, нулевому ходу соответствует перемещение на две клетки по горизонтали, и «-1» клетку по вертикали (знак минус указывает на направление перемещения). Для выполнения ходов удобно использовать следующие массивы:

int horizontal[] = {2, 1, -1, -2, -2, -1, 1, 2};
int vertical[] = {-1, -2, -2, -1, 1, 2, 2, 1};

Значения элементов этих массивов соответствуют перемещению по горизонтали и по вертикали для всех возможных ходов. Например, для выполнения хода 4 нужно выполнить две операции:

X += horizontal[4];
Y += vertical[4];

где, X и Y – текущие координаты (по горизонтали и вертикали, соответственно).

Скачать программу (knight.zip — 250kB)

Скачать исходники (knight_src.zip — 16,4kB) (Для компиляции необходим Borland C++ Builder 5)

Постовой

Выбираем надежный платный хостинг

  • nerevar

    Чувак, могу поспорить, что ты читал Дейтелов «Как программировать на С/С++». Я когда изучал С++ по этой книге тоже решал эти задачи (ну ещё про ферзей). Когда сравню твой вариант проги со своим напишу ещё коммент.

  • nerevar

    Чувак, могу поспорить, что ты читал Дейтелов «Как программировать на С/С++». Я когда изучал С++ по этой книге тоже решал эти задачи (ну ещё про ферзей). Когда сравню твой вариант проги со своим напишу ещё коммент.

  • Не надо спорить 🙂
    Прочитай последнее предложение в третьем абзаце 🙂

  • Не надо спорить 🙂
    Прочитай последнее предложение в третьем абзаце 🙂

  • potter

    Есть более интересная задачка — найти все возможные маршруты коня на этой( или другой) доске. Лет 15-ть назад для доски : 6х6 клеток я эту задачу решил. Есть мысли по поводу алгоритма?

    • С ходу в голову приходит только простой перебор, но для большой доски вариантов будет много.
      4 варианта хода из каждой точки (или меньше), если нужно сделать 35 ходов, то получим 4^35 вариантов. На самом деле будет меньше, т.к. с каждым следующим ходом вариантов будет оставаться все меньше.
      В общем, попробовать можно, но лень 🙂

    • Если знаете решение, напишите, пожалуйста, задача интересная.

  • potter

    Есть более интересная задачка — найти все возможные маршруты коня на этой( или другой) доске. Лет 15-ть назад для доски : 6х6 клеток я эту задачу решил. Есть мысли по поводу алгоритма?

    • С ходу в голову приходит только простой перебор, но для большой доски вариантов будет много.
      4 варианта хода из каждой точки (или меньше), если нужно сделать 35 ходов, то получим 4^35 вариантов. На самом деле будет меньше, т.к. с каждым следующим ходом вариантов будет оставаться все меньше.
      В общем, попробовать можно, но лень 🙂

    • Если знаете решение, напишите, пожалуйста, задача интересная.

  • Я тоже такую задачку решал, только на Qt

    • Не пробовали определить все возможные маршруты?

  • Я тоже такую задачку решал, только на Qt

    • Не пробовали определить все возможные маршруты?

  • Нет не пробывал. Задача была в качестве ДЗ

  • Нет не пробывал. Задача была в качестве ДЗ

  • Стас

    А можете сделать чтоб в данной задаче размерность доски была не фиксированной а могла задаваться?) Очень необходимо) Буду премного благодарен

    • Я последнее время переключился на web разработку и мне очень не хочется ставить IDE и вспоминать что я писал 2 года назад 🙂
      Но, насколько я помню, в этой задаче достаточно изменить размерность массивов board и accessibility.

      P.S. Для некоторых размеров доски задача может не иметь решений вообще.

  • Стас

    А можете сделать чтоб в данной задаче размерность доски была не фиксированной а могла задаваться?) Очень необходимо) Буду премного благодарен

    • Я последнее время переключился на web разработку и мне очень не хочется ставить IDE и вспоминать что я писал 2 года назад 🙂
      Но, насколько я помню, в этой задаче достаточно изменить размерность массивов board и accessibility.

      P.S. Для некоторых размеров доски задача может не иметь решений вообще.

  • Diana

    Zadacha ochen' interesnaya. Resheneie opisali vi ochen' detal'no i ponyatno.spasibo vi mne ochen' pomogli. 🙂

  • Diana

    Zadacha ochen' interesnaya. Resheneie opisali vi ochen' detal'no i ponyatno.spasibo vi mne ochen' pomogli. 🙂

  • Стас

    для доски размером NxN…надо как бы в форме сделать дополнительное окно куда будет вводится размерность доски…не могу сообразить как надо заполнять данные массивы в таком случае

    • Массив accessibility можно заполнить так. Обходим все клетки доски и из каждой пробуем выполнить все возможные варианты хода. Считаем сколько есть допустимых вариантов ходов (те, которые не выводят за пределы доски) и записываем это число в соответствующий элемент массива.
      В результате получится. В середине — восьмерки, два крайних ряда ячеек — шестерки, четверки, тройки и двойки.

      Массивы horizontal и vertical не изменяются. Исходное состояние массива board тоже (все нули).

  • Стас

    для доски размером NxN…надо как бы в форме сделать дополнительное окно куда будет вводится размерность доски…не могу сообразить как надо заполнять данные массивы в таком случае

    • Массив accessibility можно заполнить так. Обходим все клетки доски и из каждой пробуем выполнить все возможные варианты хода. Считаем сколько есть допустимых вариантов ходов (те, которые не выводят за пределы доски) и записываем это число в соответствующий элемент массива.
      В результате получится. В середине — восьмерки, два крайних ряда ячеек — шестерки, четверки, тройки и двойки.

      Массивы horizontal и vertical не изменяются. Исходное состояние массива board тоже (все нули).

  • Стас

    ага, сделал уже))) как доделаю сохранение и загрузку, залью куда нить исходник и скину сюда ссылку)

  • Стас

    ага, сделал уже))) как доделаю сохранение и загрузку, залью куда нить исходник и скину сюда ссылку)

  • pascalik.ru

    ДА…. такой «калькулятор» обыграл Гари Каспарова 😉

  • pascalik.ru

    ДА…. такой «калькулятор» обыграл Гари Каспарова 😉

  • Вячеслав

    у кого есть блок-схема для этой программы (тур коня)- скиньте пожалуйста- срочно нужно!!- завтра сдавать

  • Вячеслав

    у кого есть блок-схема для этой программы (тур коня)- скиньте пожалуйста- срочно нужно!!- завтра сдавать