dragoon's blog

By dragoon, 14 years ago, In English
I dont find any good blog posting describing the solution or may be i missed. Can any one help?
  • Vote: I like it
  • 0
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it +14 Vote: I do not like it
I think the easiest way to solve this problem is to simulate all possible games with backtracking. Once you find the given position it's not hard to determine whose next move is or who has just won the game. If the given position was not found during the backtracking then it's obviously an illegal position. This way you only have to implement very straightforward things, like recursive backtracking, and you don't have to do a boring case analysis which also is pretty error prone.
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Actually I implemented this without any recursions. Here are some checks that may help you to state that the position is illegal. Let a1 be the number of X (turns of first player), a2 be the number of 0 (second player). Then the state is illegal, if any of the following holds true:
1. a1<a2.
2. a1-a2>1.
3. a1-a2=1, but the second player already won.
4. a1-a2=0, but the first player already won.
5. Both first and second player already won.
The check, if the player has won, is quite straightforward, we consider that he won, if some horizontal, vertical, or diagonal is filled completely by this player. So, if the state is not illegal, you perform this check for both players. If someone wins, we are done.
Finally, if nothing of the previous was true, check if a1+a2=9. In that case we have a draw. If a1-a2=0, it's the first player turn, and the second player turn otherwise.
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    i am sorry, actually i wanted to mean problem D. :( I have to repost :( I sucked in my first post :(
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    i am sorry, actually i wanted to mean problem D. :( I have to repost :( I sucked in my first post :(