«Быки и коровы» (в Японии игру называют Hit & Blow) — отличная головоломка для компьютера. Идея очень простая: выписать все возможные ответы и вычёркивать те, что противоречат подсказкам.
Идея
- Построить все возможные ответы (для 4 цифр это 5040 вариантов).
- Выбрать один вариант и назвать его как попытку.
- Посмотреть, сколько получилось быков и коров, и для каждого варианта проверить: «Если бы ответом был он, получились бы те же быки и коровы?» Если нет, вычёркиваем.
- Повторять шаги 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 (Есть ли выигрышная стратегия в «Быках и коровах»?). Зато на выбор каждой попытки нужно перебрать много сочетаний, и вычисления идут дольше.
«Подсказка» в приложении устроена так же
«Подсказка» в приложении «Быки и коровы» тоже считает все варианты ответа, не противоречащие прежним подсказкам, и показывает что-то одно по порядку:
- Если в каком-то разряде при любом варианте стоит один и тот же символ, она сообщает этот разряд.
- Если есть символ, которого нет ни в одном варианте, она сообщает его.
- Если нет ни того ни другого, она открывает один разряд ответа.
Если хочешь сделать такую игру сам, загляни в статью Как сделать игру на угадывание чисел.
