ХОДОМ КОНЯ
Доктор физико-математических наук Р. БАХТИЗИН, К. ШТУКАТУРОВ.
В научно-популярной литературе нередко встречаются так называемые «шахматные» задачи, связанные с шахматными фигурами, например: можно ли ходом коня обойти доску размером 8x6, побывав на каждой клетке только один раз? Это не такая простая задача, как может показаться на первый взгляд. Нетрудно убедиться, что число возможных ходов из каждой клетки может быть от 0 до 8. Представим их в виде дерева, имеющего иерархическую структуру. Примем, что «среднее» число ходов равно двум:
(Иллюстрация 1)
Получается, что на 64-м ходу число возможных комбинаций достигает 264. Это очень большое число. Еще со школьной скамьи нам известна задача из занимательной математики про купца, который в качестве вознаграждения предложил на первую клетку шахматной доски положить одно зерно, на вторую — два, на третью - четыре и т. д. Количество зерен на последней, 64-й клетке, равное 263, оказалось столь огромно, что превышает все запасы зерна на земном шаре. Возвращаясь к нашей задаче, отметим, что перебор всех возможных комбинаций с помощью указанного дерева занимает очень много времени даже с использованием самых мощных на сегодняшний день компьютеров (для перебора использовался Pentium 4 — 1,9 ГГц, 512 Mb ОЗУ). В задаче перебора такого рода более приемлемы алгоритмы случайного поиска, когда каждый ход выбирается случайным образом из возможных. Как ни странно, именно случайный поиск значительно сокращает время вычислений. Полученное при этом решение приведено ниже.
(Иллюстрация 2)
Возникает вопрос: при каких размерах досок (не обязательно квадратных) задача с шахматным конем имеет решение? Компьютерный перебор на практике возможен только для небольших досок: за приемлемое время удается перебрать варианты с шахматной доской размером от 5x5 до 8x8. Можно доказать, что для досок 3x3 и 4x4 задача не имеет решения. Для остальных же размеров полученные результаты удобно представить в виде следующей схемы:
(Иллюстрация 3)
Например, незакрашенная ячейка, находящаяся на пересечении четвертой строки и третьего столбца, означает, что для доски paзмepoм 3x4 решение есть.
Также известны интересные частные случаи заполнения квадратных досок размерами 5+4k. Оказывается, что, используя известный способ заполнения доски 5x5, можно заполнить доски размерами 9x9, 13x13 и т. д. Как это делается, видно из рисунка.
(Иллюстрация 4)
Кроме описанного частного случая имеется также универсальный алгоритм заполнения квадратных досок размерами 10x10 и более. В левом нижнем углу доски выделяется квадрат размерами (п-3)х(п-3), заполнение которого известно. Сверху к нему «приклеивается» фрагмент размерами Зхп и сбоку (п-З)хЗ. Сначала заполняется верхний фрагмент, затем конь переходит на боковой, и после заполнения бокового фрагмента попадаем в угловую клетку малого квадрата. Как это выглядит для доски размером 10x10, показано на рисунке.
(Иллюстрация 5)
Заполнив таким образом доски размерами начиная с 10x10 и до 13x13, последующие заполнения можно получить, «вставляя» доски 3x4 и 4x3 сверху и сбоку:
(Иллюстрация 6)
Таким образом, имеется принципиальная возможность заполнить ходом коня любую квадратную доску размерами 5x5 и больше. Алгоритмы за полнения прямоугольных досок хотелось бы предложить найти читателям.
Читайте в любое время
