Wednesday, December 30, 2009

TIC TAC TOE - 'C' code and Algorithm - Part 1


I’m back with a game this time. Well, this might be a huge tutorial, but after this most of the newbie problems will perish. So let’s get started.

Introduction to game:

In a game of Tic Tac Toe, two players take turns making an available cell in a 3X3 grid with their respective tokens (either X or O). When one player has placed three tokens in a horizontal, vertical or diagonal row on the grid, the game is over and that player has won. A draw (No winner) occurs when all the cells on the grid have been filled with tokens and neither player has achieved a win.


Let’s just note down steps to be covered.
(1) Take input position from player.
(2) Check whether respective player wins with that position.
(3) If not, continue start again from 1st step.
It’s so simple to analyse these things, but there is lot more to do to achieve these steps.

Selecting Data Structure:

We need a data structure to store the values of both the players. We have 9 cells and so we need 9 blocks, to store.

Let’s make this program simple by selecting simple data structure, arrays. So we are now left with two options, single and 2-Dimensional arrays.

I selected 2-dimensional array as I have to traverse through rows and columns (I will make it clear) and diagonals too. I will later try to deal the same cases with single dimensional array.

To learn how to traverse a matrix, please read this post.(I will update this ASAP)

Take input position from player

3X3 grid has 9 cells. So let’s name them from 1 to 9.

This is a two human player game and so we will depend on user itself. System just validates the games.

The input taken from user has to be checked whether it is between 1 and 9.

Let the take input be stored in variable named ‘pos’. And so following will be a simple and clear code to validate it.

printf(“\n Enter the position: “);
}while( (pos<1) || (pos>9) );

Hope that you know the syntax and how a do-while loop works, if not go through following post.(I will update this ASAP)

When the given input, ‘pos’, is not in the prescribed range, loop is executed again and this continues until users enters a value in between 1 and 9.

Until now, we had a candy. Now let’s increase the pace.

It is obvious that we need to see that the validated position is not used earlier.
Isn’t that a new point!!! We shouldn’t take repetitive positions. And so another validation is required to see whether given position has been used earlier or not.
To do so, we need to keep a track of positions which we have used initially. So we need a storage place for positions also (we took one 2-dimensional array for 3X3 grid)

I will consider a single dimensional array of size 9 storing the information whether the particular position has been used or not.

Let us name it ‘position’.

Int position[9];

And I will initially place zero in every element of it, meaning that particular position has not been used.

for(i=0;i<9;i++) position[i]=0;

Now we have to check whether given position, ‘pos’, has been used earlier or not.

Printf(“\n Position is already used”);

We are collecting positions from 1 to 9, but the index of an array starts from 0. So we need to subtract one from the position we got so to go for respective index.

Input range: 1 to 9
Array range: 0 to 8

As said earlier, 0 represents that position has not been used yet and 1 states that it has been used. So the first ‘if’ condition checks whether given position’s respective index’s value is equal to 1, if so, it states that position is already used.

If not, value of the respective position is made 1.

But when the position is already is used, we need to ask the user to enter a new position.

printf(“\n Enter the position: “);
}while( (pos<1) || (pos>9) );

Printf(“\n Position is already used”);


Here outer do-while takes care of repetitive positions and inner do-while takes care of validating the position itself. Code executes inside out.

(1) First check whether given position is right or not.
(2) And then check whether given position used earlier or not.

So when we come out of two loops, we will have a totally valid position which user has selected.

As we are done with validating the position, let’s now utilize this position for storing user’s symbol (X or O) in 2-dimensional array. But for that, we need values of row and column.

Following is the map of the user’s position input.

1 | 2 | 3
4 | 5 | 6
7 | 8 | 9

We need to convert this into following 2-d array.

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

I will consider two variables, ‘row’ and ‘col’, representing rows and columns of the 3X3 matrix.

So, when the user enters 5, we should understand that he wanted row as 1 and col as 1.

Let us find row first and then col.

1 | 2 | 3
4 | 5 | 6
7 | 8 | 9

This is the input map and the map of row will be...

0 | 0 | 0
1 | 1 | 1
2 | 2 | 2

So for set of 1, 2, and 3 you want row value to be 0.

1, 2 and 3 ---- 0
4, 5 and 6 ---- 1
7, 8 and 9 ---- 2

Observe that for every three terms the value we need is changing.

1/3 = 0, as both are of Integer Data types

And so 2/3 =0

But 3/3 =1

This repeats in every set with the last term.

Subtract one from user’s input (pos) and then divide it with three.

(1-1)/3 = 0/3 = 0
(2-1)/3 = 1/3 = 0
(3-1)/3 = 2/3 = 0

So the logic we can conclude here is,

Row = (pos-1)/3

Now let’s switch to ‘col’.

Let us find row first and go for ‘col’ then.

1 | 2 | 3
4 | 5 | 6
7 | 8 | 9

This is the input map and the map of row will be...

0 | 1 | 2
0 | 1 | 2
0 | 1 | 2

So for set of 1, 4, and 7 you want ‘col’ value to be 0.

Forget about the 2nd and 3rd rows.

For the input of 1 you need ‘col’ value to be 0.

For the input of 2 you need ‘col’ value to be 1.

For the input of 3 you need ‘col’ value to be 2.

Isn’t that just obtained by subtracting one from input (pos)?

But we still need to deal with rest two rows. And the logic we are searching should be same to all the inputs we get. So we can conclude that subtracting one from input is not suitable to every input.

But can you deduce other inputs to fit in 1, 2 and 3?

Yes, we can do that. Subtract three from the input, until its greater than three. And finally you get a set of 1, 2 and 3 only.

Observe that 4 and 7 can be deduced to 1 when subtracted by 3.

4 - 3 = 1, which is less than 3, so stop the process.
7 – 3 = 4, which is greater than 3, so continue the process.
4 - 3 = 1, which is less than 3, so stop the process.

This is same with rest of the two sets. What would be the code now?

While (pos>3)
Pos=pos – 3 ;

It’s a simple code. Whenever the input is greater than 3, we subtract 3 from it.
If the ‘pos’ is less than three, execution comes out of the loop.

So, now we will be left with three possible values 1, 2 and 3. This is what we are waiting for, right?

So, ‘col’ will be one subtracted from these values.

Col = pos – 1;

Now we are done with validating and converting the position to our requirement.
Now we need to assign this particular position to the currently active player. (Player 1 or player 2)

Let us assume that player 1 will play with ‘1’ and player 2 will play with ‘0’, instead of ‘X’ and ‘O’.

So when its player 1 who is playing, we need to assign this particular position the value of ‘1’ and if it’s player 2 we will go for ‘0’.

if ( player==1) 

Where, tic[][] is our main 2 dimensional array representing the 3X3 grid board.
And ‘player’ is the variable for which we need to assign ‘1’ or ‘2’ accordingly between the chances.

So after player 1’s play has been processed (Either he has won or lost) we need to give chance to player 2.

if(player==1)     // Active player is ‘player 1’
player=2;     // Than next chance would be of ‘player 2’
Part 2: Tic Tac Toe - part 2

1 comment: