Задача N ферзей

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

Постановка задачи

• На доске размером NxN должно быть размещено ровно N ферзей;
• Ферзи должны находиться в разных строках;
• Ферзи должны находиться в разных столбцах;
• Ферзи не должны находиться на одной диагонали - как восходящей, так и нисходящей.

Решение задачи

1. Выбор модели

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

2. Создание модели

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

// Создаем объект модели
Модель = О2
    .Модели()
    .МодельОграничений()
    .СоздатьМодель();

3. Регистрация переменных

Создадим массив переменных ПозицииФерзей длины N, где каждая переменная — это номер столбца ферзя в соответствующей строке. Такая модель компактна: индекс массива — строка, значение переменной — столбец.

РазмерДоски = 8;

// Регистрируем переменные по одной на каждого ферзя
// Значение переменной - это номер столбца, где стоит ферзь
ПозицииФерзей = Модель.МассивПеременныхДиапазона(
    РазмерДоски,    // <-- размер массива 
    0,              // <-- левая граница диапазона значений 
    РазмерДоски - 1 // <-- правая граница диапазона значений
);

В примере используется фиксированный размер доски, но для экспериментов вы можете менять РазмерДоски на любое целое > 0 (типично 4, 8, 12 и т.д.).

4. Описание ограничений

Запрещаем двум ферзям находиться в одном столбце. Для этого накладываем глобальное ограничение ВсеРазличные на массив ПозицииФерзей. Глобальные ограничения умеют эффективно исключать невыполнимые комбинации во время поиска.

// Ограничение: позиции ферзей (номера колонок) должны быть различными
Модель.Ограничения().ВсеРазличные(ПозицииФерзей);

Два ферзя находятся на одной восходящей диагонали, если строка + столбец у них одинаковы. Формируем массив линейных выражений Позиция + Индекс и требуем, чтобы все элементы этого массива различались.

// Ограничение: все восходящие диагонали должны быть различными
ВосходящиеДиагонали = Новый Массив(РазмерДоски);
Для К = 0 По РазмерДоски - 1 Цикл
    ВосходящиеДиагонали[К] = Модель.Выражения().Сумма(ПозицииФерзей[К], К);
КонецЦикла;

Модель.Ограничения().ВсеРазличные(ВосходящиеДиагонали);

Аналогично: для нисходящих диагоналей используем выражения столбец - строка.

// Ограничение: все нисходящие диагонали должны быть различными
НисходящиеДиагонали = Новый Массив(РазмерДоски);
Для К = 0 По РазмерДоски - 1 Цикл
    НисходящиеДиагонали[К] = Модель.Выражения().Сумма(ПозицииФерзей[К], -К);
КонецЦикла;

Модель.Ограничения().ВсеРазличные(НисходящиеДиагонали);

Использование выражений col + row и col - row — типичный приём для формализации диагональных ограничений без попарных проверок. Глобальное ограничение ВсеРазличные обрабатывают такие массивы эффективно.

5. Решение модели

Запускаем поиск решения. Для этого вызываем метод Решить объекта модели.

// Выполняем поиск решения
Решение = Модель.Решить();

В задаче N ферзей отсутсвует целефая функция — мы ищем любое допустимое расположение. Модель ограничений без целевой функции — это задача выполнимости (satisfaction). Решатель вернёт либо допустимую конфигурацию, либо сообщит, что решений нет.

6. Вывод результатов

Сформируем текстовый вывод позиций (строка/столбец) для каждой фигуры.

// Выводим результаты
Если Решение.РешениеНайдено() Тогда
    Сообщение = "Позиции ферзей:" + Символы.ПС;
    Для К = 0 По РазмерДоски - 1 Цикл
        ПозицияФерзя = Решение.ЗначениеПеременной(ПозицииФерзей[К]);
        
        НомерСтроки     = К + 1;
        НомерСтолбца    = ПозицияФерзя + 1;
        
        Сообщение = Сообщение + СтрШаблон(
            "%1)%2 Строка: %3, Столбец: %4 %5",
            Строка(К + 1),
            Символы.Таб,
            НомерСтроки,
            НомерСтолбца,
            Символы.ПС
        );
    КонецЦикла;
    
    Сообщить(Сообщение);	    
Иначе
    Сообщить("Решений не найдено.");
КонецЕсли;

Полный код решения задачи

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

// Создаем объект модели
Модель = О2
    .Модели()
    .МодельОграничений()
    .СоздатьМодель();

// Вводим начальные данные
РазмерДоски = 8;

// Регистрируем переменные по одной на каждого ферзя
// Значение переменной - это номер колонки, где стоит ферзь
ПозицииФерзей = Модель.МассивПеременныхДиапазона(
    РазмерДоски,    // <-- размер массива 
    0,              // <-- левая граница диапазона значений 
    РазмерДоски - 1 // <-- правая граница диапазона значений
);

// Ограничение: позиции ферзей (номера колонок) должны быть различными
Модель.Ограничения().ВсеРазличные(ПозицииФерзей);

// Ограничение: все восходящие диагонали должны быть различными
ВосходящиеДиагонали = Новый Массив(РазмерДоски);
Для К = 0 По РазмерДоски - 1 Цикл
    ВосходящиеДиагонали[К] = Модель.Выражения().Сумма(ПозицииФерзей[К], К);
КонецЦикла;

Модель.Ограничения().ВсеРазличные(ВосходящиеДиагонали);

// Ограничение: все нисходящие диагонали должны быть различными
НисходящиеДиагонали = Новый Массив(РазмерДоски);
Для К = 0 По РазмерДоски - 1 Цикл
    НисходящиеДиагонали[К] = Модель.Выражения().Сумма(ПозицииФерзей[К], -К);
КонецЦикла;

Модель.Ограничения().ВсеРазличные(НисходящиеДиагонали);

// Выполняем поиск решения
Решение = Модель.Решить();

// Выводим результаты
Если Решение.РешениеНайдено() Тогда 
    Сообщение = "Позиции ферзей:" + Символы.ПС;
    Для К = 0 По РазмерДоски - 1 Цикл
        ПозицияФерзя = Решение.ЗначениеПеременной(ПозицииФерзей[К]);
        
        НомерСтроки 	= К + 1;
        НомерСтолбца 	= ПозицияФерзя + 1;
        
        Сообщение = Сообщение + СтрШаблон(
            "%1)%2 Строка: %3, Столбец: %4 %5",
            Строка(К + 1),
            Символы.Таб,
            НомерСтроки,
            НомерСтолбца,
            Символы.ПС
        );
    КонецЦикла;
    
    Сообщить(Сообщение);	    
Иначе
    Сообщить("Решений не найдено.");
КонецЕсли;

  Скачать пример