## Wednesday, December 30, 2009

### TIC TAC TOE - 'C' code and Algorithm - Part 2

Let’s just recollect what we have been through...

(1) We took position as input from user.
(2) Validated the position to be in the range of 1 and 9.
(3) Made sure that the given position is not repeated.
(4) Calculated position for two dimensional array.
(5) And then stored respective value considering the active player.

Now comes the actual part, checking whether particular move of the player made him win or game to draw.

There are many possible ways that a player can win in this game. One can win by making three equal symbols in any of the three rows, or even any of the three columns, or even any of the two diagonals.

So there are totally 8 possible ways that a player can win. If all of these chances are missed, game is said to be draw.

There are two ways in deciding completion of game. One being traversing whole board and finding whether it has any triplet hanging around row or column or even diagonal and second being to spread out from the active position and is its effect on board.
I will go for second way as it’s sensible to work with active position then searching whole board every time.

When a player enters the position, we need to check what effect it has to the board. From the very point it stands, we need to check the possible row, column and diagonal(s).

I have divided the board into three sections. First, three rows come under horizontal section. Second, three columns come under vertical section and finally, two diagonals come under diagonal section.

Let us visualize the situation.....

00 | 01 | 02
10 | 11 | 12
20 | 21 | 22

Following is the map of board. Let’s say that, player 1 chose ‘12’ as his position.

00 | 01 | 02
10 | 11 | 12
20 | 21 | 22

So the possible triplets which may make him win are (10, 11 and 12) and (02, 12 and 22)

I will go for another example....

This time player 2 chose 11 as his position, so the possible winning triplets are...

00 | 01 | 02
10 | 11 | 12
20 | 21 | 22

2nd row ---- (10, 11 and 12)

2nd column ---- (01, 11 and 21)

Diagonal ---- (00, 11 and 22) and

Cross diagonal ---- (02, 11 and 20)

Position we have in hand is 11. So we will traverse the row it stands in. Turn left from 11 to go to 10, but you will end up with two terms only, to compare.

And it’s same with other case too, when you take right turn and go to 12.

Now we’ll try vertical/column. Go up and meet 01 or greet 21 turning down from 11.

One would feel happy if he gets a position on the border of board as he can traverse in a single direction picking the three stones for comparison.

And the answer is just crouching in the corner. Try to make the given position friendlier so that you can easily play with it.

Note:
There might be different cases in front you; out of which some are so easy to solve and rest of them ask you to commit suicide. In that case, try to bring those evil cases to the range where you can easily solve them. And if you fail to do so, break the problem into sub sections and solve them individually.

So in this case, we will be so happy if the user enters a border position as we can just run in a direction comparing the three terms.v
Now, 11 is the demon in our hand. We need to mask this position in such a way that it represents a border term.

First thing is first; you need to agree with me that comparing the three terms in any order is same. Isn’t that right?

In the case of horizontal or row checking, we can start the comparison from the first element of the row. So I will try to mask the 11 term to 10; which is the position where comparison starts.

11 ---- 10
12 ---- 10
10 ---- 10

Did you observe the similarity?

Column number is zero in every case. That’s it; we are done with masking the position. Whatever the position is given, just change the column number to zero and start the comparison in that row going three steps right.

Have a gulp of air. Check the position’s map again to clear the fog in mind.

00 | 01 | 02
10 | 11 | 12
20 | 21 | 22

Coming to column checking; just make the row number to zero and traverse towards down.

So we are ready with the blueprint for both row and column checking’s.

Let’s start working....

Row checking:

When one traverses through a row, the value of row remains same and the column itself changes (increments).

```
int col = 0 , temp, fail = 0;
temp = tac[row][col];

while(col<3)
{
if(tac[row][col]!=temp)
// say that all row elements are not equal...
fail = 1;
else
col++;
}
```

Initially I made ‘col’ to be zero and throughout this snippet the value of ‘row’ stays constant; saying that we are traversing in same row. ‘temp’ is used to store the value of first term in that row and it is compared with rest of the two elements.

So when the three terms are equal, we come out with ‘fail’ as zero or one when all the three are not equal.

Column Checking:

When one traverses through a column, the value of column remains same and the row itself changes (increments).

```
int row = 0, temp, fail = 0;
temp=toe[row][col];

while(row<3)
{
if(toe[row][col]!=temp)
fail = 1; // say that all row elements are not equal...
else
row++;
}
```

So we are done with both row and column checking. The only part left in front of us is the diagonal checking.

Diagonal Checking:

There are two diagonals to be verified. Elements of them being, (00, 11 and 22) and (02, 11 and 20)

Let us consider the first diagonal (00, 11 and 22) initially.

One can observe that the values of both row and column are equal. And so whenever we face a position which has row and column values equal, we should go for the checking of first diagonal.

```
if ( row == col)
{
row=0;
temp=tic[0][0];
count=0;

for ( row=0 ; row<3 ; row++ )
if ( tic[row][row] == temp )
count++;

if(count==3)
// Game over
}
```

Values of the ‘row’ variable in ‘for’ loop are 0, 1 and 2. And so tic[row][row] would be replaced by tic[ 0 ][ 0 ],tic[ 1 ][ 1 ] and tic[ 2 ][ 2 ].

‘count’ variable is used to count the number of same terms. And so if the ‘count’ variable turns 3 after the for loop is completed than it says that all the three terms are equal; which also says that game is over as one of the player has won.
Now we are left with cross diagonal.

When ‘11’ is given as input, our program would directly go and search the first diagonal initially. If it fails, we need to go for next diagonal.

So the only elements left over are 20 and 02.

```
if( ((row == 2)&&(col == 0)) || ((row == 0)&&(col == 2)) )
{
row = 0;
col = 2;
temp=tic[row][row];
count=0;

for (k=1 ; k<=3 ; k++)
{
if ( tic[row][col] == temp )
count++;

row++;
col--;
}

if(count==3)
// Game over
}
```

In the cross diagonal, positions of the terms are 02, 11 and 20.

Observe that row numbers are increasing and column numbers are decreasing.

Row --- 0, 1 and 2
Column --- 2, 1 and 0

And there are three terms, so I can conclude that, one need to work out three times with twp variables; one increasing and other decreasing.

```
for (k=1 ; k<=3 ; k++)
{
if ( tic[row][col] == temp )
count++;

row++;
col--;
}
```

Above code does the same; ‘for’ loop is executed three times and meanwhile the values of both row and column are changed respectively.

This completes the whole program.