1275. Find Winner on a Tic Tac Toe Game

Problem

Tic-tac-toe is played by two players A and B on a 3 x 3 grid.

Here are the rules of Tic-Tac-Toe:

• Players take turns placing characters into empty squares (" ").
• The first player A always places "X" characters, while the second player B always places "O" characters.
• "X" and "O" characters are always placed into empty squares, never on filled ones.
• The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
• The game also ends if all squares are non-empty.
• No more moves can be played if the game is over.

Given an array moves where each element is another array of size 2 corresponding to the row and column of the grid where they mark their respective character in the order in which A and B play.

Return the winner of the game if it exists (A or B), in case the game ends in a draw return "Draw", if there are still movements to play return "Pending".

You can assume that moves is valid (It follows the rules of Tic-Tac-Toe), the grid is initially empty and A will play first.

Example 1:

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"
Explanation: "A" wins, he always plays first.
"X  "    "X  "    "X  "    "X  "    "X  "
"   " -> "   " -> " X " -> " X " -> " X "
"   "    "O  "    "O  "    "OO "    "OOX"

Example 2:

Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
Output: "B"
Explanation: "B" wins.
"X  "    "X  "    "XX "    "XXO"    "XXO"    "XXO"
"   " -> " O " -> " O " -> " O " -> "XO " -> "XO " 
"   "    "   "    "   "    "   "    "   "    "O  "

Example 3:

Input: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
Output: "Draw"
Explanation: The game ends in a draw since there are no moves to make.
"XXO"
"OOX"
"XOX"

Example 4:

Input: moves = [[0,0],[1,1]]
Output: "Pending"
Explanation: The game has not finished yet.
"X  "
" O "
"   "

Constraints:

• 1 <= moves.length <= 9
• moves[i].length == 2
• 0 <= moves[i][j] <= 2
• There are no repeated elements on moves.
• moves follow the rules of tic tac toe.

Problem Summary

A and B play Tic-Tac-Toe on a 3 x 3 grid. The rules of Tic-Tac-Toe are as follows:

• Players take turns placing pieces on empty squares (" ").
• The first player A always uses "X" as the piece, while the second player B always uses "O" as the piece.
• "X" and "O" can only be placed in empty squares, not on squares that are already occupied.
• The game ends as soon as 3 identical (non-empty) pieces form a straight line (row, column, or diagonal).
• If all squares are filled with pieces (not empty), the game also ends.
• After the game ends, no more moves can be made.

Given an array moves, where each element is another array of size 2 (the elements correspond to the row and column of the grid respectively), it records the positions of the two players' pieces in the order of A's and B's moves (A first, then B). If the game has a winner (A or B), return the winner of the game; if the game ends in a draw, return "Draw"; if there are still moves to be made (the game has not ended), return "Pending". You can assume that moves is valid (follows the rules of Tic-Tac-Toe), the grid is initially empty, and A will move first.

Note:

• 1 <= moves.length <= 9
• moves[i].length == 2
• 0 <= moves[i][j] <= 2
• There are no repeated elements in moves.
• moves follows the rules of Tic-Tac-Toe.

Solution Approach

• Two players play 3*3 Tic-Tac-Toe. A moves first, then B. Output whoever can win; if it is a draw, output “Draw”; if the game has not ended yet, output “Pending”. Game rule: whoever can first occupy any full row, column, or diagonal wins.
• Easy problem. The given move array has at most 3 moves, and to win the game, one must make 3 moves, so we can first simulate by placing all of A's and B's moves on the board according to the given moves array. Then check the three cases of rows, columns, and diagonals in order. If all checks are finished, the remaining cases are draw and deadlock situations.

Code

package leetcode

func tictactoe(moves [][]int) string {
	board := [3][3]byte{}
	for i := 0; i < len(moves); i++ {
		if i%2 == 0 {
			board[moves[i][0]][moves[i][1]] = 'X'
		} else {
			board[moves[i][0]][moves[i][1]] = 'O'
		}
	}
	for i := 0; i < 3; i++ {
		if board[i][0] == 'X' && board[i][1] == 'X' && board[i][2] == 'X' {
			return "A"
		}
		if board[i][0] == 'O' && board[i][1] == 'O' && board[i][2] == 'O' {
			return "B"
		}
		if board[0][i] == 'X' && board[1][i] == 'X' && board[2][i] == 'X' {
			return "A"
		}
		if board[0][i] == 'O' && board[1][i] == 'O' && board[2][i] == 'O' {
			return "B"
		}
	}
	if board[0][0] == 'X' && board[1][1] == 'X' && board[2][2] == 'X' {
		return "A"
	}
	if board[0][0] == 'O' && board[1][1] == 'O' && board[2][2] == 'O' {
		return "B"
	}
	if board[0][2] == 'X' && board[1][1] == 'X' && board[2][0] == 'X' {
		return "A"
	}
	if board[0][2] == 'O' && board[1][1] == 'O' && board[2][0] == 'O' {
		return "B"
	}
	if len(moves) < 9 {
		return "Pending"
	}
	return "Draw"
}