# TCTCTOE - Editorial

Setter: Daanish Mahajan
Tester & Editorialist: Taranpreet Singh

Easy

# PREREQUISITES

Depth First Search

# 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.

Print

• 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;
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());}

StringTokenizer st;
}

public FastReader(String s) throws Exception{
}

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{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}


Feel free to share your approach. Suggestions are welcomed as always.

6 Likes

can anyone tell me why the hell my code is getting WA.

/* package codechef; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Codechef {
public static void main(String[] args) throws java.lang.Exception {
int t = Integer.parseInt(inp.readLine());
while (t-- > 0) {
String a = inp.readLine();
String b = inp.readLine();
String c = inp.readLine();
int countX = 0, count_ = 0, countO = 0;
for (int i = 0; i < 3; i++) {
// a String
if (a.charAt(i) == 'X') {
countX++;
} else if (a.charAt(i) == 'O') {
countO++;
} else {
count_++;
}

// b String
if (b.charAt(i) == 'X') {
countX++;
} else if (b.charAt(i) == 'O') {
countO++;
} else {
count_++;
}

// c String
if (c.charAt(i) == 'X') {
countX++;
} else if (c.charAt(i) == 'O') {
countO++;
} else {
count_++;
}
}
//            System.out.println(countX + " " + countO + " " + count_);
int countXWinner = checkWinnerX(a, b, c, 'X');
int countOWinner = checkWinnerO(a, b, c, 'O');
//            System.out.println(countXWinner + " " + countOWinner);
int ans = 3;
if (countX == countO) {
if (countXWinner == 0) {
if (countOWinner > 0) {
// System.out.println(1);
ans = 1;
} else {
// System.out.println(2);
ans = 2;
}
} else {
// System.out.println(3);
ans = 3;
}
} else if (countX == (countO + 1)) {
if (count_ > 0) {
if (countXWinner > 0 && countOWinner > 0) {
// System.out.println(3);
ans = 3;
} else if (countXWinner > 0 && countOWinner == 0) {
// System.out.println(1);
ans = 1;
} else {
// System.out.println(2);
ans = 2;
}
} else {
if ((countXWinner > 0 && countOWinner > 0) || (countOWinner > 0)) {
// System.out.println(3);
ans = 3;
} else  {
// System.out.println(1);
ans = 1;
}
}
} else {
// System.out.println(3);
ans = 3;
}
System.out.println(ans);
}
}

private static int checkWinnerO(String a, String b, String c, char o) {
int countWin = 0;
if (a.equals("OOO")) {
countWin++;
}
if (b.equals("OOO")) {
countWin++;
}
if (c.equals("OOO")) {
countWin++;
}
if (a.charAt(0) == o && b.charAt(0) == o && c.charAt(0) == o) {
countWin++;
}
if (a.charAt(1) == o && b.charAt(1) == o && c.charAt(1) == o) {
countWin++;
}
if (a.charAt(2) == o && b.charAt(2) == o && c.charAt(2) == o) {
countWin++;
}
if (a.charAt(0) == o && b.charAt(1) == o && c.charAt(2) == o) {
countWin++;
}
if (a.charAt(2) == o && b.charAt(1) == o && c.charAt(0) == o) {
countWin++;
}
return countWin;
}

private static int checkWinnerX(String a, String b, String c, char x) {
int countWin = 0;
if (a.equals("XXX")) {
countWin++;
}
if (b.equals("XXX")) {
countWin++;
}
if (c.equals("XXX")) {
countWin++;
}
if (a.charAt(0) == x && b.charAt(0) == x && c.charAt(0) == x) {
countWin++;
}
if (a.charAt(1) == x && b.charAt(1) == x && c.charAt(1) == x) {
countWin++;
}
if (a.charAt(2) == x && b.charAt(2) == x && c.charAt(2) == x) {
countWin++;
}
if (a.charAt(0) == x && b.charAt(1) == x && c.charAt(2) == x) {
countWin++;
}
if (a.charAt(2) == x && b.charAt(1) == x && c.charAt(0) == x) {
countWin++;
}
return countWin;
}
}



I Have already tested manually approx 25 extra test case.

I think you missed edge cases such as
XXX this is a valid path
0X0
0X0 as
X_X is valid
0X0
0X0
there are 4*3+4+6 = 22 such edge cases

1 Like

Simple JAVA Approach

  import java.util.*;
import java.lang.*;
import java.io.*;
class Main{
static int a=0;
static int b=0;
static int c=0;
public static void numbers(String[] ttt){
int countX=0;
int countO=0;
int count_=0;
for(int i=0;i<3;i++){
String str=ttt[i];
for(int j=0;j<3;j++){
char ch=str.charAt(j);
if(ch=='X'){
countX++;
}else if(ch=='O'){
countO++;
}else{
count_++;
}
}
}
a=countX;
b=countO;
c=count_;
}
public static int howManyWon(String[] ttt){
int xRow=0;
int xCol=0;
int Owon=0;
int dxwon=0;
int dowon=0;
// check horizontally
String p=ttt[0];
String q=ttt[1];
String r=ttt[2];
if(p.equals("XXX")){
xRow++;
}else if(p.equals("OOO")){
Owon++;
}

if(q.equals("XXX")){
xRow++;
}else if(q.equals("OOO")){
Owon++;
}

if(r.equals("XXX")){
xRow++;
}else if(r.equals("OOO")){
Owon++;
}
// check Vertically
String x=""+p.charAt(0)+q.charAt(0)+r.charAt(0);
String y=""+p.charAt(1)+q.charAt(1)+r.charAt(1);
String z=""+p.charAt(2)+q.charAt(2)+r.charAt(2);
if(x.equals("XXX")){
xCol++;
}else if(x.equals("OOO")){
Owon++;
}

if(y.equals("XXX")){
xCol++;
}else if(y.equals("OOO")){
Owon++;
}

if(z.equals("XXX")){
xCol++;
}else if(z.equals("OOO")){
Owon++;
}

// diagnolly

String d1=""+p.charAt(0)+q.charAt(1)+r.charAt(2);
String d2=""+r.charAt(0)+q.charAt(1)+p.charAt(2);
if(d1.equals("XXX")){
dxwon++;
}else if(d1.equals("OOO")){
dowon++;
}

if(d2.equals("XXX")){
dxwon++;
}else if(d2.equals("OOO")){
dowon++;
}

int Xwon=xRow+xCol;

if((Xwon==1 && Owon==0) || (xRow==1 && xCol==1 ) || dxwon==2 || dxwon==1){
// x actually

return 1;
}else if((Xwon==0 && Owon==1) || dowon==2 || dowon==1){
// O actually won
return 0;
}else if(Xwon==0 && Owon==0 && dxwon==0 && dowon==0){
return 2;
}else{
return 3;
}

}
public static void main (String[] args) throws java.lang.Exception
{
int T=sc.nextInt();
for(int t=0;t<T;t++){
// sc.nextLine();
String ttt[]=new String[3];
for(int i=0;i<3;i++){
}
numbers(ttt); // x, o , _ numbers
int l=howManyWon(ttt); // who wons

if(a-b>1){
System.out.println("3");
continue;
}
if(b>a){
System.out.println("3");
continue;
}
if(l==3){
System.out.println("3");
continue;
}
if(l==1){
if(a!=b+1){
System.out.println("3");
}else{
System.out.println("1");
}
continue;
}
if(l==0){
if(a!=b){
System.out.println("3");
}
else{
System.out.println("1");
}
continue;
}
if(l==2){
if(c==0){
System.out.println("1");
}
else{
System.out.println("2");

}
continue;
}
}
}
}


This was my code in JAVA. It got accepted

These are the Test Cases :

25
XXX
OXO
XOO
XOX
___
___
X_O
_OX
O_X
OOO
OOO
OOO
XXX
OOO
OOO
___
___
___
XOX
XXO
O_O
XXX
OOO
___
_OX
OX_
XO_
OXX
XOO
OXX
OXO
XOX
XXO
XOX
OXO
OXO
XOX
OX_
XO_
XO_
___
__X
XOX
__X
_O_
XOX
XXO
O_O
XXX
OOO
___
OOO
XXX
XXX
XOO
OOO
OXX
XXX
OOX
OOX
XOO
OXO
XXX
XOO
_X_
XXX
XOX
OXO
XOX
XXX
XXX
XXX
OOO
___
___


Having Respected Output as :

1
2
1
3
3
2
2
3
3
1
3
3
1
2
2
2
3
3
3
1
1
3
1
3


Check for this-
XOO
XOO
XXX
Expected output for that should be 1

Yes I am getting 1 for the test case -

XOO
XOO
XXX


Your code is failing in this test case. Answer should be 3 your code will give 2.

1
OXX
XOX
__O

Thanks Man, I got my Mistake.

Hey I wonder why online compiler is giving wrong answer even though I have checked most of the edge cases

#include<bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i,n) for(i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?++i:--i)
#define ll long long
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define test cout<<"This is TEST********\n";
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define sz(c) (int)c.size()
#define ans(x) cout<<x<<'\n';
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pl;
typedef vector<int>		vi;
typedef vector<ll>		vl;
typedef vector<pii>		vpii;
typedef vector<pl>		vpl;
typedef vector<vi>		vvi;
typedef vector<vl>		vvl;

void solve() {
int i, j,k, row[3] = {0}, col[3] = {0}, diag[2] = {0},  win = -1, nx=0, ny=0;
string n;
fo(i, 3) {
cin >> n;
fo(j, 3)
{	k=int(n[j]);
row[i] += k;
col[j] += k;
if (i == j) diag[0] += k;
if (i == 2 - j) diag[1] += k;
if(k==88)nx++;
else if(k==79)ny++;
}
}
if ((nx - ny) > 1 || ny>nx ) {
ans(3); return;
}

fo(i, 3) {

if (row[i] == 264 || col[i]==264 || diag[i%2]==264) {

if(win==-1) {if(nx<=ny){ans(3);return;}
win=0;}
else if(win!=0){ans(3);return;}
}

if (row[i] == 237 || col[i]==237 || diag[i%2]==237) {

if(win==-1) { if(ny<nx){ans(3);return;}win=0;}
else if(win!=1){ans(3);return;}
}

}
if (nx+ny==9 || win!=-1) {
ans(1);return;
}

ans(2);

}

signed main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

int t;
cin >> t;
while (t--) {
solve();
}

return 0;
}


Solution: 46298975 | CodeChef @darshancool25. I code the same logic (as per ur video editorial) but still there is an issue and I am unable to find that.

Because you checked â€śmostâ€ť instead of â€śallâ€ť

1
___
OOO
XXX

1 Like
1
__X
_XO
XOO

if(res>1) cout<<"3\n";


Is the mistake.

1
XXX
OXO
XOO

Should be 1, not 3

Damn in my checking function I copied the win checker for X to O but forgot to change the win variable value to 1.
Thanks man

1 Like

@dharshancool25
can you please explain me that why should we take the condition
!((x==o)||(x==o+1)) in that why should we use ! this .
if two person wins the game ,we need to check that the count of x and o should be equal or greater than one if any one of its is true canâ€™t we print 3 .why should we go for ! this sir.
thank you in advance

tried 30 + cases .pls tell me that one damn case where its going wrong

#include
using namespace std;

int main()
{
long long int T;
cin>>T;
for( long long int k=0;k<T;k++)
{ int X=0,O=0;
char r1[3],r2[3],r3[3];
cin>>r1[0]>>r1[1]>>r1[2];
cin>>r2[0]>>r2[1]>>r2[2];
cin>>r3[0]>>r3[1]>>r3[2];

    for(int i=0;i<3;i++)//counting X and O
{
if(r1[i]=='X')
X++;
else if(r1[i]=='O')
O++;

if(r2[i]=='X')
X++;
else if(r2[i]=='O')
O++;

if(r3[i]=='X')
X++;
else if(r3[i]=='O')
O++;

}
bool o2=false;
bool d=false;
bool h=false;
bool v=false;
bool won=false;
bool win2=false;  /**more than one winner case is
not reachable except for
the cases where x wins through
two ways simultaneously for eg.XXX
OXO
OOX
i make win2 true whenever this happens**/

