Algorithm
problem link- https://www.spoj.com/problems/TOE2/
TOE2 - Tic-Tac-Toe ( II )
In the game of tic-tac-toe, two players take turns marking squares of an initially empty 3 × 3 grid with either X’s or O’s. The first player always marks squares using X’s, whereas the second player always marks squares using O’s. If at any point during the game either player manages to mark three consecutive squares in a row, column, or diagonal with his/her symbol, the game terminates.
Given a board configuration, your goal is to determine whether the board configuration represents the possible final state of a valid tic-tac-toe game.
Input
The input test file will contain multiple cases. Each test case consists of a single line containing 9 characters, which represent the 9 squares of a tic-tac-toe grid, given one row at a time. Each character on the line will either be ‘X’, ‘O’ (the letter O), or ‘.’ (indicating an unfilled square). The end-of-file is marked by a single line containing the word “end”.
Output
For each input test case, write a single line containing either the word “valid” or “invalid” indicating whether the given board configuration is the final state of some possible tic-tac-toe game.
Example
Input: XXXOO.XXX XOXOXOXOX OXOXOXOXO XXOOOXXOX XO.OX...X .XXX.XOOO OOXXXOOXO end Output: invalid valid invalid valid valid invalid invalid
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <map>
#include <list>
using namespace std;
string g[3];
bool checkrows(char winner){
for(int i=0;i<3;i++){
if(g[i][0]==winner&&g[i][1]==winner&&g[i][2]==winner){
return true;
}
}
return false;
}
bool checkcols(char winner){
for(int i=0;i<3;i++){
if(g[0][i]==winner&&g[1][i]==winner&&g[2][i]==winner){
return true;
}
}
return false;
}
bool checkdiagnols(char winner){
if(g[0][0]==winner&&g[1][1]==winner&&g[2][2]==winner){
return true;
}
if(g[0][2]==winner&&g[1][1]==winner&&g[2][0]==winner){
return true;
}
return false;
}
int main(){
string temp;
while(true){
cin>>temp;
if(temp=="end")break;
bool possible=true;
g[0]=temp.substr(0,3);
g[1]=temp.substr(3,3);
g[2]=temp.substr(6,3);
int xcount=0,ocount=0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
if(g[i][j]=='X'){
xcount++;
continue;
}
if(g[i][j]=='O'){
ocount++;
}
}
}
if(ocount>xcount){
possible=false;
}
if((xcount-ocount)>1){
possible=false;
}
//cout<<xcount<<" "<<ocount<<endl;
bool winnerx=(checkrows('X')||checkcols('X')||checkdiagnols('X'));
if(winnerx){
if((xcount-ocount)!=1){
possible=false;
}
}
bool winnero=(checkrows('O')||checkcols('O')||checkdiagnols('O'));
if(winnero){
if((xcount-ocount)!=0){
possible=false;
}
}
if(winnerx==true&&winnero==true){
possible=false;
}
if(winnerx!=true&&winnero!=true){
if(xcount+ocount!=9)possible=false;
}
if(possible){
printf("valid\n");
}
else{
printf("invalid\n");
}
}
return 0;
}Input
XOXOXOXOX
OXOXOXOXO
XXOOOXXOX
XO.OX...X
.XXX.XOOO
OOXXXOOXO
end
Output
valid
invalid
valid
valid
invalid
invalid
#2 Code Example with Java Programming
Code -
Java Programming
#include<stdio.h>
char str[10],**temp;
int main()
{
int i,j,no_X,no_O,flag,win_X,win_O;
while(1)
{
gets(str); no_X = no_O = flag = win_X = win_O = 0;
if(str[0]=='e')
break;
for(i=0; i<9; i++)
{
if(str[i] == 'X')
no_X++;
else if(str[i] == 'O')
no_O++;
}
if(str[4] != '.')
{
if(str[4] == 'O')
{
if((str[0] == 'O' && str[8] == 'O') || (str[1] == 'O' && str[7] == 'O') || (str[2] == 'O' && str[6] == 'O') || (str[3] == 'O' && str[5] == 'O'))
win_O = 1;
}
else
{
if((str[0] == 'X' && str[8] == 'X') || (str[1] == 'X' && str[7] == 'X') || (str[2] == 'X' && str[6] == 'X') || (str[3] == 'X' && str[5] == 'X'))
win_X = 1;
}
}
if(str[1] != '.')
{
if(str[0] == 'O')
{
if((str[3] == 'O' && str[6] == 'O') || (str[1] == 'O' && str[2] == 'O'))
win_O =1;
}
else
{
if((str[3] == 'X' && str[6] == 'X') || (str[1] == 'X' && str[2] == 'X'))
win_X =1;
}
}
if(str[8] != '.')
{
if(str[8] == 'O')
{
if((str[5] == 'O' && str[2] == 'O') || (str[7] == 'O' && str[6] == 'O'))
win_O = 1;
}
else
{
if((str[5] == 'X' && str[2] == 'X') || (str[7] == 'X' && str[6] == 'X'))
win_X = 1;
}
}
if(win_X == 1 && win_O == 1)
flag = 1;
else
{
if(win_X == 1 && win_O == 0 && no_X != no_O + 1)
flag = 1;
else if(win_X == 0 && win_O == 1 && no_X != no_O)
flag = 1;
else if(win_X == 0 && win_O == 0 && (no_X != 5 || no_O != 4))
{
flag = 1;
}
}
if(flag)
printf("invalid\n");
else
printf("valid\n");
}
return 0;
}Input
XOXOXOXOX
OXOXOXOXO
XXOOOXXOX
XO.OX...X
.XXX.XOOO
OOXXXOOXO
end
Output
valid
invalid
valid
valid
invalid
invalid
Demonstration
SPOJ Solution-TOE2 Tic-Tac-Toe ( II )-Solution in C, C++, Java, Python