Tic Tac Toe

Slug: tic-tac-toe2412

Difficulty: Medium

Id: 703239

Topic Tags: Arrays, Data Structures, Algorithms

Company Tags: Flipkart, Accolite, Amazon, Microsoft

Summary

The Tic Tac Toe problem is a classic game of strategy and logic. Given the current state of the board, determine whether it's possible to win or not for both X and O players. The game follows standard rules where two players take turns marking empty squares on a 3x3 grid with either X or O. The player who first gets three in a row (horizontally, vertically, or diagonally) wins the game.

Detailed Explanation

To solve this problem, we need to implement a function that takes the current state of the board as input and returns whether it's possible for X to win or not. We can do this by analyzing all possible moves from the given position and checking if any of them result in a winning situation.

Here's a step-by-step breakdown of the solution:

Initialize two variables, winX and winO, to track whether it's possible for X or O to win respectively.
Iterate over each cell on the board.
For each cell, simulate all possible moves by both players (X and O) from that position.
Check if any of these simulated moves result in a winning situation for either player. If yes, update winX or winO accordingly.
Return !winO as the final answer, indicating whether it's possible for X to win.

Here's an ASCII art diagram representing the board:

 1 | 2 | 3
  ---------
4 | 5 | 6
  ---------
7 | 8 | 9

Time complexity: O(1) since we're not iterating over any data structure. Space complexity: O(1) as we're only using a few extra variables.

Optimized Solutions

Java

public boolean canWin(char[][] board, char player) { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (board[i][j] == ' ') { // Simulate move by current player board[i][j] = player; // Check if the simulated move results in a win boolean win = checkWin(board); // Undo the simulated move board[i][j] = ' '; // If the simulated move resulted in a win, return true if (win) { return true; } } } } // If no winning moves are found, return false return false; } public boolean checkWin(char[][] board) { // Check rows and columns for a win for (int i = 0; i < 3; i++) { if ((board[i][0] == board[i][1] && board[i][1] == board[i][2]) || (board[0][i] == board[1][i] && board[1][i] == board[2][i])) { return true; } } // Check diagonals for a win if ((board[0][0] == board[1][1] && board[1][1] == board[2][2]) || (board[0][2] == board[1][1] && board[1][1] == board[2][0])) { return true; } // If no win is found, return false return false; }