PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Daanish Mahajan
Tester & Editorialist: Taranpreet Singh
DIFFICULTY
Easy
PREREQUISITES
PROBLEM
Tic-tac-toe is a game played between two players on a 3 \times 3 grid. In a turn, a player chooses an empty cell and places their symbol on the cell. The players take alternating turns, where the player with the first turn uses the symbol X and the other player uses the symbol O. The game continues until there is a row, column, or diagonal containing three of the same symbol (X or O), and the player with that token is declared the winner. Otherwise if every cell of the grid contains a symbol and nobody won, then the game ends and it is considered a draw.
You are given a tic-tac-toe board A after a certain number of moves, consisting of symbols O, X, and underscore(\_). Underscore signifies an empty cell.
- 1: if the position is reachable, and the game has drawn or one of the players won.
- 2: if the position is reachable, and the game will continue for at least one more move.
- 3: if the position is not reachable.
QUICK EXPLANATION
- Each state of the game can be represented as a node in a graph, edge u to v denoting that from state u, it is possible to reach state v in one move and the game did not end at state u.
- For a given state, if it is reachable from start state, and there’s no outgoing edge from that state, the answer is 1.
- For a given state, if it is reachable from start state, and there’s there’s atleast one outgoing edge from that state, the answer is 2.
EXPLANATION
There are two solutions for this problem. One solution is generic approach to such problems, by modelling the game states as a graph, second approach is specific to this problem, figuring out cases in order to determine if it is reachable, and if yes, whether the game has ended or not.
We’d discuss the graph approach, though case based approach can be found in Setter’s solution section.
Let’s represent each state of the grid as a node in graph.
What is the number of nodes in this graph? Each cell can have either of the three characters at any time, and there are 9 such positions, hence there are 3^9 = 19683 states. Hence, we can easily store the answers for all states, and answer queries in O(1).
Let’s add edge from node u to node v, if and only if the game hasn’t ended at state u and there exists a move which converts board in state u to board in state v. From each state, there can be at most 9 outgoing edges.
We start from node corresponding to empty grid, calling this the source state.
Referring to problem statement, answer is 1 is the position is reachable, and either one of the player has won, or there’s no move possible. In terms of our graph, it is equivalent to the target state node being reachable from source state node, and there’s no outgoing edge from target state node.
Similarly, answer is 2 if target state node is reachable from source state node and there’s at least 1 outgoing edge from target state node.
Hence, all we need to do is to
- Find a way to encode grid state into a node id.
- Given a board, check if either player won, or the grid is completely filled.
Grid encoding can be done by numbering cells of grid from 0 to 8 and replacing characters by 0, 1 and 2, and computing \displaystyle\sum_{i = 0}^8 g(i) * 3^i, g(i) denoting the value at ith cell.
You may refer DFS implementation in tester solution.
TIME COMPLEXITY
The time complexity for DFS approach is O(3^9*9+T).
The time complexity for case based implementation is O(3^2) per test case.
SOLUTIONS
Setter's Solution
#include<bits/stdc++.h>
# define pb push_back
#define pii pair<int, int>
#define mp make_pair
# define ll long long int
using namespace std;
const int maxt = (int)pow(3, 9);
int main()
{
int t; cin >> t;
while(t--){
string s[3];
int cX = 0, cO = 0, winX = 0, winO = 0;
// row
for(int i = 0; i < 3; i++){
cin >> s[i];
int cXr = 0, cOr = 0;
for(int j = 0; j < 3; j++){
if(s[i][j] == 'X')cXr++;
else if(s[i][j] == 'O')cOr++;
}
cX += cXr; cO += cOr;
if(cXr == 3)winX++;
else if(cOr == 3)winO++;
}
// column
for(int j = 0; j < 3; j++){
int cXc = 0, cOc = 0;
for(int i = 0; i < 3; i++){
if(s[i][j] == 'X')cXc++;
else if(s[i][j] == 'O')cOc++;
}
if(cXc == 3)winX++;
else if(cOc == 3)winO++;
}
// left diagonal
int cXd = 0, cOd = 0;
for(int i = 0; i < 3; i++){
if(s[i][i] == 'X')cXd++;
else if(s[i][i] == 'O')cOd++;
}
if(cXd == 3)winX++;
else if(cOd == 3)winO++;
// right diagonal
cXd = 0; cOd = 0;
for(int i = 0; i < 3; i++){
if(s[i][2 - i] == 'X')cXd++;
else if(s[i][2 - i] == 'O')cOd++;
}
if(cXd == 3)winX++;
else if(cOd == 3)winO++;
int ans = 2;
if((winX >= 1 && winO >= 1) || !(cX == cO || cX == cO + 1) || (winO >= 1 && cX == cO + 1) || (winX >= 1 && cX == cO))ans = 3;
else if((winX >= 1 || winO >= 1) || (cX + cO == 9))ans = 1;
cout << ans << endl;
}
}
Tester's Solution
import java.util.*;
import java.io.*;
class TCTCTOE{
//SOLUTION BEGIN
int[] pow3, state;
void pre() throws Exception{
pow3 = new int[10];
pow3[0] = 1;
for(int i = 1; i< pow3.length; i++)pow3[i] = pow3[i-1]*3;
state = new int[pow3[9]];
Arrays.fill(state, 3);
//1 -> reachable and ended
//2 -> reachable and going on
//3 -> not reachable
char[][] start = new char[][]{
{'_', '_', '_'},
{'_', '_', '_'},
{'_', '_', '_'}
};
dfs(start, 'X');
}
void dfs(char[][] g, char turn){
int id = encode(g);
if(state[id] != 3)return;//This state is already processed
if(ended(g)){
state[id] = 1;
return;
}
state[id] = 2;
for(int i = 0; i< g.length; i++){
for(int j = 0; j< g[i].length; j++){
if(g[i][j] == '_'){
g[i][j] = turn;
dfs(g, (char)('X' + 'O'-turn));
g[i][j] = '_';
}
}
}
}
void solve(int TC) throws Exception{
char[][] grid = new char[3][];
for(int i = 0; i< grid.length; i++)grid[i] = n().toCharArray();
pn(state[encode(grid)]);
}
//Checks if the game is finished or not.
boolean ended(char[][] g){
boolean win = false;
for(int i = 0; i< 3; i++){
win |= g[i][0] != '_' && g[i][0] == g[i][1] && g[i][1] == g[i][2];
win |= g[0][i] != '_' && g[0][i] == g[1][i] && g[1][i] == g[2][i];
}
win |= g[0][0] != '_' && g[0][0] == g[1][1] && g[1][1] == g[2][2];
win |= g[0][2] != '_' && g[0][2] == g[1][1] && g[1][1] == g[2][0];
boolean filled = true;
for(char[] row:g)
for(char cell:row)
filled &= cell != '_';
return win || filled;
}
int encode(char[][] g){
int id = 0;
for(int i = 0; i< g.length; i++)
for(int j = 0; j< g[i].length; j++)
id += pow3[i*3+j]*get(g[i][j]);
return id;
}
int get(char ch){
switch(ch){
case '_':return 0;
case 'X':return 1;
case 'O':return 2;
default: return -1;
}
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new TCTCTOE().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 
