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

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

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

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

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

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

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

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

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

https://ru.wikipedia.org/wiki/Крестики-нолики

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 вариантов, наверное он вычел еще какие-то, которые я не учел.

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

(13) Как все

Гугл говорит - 255 168 комбинаций.

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

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

Взято отсюда:
http://www.se16.info/hgb/tictactoe.htm

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

(15) Не пойдет. Не учтены комбинации когда игра не закончена.

(16) Не нужно убирать симметричные комбинации.

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

(15) >> Победа за 9 шагов: 81 792 комбинаций

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

(18) >>>Не пойдет. Не учтены комбинации когда игра не закончена.

В  смысле? Среди 255 168 - все возможные варианты до окончания игры. Если бы просто заполняли эту табличку 3x3 - было бы 9! вариантов.

(20) Это не чушь. 81 792 комбинаций, чтобы довести игру до победы на 9м шаге.

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

+ (22) Проверяем то же самое но в крестах:

Считаем: Нужно расставить 5 крестов в 9 клетках, оставшиеся клетки займут нули:
Ответ: Первый крест ставится 9 вариантами.
Второй ставится 8 вариантами.
Третий 7
Четвертый 6
Пятый 5

Итого: 9*8*7*6*5 = 15120 вариантов
Из этого числа нужно убрать все возможные перестановки.
Так как крестов 5, то делим 15120 на 5* 4*3*2 = 120:
15120 / 120 = 126

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

(21) >> Среди 255 168 - все возможные варианты до окончания игры

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

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

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

Итого: Все позиции посчитаны в (10) при условии что игроки делали ходы по очереди.

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

000
ХХХ
0ХХ

(27) Да, но нам это не нужно

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

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

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

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

Допустим ход начнем с крестика.
На первом шаге возможно 9 вариантов поставить крестик.
На втором шаге  - 8 вариантов поставить нолик. то есть уже комбинаций 9*8
На третьем шаге - 9 * 8 * 7
И так далее.

Но игру мы можем начать с нолика, тогда полученное значение 9! умножаем на 2 ))).

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

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

(35) Ок.
Вечером подумаю.

Тут двояко можно считать:
- считать количество ветвей Шаг1->Шаг2->Шаг3 и так далее;
- считать состояния: На шаге1 - количество комбинаций, плюс количество комбинаций на шаге2 и т.д.

Потом можно считать все, вплоть до заполнения последней ячейки, или ограничиваясь окончанием игры (победа или ничья)

Что мы считаем?

https://www.jesperjuul.net/ludologist/255168-ways-of-playing-tic-tac-toe

По ссылке:
всего существует 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 степени без поворотов поля и без учёта правил игры.

так как вопрос звучит?
Правильно ли понимаю: "Сколькими способами можно сыграть в крестики-нолики?"
Если так считать, то верный ответ дан тут (15).

То есть, до победы на 5 шаге существует 1 440 вариантов развития игры.

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

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

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

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

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

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

(46) не делил

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

Все не читал. Народ, к чему пришли?
Сколько комбинаций крестиков ноликов?

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

(49) в (10) и (11)

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

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

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

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

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

(54) в (10) показан пример, его нужно скопировать в калькулятр, и ответ получится 5854.

(55) Да, ты ошибся практически сразу же...

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

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

(0) С какой целью вы считаете число вариантов?
Что это дает?

Там всех стратегий- не более пяти, примитивнейшая игра!
Стадо дебилов на марше!

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

(59) +100 :)

(0)352620

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

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

Х0Х


Х
0
Х

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

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

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

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