@TomskDiver

Есть ли алгоритм решения игры Быки и коровы?

Подскажите есть ли алгоритм решения задачи по игре Быки и коровы. Задание выглядит как-то так:
В игре были сделаны ходы:
1985 1 бык, 2 коровы
5147 1 бык, 0 коров
4801 0 быков, 3 коровы
6870 0 быков, 2 коровы
По сделанным ранее ходам отгадать правильный ответ.
  • Вопрос задан
  • 4891 просмотр
Решения вопроса 1
@DeepBlue
Если цель - запрограммировать решение, то перебор всех четырёхзначных чисел с проверками, удовлетворяют ли они всем указанным условиям, будет работать разумное время. Если всё-таки нужно быстрее, чем перебором, тогда нужно придумывать трюки, как его в конкретной ситуации сокращать. Например, в данном примере можно рассуждать так:

1. Раз 1985 содержит три цифры числа, значит, 1 или 5 в нём есть. Раз 5147 содержит только одну, значит, 4 и 7 в нём нету.
2. 4801 содержит 3 цифры, но мы уже знаем, что 4-ки нет. Значит, 801 присутствуют. Из 5147 видно, что 1 на втором месте, а пятёрки нет.
3. Раз пятёрки нет, то из 1985 следует, что есть 198. Объединяя с п.2, получаем, что число состоит из цифр 0189.
4. Единица на втором месте, а 0 точно не на 3-м и не на 4-м. Значит, 0 на первом.
5. В 1985 единица и девятка не быки, значит, 8 - на своём месте. Значит, 0189 - единственное подходящее число.

Но боюсь, что написать программу, которая будет генерировать рассуждения такого типа, непросто. Тем не менее, некоторые идеи отсюда можно использовать для сокращения перебора: например, можно сначала найти возможные варианты набора цифр, а затем для каждого из них искать подходящий порядок.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
@TomskDiver Автор вопроса
DeepBlue, спасибо! Всё отлично объяснили! Решил еще 4 подобных задания. Но вот такое последнее не осилил:
В игре были сделаны ходы:
3086 1 бык 1 корова
7914 1 бык 1 корова
0794 1 бык 1 корова
6491 1 бык 1 корова
1947 1 бык 1 корова
По сделанным ранее ходам отгадать правильный ответ.
Осилите?
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы