CSC-220 Tic-Tac-Toe Solution

PlayTicTacToe.java

/*
 * Name: Antonio Silvestri
 * Date: 10/1/2018
 * Course Number: CSC-220
 * Course Name: Data Structures
 * Problem Number: HW4
 * Email: silvestri@stcc.edu
 * Main Program to Drive TicTacToe Class V3.2
 */

package tictactoe;

import java.util.Scanner;

public class PlayTicTacToe {

	private static void playGame(Scanner keyboard) {

		char p = 'X';
		TicTacToe ttt = new TicTacToe();
		int r, c;

		do {
			System.out.println(ttt);
			do {
				System.out.print("'" + p + "', choose your location (row, column): ");
				try {
					r = keyboard.nextInt();
					c = keyboard.nextInt();
					if (!ttt.isValid(r, c))
						System.out.println("That is not a valid location. Try again.");
					else if (ttt.playerAt(r, c) != ' ')
						System.out.println("That location is already full. Try again.");
					else
						break;
				}
				catch (Exception e) {
					System.out.println("Bad Integer Entered. Try Again.");
					keyboard.nextLine();  //IMPORTANT! Clear keyboard!!!
				}
			} while (true);

			ttt.playMove(p, r, c);

			if (p == 'X')
				p = 'O';
			else
				p = 'X';

		} while (!ttt.isWinner('X') && !ttt.isWinner('O') && !ttt.isFull());

		System.out.println(ttt);
		
		String status;
		if (ttt.isWinner('X'))
			status = "X is the winner!";
		else if (ttt.isWinner('O'))
			status = "O is the winner!";
		else
			status = "The game is a tie.";
		status += " After " + ttt.getTurns() + " plays.";
		System.out.println(status);
	}

	// **********************************************

	private static void process(Scanner sc, String args[]) {
		playGame(sc);
		sc.nextLine(); // IMPORTANT!! Reset Scanner
	}

	// **********************************************

	private static boolean doThisAgain(Scanner sc, String prompt) {
		System.out.print(prompt);
		String doOver = sc.nextLine();
		return doOver.equalsIgnoreCase("Y");
	}

	// **********************************************

	public static void main(String args[]) {
		final String TITLE = "Play Tic Tac Toe V1.0";
		final String CONTINUE_PROMPT = "Play again? [y/N] ";

		System.out.println("Welcome to " + TITLE);
		Scanner sc = new Scanner(System.in);
		do {
			process(sc, args);
		} while (doThisAgain(sc, CONTINUE_PROMPT));
		sc.close();
		System.out.println("Thank you for using " + TITLE);
	}

}

PlayTicTacToe2.java

/*
 * Name: Antonio Silvestri
 * Date: 10/1/2018
 * Course Number: CSC-220
 * Course Name: Data Structures
 * Problem Number: HW4
 * Email: silvestri@stcc.edu
 * Main Program to Drive TicTacToe Class V3.2
 */

package tictactoe;

import java.util.Scanner;

public class PlayTicTacToe2 {

	private static void playGame(Scanner keyboard) {

		char p = 'X';
		TicTacToe ttt = new TicTacToe();
		int r, c;

		do {
			System.out.println(ttt);
			if (p == 'X') {
				do {
					System.out.print("'" + p + "', choose your location (row, column): ");
					try {
						r = keyboard.nextInt();
						c = keyboard.nextInt();
						if (!ttt.isValid(r, c))
							System.out.println("That is not a valid location. Try again.");
						else if (ttt.playerAt(r, c) != ' ')
							System.out.println("That location is already full. Try again.");
						else
							break;
					} catch (Exception e) {
						System.out.println("Bad Integer Entered. Try Again.");
						keyboard.nextLine(); // IMPORTANT! Clear keyboard!!!
					}
				} while (true);

				ttt.playMove(p, r, c);
				p = 'O';
			}
			else {
				// O is playing.
				// Generate a row and col that hasn't been played
				do {
					r = (int)(3 * Math.random());
					c = (int)(3 * Math.random());
				} while (ttt.playerAt(r, c) != ' ');
				
				ttt.playMove(p, r, c);
				p = 'X';
			}

		} while (!ttt.isWinner('X') && !ttt.isWinner('O') && !ttt.isFull());

		System.out.println(ttt);

		String status;
		if (ttt.isWinner('X'))
			status = "X is the winner!";
		else if (ttt.isWinner('O'))
			status = "O is the winner!";
		else
			status = "The game is a tie.";
		status += " After " + ttt.getTurns() + " plays.";
		System.out.println(status);
	}

	// **********************************************

	private static void process(Scanner sc, String args[]) {
		playGame(sc);
		sc.nextLine(); // IMPORTANT!! Reset Scanner
	}

	// **********************************************

	private static boolean doThisAgain(Scanner sc, String prompt) {
		System.out.print(prompt);
		String doOver = sc.nextLine();
		return doOver.equalsIgnoreCase("Y");
	}

	// **********************************************

	public static void main(String args[]) {
		final String TITLE = "Play Tic Tac Toe V2.0";
		final String CONTINUE_PROMPT = "Play again? [y/N] ";

		System.out.println("Welcome to " + TITLE);
		Scanner sc = new Scanner(System.in);
		do {
			process(sc, args);
		} while (doThisAgain(sc, CONTINUE_PROMPT));
		sc.close();
		System.out.println("Thank you for using " + TITLE);
	}

}

PlayTicTacToe4.java

/*
 * Name: Antonio Silvestri
 * Date: 10/1/2018
 * Course Number: CSC-220
 * Course Name: Data Structures
 * Problem Number: HW4
 * Email: silvestri@stcc.edu
 * Main Program to Drive TicTacToe Class V3.2
 */

package tictactoe;

import java.util.Scanner;

public class PlayTicTacToe4 {

	private static int[] findTwo(TicTacToe ttt, char player) {
		// Process Rows
		for (int r = 0; r < 3; r++)
			for (int i = 0; i < 3; i++) {
				boolean found = true;
				for (int j = 0; j < 3; j++)
					found = found && ttt.getPlayerAt(r, j) == (i == j ? ' ' : player);
				if (found)
					return new int[] { r, i };
			}

		// Process Cols
		for (int c = 0; c < 3; c++)
			for (int i = 0; i < 3; i++) {
				boolean found = true;
				for (int j = 0; j < 3; j++)
					found = found && ttt.getPlayerAt(j, c) == (i == j ? ' ' : player);
				if (found)
					return new int[] { i, c };
			}

		// Process TL-BR diagonal
		for (int i = 0; i < 3; i++) {
			boolean found = true;
			for (int j = 0; j < 3; j++)
				found = found && ttt.getPlayerAt(j, j) == (i == j ? ' ' : player);
			if (found)
				return new int[] { i, i };
		}

		// Process BL-TR diagonal
		for (int i = 0; i < 3; i++) {
			boolean found = true;
			for (int j = 0; j < 3; j++)
				found = found && ttt.getPlayerAt(2 - j, j) == (i == j ? ' ' : player);
			if (found)
				return new int[] { 2 - i, i };
		}

		return null;
	}

	// **********************************************

	private static void playGame(Scanner keyboard) {

		char p = 'X';
		TicTacToe ttt = new TicTacToe();
		int r, c;

		do {
			System.out.println(ttt);
			if (p == 'X') {
				do {
					System.out.print("'" + p + "', choose your location (row, column): ");
					try {
						r = keyboard.nextInt();
						c = keyboard.nextInt();
						if (!ttt.isValid(r, c))
							System.out.println("That is not a valid location. Try again.");
						else if (ttt.playerAt(r, c) != ' ')
							System.out.println("That location is already full. Try again.");
						else
							break;
					} catch (Exception e) {
						System.out.println("Bad Integer Entered. Try Again.");
						keyboard.nextLine(); // IMPORTANT! Clear keyboard!!!
					}
				} while (true);

				ttt.playMove(p, r, c);
				p = 'O';
			} else {
				// O is playing.
				// First find 2 O's and a blank choose the blank and win!,
				// Else find 2 X'x and a blank choose the blank to block,
				// Else Generate a row and col that hasn't been played
				int move[] = findTwo(ttt, TicTacToe.O);
				if (move != null) {
					r = move[0];
					c = move[1];
				} 
				else {
					move = findTwo(ttt, TicTacToe.X);
					if (move != null) {
						r = move[0];
						c = move[1];
					} 
					else {
						do {
							r = (int) (3 * Math.random());
							c = (int) (3 * Math.random());
						} while (ttt.playerAt(r, c) != ' ');
					}
				}

				ttt.playMove(p, r, c);
				p = 'X';
			}
		} while (!ttt.isWinner('X') && !ttt.isWinner('O') && !ttt.isFull());

		System.out.println(ttt);

		String status;
		if (ttt.isWinner('X'))
			status = "X is the winner!";
		else if (ttt.isWinner('O'))
			status = "O is the winner!";
		else
			status = "The game is a tie.";
		status += " After " + ttt.getTurns() + " plays.";
		System.out.println(status);
	}

