![]() But we can actually ignore that since there's no way to win two ways without a common cell without having already violated the "maximum difference of one" rule, since you need six cells for that, with the opponent only having three. There's actually another limitation in that it's impossible for one side to have won in two different ways without a common cell (again, they would have won in a previous move), meaning that: XXXĬan be. ![]() If both have three in a row, then one of them would have won in the previous move. In addition, it's impossible to have a state where both sides have three in a row, so they can be discounted as well. There are only 3 9, or 19,683 possible combinations of placing x, o or in the grid, and not all of those are valid.įirst, a valid game position is one where the difference between x and o counts is no more than one, since they have to alternate moves. This is one of those problems that's actually simple enough for brute force and, while you could use combinatorics, graph theory, or many other complex tools to solve it, I'd actually be impressed by applicants that recognise the fact there's an easier way (at least for this problem). ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |