Как Выигрывать в Игре Быки и Коровы

Существует старинная народная логическая игра. Называется быки и коровы. Её ещё называют mastermind.

в mastermind вместо чисел - цвета — **в mastermind** вместо чисел — цвета

Правила простые:

Ведущий задумывает случайное тайное 4-значное число с неповторяющимися цифрами. Игрок делает попытки отгадать число. Попытка — это 4-значное число с неповторяющимися цифрами, сообщаемое ведущему. Ведущий дает подсказки , сколько цифр угадано без совпадения с их позициями в тайном числе (количество коров) и сколько угадано вплоть до позиции в тайном числе (количество быков). Например:

Задумано тайное число «3219». Попытка: «2310».

Результат: две «коровы» (две цифры: «2» и «3» — угаданы на неверных позициях) и один «бык» (одна цифра «1» угадана вплоть до позиции).

Побеждает тот, кто угадает число за меньшее количество ходов.

В этом тексте я хотел бы представить мой алгоритм для поиска решения в этой игре. Я назвал этот метод: матрица возможных решений.

Для определённости пусть будет вариант игры из трёхразрядного числа. Для четырехзначных чисел суть та же самая. Суть алгоритма покажу в частном виде, то есть на примере.

Подготовка

Первым делом надо расчертить вот такую таблицу вариантов. Это и есть матрица возможных решений. Изначально она пустая. Тут перечислено какие числа могут быть в сотнях, какие в десятках, а какие в единицах.

То есть таблица показывает какие числа могут быть в каждом разряде. Чтобы заполнить таблицу надо делать ходы.

Ход №1: Вариант 123 — подсказка: 2 коровы

Подсказки вида ноль быков и несколько коров — это просто подарок судьбы, так как можно смело замазать в матрице решений аж три ячейки. Сейчас это значит, что 1- это не бык 2-это не бык 3-это не бык

Ход №2: 298 — подсказка: 1 корова

Это значит что 2, 9 и 8 не быки. Замазывает эти ячейки в матрице решений.

Ход №3: 354подсказка:2 коровы

Тоже это значит что 3 5 4 не быки. Замазываем эти ячейки в матрице.

Ход №4: 532-подсказка: 2 быка

Когда появляются быки, то замазать в таблице ничего не надо. А надо делать гипотезы исходя из возможной комбинаторики.

В данном случае, присутствует вся информация, чтобы выиграть. Когда есть подсказка 2 быка, то тут надо проверить три гипотезы. Одна останется и две будут опровергнуты.

1.Гипотеза: быки это 53_ (спойлер: ошибочно)

Тогда 2 нет в числе. Тогда 1 3 тоже коровы. То есть в числе должны быть числа 1 3 5. Однако вторая подсказка говорит о том что есть еще четвертое число отличное от 1 3 5. Противоречие. Гипотеза не состоятельная.

3.Гипотеза: быки это 5_2 (спойлер: ошибочно)

Тогда в числе нет 3. На основе хода 3 значит есть 1 2 4 5 . Но это 4 числа! Перебор. Противоречие.

2.Гипотеза: быки это _32 (спойлер: правильно)

Тогда 5 нет в числе. Значит в числе есть ещё и 4. Значит нет 1 ,9, 8 и 5 . Нет ни одной подсказки, которая бы нарушала гипотезу. Получается ответ это 432.