Генератор латинских квадратов? (Судоку как проблема ограничения)

Цель

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

  • Значения не могут повторяться подряд
  • Значения не могут повторяться в столбце
  • Значения не могут повторяться попарно в любых двух строках

Пример для первых 3 ограничений:

2     3    5    7    11   13
7     2    11   3    13   5
11    5    2    13   7    3
3     7    13   2    5    11
5     13   3    11   2    7
13    11   7    5    3    2

Здесь мы выбрали простые числа, но значения являются произвольными (при условии, что существует 6 различных значений). Обратите внимание, что это то же самое, что и судоку в сетке 6 x 6, с дополнительным ограничением на то, что в рядах нет повторяющихся пар (известных как биграммы). То есть, 2 3 появляется только в первом ряду, но ни в каком другом, и так далее для любой другой пары.

  • Значения должны быть связаны с другими 6 значениями, которые соответствуют этим ограничениям:
    • Значения 2-го набора не могут повторяться подряд
    • Значения 2-го набора не могут повторяться в столбце
    • Когда в паре с 1-ыми установленными значениями, 2-ые установленные значения не могут повторяться.

То есть нам нужно иметь еще шесть значений (опять же, произвольных - они могут быть "a, b, c, d, e, f"), которые сопоставляются с первыми шестью. Последнее ограничение означает, что если вы используете (2а) нигде, вы не можете использовать его снова.

Последнее ограничение 2-го множества является проблемой. Не существует решения для n x n сеток, где n = 6. Это гаечный ключ в работах. Мы хотим свести к минимуму количество повторов, чтобы создать "сортирующую" ортогональную пару латинских квадратов.

Вопрос

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

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

Источник

2 ответа

Решение

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

Источник

Посмотрите: Танцы Ссылки

В компьютерных науках Dancing Links, также известный как DLX, является техникой, предложенной Дональдом Кнутом для эффективной реализации его Алгоритма X. Алгоритм X является рекурсивным, недетерминированным, алгоритмом возврата в глубину, который находит все решения для точной проблемы покрытия. Некоторые из наиболее известных проблем точного покрытия включают мозаику, проблему N королев и судоку.

Источник
Другие вопросы по тегам