Допомога у програмуванні, відповіді на питання / Алгоритм / Як проаналізувати майстер-подібну гру, використовуючи логічні висновки - алгоритм, набір, логіка

Як проаналізувати майстер-подібну гру, використовуючи логічні висновки - алгоритм, набір, логіка

ВІДМОВА ВІДПОВІДАЛЬНОСТІ: Я НЕ шукаю рішення для Mastermind.

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

Існує N можливі кольори, відомі заздалегідь. Існує невідомий набір (можливо, з повтореннями) k які вибираються і зберігаються в таємниці. Мета - вгадати кольори (з повтореннями) у секретному наборі. Дозвольте мені ще раз підкреслити, що це набір, так порядок не має значення, але повторення дозволено. Наприклад

Кольори є a,b,c,d,e,f,g,h (N=8) і невідомий набір є {a,c,c} (k=3)

Зроблені послідовні припущення, що приводять до отримання додаткової інформації про секретний набір. Кожен здогадок має бути встановленим (повторення дозволено) від k кольори Відповідь на кожну здогадку полягає у кількості спільних кольорів між припущеннями та невідомими встановленими підрахунками повторень. Наприклад

Вгадати: a,d,e Результат: 1

Вгадати: b,c,f Результат: 1

Вгадати: a,a,g Результат: 1

Вгадати: a,c,h Результат: 2

Вгадати: 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.

Я можу працювати через логіку таким чином, але я не знаю, як програмувати це взагалі. Якщо хтось може запропонувати структурований спосіб це зробити, це було б здорово. Я б вважав за краще пояснення високого рівня, з псевдовим кодом, а не повною реалізацією на будь-якій одній мові. Дякую.

Відповіді:

1 для відповіді № 1

Прямий вперед: Побудуйте загальну кількість можливих комбінацій. Потім, як ввімкнені гаджети, видаліть комбінації, які неможливі, задовольняють результат для поточної здогадки. Якщо ви залишили лише одну комбінацію, це рішення. Або раніше, коли ви більше не мали певного кольору, то це (очевидно) виключено з можливого секретного коду.

1 для відповіді № 2

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

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

(+,0,0,-,-,0,0,0) | (-,0,0,+,-,0,0,0) | (-,0,0,-,+,0,0,0)
(0,+,-,0,0,-,0,0) | (0,-,+,0,0,-,0,0) | (0,-,-,0,0,+,0,0)
(+,0,0,0,0,0,-,0) | (-,0,0,0,0,0,+,0)
(+,0,+,0,0,0,0,-) | (+,0,-,0,0,0,0,+) | (-,0,+,0,0,0,0,+)
(0,-,0,0,-,0,0,-)

Тепер ви можете перевірити узгодженість міжколи з'являється інформація. Існує 3 можливості після першої гадання, кожна з яких однаково справедлива. Після другої гадання є 9 можливостей (1 з перших 3 і 1 з другого 3), кожен з них дійсний. Після третьої здогадки існує 18 можливостей, з яких лише 9 дійсні. Це тому, що ліва опція з 3 вимагає залишити варіант з 1 і навпаки. Після четвертої здогадки існує 5 дійсних можливостей. Після п'ятої гадання, існує лише одна дійсна можливість, а саме: