TicTacToe - 2D Array - Linear Search

Pages: 12
Hello, I'm having a little problem with completing this little TicTacToe program using a 2D array, it may seem a little messy because of my debugging, like cout<<*pMove<<endl; which is there to see if I'm hitting the correct index in the array.

The issue I'm having is with the linear search algorithm, I know how to search through a 1D array and modify but am not too certain how to do it with this 2D grid type array. I find where the value is, possibly its index but then I need to update the board with the played move.

Any ideas on this would be great, I've been holding on from posting here for 2 days but it's killing me..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <iostream>

using namespace std;

void DisplayBoard(char array[][3], int size);
void GrabInput(char player);
void UpdateBoard(char array[][3], int size, char player, char currentMove);
int PrintBoard(char array[][3], int size, char currentMove);

char board[3][3] = { {'1','2','3' }, {'4','5','6'}, {'7','8','9'} };

char player1, player2;
char firstMove = 0;
char currentMove;
int currentPlayer; 

int main()
{
	char* pMove = &currentMove;
	*pMove = currentMove;

	DisplayBoard(board, 3);
	GrabInput('1');
	cout<<*pMove<<endl;
	system("pause");
	UpdateBoard(board, 3, '1', *pMove);
	PrintBoard(board, 3, *pMove);
	GrabInput(2);
	UpdateBoard(board, 3, 2, currentMove);
	PrintBoard(board, 3, currentMove);
	
	system("pause");
	return 0;
}

