сколько существует различных комбинаций в игре в крестики-нолики 3x3? #759179

Нужно посчитать сколько возможно вариантов состояний поля в игре крестики нолики 3х3.

9! (факториал) не предлагать

жениться тебе надо...

3^9 тоже не предлагать

Хотябы как посчитать количество вариантов после третьего хода? Тоесть поставили Х, потом О, потом еще Х.

в начале - все пусто, 1состояние - на первом ходе - любое поле м.б. заполнено X, 9 состояний - на втором ходе - свободные поля могут быть заполнены 0, 8 состояний - на третьем ходе - любое поле м.б. заполнено X, 7 состояний - на четвертом ходе - любое поле м.б. заполнено 0, 6 состояний - на пятом ходе - любое поле м.б. заполнено X, 5 состояний - пять ходов - минимум для выигрыша итого 9*8*7*6*5+1 = 15121 - это если принимать во внимание ориентацию поля, если нет - то намного меньше - исключаются зеркальные. это я так, не думая посчитал, как одинэсник, не математик

с учетом того, что на пятом ходу выигрыш только при определенной растановке на предыдущих ходах - то все не так...

то есть ты думаешь что на третьем ходу возможно 9*8*7 состояний?

Я думаю что в 2 раза меньше

1+ 9+ 9*8+ 9*8*7/2+ 9*8*7/2*6/2+ 9*8*7/2*6/2*5/3+ 9*8*7/2*6/2*5/3*4/3+ 9*8*7/2*6/2*5/3*4/3*3/4+ 9*8*7/2*6/2*5/3*4/3*3/4*2/4+ 9*8*7/2*6/2*5/3*4/3*3/4*2/4*1/5- 192 где 192 - это те варианты когда выиграли оба

Получилось 5854

другой чувак из США насчитал 5478 вариантов, наверное он вычел еще какие-то, которые я не учел.

симметричные варианты как один рассмартивать?

Как все

Гугл говорит - 255 168 комбинаций. Из них: Победа за 5 шагов:  1 440 комбинаций Победа за 6 шагов:  5 328 комбинаций Победа за 7 шагов: 47 952 комбинаций Победа за 8 шагов: 72 576 комбинаций Победа за 9 шагов: 81 792 комбинаций Ничья:             46 080 комбинаций Всего:             255 168  комбинаций

+ если убрать симметричные комбинации, то количество будет либо 31 896, либо 26 830, зависит от того, что считать симметричной комбинацией. Взято отсюда:

+ расчеты комбинаций игры до завершения игры - то есть до победы одной из сторон или ничьи. Общее число комбинаций - будет 9!.

Не пойдет. Не учтены комбинации когда игра не закончена. Не нужно убирать симметричные комбинации.

Не верно, совсем. Правильно считать как в

>> Победа за 9 шагов: 81 792 комбинаций Вообще чушь. На 9 шаге возможно всего 126 комбинаций если считать по , среди них как победы, так и ничья.

>>>Не пойдет. Не учтены комбинации когда игра не закончена. В  смысле? Среди 255 168 - все возможные варианты до окончания игры. Если бы просто заполняли эту табличку 3x3 - было бы 9! вариантов. Это не чушь. 81 792 комбинаций, чтобы довести игру до победы на 9м шаге.

Не может быть 9! Считаем: Нужно расставить 4 нолика в 9 клетках, оставшиеся клетки займут кресты: Ответ: Первый нолик ставится 9 вариантами. Второй ставится 8 вариантами. Третий 7 Четвертый 6 Итого: 9*8*7*6 = 3024 вариантов Из этого числа нужно убрать все возможные перестановки. Так как ноликов 4, то делим 3024 на 4*3*2 = 24: 3024 / 24 = 126

+ Проверяем то же самое но в крестах: Считаем: Нужно расставить 5 крестов в 9 клетках, оставшиеся клетки займут нули: Ответ: Первый крест ставится 9 вариантами. Второй ставится 8 вариантами. Третий 7 Четвертый 6 Пятый 5 Итого: 9*8*7*6*5 = 15120 вариантов Из этого числа нужно убрать все возможные перестановки. Так как крестов 5, то делим 15120 на 5* 4*3*2 = 120: 15120 / 120 = 126

Вариантов состояния поля не больше 3^9, причем часть исключается как невозможные из-за того что игра будет завершена до того как этот вариант станет возможным.

>> Среди 255 168 - все возможные варианты до окончания игры Не нужно до окончания игры, нужно учесть что игра могла быть не закончена.

3^9 = 19683, это меньше чем 255168 из , значит в не верно.

Там, возможно, считают варианты последовательностей ходов. Ведь к одному и тому же состоянию можно прийти разными последовательностями.

