Search code examples
javarecursiontreetic-tac-toe

All Tic Tac Toe Board Possibilities - Stack Overflow - Java Recursion General Trees

I am trying to generate all possible moves in the game tic tac toe with recursion and trees in java.

I am using General Trees and recursion which I find to be tough. However, the first generation in the tree should have 1 spot filled, then the next generation has 2 spots filled, then the next generation has 3 spots filled, then the next generation has 4 spots filled, etc.

My aim is to create a Node:

       #
      / 
     #-#-#-#-#-#-#-#-#
    / / / / / / / / /
(should be filled) #-#-#-#-#-#-#-#-#

Each child node has 9 siblings. Each sibling has 1/9 possible placements. An 'X' or 'O' is alternated and placed in each new generation of children (in 1 out of those 9 spots). By the last generation, the tree should be filled with X's and O's.

Trouble: My insertLayer method is recursively called infinitely. It gets stuck somewhere between the 6-8 when I input a counter to keep track of how it is growing.

Solution

  • This condition is always true:

    if (gameBoard[i][j] != 'X' || gameBoard[i][j] != 'O')

    so you’ll recurse forever.

    Change || to &&:

    if (gameBoard[i][j] != 'X' && gameBoard[i][j] != 'O')

    or better, because it’s clearer and simpler:

    if (gameBoard[i][j] != ' ')

    Note: This may not be your only bug, but it’s the most obvious and severe one I noticed.