EZ
3^9 возможных состояний
но это без учета симметрии
но это без учета симметрии
это ограничение сверху
Size: a a a
2017 October 31
Dv
Всем привет. Меня тут мучает вопрос важный. Хочу написать алгоритм подсчета всех возможных партий в крестики-нолики. Написал и получилась фигня какая-то, 115 - это слишком мало. Может кто знает как нужно? Или ссылку.
Вот что быстро нашлось: http://www.se16.info/hgb/tictactoe.htm
Dv
Там у автора побольше выходит.
AJ
Вот что быстро нашлось: http://www.se16.info/hgb/tictactoe.htm
о, спасибо. Я вот искал именно алгоритм, мне кажется он должен быть сильно проще чем математическое решение. Но если не найду, буду читать как решается математически
X
он действительно сильно проще, чем математическое решение
X
я даже не могу слёта сказать, как правильно учесть все повороты и отражения, чтобы избежать повторного учёта партий
АГ
Там у автора побольше выходит.
тоже предположил что число больше должно быть, может автор вопроса имел в виду выигрышные комбинации.. ?
X
ну то есть, если пойти от мысли, что варианта победы может быть только три с точностью до поворотов и отражений (диагональ, крайняя строка и средняя строка)
X
то не совсем понятно, как избежать повторных подсчётов комбинаторно
X
ну, положим, мы рассматриваем все варианты победы в 2.5 хода (т.е. первого игрока)
X
положим, что начали с "первой строки" (все победы путём заполнения верхней строчки)
X
с понтом "потом умножим на количество возможных отражений/поворотов"
АГ
ну то есть, если пойти от мысли, что варианта победы может быть только три с точностью до поворотов и отражений (диагональ, крайняя строка и средняя строка)
наверно тогда уже 2?
X
три варианта победы
АГ
крайняя средняя - обе 3 в ряд
АГ
это один
АГ
+ диагональ
X
не
X
никакой поворот или отражение не переводит строку крайнюю в строку среднюю
X
а, поменяв местами крайнюю и среднюю, можно превратить ничью в выигрыш, поэтому менять местами нельзя