	// **********************************************

	private static void process(Scanner sc, String args[]) {
		playGame(sc);
		sc.nextLine(); // IMPORTANT!! Reset Scanner
	}

	// **********************************************

	private static boolean doThisAgain(Scanner sc, String prompt) {
		System.out.print(prompt);
		String doOver = sc.nextLine();
		return doOver.equalsIgnoreCase("Y");
	}

	// **********************************************

	public static void main(String args[]) {
		final String TITLE = "Play Tic Tac Toe V4.0";
		final String CONTINUE_PROMPT = "Play again? [y/N] ";

		System.out.println("Welcome to " + TITLE);
		Scanner sc = new Scanner(System.in);
		do {
			process(sc, args);
		} while (doThisAgain(sc, CONTINUE_PROMPT));
		sc.close();
		System.out.println("Thank you for using " + TITLE);
	}

}

PlayTicTacToe5.java

/*
 * Name: Antonio Silvestri
 * Date: 10/1/2018
 * Course Number: CSC-220
 * Course Name: Data Structures
 * Problem Number: HW4
 * Email: silvestri@stcc.edu
 * Main Program to Drive TicTacToe Class V3.2
 */

package tictactoe;

import java.util.Scanner;

public class PlayTicTacToe5 {

	private static void playGame(Scanner keyboard) {

		char p = 'X';
		TicTacToeMinimax ttt = new TicTacToeMinimax();
		int r, c;

		do {
			System.out.println(ttt);
			if (p == 'X') {
				do {
					System.out.print("'" + p + "', choose your location (row, column): ");
					try {
						r = keyboard.nextInt();
						c = keyboard.nextInt();
						if (!ttt.isValid(r, c))
							System.out.println("That is not a valid location. Try again.");
						else if (ttt.playerAt(r, c) != ' ')
							System.out.println("That location is already full. Try again.");
						else
							break;
					} catch (Exception e) {
						System.out.println("Bad Integer Entered. Try Again.");
						keyboard.nextLine(); // IMPORTANT! Clear keyboard!!!
					}
				} while (true);

				ttt.playMove(p, r, c);
				p = 'O';
			}
			else {
				// O is playing.
				// Generate a row and col that hasn't been played
				Point o = ttt.findBestComputerMove();
				ttt.playMove(p, o.x, o.y);
				p = 'X';
			}

		} while (!ttt.isWinner('X') && !ttt.isWinner('O') && !ttt.isFull());

		System.out.println(ttt);

		String status;
		if (ttt.isWinner('X'))
			status = "X is the winner!";
		else if (ttt.isWinner('O'))
			status = "O is the winner!";
		else
			status = "The game is a tie.";
		status += " After " + ttt.getTurns() + " plays.";
		System.out.println(status);
	}

	// **********************************************

	private static void process(Scanner sc, String args[]) {
		playGame(sc);
		sc.nextLine(); // IMPORTANT!! Reset Scanner
	}

	// **********************************************

	private static boolean doThisAgain(Scanner sc, String prompt) {
		System.out.print(prompt);
		String doOver = sc.nextLine();
		return doOver.equalsIgnoreCase("Y");
	}

	// **********************************************

	public static void main(String args[]) {
		final String TITLE = "Play Tic Tac Toe V5.0";
		final String CONTINUE_PROMPT = "Play again? [y/N] ";

		System.out.println("Welcome to " + TITLE);
		Scanner sc = new Scanner(System.in);
		do {
			process(sc, args);
		} while (doThisAgain(sc, CONTINUE_PROMPT));
		sc.close();
		System.out.println("Thank you for using " + TITLE);
	}

}

Point.java

package tictactoe;

public class Point {

    int x, y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "[" + x + ", " + y + "]";
    }
}

TicTacToe.java

// Tony Silvestri
// 10/19/2016
// CSC-220 Data Structures
// silvestri@stcc.edu
// HW4
// Solution to the TicTacToe Class

package tictactoe;

public class TicTacToe {
	public static final char SPACE = ' ';
	public static final char X = 'X';
	public static final char O = 'O';
	public static final char BAD = '#';
	public static final int SIZE = 3;

	private char board[][];
	private int turns;

	public TicTacToe() {
		this.turns = 0;
		this.board = new char[SIZE][SIZE];
		for (int i = 0; i < board.length; i++)
			for (int j = 0; j < board[i].length; j++)
				this.board[i][j] = TicTacToe.SPACE;
	}

	public boolean isValid(int r, int c) {
		return r >= 0 && r < this.board.length && c >= 0 && c < this.board[r].length;
	}

	public char playerAt(int r, int c) {
		if (this.isValid(r, c))
			return this.board[r][c];
		return TicTacToe.BAD;
	}
	
	public char getPlayerAt(int r, int c) {
		return this.playerAt(r, c); // Synonym!
	}

	public int getTurns() {
		return this.turns;
	}
	
	private static boolean allEqualTo(char array[], char c) {
		for (int i = 0; i < array.length; i++)
			if (array[i] != c)
				return false;
		return true;				
	}

	public boolean isWinner(char c) {
		// Check rows
		for (int i = 0; i < this.board.length; i++) {
			if (TicTacToe.allEqualTo(this.board[i], c))
				return true;
		}

		char temp[] = new char[this.board.length];
		
		// Check columns
		for (int i = 0; i < this.board.length; i++) {
			for (int j = 0; j < this.board.length; j++)
				temp[j] = this.board[j][i];
			if (TicTacToe.allEqualTo(temp, c)) 
				return true;
		}

		// Check Diagonal \
	    for (int i = 0; i < this.board.length; i++)
	    	temp[i] = this.board[i][i];
	    if (TicTacToe.allEqualTo(temp, c)) 
			return true;
				
		// Check Diagonal /
		for (int i = 0; i < this.board.length; i++)
			temp[i] = this.board[i][this.board.length - 1 - i];
		if (TicTacToe.allEqualTo(temp, c)) 
			return true;
			
		return false;
	}
	
	public boolean isTied() {
		return this.isFull() && !this.isWinner('X') && !this.isWinner('O');
	}

	public boolean isFull() {
		for (int i = 0; i < this.board.length; i++)
			for (int j = 0; j < this.board[0].length; j++)
				if (this.board[i][j] == TicTacToe.SPACE)
					return false;
		return true;
	}

	public void playMove(char p, int r, int c) {
		if (this.isValid(r, c) && this.board[r][c] == TicTacToe.SPACE) {
			this.board[r][c] = p;
			this.turns++;
		}
	}

	public String toStringOld() {
		String grid = "";
		for (int i = 0; i < this.board.length; i++) {
			for (int j = 0; j < this.board[i].length; j++) {
				grid += String.format(" %c ", this.board[i][j]);
				if (j < this.board[0].length - 1)
					grid += "|";
			}
			grid += "\n";
			if (i < this.board.length - 1)
				grid += "---+---+---\n";
		}
		return grid;
	}
	
	public String toString() {
		StringBuilder grid = new StringBuilder();
		for (int i = 0; i < this.board.length; i++) {
			for (int j = 0; j < this.board[i].length; j++) {
				grid.append(String.format(" %c ", this.board[i][j]));
				if (j < this.board[0].length - 1)
					grid.append("|");
			}
			grid.append("\n");
			if (i < this.board.length - 1)
				grid.append("---+---+---\n");
		}
		return grid.toString();
	}
	
}

TicTacToeMinimax.java

// Tony Silvestri
// 10/19/2016
// CSC-220 Data Structures
// silvestri@stcc.edu
// HW4
// Solution to the TicTacToe Class

package tictactoe;

import java.util.ArrayList;
import java.util.List;

public class TicTacToeMinimax {
	public static final char SPACE = ' ';
	public static final char X = 'X';
	public static final char O = 'O';

	private char board[][];
	private int turns;

	public TicTacToeMinimax() {
		this.turns = 0;
		this.board = new char[3][3];
		for (int i = 0; i < board.length; i++)
			for (int j = 0; j < board[0].length; j++)
				this.board[i][j] = TicTacToeMinimax.SPACE;
	}

	public boolean isValid(int r, int c) {
		return r >= 0 && r < this.board.length && c >= 0 && c < this.board[0].length;
	}

	public char getPlayerAt(int r, int c) {
		return this.playerAt(r, c); // Synonym!
	}

	public char playerAt(int r, int c) {
		if (this.isValid(r, c))
			return this.board[r][c];
		return TicTacToeMinimax.SPACE;
	}

	public int getTurns() {
		return this.turns;
	}

