Логические игры незаменимы для развития детей школьного и дошкольного возрастов, но так же актуальны и интересны взрослому человеку. Практически все логические игры имеют ярко выраженную математическую направленность, вследствие чего, могут быть решены методом комбинаторного анализа.
В данной работе приводится пример решения логической игры «Быки и коровы».
Эта, простая на первый взгляд, игрушка, однако заставит вас, напрячь серое вещество – это шедевр времяубивания на лекциях, уроках, работе или дома. Правила просты.
В классическом варианте игра рассчитана на двух игроков, каждый из которых задумывает и записывает тайное 4-значное число с неповторяющимися цифрами. Игрок, который начинает игру по жребию, делает первую попытку отгадать число. Попытка — это 4-значное число с неповторяющимися цифрами, сообщаемое противнику. Противник сообщает в ответ, сколько цифр угадано без совпадения с их позициями в тайном числе (то есть количество коров) и сколько угадано вплоть до позиции в тайном числе (то есть количество быков).
«Быки» - это те цифры вашего числа, расположение которых поразрядно совпадает с цифрами загаданного числа;
«Коровы» - это те цифры вашего числа, которые присутствуют в загаданном числе, но находятся в другом месте, (в другом разряде, на другой позиции).
Рассмотрим пример: Загадано число «2308».
В числе присутствуют цифры - 2, 3, 0, 8;
На ваши попытки его угадать, ответом будет следующее:
1. «1234» - 0б, 2к («коровы» цифры 2 и 3, так как они присутствуют в загаданном числе, но находятся не на своих местах);
2. «5678» - 1б, 0к («бык» это цифра 8, находится на 4-й позиции, т.е. на месте);
3. «2380» - 2б, 2к (2,3 - быки, 8,0 - коровы, 2 и 3 на местах, 8,0 не на местах ).
и т.д.
В среднем, пытливому уму требуется от 6 до 8 попыток, чтобы отгадать любое 4-хзначное число.
Стоит заметить, что игра, о которой идет речь, представляют собой весьма интересный объект для исследования на компьютере. Достаточно сказать, что в написании программы для «Быков и коров» участвовал один из крупнейших в мире специалистов в области программирования американец Д. Кнут. В нашей стране ряд результатов в этой области был получен группой студентов кафедры кибернетики МИСиС под руководством доцента М. Гендлера.
Основная задача, привлекающая математиков и программистов, состоит в нахождении оптимального алгоритма, то есть такой стратегии игры, при которой количество шагов для достижения максимально результата (получения 4 быков) будет минимальным.
На сегодняшний день существует несколько вариантов для решения этой задачи. Один из них представлен в работе А. Словеснова «Оптимальный алгоритм в игре быки и коровы», в которой он доказывает, что существует алгоритм, следую которому можно отгадать число, сделав не более 7, но и не менее 6 ходов.
Алгоритм заключается в переборе комбинаций, начиная с 0123, 1245, 2456 и.т.д., пытаясь найти ход с максимальной результативностью. Данная схема позволяет проверить практически все цифры на различных позициях, и по подсказкам (быкам и коровам) провести анализ и отгадать число.
Но данный алгоритм предназначен для случая, когда на первом месте в загаданной четырехзначной комбинации может стоять «0, что является одной из разновидностей игры. Но все же вернемся к классическому варианту.
В правилах сказано: «…Каждый из игроков задумывает и записывает тайное 4-хзначное число…», а число не может начинаться с 0, следовательно, данный алгоритм не будет столь результативен, если вообще может быть применен, в классической игре, тем более, если игра реализуется в компьютерной программе, где правила ввода число и проверочных комбинаций строго обозначены.
В ходе решения данной задачи мной был разработан алгоритм, позволяющий угадать число за максимум 8-9 шагов, а в частных случаях и за 5-7.
Заключается он в следующем.
Начинаем перебор с комбинации «1234», каждый следующий шаг меняем последнюю цифру на следующую по порядку за ней, т.е после «1234» будет комбинация «1235» и.т.д. По изменению числа «коров» мы с легкостью определяем цифры, участвующие в записи числа, ну а уж если появляется «бык», то и узнаем одну из конечных позиций. Когда станут известны все 4 коровы остается только подобрать выигрышную комбинацию. Сделав анализ предыдущих шагов, данная процедура займет максимум 2 шага.
Рассмотрим работу данного алгоритма на примере: пусть загадано число 2876.
Начинаем перебор:
1234 |
1 к, 0 б |
1235 |
1 к, 0 б |
1236 |
1 к, 1 б |
1237 |
2 к, 0 б |
1238 |
2 к, 0 б |
Итак, сделав всего 5 ходов, мы определили 3 цифры участвующие в записи числа: 6 (счетчик быков изменился, а значит, данная цифра присутствует в числе на той же позиции), 7 (счетчик коров изменился), 8 (мы не меняли цифры ни в одной из позиций, кроме последней, следовательно, данная цифра присутствует в числе).
Осталось найти последнюю цифру и определить число. Мы знаем, что «6» стоит в числе на последнем месте и что последняя корова скрывается в комбинации «123».
Начинаем простой перебор и, анализируя предыдущие шаги, делаем следующие. В итоге получаем следующий результат:
1786 |
2 к, 1 б |
2876 |
0 к, 4 б |
Итак, на данном примере я доказала, что данный алгоритм действенный и пригодный для решения конкретно этой игры. Возможно так же применение этого алгоритма в подобных играх, основанных на комбинаторном анализе.