/*****
 *
 *	Stephen Fulwider
 *	BHCSI - 2007
 *	Tic-Tac-Toe Program
 *
 *	Utilizes backtracking for a computer opponent
 *
 *****/

import java.io.*;
import java.util.*;

public class TTTBacktrack
{
	private int[][] board;
	private int numMoves;
	
	private static final int EMPTY = 0;
	private static final int X = -1;
	private static final int O = 1;
	private static final int SIZE = 3;
	
	private TTTBacktrack()
	{
		board = new int[SIZE][SIZE];
		for (int i=0; i<SIZE; i++)
			Arrays.fill(board[i], EMPTY);
		numMoves = 0;
	}

	/* try to make a move -- return true if move made, false otherwise */
	private boolean makeMove(int r, int c, int move)
	{
		if (!inBounds(r,c))
			return false;
		if (board[r][c] != EMPTY)
			return false;
		board[r][c] = move;
		numMoves++;
		return true;
	}
	private void undoMove(int r, int c)
	{
		numMoves--;
		board[r][c] = EMPTY;
	}
	/* determine if spot is in bounds */
	private boolean inBounds (int r, int c)
	{
		return (r>=0 && r<SIZE && c>=0 && c<SIZE);
	}
	
	private int getNumMoves()
	{
		return numMoves;
	}
	
	/*
	 * cp == current player
	 */
	private spot getCompMove(int cp)
	{
		int min = Integer.MIN_VALUE;
		spot nextMove;
		spot bestMove = new spot(-1,-1,-1);
		
		/* go through each spot, try each open spot -- start @ 1,1 because it is
		 *	important to always try and fill the center first */
		for (int i=1; i<=SIZE; i++)
			for (int j=1; j<=SIZE; j++)
			{
				/* try to make this move, continue if this spot can't be played in */
				if (!makeMove(i%SIZE,j%SIZE,cp))
					continue;
				
				/* get result of making this move */
				int result = winner();
				
				/* if this move allows current player to win or game to be a draw,
				 *	return this as the result */
				if (result==cp || numMoves==SIZE*SIZE)
				{
					undoMove(i%SIZE,j%SIZE);
					return new spot(i%SIZE,j%SIZE,result);
				}
				
				/* get opponent's best counter move */
				nextMove = getCompMove(cp*-1);
				
				/* if this is the better than the best move found so far for this
				 *	player, then take it */
				if (nextMove.result*cp > min)
				{
					min = nextMove.result*cp;
					bestMove = new spot(i%SIZE,j%SIZE,min);
				}
				undoMove(i%SIZE,j%SIZE);
			}
			
			/* return this spot with result of min * player */
			return new spot(bestMove.x,bestMove.y,min*cp);	
	}
	
	private int winner()
	{
		/* check rows */
		for (int i=0; i<SIZE; i++)
			if (board[i][0] == board[i][1] && board[i][1] == board[i][2] && board[i][0] != EMPTY)
				return board[i][0];
				
		/* check cols */
		for (int i=0; i<SIZE; i++)
			if (board[0][i] == board[1][i] && board[1][i] == board[2][i] && board[0][i] != EMPTY)
				return board[0][i];
				
		/* check diags */
		if (board[0][0] == board[1][1] && board[1][1] == board[2][2] && board[0][0] != EMPTY)
			return board[0][0];
		if (board[2][0] == board[1][1] && board[1][1] == board[0][2] && board[2][0] != EMPTY)
			return board[2][0];
			
		/* else no winner yet or tie */
		return EMPTY;
		
	}
	
	/* print board */
	public String toString()
	{
		String s = "\n";
		for (int i=0; i<SIZE; i++)
		{
			for (int j=0; j<SIZE; j++)
				s += getPieceName(board[i][j]) + (j!=SIZE-1?" | ":"");
			s += "\n" + (i!=SIZE-1?"---------\n":"\n");
		}
		return s;
	}
	
	/* main to get it all going */
	public static void main(String[] args) throws Exception
	{
		System.out.println("X is Human, O is Computer\nHuman makes first move");
		TTTBacktrack game = new TTTBacktrack();
		Scanner stdIn = new Scanner(System.in);
		int r,c;
		int winner;
		
		while ((winner = game.winner()) == EMPTY && game.getNumMoves() != 9)
		{
			System.out.println(game);
			do
			{
				System.out.println("Input your move");
				r = stdIn.nextInt();
				c = stdIn.nextInt();
			} while (!game.makeMove(r,c,X));
			if ((winner = game.winner()) != EMPTY)
				break;
			spot compMove = game.getCompMove(O);
			game.makeMove(compMove.x,compMove.y,O);
		}
		
		if (game.getNumMoves() == 9)
			System.out.println("Game is a draw!");
		else
			System.out.println(getPieceName(winner) + " WINS!");
		System.out.println(game);
	}
	
	public static String getPieceName(int piece)
	{
		if (piece == 0)
			return " ";
		else if (piece == -1)
			return "X";
		return "O";
		
	}

}

// (x,y) cooridiate point class w/ cnt of that spot
class spot
{
	public int x, y, result;
	
	public spot (int xx, int yy, int r)
	{
		x = xx;
		y = yy;
		result = r;
	}
	public spot(int xx, int yy)
	{
		this(xx,yy,0);
	}
	
	
	
}