Алгоритм рассадки с ограничениями

Question

Я пытаюсь составить программу, в которой в течение 5 дней каждый день будет создаваться новый порядок рассадки. Существует ограничение, которому необходимо следовать:

• Люди сидят в группах по 4 человека и не могут находиться в одной группе с другим человеком более одного раза в течение 5 дней. Всего около 30-35 человек.

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

Кроме того, возможно ли определить, может ли это ограничение быть выполнено при данном размере выборки? Я новичок в области теории графов и не знаю, какие алгоритмы жизнеспособны в этой ситуации.

Answer 1

Ссылка ниже является хорошей отправной точкой для проблемы социального игрока в гольф. Он содержит решения для более простых случаев (включая некоторые с 4-таблицами) и дает ссылки на некоторые более сложные статьи: http://www.mathpuzzle.com/MAA/54-Golf%20Tournaments/mathgames_08_14_07.html