Your task is to produce answers for questions 9.100 - 9.105 in the book. All of these questions are counting questions about tic-tac-toe board configurations. Rather than write a proof, you are asked to write code to count for you.
You will need a copy of the textbook to see the problem definitions.
You are expected to modify these files:
BoardCounting.java – there is a method for each problemYou are expected to read, use, but not necessarily modify these files:
Board.java – a Java representation of a tic-tac-toe board with lots of useful helper methods. You are free to add more helper methods.To answer each question, you should write a recursive algorithm that essentially “plays” the game of Tic-Tac-Toe and keeps track of the relevant information to answer the question.
For example, the first question asks you to count the number of filled in boards. You can approach this recursively by observing the following:
number of filled in boards =
number of filled in boards after X goes in (1,1) +
number of filled in boards after X goes in (1,2) +
number of filled in boards after X goes in (1,3) +
number of filled in boards after X goes in (2,1) +
number of filled in boards after X goes in (2,2) +
number of filled in boards after X goes in (2,3) +
number of filled in boards after X goes in (3,1) +
number of filled in boards after X goes in (3,2) +
number of filled in boards after X goes in (3,3)
Then counting the
number of filled in boards after X goes in (1,1)
can be computed by counting number of filled in boards after O goes in each of the remaining open positions. Eventually, all positions are filled in the and the number of boards to count is 1!
While you should not modify the existing methods, you are free (and encouraged!) to write helper methods. In fact, this will be critical for questions that ask you to count distinct boards. There, you may want a helper function that returns a set of boards, rather than simply an integer.