int winner=0;
//deciding if anyone won
for(int i=0;i<3;i++)
{
if(r1[i]==r2[i] && r2[i]==r3[i] && (r3[i]=='X' || r3[i]=='O') )
{   if(r3[i]=='O')
{o2=true;}
won=true;
winner++;
if(r1[i]=='X')
{v=true;}
}
}

if(r1[0]==r1[1] && r1[1]==r1[2] && (r1[2]=='X' || r1[2]=='O') )
{   if(r1[2]=='O')
{o2=true;}
won=true;
winner++;
if(r1[0]=='X')
{h=true;}
}

if(r2[0]==r2[1] && r2[1]==r2[2] && (r2[2]=='X' || r2[2]=='O') )
{   if(r2[2]=='O')
{o2=true;}
won=true;
winner++;
if(r2[0]=='X')
{h=true;}
}
if(r3[0]==r3[1] && r3[1]==r3[2] && (r3[2]=='X' || r3[2]=='O') )
{   if(r3[2]=='O')
{o2=true;}
won=true;
winner++;
if(r3[0]=='X')
{h=true;}
}

if( ( ( r1[0]==r2[1] && r2[1]==r3[2] ) || ( r1[2]==r2[1] && r2[1]==r3[0] ) ) && ( r2[1]=='X' || r2[1]=='O') )
{   if(r2[1]=='O')
{o2=true;}
won=true;
winner++;
if(r2[1]=='X')
{
d=true;
}
if(( r1[0]==r2[1] && r2[1]==r3[2] ) && ( r1[2]==r2[1] && r2[1]==r3[0] ) && r2[1]=='X')
{win2=true;}
}

if(h==true && v==true || d==true && h==true || v==true && d==true)/**this checks if two wins
have happened simultaneously**/

{ win2=true;}

if(X-O==1 || X-O==0)//as we start with X ,O can never be more than X
{
if(X+O!=9 && won==false)
{cout<<2<<endl;}
else if ((winner>1 && win2==false ) || ( o2==true && X-O==1) )
{cout<<3<<endl;}
else
{cout<<1<<endl;}
}
else
{
cout<<3<<endl;
}

}
return 0;


}

1
___
___
__O


@ojas_17

https://www.codechef.com/viewsolution/46624166
Can someone please provide test case(s) where this wont work. Have been trying for a long time

#include <bits/stdc++.h>
#define int long long int
using namespace std;

bool hasWonX = false, hasWonO = false, rowWinX = false, rowWinO = false, colWinX = false, colWinO = false, diagWinX = false, diagWinO = false;

bool oneKindOfWinX()
{
if ((rowWinX && !colWinX && !diagWinX) || (!rowWinX && colWinX && !diagWinX) || (!rowWinX && !colWinX && diagWinX))
return true;
else
return false;
}

bool oneKindOfWinO()
{
if ((rowWinO && !colWinO && !diagWinO) || (!rowWinO && colWinO && !diagWinO) || (!rowWinO && !colWinO && diagWinO))
{
// cout << (rowWinO && !colWinO && !diagWinO) << " " << (!rowWinO && colWinO && !diagWinO) << " " << (!rowWinO && !colWinO && diagWinO) << "\n";
return true;
}
else
{
return false;
}
}