void DisplayBoard(char array[][3], int size)
{
	system("cls");
	cout<<"::Tic Tac Toe::\n\n";

	for (int x = 0; x < size; x++)
	{
		for (int y = 0; y < size; y++)
		{
			cout<<array[x][y];
			cout<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
}

void GrabInput(char player)
{
	char* pMove = &currentMove;

	if (player == '1')
	{
		cout<<"\n";
		cout<<"Your Move:\n\n";
		cout<<"Player 1 (1-9): ";
		cin>>player1;
		//currentPlayer = player1;
		*pMove = currentMove = player1;
	}
	if (player == '2')
	{
		cout<<"\n";
		cout<<"Your Move:\n\n";
		cout<<"Player 2 (1-9): ";
		cin>>player2;
		//currentPlayer = player2;
		*pMove = currentMove = player2;
	}
}

void UpdateBoard(char array[][3], int size, char player, char currentMove)
{
	for (int x = 0; x < size; x++)
	{
		for (int y = 0; y < size; y++)
		{
			switch(player1)
			{
				case '1': array[0][0] = 'X'; break;
				case '2': array[1][0] = 'X'; break;
				case '3': array[2][0] = 'X'; break;
				case '4': array[1][0] = 'X'; break;
				case '5': array[1][1] = 'X'; break;
				case '6': array[1][2] = 'X'; break;
				case '7': array[2][0] = 'X'; break;
				case '8': array[2][1] = 'X'; break;
				case '9': array[2][2] = 'X'; break;
			}
			switch(player2)
			{
				case '1': array[0][0] = 'O'; break;
				case '2': array[1][0] = 'O'; break;
				case '3': array[2][0] = 'O'; break;
				case '4': array[1][0] = 'O'; break;
				case '5': array[1][1] = 'O'; break;
				case '6': array[1][2] = 'O'; break;
				case '7': array[2][0] = 'O'; break;
				case '8': array[2][1] = 'O'; break;
				case '9': array[2][2] = 'O'; break;
			}
		}
	}
}

int PrintBoard(char array[][3], int size, char currentMove)
{
	system("cls");
	cout<<"::Tic Tac Toe::\n\n";

	for (int x = 0; x < size; x++)
	{
		for (int y = 0; y < size; y++)
		{
			if (currentMove == array[x][y])
			{
				return x;

			}

		}
		cout<<endl;
	}
	cout<<endl;
}


Sorry for the messy code, you might need to run it to see what I mean
The issue doesn't seem to be with the linear search itself but going through the for loop to modify the index with either an 'X' or an 'O' - then of course I'd need to implement a boolean to check for wins/draws but that comes later.

At the moment I'm stuck with passing on currentMove to PrintBoard so it can display the board with the new move made.

Any help with this would be appreciated.
Anyone that could give me some guidance or throw a few ideas out there so I can think about?
Ok, here are a few ideas. See if you can figure out what they are.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
using namespace std;

void DisplayBoard(char array[][3], int size);

void GrabInput(char player);

void UpdateBoard(char array[][3], int size, char player, char currentMove);
int PrintBoard(char array[][3], int size, char currentMove);

char board[3][3] = { {'1','2','3' }, {'4','5','6'}, {'7','8','9'} };

char player1 = 'X', player2 = 'O' ; // initialize all the variables
char firstMove = 0 ;
char currentMove = 0 ; // place to store the current move 1-9 input by the user
char currentPlayer = player1 ; // either 'X' or 'O' depending on who is to move

int main()
{
    DisplayBoard( board, 3 ) ;

    for( int move = 0 ; move < 9 ; ++move )
    {
        GrabInput( currentPlayer ) ;
        UpdateBoard( board, 3, currentPlayer, currentMove ) ;
        DisplayBoard( board, 3 ) ;

        //switch currentPlayer for the next turn
        if( currentPlayer == player1 ) currentPlayer = player2 ;
        else currentPlayer = player1 ;
    }
}

void DisplayBoard(char array[][3], int size)
{
    cout<<"\n\n\n::Tic Tac Toe::\n\n";

    for (int x = 0; x < size; x++)
    {
        for (int y = 0; y < size; y++)
        {
            cout<<array[x][y];
            cout<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}

void GrabInput(char player)
{
    cout<<"\n";
    cout<<"Your Move:\n\n";
    cout<<"Player " << player <<  " (1-9): ";
    cin>>currentMove; // store the input in currentMove
}

void UpdateBoard(char array[][3], int /*size*/, char player, char currentMove)
{
    switch( currentMove )
    {
            case '1': array[0][0] = player ; break ;
            case '2': array[0][1] = player ; break ;
            case '3': array[0][2] = player ; break ;
            case '4': array[1][0] = player ; break ;
            case '5': array[1][1] = player ; break ;
            case '6': array[1][2] = player ; break ;
            case '7': array[2][0] = player ; break ;
            case '8': array[2][1] = player ; break ;
            case '9': array[2][2] = player ; break ;
    }
}


Note: This is by no means finished code. The code follows the structure of the original code as closely as possible. The intent is to throw up a few ideas that you could use.
Last edited on
Hello, thanks for taking the time to review my code, I've used what you suggested and I'm stuck making it change to player2 ( O ). I know it has to do with the DisplayBoard function not taking in currentPlayer as a parameter but I'm not sure how to go about it.. hmm..

Here's the updated code, I put some couts in there to see what was being loaded into currentPlayer and currentMove and was surprised to see memory addresses, can anyone explain this to me as well?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>

using namespace std;

void DisplayBoard(char array[][3], int size);

void GrabInput(char player);

void UpdateBoard(char array[][3], int size, char player, char currentMove);
int PrintBoard(char array[][3], int size, char currentMove);

char board[3][3] = { {'1','2','3' }, {'4','5','6'}, {'7','8','9'} };

char player1 = 'X', player2 = 'O'; //Initialized variables
char currentMove = '0'; //Place to store current move inputted by user 1-9
char currentPlayer = player1; //Current player initialized as player1 with either X or O

int main()
{
	char* cMove = &currentMove;
	*cMove = currentMove;

	DisplayBoard(board, 3);

	for (int move = 0; move < 9; ++move)
	{
		
		GrabInput(currentPlayer);
		UpdateBoard(board, 3, currentPlayer, currentMove);
		cout<<"Current Player: "<< cout<<currentPlayer<<endl;
		cout<<"Current Move: "<< cout<<currentMove<<endl;
		cout<<"Current Move: "<< cout<<*cMove<<endl;
		system("pause");
		DisplayBoard(board, 3);

		//Switch current player for next move
		if (currentPlayer == player1) currentPlayer == player2;
		else currentPlayer == player1;
	}
	//system("pause");
	return 0;
}

void DisplayBoard(char array[][3], int size)
{
	system("cls");
	cout<<"::Tic Tac Toe::\n\n";

	for (int x = 0; x < size; x++)
	{
		for (int y = 0; y < size; y++)
		{
			cout<<array[x][y];
			cout<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
}

void GrabInput(char player)
{
	char* cMove = &currentMove;	
	
	cout<<"\n";
	cout<<"Your move:\n\n";
	cout<<"Player "<<player<<" (1-9): ";
	cin>>currentMove; //Store move of designated player into currentMove

	*cMove = currentMove;
}

void UpdateBoard(char array[][3], int /*size*/, char player, char currentMove)
{
	char* cMove = &currentMove;
	

	switch(currentMove)
	{
		case '1': array[0][0] = player ; break ;
        case '2': array[0][1] = player ; break ;
        case '3': array[0][2] = player ; break ;
		case '4': array[1][0] = player ; break ;
		case '5': array[1][1] = player ; break ;
		case '6': array[1][2] = player ; break ;
		case '7': array[2][0] = player ; break ;
		case '8': array[2][1] = player ; break ;
		case '9': array[2][2] = player ; break ;
	}
	*cMove = currentMove;
}

int PrintBoard(char array[][3], int size, char currentMove)
{
	system("cls");
	cout<<"::Tic Tac Toe::\n\n";

	for (int x = 0; x < size; x++)
	{
		for (int y = 0; y < size; y++)
		{
			if (currentMove == array[x][y])
			{
				return x;

			}

		}
		cout<<endl;
	}
	cout<<endl;
}


Thanks
Get rid of all these pointers (in all functions)
1
2
3
	//char* cMove = &currentMove;
	//*cMove = currentMove;
        // etc.. 


You don't need them; to modify the value of currentMove just assign to it.

Knock off int PrintBoard(char array[][3], int size, char currentMove);
You are not using it anywhere.

And change the equality comparison to assignment in:
1
2
		if (currentPlayer == player1) currentPlayer /*==*/ = player2;
		else currentPlayer /*==*/ = player1;


> I put some couts in there to see what was being loaded into currentPlayer and currentMove
> and was surprised to see memory addresses,

You put in one cout too many:
1
2
		cout<<"Current Player: "<< /*cout<< */ currentPlayer<<endl;
		cout<<"Current Move: "<<  /*cout<<*/ currentMove<<endl;



Once you have got this much working, post your code. Next, you need to get rid of those global variables.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>

using namespace std;

void DisplayBoard(char array[][3], int size);

void GrabInput(char player);

void UpdateBoard(char array[][3], int size, char player, char currentMove);
//int PrintBoard(char array[][3], int size, char currentMove);

char board[3][3] = { {'1','2','3' }, {'4','5','6'}, {'7','8','9'} };

char player1 = 'X', player2 = 'O'; //Initialized variables
char currentMove = '0'; //Place to store current move inputted by user 1-9
char currentPlayer = player1; //Current player initialized as player1 with either X or O

int main()
{
	//char* cMove = &currentMove;
	//*cMove = currentMove;

	DisplayBoard(board, 3);

	for (int move = 0; move < 9; ++move)
	{

		GrabInput(currentPlayer);
		UpdateBoard(board, 3, currentPlayer, currentMove);
		cout<<"Current Player: " /*<< cout */ <<currentPlayer<<endl;
		cout<<"Current Move: "<< cout<<currentMove<<endl;
		//cout<<"Current Move: " /*<< cout*/ <<*cMove<<endl;
		//system("pause");
		DisplayBoard(board, 3);

		//Switch current player for next move
		if (currentPlayer == player1) currentPlayer = player2;
		else currentPlayer = player1;
	}
	//system("pause");
	return 0;
}

void DisplayBoard(char array[][3], int size)
{
	//system("cls");
	cout<<"::Tic Tac Toe::\n\n";

	for (int x = 0; x < size; x++)
	{
		for (int y = 0; y < size; y++)
		{
			cout<<array[x][y];
			cout<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
}

void GrabInput(char player)
{
	//char* cMove = &currentMove;

	cout<<"\n";
	cout<<"Your move:\n\n";
	cout<<"Player "<<player<<" (1-9): ";
	cin>>currentMove; //Store move of designated player into currentMove

	//cMove = currentMove;
}

void UpdateBoard(char array[][3], int /*size*/, char player, char currentMove)
{
	//char* cMove = &currentMove;


	switch(currentMove)
	{
		case '1': array[0][0] = player ; break ;
        case '2': array[0][1] = player ; break ;
        case '3': array[0][2] = player ; break ;
		case '4': array[1][0] = player ; break ;
		case '5': array[1][1] = player ; break ;
		case '6': array[1][2] = player ; break ;
		case '7': array[2][0] = player ; break ;
		case '8': array[2][1] = player ; break ;
		case '9': array[2][2] = player ; break ;
	}
	//*cMove = currentMove;
}

Wow dude I feel like the biggest newb, I've been concentrating too much on things I don't yet understand properly and completely abandoned the basics, can't believe I didn't notice the comparison assignment.

This helped me a lot, now that my main issue is out of the way I can work on checking for wins and draws.

Thanks a lot dude!
I'm amazed that everybody is using switch statement and testing every possible input instead of finding a algorithm like this one:

array[int((player-1)/3)][(player-1)%3]= player;

Last edited on
> I'm amazed that everybody is using switch statement and testing every possible input
> instead of finding a algorithm like this one

It is not particularly surprising; most programmers who realize that
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void foo( char array[3][3], char player, char move )
{
    switch(move)
    {
        case '1' : array[0][0] = player ; break ;
        case '2' : array[0][1] = player ; break ;
        case '3' : array[0][2] = player ; break ;
        case '4' : array[1][0] = player ; break ;
        case '5' : array[1][1] = player ; break ;
        case '6' : array[1][2] = player ; break ;
        case '7' : array[2][0] = player ; break ;
        case '8' : array[2][1] = player ; break ;
        case '9' : array[2][2] = player ; break ;
    }
}


can be written cryptically without testing every possible input this way:
1
2
3
4
5
void bar( char array[3][3], char player, char move )
{
    if( move > '0' && move <= '9' )
        array[ ( move - '1' ) / 3 ][ ( move - '1' ) % 3 ] = player ;
}


would also know that a more elegant way to write the cryptic version is:
1
2
3
4
5
void baz( char array[3][3], char player, char move )
{
    if( move > '0' && move <= '9' )
        array[0][ move - '1' ] = player ;
}


There is a case for foo() (transparent, easy to understand, even for a beginner) and for baz() (cryptic elegance), but is is difficult to argue in favour of bar().
Last edited on
@JLBorges
Im not amazed from the algorithm im amazed from the way they think they just used the straight way and didnt think in any other way or even give it a try.
your baz function is not right its totally wrong or i didnt get the idea of it?
> your baz function is not right its totally wrong or i didnt get the idea of it?

You could check it out by writing a small test program.
hmm.. Without writing a test i figured it out and its happening because arrays are chains or squences of data really interesting way.
@AkramIzzeldin
I think your amazement misses a huge point in all this, you're viewing it from a frame of someone with a lot more experience than most of us. I'm using the tools I know of. If I knew I could write it as simple as JLBorges' 'cryptic' version, which to me, makes a lot more sense, I would have.

It's kind of like failing to understand why a baby cries or makes sounds with his mouth instead of just saying 'I'm hungry, feed me.' He just hasn't learned to do so yet.

I'm in that baby's position, obviously if I knew all these shortcuts I wouldn't be asking questions, I'd be answering them =]
^^
my solution is simple i get it in 1 min i mean i just write odds and see the pattern it's not like JLBorges' solution cause his solution requires you to have some knowledge in how arrays are allocated or how they work but my solution doesn't require any knowledge.
My solution is like how babies know how to breath with know knowledge how the breathing is done, while the JLBorges' solution is just like you said.
- What do you mean with "JLBorges cryptic version, which to me make mor sense" more than what? because his cryptic version is more difficult than any other
Sorry, what I meant was his 'elegant' version of writing the same code seemed to make most sense to me out of all the ones listed. I understand yours as well and appreciate the different inputs but I never knew you could state it that way, I thought it would go out of bounds, but I've been messing around with it and it works different ways. I guess it's because of the condition and the fact it's a char so if you input 12 it will take it as '1' and 2' and fill in X O in those tiles.
1. The standard specifies that for characters '0', '1', ... '9' (decimal digits), the value of each character for a decimal digit after '0' is be one greater than the value of the previous.

Therefore, '7' - '0' yields the integer 7, and '7' - '1' yields the integer 6.
In the above code, if move == '7', move - '1' == 6

2. An array of three elements looks like this, with lower addresses towards the left:

1
2
3
4
5
__________________________________________________________________________________
|                          |                          |                          |  
|             0            |             1            |           2              |
|                          |                          |                          |
__________________________________________________________________________________


In our case, each element of the big array is an array of three chars;
char array[3][3] looks like this:

1
2
3
4
5
__________________________________________________________________________________
|       |         |        |       |         |        |       |         |        |
|  0,0` |   0,1   |   0,2  |  1,0` |   1,1   |   1,2  |  2,0` |   2,1   |   2,2  |
|       |         |        |       |         |        |       |         |        |
__________________________________________________________________________________


And we are just treating that as an array of nine chars.
@JLBorges
Thanks for the diagram and explanation.

One question though, how does it know to treat it as an array of nine chars and how does say if move == '7' which becomes [0][6] according to the syntax, then know to point to 1,2 in your diagram?

What's the mindset behind the compiler when allocating this?
Last edited on
> how does it know to treat it as an array of nine chars

"It" doesn't. We know.


> and how does say if move == '7' which becomes [0][6] according to the syntax,
> then know to point to 1,2 in your diagram?

Ok. Let us start from first principles.

If we have char a[3] ; a is an array containing three elements of type char.
If T is some type, and we have T b[3] ; b is an array containing three elements of type T.

The elements of an array are allocated contiguously in memory; one after the other, leaving no gaps in between. So T b[3] looks as in the first diagram above, where each element is of type T.

When we say b[0] we are referring to the element at position 0, the element that is right at the beginning of the array. (Actually the [] is an operation on a pointer, but we will leave that nicety aside for the moment.)

When we say b[1] we are referring to the element at position 1, the element that is immediately after the element at position 0.

In general, when we say b[n], we are referring to the element at position n, the element that is n elements away from the element right at the beginning of the array. Since we specified b, the compiler 'knows' which array we are talking about, and since we specified n, the compiler 'knows' which element of that array we are talking about. Using this information, it figures out where the element b[n] would be and generates the code to access that element. While doing this, it places implicit trust in the programmer; it takes for granted that there must an element at position n; that there are at least n more elements after the the first one at position 0.

Now it is easy to see what would happen if we try to modify b[7]. The compiler assumes that we know what we are doing; we have asked it to access an element which is seven elements away from the begining of b and would generate the code for doing precisely that. However, there are only three elements in the array, at positions 0, 1 and 2; there are no elements after that; an element at position 7 just does not exist. And when we run our program, unpleseant things happen. The C++ language refuses to say anything about how bad it could possibly get; in this situation, C++ permits the implementation to get as nasty as it pleases. (In jargon: this results in 'undefined behaviour'.)

Now let us replace this hypothetical T with an actual type:
1
2
3
typedef char T[3] ; // the type T is 'array of three chars'
T b[3] ; // b is an array of three elements of type T
char arr[3][3] ; // arr is an array of three elements of type T 

'b' and 'arr' are of the same type; they are laid out as in the second diagram above.

b[0] or arr[0] is the element at position 0, an array of chars, right at the beginning.

arr:
1
2
3
4
5
__________________________________________________________________________________
|                          |                          |                          |
|             0            |             1            |           2              |
|                          |                          |                          |
__________________________________________________________________________________


1
2
3
4
5
__________________________________________________________________________________
|       |         |        |       |         |        |       |         |        |
|  0,0  |   0,1   |   0,2  |  1,0` |   1,1   |   1,2  |  2,0  |   2,1   |   2,2  |
|       |         |        |       |         |        |       |         |        |
__________________________________________________________________________________


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
          arr[0]
____________________________
|       |         |        |
|  0    |   1     |   2    |
|       |         |        |
____________________________

                                     arr[1]
                            ____________________________
                            |       |         |        |
                            |  0    |   1     |   2    |
                            |       |         |        |
                            ____________________________

                                                                 arr[2]
                                                       ____________________________
                                                       |       |         |        |
                                                       |  0    |   1     |   2    |
                                                       |       |         |        |
                                                       ____________________________

arr[0][6] accesses an element six positions away from arr[0][0]

1
2
3
4
5
__________________________________________________________________________________
|       |         |        |       |         |        |       |         |        |
|  0    |     1   |   2    |  3    |   4     |   5    |   6   |   7     |   8    |
|       |         |        |       |         |        |       |         |        |
__________________________________________________________________________________


whilch is the same element as arr[2][0]
Last edited on
That has to be the easiest to understand explanation I've read thus far =]

My thinking was if it's arr[3][3] and you set it to search from [0] to [6] then it would look through [0] on the first dimension, then go out of bounds on the second dimension since it only has a size of 3, but now I see they're linked in the way you represent it (otherwise it wouldn't work).

This makes it so much easier to search and modify values, I was aware of the linear search algorithm for a single dimensional array but didn't know how to apply it with more dimensions.

This is great thanks!
> This makes it so much easier to search and modify values, I was aware of the linear search algorithm
> for a single dimensional array but didn't know how to apply it with more dimensions.

Prefer iterating over nested structures using nested loops.

1
2
3
4
5
6
7
8
9
10
11
12
int arr[10][5] = { /* ... */ } ;

int main()
{
      
      for( int row = 0 ; row < 10 ; ++row )
            for( int col = 0 ; col < 5 ; ++col )
                if( arr[row][col] == 5 )
                {
                      // found 5 at position row, col 
                }
}


An array where every element is an array is not the only such nested construct that is possible. A nested loop will work every time.

In general, prefer simple transparent code over 'clever' code.
Pages: 12