Как проанализировать игру, похожую на вдохновителя, используя логические выводы

Question

---

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Я НЕ ищу решение Mastermind.

---

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

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

Цвета a,b,c,d,e,f,g,h (N=8) и неизвестный набор {a,c,c} (k=3).

Получены последовательные предположения, которые дают больше информации о наборе секретов. Каждое предположение должно быть набором (допускается повторение) k цветов. Ответом на каждое предположение является количество цветов, общих между догадкой и неизвестным набором повторений. Например

1. Угадай: a,d,e Результат: 1

2. Угадай: b,c,f Результат: 1

3. Угадай: a,a,g Результат: 1

4. Угадай: a,c,h Результат: 2

5. Угадай: b,e,h Результат: 0

Предположения сделаны кем-то другим. Мои цели:

- определить, когда известна информация об определенном цвете.

- Определить, когда может быть логически выведен неизвестный набор.

В начале игры ни один цвет не определен в наборе или определенно отсутствует в неизвестном наборе (при условии N>1). После предположения, которое приводит к 0, все цвета этого предположения, как известно, не находятся в неизвестном наборе. Если результат равен k, то известно, что все цвета этого предположения находятся в неизвестном наборе. У меня проблемы с написанием программы, чтобы выяснить все случаи между ними. Например, ничего не известно наверняка о любом из цветов до последнего предположения выше. После последнего предположения известно, что набор равен a,c,c. Логика такова:

• К 5, b,e,h нет в неизвестном наборе
• К 4 a,c находятся в неизвестном наборе
• По 1, d нет в неизвестном наборе
• По 2, f не в неизвестном наборе
• К 3, g нет в неизвестном наборе
• Поэтому единственными цветами в неизвестном наборе являются a и c.
• К 3, a не входит в неизвестный набор более одного раза.
• Следовательно, неизвестный набор - a,c,c.

Я могу работать с логикой таким образом, но я не уверен, как программировать это вообще. Если бы кто-то мог предложить структурированный способ сделать это, это было бы здорово. Я бы предпочел объяснение высокого уровня с псевдокодом, а не полную реализацию на каком-либо одном языке. Спасибо.

Answer 1

Вы можете кодировать логику после каждой догадки следующим образом.Возьмем массив длины N, где запись позиции i равна +1, если i -й цвет находится в наборе, -1, если i -й цвет отсутствует в наборе, и 0 если неизвестно, присутствует ли i -й цвет в наборе.

После каждого предположения вы создаете возможные массивы, удовлетворяющие полученному результату.Если предположение дает результат r, тогда будет (k choose r) (или меньше, если есть повторяющиеся цвета) возможных массивов.Для вашего примера, массивы (здесь я использовал + вместо +1 и - вместо -1 для краткости)

1. (+,0,0,-,-,0,0,0) | (-,0,0,+,-,0,0,0) | (-,0,0,-,+,0,0,0)
2. (0,+,-,0,0,-,0,0) | (0,-,+,0,0,-,0,0) | (0,-,-,0,0,+,0,0)
3. (+,0,0,0,0,0,-,0) | (-,0,0,0,0,0,+,0)
4. (+,0,+,0,0,0,0,-) | (+,0,-,0,0,0,0,+) | (-,0,+,0,0,0,0,+)
5. (0,-,0,0,-,0,0,-)

Теперь вы можете проверять согласованность возможностей по мере поступления информациив. Есть 3 варианта после первого предположения, каждый из которых одинаково действителен.После второго предположения существует 9 возможностей (1 из первых 3 и 1 из вторых 3), и каждая из них действительна.После третьего предположения существует 18 возможностей, из которых только 9 действительны.Это потому, что левая опция от 3 требует левой опции от 1 и наоборот.После четвертого предположения есть 5 действительных возможностей.После пятого предположения существует только 1 действительная возможность, а именно:

1. (+,0,0,-,-,0,0,0)
2. (0,-,+,0,0,-,0,0)
3. (+,0,0,0,0,0,-,0)
4. (+,0,+,0,0,0,0,-)
5. (0,-,0,0,-,0,0,-)

Теперь известно включение / исключение каждого цвета.Вы можете обрабатывать кратности аналогичным образом.

Answer 2

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

Answer 3

Выбранные позиции: ade = 1 => 3 возможных 100, 010, 001

Не известен для этой строки: bcfgh =? => 5 наименований = 32 возможных

объединить их, чтобы дать 32 * 3 = 96 возможных ответов

повторите для следующей строки и удалите те, которые не возможны для всех строк

пока не остался один возможный

Answer 4

Кнут описано решение.Я реализовал это.