cs1302-ce26 Tic-Tac-Toe Solver

This class exercise futher explores the concept of recursion.

You will write a method to print all possible Tic-Tac-Toe boards from a given starting point. Some helpful utility methods are provided for you in the starter code contained in the provided Maven project.

Course-Specific Learning Outcomes

LO2.c: Use recursion to solve a non-trivial problem in a software solution.

References and Prerequisites

CSCI 1302 Recursion Tutorial

Questions

In your notes, clearly answer the following questions. These instructions assume that you are logged into the Odin server.

NOTE: If a step requires you to enter in a command, please provide in your notes the full command that you typed to make the related action happen. If context is necessary (e.g., the command depends on your present working directory), then please note that context as well.

Getting Started

Use Git to clone the repository for this exercise onto Odin into a subdirectory called cs1302-ce26:
```
$ git clone --depth 1 https://github.com/cs1302uga/cs1302-ce26.git
```
Change into the cs1302-ce26 directory that was just created and look around. There should be multiple Java files contained within the directory structure. To see a listing of all of the files under the src subdirectory, use the find command as follows:
```
$ find src
```

Exercise Steps

Checkpoint 1 Steps

While looking in the src directory, you likely saw a file called TTTUtility.java. This file contains a Tic-Tac-Toe utility class with some helpful methods. Take a few minutes to familiarize yourselves with the documentation for these methods using the documentation found here: TTT Utility
Take a few more minutes to read through TTTSolver.java. This file contains a main method which takes in an encoding for a game board. It then passes this game board to printAllBoards. We will implement printAllBoards soon. For now, it simply prints the current game board.
Next, use Maven to compile and run the code.. Please use the exec:java phase with the -Dexec.mainClass option to run. The program should ask you to enter a game board. Enter a valid game board and make sure the board is printed to the screen before moving on.
- Once you get the code to compile and run, please write down the command you used in your notes along with your chosen board configuration.
Open the TTTUtility.java file and implement the isCat method. The method takes a String reference to the current game board. Note: a game is a cat game (or tie) if all spaces are full and neither 'X' nor 'O' has won the game. To simplify your implementation, use the methods already present in TTTUtility.
Add a line to the main method in TTTSolver.java to print true if the specified game board is a tie and false otherwise. You should use the isCat method that you wrote in the previous step.
Ensure you pass checkstyle, recommit if needed, and tag as checkpoint-1.

Checkpoint 2 Steps

Consider a recursive implementation for the printAllBoards method in TTTSolver.
- Identify the base case(s). Give an example. Hint: A base case for tic-tac-toe would be any configuration resulting in the game being over.
- Identify the recursive case(s).
- Draw the recursion tree for printAllBoards("XOXOXO---").
Implement the printAllBoards method in TTTSolver.
Use Maven to compile and run the code. After you've confirmed that it compiles and runs, ensure you pass checkstyle, recommit if needed, and tag as checkpoint-2.
Check your recursion tree against the solution here _____ before moving on___

Checkpoint 3 Steps

Implement a new method in TTTSolver called countAllWinningBoards that, given an initial board state and a player, returns a count of all winning board states for that player that can be reached via a valid sequence of moves by each player. Here is the signature for the method to help you get started:
```
int countAllWinningBoards(String board, char player)
```
In the main method of TTTSolver, add code to test your countAllWinningBoards method by reading input from the user. Since we already have the user entering a board, you will just need to add a prompt for the user to type which player to evaluate (X or O). Then, output the result of calling countAllWinningBoards(board, player) to the console.
Use Maven to compile and run the code. Then, add some print statements to convince your instructor or TA that your code is working. Use initial board configurations that you can compute manually at first.
Ensure you pass checkstyle, recommit if needed, and tag as checkpoint-3.

Submission Steps

Each student needs to individually submit their own work.

Create a plain text file called SUBMISSION.md directly inside the cs1302-ce26 directory with the following information.
1. Your name and UGA ID number;
2. Collaborator names, if any; and
3. If you created the API website, include the full link to the site you generated.
Here is an example of the contents of SUBMISSION.md.
```
1. Sally Smith (811-000-999)
2. Collaborators: Joe Allen, Stacie Mack
3. https://webwork.cs.uga.edu/~user/cs1302-ce26-doc
```
Change directories to the parent of cs1302-ce26 (e.g., cd .. from cs1302-ce26). If you would like to make a backup tar file, the instructions are in the submissions steps for ce02. We won't repeat those steps here and you can view them as optional.
Use the submit command to submit this exercise to csci-1302:
```
$ submit cs1302-ce26 csci-1302
```
Read the output of the submit command very carefully. If there is an error while submitting, then it will displayed in that output. Additionally, if successful, the submit command creates a new receipt file in the directory you submitted. The receipt file begins with rec and contains a detailed list of all files that were successfully submitted. Look through the contents of the rec file and always remember to keep that file in case there is an issue with your submission.

Note: You must be on Odin to submit.

Copyright © Michael E. Cotterell, Brad Barnes, and the University of Georgia. This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License to students and the public. The content and opinions expressed on this Web page do not necessarily reflect the views of nor are they endorsed by the University of Georgia or the University System of Georgia.

cs1302uga/cs1302-ce26