Итого: Все позиции посчитаны в при условии что игроки делали ходы по очереди. Теперь нужно из них найти все невозможные позиции. Я насчитал только 192, это когда выиграли оба: 000 ХХХ 0ХХ

Да, но нам это не нужно

ИМХО комбинаций гораздо меньше подсчитанных тут арихметиками. Поясняю: игра идет не до тупого заполнения всех клеток, а до явного выигрыша/ничьей. При этом, понятно, больше половины клеток остаются пустыми.

Это уже давно выяснили

ммм.. всё не читал, но.. поддерживаю давно выясненное :)

Перечитал условие задачи. Давайте поясним: - если речь идет о том, сколько комбинаций игры вообще возможно вплоть до заполнения таблички 3х3, то правильный ответ будет 9! * 2 = 725 760. Почему? Простой ответ. Допустим ход начнем с крестика. На первом шаге возможно 9 вариантов поставить крестик. На втором шаге  - 8 вариантов поставить нолик. то есть уже комбинаций 9*8 На третьем шаге - 9 * 8 * 7 И так далее. Но игру мы можем начать с нолика, тогда полученное значение 9! умножаем на 2 ))).

Вариантов заполнения всех клеток всего 126, так что утверждение "комбинаций гораздо меньше" не верно.

Не верно, это уже выяснили

Ок. Вечером подумаю. Тут двояко можно считать: - считать количество ветвей Шаг1->Шаг2->Шаг3 и так далее; - считать состояния: На шаге1 - количество комбинаций, плюс количество комбинаций на шаге2 и т.д. Потом можно считать все, вплоть до заполнения последней ячейки, или ограничиваясь окончанием игры (победа или ничья) Что мы считаем?

По ссылке: всего существует 255 168 комбинаций игры. Of these, 131,184 are won by the first player, 77,904 are won by the second player, and 46,080 are drawn. Не учитывая зеркалирование.

3 в 9 степени без поворотов поля и без учёта правил игры.

так как вопрос звучит? Правильно ли понимаю: "Сколькими способами можно сыграть в крестики-нолики?" Если так считать, то верный ответ дан тут . То есть, до победы на 5 шаге существует 1 440 вариантов развития игры.

нет. Вопрос звучит как в , "сколько состояний?"

Ну тогда ты в наверное прав. Вечером попробую перебрать все варианты))

Нужно теперь найти невозможные варианты из

Народ, вон в уже давно сказали что вариантов не более чем 3^9. Это обычная комбинаторика. В одной ячейке может быть 3 значения- "Пусто", "Х", "О". Всего в колонке 3 ячейки. Т.е. по одной колонке количество вариантов 3^3. Далее... Колонок у нас 3. В каждой колонке 3^3 вариантов. В результате все поле может быть заполнено количеством вариантов равным (3^3)^3 = 3^(3*3) = 3^9.

Это уже давно выяснили. Зачем повторять одно и то же? Сейчас задача стоит из

а 192 точно разделил на 5? или не делил?

не делил

Блин.. вчера в гости позвали.. забыл про эту задачку)))

Все не читал. Народ, к чему пришли? Сколько комбинаций крестиков ноликов? Я вот думаю их всего 3 :) 1. Победитель первый 2. Победитель второй 3. Никто не победил, т.к. в эту игру нельзя выиграть. Только разве оппонент не дальновиден и не может рассчитать два хода на перед :)

в и

Шанс встретить динозавра.

Оба выиграть не могут по определению. И правилу игры. Эх математики, все время детали отбрасываете :) "5854" вариации... как много, для столь пустой игры :)

Это давно уже выяснили, еще в 10 я об этом писал.

А сумма 5854, как получена?

15120 я тебе выдал практически сразу же...

в показан пример, его нужно скопировать в калькулятр, и ответ получится 5854. Да, ты ошибся практически сразу же...

А почему он ошибся?

9*8*7/2 - почему вариант третьего хода? Т.е. третий ход в 3,5 клетки можно только сделать? Как можно сходить в пол клетки?

С какой целью вы считаете число вариантов? Что это дает? Там всех стратегий- не более пяти, примитивнейшая игра! Стадо дебилов на марше!

Я сведу все к 3-ем итоговым составляющим, вне зависимости вариантов :)

+100 :)

352620

Ошибся, это варианты конечного результата, состояний намного больше будет.

Думаю ты считаешь эти комбинации разными вариантами. Голову включи. Х0Х Х 0 Х

Поле то крутить нельзя наверное.

+Если можно крутить поле, то первый ход никак не 9 вариантами будет как тут все считали.

В дополнение, и явно не может быть вариантов ХХХ 000

Это я учитываю. Как только кто-то первый выиграл, второй уже не ходит.