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

    @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 - единственное подходящее число.

    Но боюсь, что написать программу, которая будет генерировать рассуждения такого типа, непросто. Тем не менее, некоторые идеи отсюда можно использовать для сокращения перебора: например, можно сначала найти возможные варианты набора цифр, а затем для каждого из них искать подходящий порядок.
    Ответ написан
    Комментировать