	private static boolean allEqualTo(char array[], char c) {
		for (int i = 0; i < array.length; i++)
			if (array[i] != c)
				return false;
		return true;
	}

	public boolean isWinner(char c) {
		// Check rows
		for (int i = 0; i < this.board.length; i++) {
			if (TicTacToeMinimax.allEqualTo(this.board[i], c))
				return true;
		}

		char temp[] = new char[this.board[0].length];

		// Check columns
		for (int i = 0; i < this.board[0].length; i++) {
			for (int j = 0; j < this.board.length; j++)
				temp[j] = this.board[j][i];
			if (TicTacToeMinimax.allEqualTo(temp, c))
				return true;
		}

		// Check Diagonal \
		for (int i = 0; i < this.board.length; i++)
			temp[i] = this.board[i][i];
		if (TicTacToeMinimax.allEqualTo(temp, c))
			return true;

		// Check Diagonal /
		for (int i = 0; i < this.board.length; i++)
			temp[i] = this.board[i][this.board[0].length - 1 - i];
		if (TicTacToeMinimax.allEqualTo(temp, c))
			return true;

		return false;
	}

	public boolean isTied() {
		return this.isFull() && !this.isWinner('X') && !this.isWinner('O');
	}

	public boolean isFull() {
		for (int i = 0; i < this.board.length; i++)
			for (int j = 0; j < this.board[0].length; j++)
				if (this.board[i][j] == TicTacToeMinimax.SPACE)
					return false;
		return true;
	}

	public void playMove(char p, int r, int c) {
		if (this.isValid(r, c) && this.board[r][c] == TicTacToeMinimax.SPACE) {
			this.board[r][c] = p;
			this.turns++;
		}
	}

	public String toStringOld() {
		String grid = "";
		for (int i = 0; i < this.board.length; i++) {
			for (int j = 0; j < this.board[0].length; j++) {
				grid += String.format(" %c ", this.board[i][j]);
				if (j < this.board[0].length - 1)
					grid += "|";
			}
			grid += "\n";
			if (i < this.board.length - 1)
				grid += "---+---+---\n";
		}
		return grid;
	}

	public String toString() {
		StringBuilder grid = new StringBuilder();
		for (int i = 0; i < this.board.length; i++) {
			for (int j = 0; j < this.board[0].length; j++) {
				grid.append(String.format(" %c ", this.board[i][j]));
				if (j < this.board[0].length - 1)
					grid.append("|");
			}
			grid.append("\n");
			if (i < this.board.length - 1)
				grid.append("---+---+---\n");
		}
		return grid.toString();
	}

	public List<Point> getAvailableStates() {
		List<Point> availablePoints = new ArrayList<>();
		for (int i = 0; i < 3; ++i) {
			for (int j = 0; j < 3; ++j) {
				if (board[i][j] == SPACE) {
					availablePoints.add(new Point(i, j));
				}
			}
		}
		return availablePoints;
	}

	private Point computersMove;

	public Point findBestComputerMove() {
		minimax(0, O);
		return computersMove;
	}
	
	private int minimax(int depth, char turn) {
		if (hasOWon())
			return +1;
		if (hasXWon())
			return -1;

		List<Point> pointsAvailable = getAvailableStates();
		if (pointsAvailable.isEmpty())
			return 0;

		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;

		for (int i = 0; i < pointsAvailable.size(); ++i) {
			Point point = pointsAvailable.get(i);
			if (turn == O) {
				this.playMove(O, point.x, point.y);
				int currentScore = minimax(depth + 1, X);
				max = Math.max(currentScore, max);

				//if (depth == 0)
				//	System.out.println("Score for position " + (i + 1) + " = " + currentScore);
				if (currentScore >= 0) {
					if (depth == 0)
						computersMove = point;
				}
				if (currentScore == 1) {
					board[point.x][point.y] = SPACE;
					break;
				}
				if (i == pointsAvailable.size() - 1 && max < 0) {
					if (depth == 0)
						computersMove = point;
				}
			} else if (turn == X) {
				this.playMove(X, point.x, point.y);
				int currentScore = minimax(depth + 1, O);
				min = Math.min(currentScore, min);
				if (min == -1) {
					board[point.x][point.y] = SPACE;
					break;
				}
			}
			board[point.x][point.y] = SPACE; // Reset this point
		}
		return turn == O ? max : min;
	}

	private boolean hasOWon() {
		return this.isWinner('O');
	}

	private boolean hasXWon() {
		return this.isWinner('X');
	}
}