794. Valid Tic-Tac-Toe State

A Tic-Tac-Toe board is given as a string array board. Return True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.

The board is a 3 x 3 array, and consists of characters " ", "X", and "O".  The " " character represents an empty square.

Here are the rules of Tic-Tac-Toe:

  • Players take turns placing characters into empty squares (" ").
  • The first player always places "X" characters, while the second player always places "O" characters.
  • "X" and "O" characters are always placed into empty squares, never 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.
Example 1:
Input: board = ["O  ", "   ", "   "]
Output: false
Explanation: The first player always plays "X".

Example 2:
Input: board = ["XOX", " X ", "   "]
Output: false
Explanation: Players take turns making moves.

Example 3:
Input: board = ["XXX", "   ", "OOO"]
Output: false

Example 4:
Input: board = ["XOX", "O O", "XOX"]
Output: true

Note:

  • board is a length-3 array of strings, where each string board[i] has length 3.
  • Each board[i][j] is a character in the set {" ", "X", "O"}.

Rust Solution

struct Solution;

impl Solution {
    fn valid_tic_tac_toe(board: Vec<String>) -> bool {
        let mut a = vec![vec![]; 3];
        let mut x = 0;
        let mut o = 0;
        for (i, row) in board.iter().enumerate() {
            for c in row.chars() {
                match c {
                    'X' => {
                        x += 1;
                    }
                    'O' => {
                        o += 1;
                    }
                    _ => {}
                }
                a[i].push(c);
            }
        }
        let win_x = Self::win(&a, 'X');
        let win_o = Self::win(&a, 'O');
        x == o + 1 && win_x >= 0 && win_o == 0 || x == o && win_x == 0 && win_o <= 1
    }

    fn win(board: &[Vec<char>], c: char) -> i32 {
        let mut rows = vec![0; 3];
        let mut cols = vec![0; 3];
        let mut diagonals = vec![0; 2];
        for i in 0..3 {
            for j in 0..3 {
                let v = if board[i][j] == c { 1 } else { 0 };
                rows[i] += v;
                cols[j] += v;
                if i == j {
                    diagonals[0] += v;
                }
                if i + j == 2 {
                    diagonals[1] += v;
                }
            }
        }
        let mut sum = 0;
        if rows.iter().any(|&row| row == 3) {
            sum += 1;
        }
        if cols.iter().any(|&col| col == 3) {
            sum += 1;
        }
        if diagonals.iter().any(|&diagonal| diagonal == 3) {
            sum += 1;
        }
        sum
    }
}

#[test]
fn test() {
    let board = vec_string!["O  ", "   ", "   "];
    let res = false;
    assert_eq!(Solution::valid_tic_tac_toe(board), res);
    let board = vec_string!["XOX", " X ", "   "];
    let res = false;
    assert_eq!(Solution::valid_tic_tac_toe(board), res);
    let board = vec_string!["XXX", "   ", "OOO"];
    let res = false;
    assert_eq!(Solution::valid_tic_tac_toe(board), res);
    let board = vec_string!["XOX", "O O", "XOX"];
    let res = true;
    assert_eq!(Solution::valid_tic_tac_toe(board), res);
    let board = vec_string!["XXX", "OOX", "OOX"];
    let res = true;
    assert_eq!(Solution::valid_tic_tac_toe(board), res);
}

Having problems with this solution? Click here to submit an issue on github.