Быки и коровы

Правила игры

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

Задумано тайное число «3219».

Попытка номер: «2310».

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

Игроки делают попытки угадать по очереди. Побеждает тот, кто угадает число первым.

Содержание

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

Задумано тайное число «3219».

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

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

При игре против компьютера игрок вводит комбинации одну за другой, пока не отгадает всю последовательность.

Быки и коровы алгоритм.

Правила игры изложены в отдельной статье, а здесь мы займёмся изучением вопроса оптимального алгоритма поиска числа противника в игре быки и коровы. И так, есть общие принципы как следует задавать вопросы:

• Вопрос должен быть таким, чтобы ответ был максимально информативен.
• Категорически избегаем повторений. Нет нужды спрашивать то, что мы уже знаем.
• Немного везения как никогда будет кстати.

Сколько комбинаций цифр можно составить? Первую цифру можно загадать десятью способами, вторую девятью и тд. И получаем 10*9*8*7 = 5040. Вот это общее количество комбинаций. А вариантов ответов может быть всего 14, они все показаны на рисунке.

В приведённой таблице рассмотрены все варианты ответов. Самый желанный и вкусный — это 4 быка, то есть сразу выигрыш. И такой вариант один. Самый вариативный это 1 корова — имеет 1440 вариантов расстановки цифр. По большому счёту наши дальнейшие шаги буде определять наш первый ход. А тут мы может положиться только на нашу удачу, расположение звёзд, расставленной мебели по фен-шую и наличию кофе. То есть любую комбинацию цифр. И по полученному ответу мы планируем дальнейшие шаги. Рассмотрим варианты, кроме 4быков:

• 0 быков, 0 коров — это тоже вполне удачный ход! Эти цифры сразу исключаем из угадываемого числа, но можем использовать для выявления быков.
• 1 бык или 1 корова — то есть мы нашли одну цифру, но какая она не ясно.
• 1 бык и 1 корова, или 2 быка или 2 коровы — нашли 2 цифры.
• 3 быка и 0 коров, 2 быка и 1 корова, 1 бык 2 коровы. Нашли 3 цифры, но самый желанный — это три быка, всего 24 комбинации! На практике 4 хода.
• 2 быка и 2 коровы, 1 бык и 3 коровы, 4 коровы — то есть мы нашли все цифры. Здесь мы можем кричать ура, так как выигрыш считайте у нас в кармане! Самое большее 9 комбинаций!

Дальнейшую стратегию рассмотрим на примерах игры, так будет гораздо наглядней и проще.

Первый пример

На первый вопрос 1234 мы получили ответ одна корова. Вторым вопросом была комбинация 5678. И тут удача — два быка и одна корова. Логика третьего хода следующая: мы угадали три цифры, нужно определить их расположение. И мы точно знаем что цифра 9 и 0 отсутствуют в загаданном числе. Потому берём две цифры из второго вопроса, но ставим на другие места и доставляем 0 и 9.

Получаем такой вопрос: 7890, на который мы получили ответ 2 коровы. Поздравляем — мы точно определили 2 быка: 7 на третьем месте, 8 на четвёртом. Далее мы знаем что 5 или 6 точно есть в загаданном числе. Уберём одно и поставим на другое место. Последнее число возьмём из первого вопроса, тут без разницы какое — чистое везение. Получаем такой вопрос — 4578. И радуемся победе, мы отгадали, ответ четыре быка!

Второй пример

На первый вопрос 0123 мы получили ответ 1 бык, 2 коровы. Вторым вопросом задаём 4567. Получаем в ответе 1 корова. Всё, мы снова исключили две цифры — это 8 и 9. И теперь мы возьмём две цифры с первого вопроса и как обычно поставим на другое место, добавим 8 и 9.

Получился такой вопрос 2389, ответ на который был одна корова. Казалось бы результат так себе, но не тут-то было! Скомбинируем третий вопрос так — возьмём ноль с первого вопроса, но менять его место не будем, возьмём двойку с третьего и поставим на второе и разбавим несуществующими. Вот что получили: 0289. Ответом было два быка! Теперь тройку тоже вычеркнем, а это значит, что единичка точно в числе есть. Теперь осталось всего два варианта и мы выбираем 0215. И получаем 4 быка! Пятёрочка — это чистое везение.

Третий пример

В первый раз спросим 9012. Получаем 2 коровы. Второй вопрос — 3456 — тоже две коровы. Так, 7 и 8 исключаем. Теперь перетасовываем второй вопрос и уберём одну, заменив на семерку. Получаем такой вариант : 6573. Ответ — одна корова. Что мы поняли? Цифра 4 точно есть и получили расположения, где цифры 3, 5 и 6 точно не стоят.

Четвёртый вопрос формируем так — комбинируем третий и первый вопрос, меняя местами. Вот какую комбинацию мы получили — 1234. Ответ — три быка. 3 и 4 стоят на своих местах, проверяем только первые цифры. 9234 — ответом на него было 2 быка, одна корова. Всё, мы нашли число! 1934.

Четвёртый пример

Первый вариант у нас 4590, ответ — один бык. Второй ход 1236 и ответ три коровы. Снова 7 и 8 вне игры. На третьем ходу тасуем цифры третьего вопроса и разбавляем 7. 7263, что даёт нам снова 3 коровы. Значит единичку выбрасываем.

Теперь нам нужно правильно расположить наших коров и найти быка с первого вопроса. Задаём такой вариант — 4623, ответ на него два быка и одна корова. Значит не четвёрка. Тройку мы не меняли и потому точно можем сказать, что именно тройка не на своём месте! Пробуем ещё раз — 3620. И бинго. Мы разгадали число!

Бытует мнение, что выявив цифры, которые точно отсутствуют в загаданном числе, то их использовать дальше нельзя. И следует оперировать только найденными коровами, чтобы найти быков. Я придерживаюсь другого мнения. «Пустышки» крайне полезны в выявлении быков, так как мы можем точно определить цифры, которые стоят на своих местах. И это не будет какой либо потерей хода. Наоборот, оперируя только найденными коровами можно запутаться в том, какая из коров в данный момент стала быком.

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

Где похожие задачи? Перспективы прикладного применения

Может кто-нибудь предложить прикладное применение этому алгоритму (приложению)?

Ведь «маленькие кусочки информации» машина увязывает в одно целое и на основании этого получается «достаточная информация» для принятия решения о следующем вопросе (остальные функции тривиальны).

Хотелось бы такую идею услышать и поучаствовать в ее реализации.

Если у Вас остались вопросы, то задать их Вы можете, нажав на эту кнопочку .