int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("../input.txt", "r", stdin);
freopen("../output.txt", "w", stdout);
#endif

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int t;
cin >> t;
while (t--)
{
hasWonX = false, hasWonO = false, rowWinX = false, rowWinO = false, colWinX = false, colWinO = false, diagWinX = false, diagWinO = false;
string r1, r2, r3;
cin >> r1 >> r2 >> r3;

int spaceCount = 0, oCount = 0, xCount = 0;

for (int i = 0; i < 3; i++)
{
if (r1[i] == '_')
spaceCount++;
if (r2[i] == '_')
spaceCount++;
if (r3[i] == '_')
spaceCount++;
if (r1[i] == 'X')
xCount++;
if (r2[i] == 'X')
xCount++;
if (r3[i] == 'X')
xCount++;
if (r1[i] == 'O')
oCount++;
if (r2[i] == 'O')
oCount++;
if (r3[i] == 'O')
oCount++;
}

// Case 1 - game is reachable and decided
// Case 2 - game is reachable and not decided
// Case 3 - game is unreachable

//Row wins
if ((r1[0] == r1[1] && r1[1] == r1[2] && r1[1] == 'X') || (r2[0] == r2[1] && r2[1] == r2[2] && r2[1] == 'X') || (r3[0] == r3[1] && r3[1] == r3[2] && r3[1] == 'X'))
{
hasWonX = true;
rowWinX = true;
}
if ((r1[0] == r1[1] && r1[1] == r1[2] && r1[1] == 'O') || (r2[0] == r2[1] && r2[1] == r2[2] && r2[1] == 'O') || (r3[0] == r3[1] && r3[1] == r3[2] && r3[1] == 'O'))
{
hasWonO = true;
rowWinO = true;
}

//Col wins
if ((r1[0] == r2[0] && r2[0] == r3[0] && r2[0] == 'X') || (r1[1] == r2[1] && r2[1] == r3[1] && r2[1] == 'X') || ((r1[2] == r2[2] && r2[2] == r3[2] && r2[2] == 'X')))
{
hasWonX = true;
colWinX = true;
}
if ((r1[0] == r2[0] && r2[0] == r3[0] && r2[0] == 'O') || (r1[1] == r2[1] && r2[1] == r3[1] && r2[1] == 'O') || ((r1[2] == r2[2] && r2[2] == r3[2] && r2[2] == 'O')))
{
hasWonO = true;
colWinO = true;
}

//Diag wins
if ((r1[0] == r2[1] && r2[1] == r3[2] && r2[1] == 'X') || (r3[0] == r2[1] && r2[1] == r1[2] && r2[1] == 'X'))
{
hasWonX = true;
diagWinX = true;
}
if ((r1[0] == r2[1] && r2[1] == r3[2] && r2[1] == 'O') || (r3[0] == r2[1] && r2[1] == r1[2] && r2[1] == 'O'))
{
hasWonO = true;
diagWinO = true;
}

//Case break - if x greater or o greater
if(xCount - oCount > 1 || oCount - xCount > 1 || (oCount > xCount && hasWonX) || (xCount > oCount && hasWonO) )
{
cout << "3\n";
continue;
}

//Case 1a) - X wins
if (hasWonX && oneKindOfWinX() && !hasWonO)
{
cout << "1\n";
continue;
}
// Case 1b) - O wins
else if (hasWonO && oneKindOfWinO() && !hasWonX)
{
cout << "1\n";
continue;
}
// Case 1c) - Draw
else if (spaceCount == 0 && !hasWonO && !hasWonO)
{
cout << "1\n";
continue;
}

//Case 2) - Continue
else if (!hasWonO && !hasWonX && spaceCount > 0)
{
cout << "2\n";
continue;
}

// Case 3) - Unreachable
else if ((hasWonO && hasWonX) || !oneKindOfWinO() || oneKindOfWinX())
{
cout << "3\n";
continue;
}
else
cout << "why? \n";
// If it reaches here I am stupid

// cout << "hasWonX " << hasWonX << " "
//      << "hasWonO " << hasWonO << " "
//      << "rowWinX " << rowWinX << " "
//      << "rowWinO " << rowWinO << " "
//      << "colWinX " << colWinX << " "
//      << "colWinO " << colWinO << " "
//      << "diagWinX " << diagWinX << " "
//      << "diagWinO " << diagWinO << "\n";
}
return 0;
}`