Существует старинная народная логическая игра. Называется быки и коровы. Её ещё называют 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.
Вот и получается, что ответ найден на пятом шаге.
Ход №5: 432 Победа!
Вот заготовка для того, чтобы заносить в неё развет-данные в игре быки и коровы. Её можно распечатать на A5 для каждой игры.
Итоги
Как видите, удалось выиграть с 5 шагов. Алгоритм работает.
Хорошая это игра быки и коровы. Учит тактике, учит строить гипотезы, доказывать и опровергать их.
Надеюсь этот приём с матрицей поможет другим научиться разгадывать игру быки и коровы.
Ссылки
Метод решета в игре «Быки и коровы»
Загадочное происхождение настольной игры про взлом кодов Mastermind
Автор: aabzel
