Правила игры изложены в отдельной статье, а здесь мы займёмся изучением вопроса оптимального алгоритма поиска числа противника в игре быки и коровы. И так, есть общие принципы как следует задавать вопросы:
- Вопрос должен быть таким, чтобы ответ был максимально информативен.
- Категорически избегаем повторений. Нет нужды спрашивать то, что мы уже знаем.
- Немного везения как никогда будет кстати.
Сколько комбинаций цифр можно составить? Первую цифру можно загадать десятью способами, вторую девятью и тд. И получаем 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. И бинго!!!! Мы разгадали число!
Бытует мнение, что выявив цифры, которые точно отсутствуют в загаданном числе, то их использовать дальше нельзя. И следует оперировать только найденными коровами, чтобы найти быков. Я придерживаюсь другого мнения. «Пустышки» крайне полезны в выявлении быков, так как мы можем точно определить цифры, которые стоят на своих местах. И это не будет какой либо потерей хода. Наоборот, оперируя только найденными коровами можно запутаться в том, какая из коров в данный момент стала быком.
Я старался в кратце описать ход своих мыслей при игре в быков и коров. Конечно, у каждого свой стиль игры. и многое зависит от везения. И на последок, удачи Вам и приятной игры.
