«Быки и коровы» (в Японии игру называют Hit & Blow) — отличная головоломка для компьютера. Идея очень простая: выписать все возможные ответы и вычёркивать те, что противоречат подсказкам.

Идея

  1. Построить все возможные ответы (для 4 цифр это 5040 вариантов).
  2. Выбрать один вариант и назвать его как попытку.
  3. Посмотреть, сколько получилось быков и коров, и для каждого варианта проверить: «Если бы ответом был он, получились бы те же быки и коровы?» Если нет, вычёркиваем.
  4. Повторять шаги 2 и 3, пока не угадаем.

Главное — шаг 3: оставлять только те варианты, которые дают такую же подсказку. Компьютер механически делает для всех вариантов то, что человек делает в уме.

Программа

На JavaScript это выглядит так. Запустить можно в инструментах разработчика браузера или в Node.js на компьютере.

// Считаем быков и коров
function judge(answer, guess) {
  let hit = 0, blow = 0;
  for (let i = 0; i < guess.length; i++) {
    if (guess[i] === answer[i]) hit++;
    else if (answer.includes(guess[i])) blow++;
  }
  return [hit, blow];
}

// Строим все ряды из разных цифр
function allCodes(digits, prefix = '') {
  if (prefix.length === digits) return [prefix];
  const list = [];
  for (const d of '0123456789') {
    if (!prefix.includes(d)) list.push(...allCodes(digits, prefix + d));
  }
  return list;
}

// Каждый раз называем первый из вариантов, не противоречащих подсказкам
function solve(answer) {
  let candidates = allCodes(answer.length);
  for (let turn = 1; ; turn++) {
    const guess = candidates[0];
    const [hit, blow] = judge(answer, guess);
    console.log(turn, guess, hit, blow, candidates.length);
    if (hit === answer.length) return turn;
    candidates = candidates.filter((c) => {
      const [h, b] = judge(c, guess);
      return h === hit && b === blow;
    });
  }
}

solve('4719');
  • judge считает быков и коров по ответу и попытке. Все символы разные, поэтому правило простое: если символ на своём месте, это бык; если не на своём, но есть в ответе, это корова.
  • allCodes строит все ряды из разных цифр.
  • solve называет первый вариант из списка и оставляет только те, что дают ту же подсказку, и так по кругу.

Результат

Для ответа «4719» программа вывела следующее (слева направо: номер попытки, попытка, быки, коровы, число вариантов перед попыткой).

1 0123 0 1 5040
2 1456 0 2 1440
3 2547 0 2 369
4 3674 0 2 80
5 4268 1 0 15
6 4395 1 1 6
7 4719 4 0 1

Число вариантов уменьшалось так: 5040 → 1440 → 369 → 80 → 15 → 6 → 1, и на 7-й попытке ответ найден. Когда мы прогнали через эту программу все 5040 возможных ответов, в среднем понадобилось около 5,56 попытки, а самый трудный ответ потребовал 9.

Как решать за меньшее число ходов

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

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

С такими приёмами для 4 цифр любой ответ находится не больше чем за 7 попыток, а в среднем за 5,3 (Есть ли выигрышная стратегия в «Быках и коровах»?). Зато на выбор каждой попытки нужно перебрать много сочетаний, и вычисления идут дольше.

«Подсказка» в приложении устроена так же

«Подсказка» в приложении «Быки и коровы» тоже считает все варианты ответа, не противоречащие прежним подсказкам, и показывает что-то одно по порядку:

  1. Если в каком-то разряде при любом варианте стоит один и тот же символ, она сообщает этот разряд.
  2. Если есть символ, которого нет ни в одном варианте, она сообщает его.
  3. Если нет ни того ни другого, она открывает один разряд ответа.

(Как пользоваться подсказкой)

Если хочешь сделать такую игру сам, загляни в статью Как сделать игру на угадывание чисел.