C++

Forum

 
TicTacToe - 2D Array - Linear Search

Pages: 12
Fourc00h (44)
So does this above code return the index of that value, do you have to store the index into a variable before modifying it or can you modify it with a shortcut or 'elegant' way as suggested before?
JLBorges (13770)
> So does this above code return the index of that value, do you have to store the index into a variable before modifying it
> or can you modify it with a shortcut or 'elegant' way as suggested before?

You mean from a function that does the linear search?

There are several ways of returning the information. For instance:
1. Two output parameters (passed by reference) returning the indices
2. Returning pair of indices
3. Returning an offset from the element at [0][0]

3 will only work with c-style arrays containing c-style arrays;
1 and 2 will also work with std::vector<std::vector<int>> (far more likely in C++).

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
 
#include <iostream>
#include <utility>

const std::size_t NROWS = 5, NCOLS = 3 ;

// return true on success, with row,col set to the indices
// return false if not found, with row set to NROWS,col set to NCOLS
bool find_1( const int array[NROWS][NCOLS], int value, std::size_t& row, std::size_t& col )
{
    for( row = 0 ; row < NROWS ; ++row )
        for( col = 0 ; col < NCOLS ; ++col )
            if( array[row][col] == value ) return true ;

    return false ; // not fomd, row == NROWS, col == NCOLS
}

// return a pair of row, col indices on success
// returen the pair NROWS,NCOLS if not found
std::pair<std::size_t,std::size_t> find_2( const int array[NROWS][NCOLS], int value )
{
    for( std::size_t row = 0 ; row < NROWS ; ++row )
        for( std::size_t col = 0 ; col < NCOLS ; ++col )
            if( array[row][col] == value ) return { row, col } ;

    return { NROWS, NCOLS } ; // not fomd, return pair NROWS,NCOLS
}


// return offset from array[0][0] on success
// return NROWS * NCOLS if not found
std::size_t find_3( const int array[NROWS][NCOLS], int value )
{
    const std::size_t BEYOND = NROWS * NCOLS ;
    for( std::size_t pos = 0 ; pos < BEYOND ; ++pos )
        if( array[0][pos] == value ) return pos ;
    return BEYOND ; // not found
}

int main()
{
    const int a[NROWS][NCOLS]
    {
        {  0,  1,  2 },
        {  3,  4,  5 },
        {  6,  7,  8 },
        {  9, 10, 11 },
        { 12, 13, 14 },
    };

    std::size_t row, col ;

    if( find_1( a, 7, row, col ) )
        std::cout << "found " << a[row][col] << " at " << row << ',' << col << '\n' ;

    const auto p = find_2( a, 7 ) ;
    row = p.first ;
    col = p.second ;
    if( row < NROWS )
        std::cout << "found " << a[row][col] << " at " << row << ',' << col << '\n' ;

    const auto offset = find_3( a, 7 ) ;
    if( offset < NROWS*NCOLS )
        std::cout << "found " << a[0][offset] << " at offset " << offset << '\n' ;
}


http://ideone.com/oDMBn9
Fourc00h (44)
Thanks for that, I've been playing around with it and when I do a search to see if a tile has been found (X or O) it stops, obviously, because it finds X and/or O in a position within the array.

What I'm not sure is, how do I tell it to look for the tile being modified like
if (array[0][0] != 1) (meaning it's changed to either X or O) then continue searching? This wouldn't work well either because it wouldn't know if it's X or O, I need it to find an unused tile or find a used one and check to see if it equals X or O, place a move if its their turn or return an error.

I think I'm kind of answering my own question here, the logic is all there in my own words but I can't seem to translate it to syntax..

Once again, here's my code:

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
 
#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);

const size_t XPOS = 3, YPOS = 3;
bool checkTile (const char array[XPOS][YPOS], char value, size_t& xpos, size_t& ypos);

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 board[XPOS][YPOS] =
	{
		{'1','2','3'},
		{'4','5','6'},
		{'7','8','9'}
	};

	size_t xpos, ypos;

	DisplayBoard(board, 3);

	for (int move = 0; move < 9; ++move)
	{
		
		GrabInput(currentPlayer);
		if (checkTile(board, currentPlayer, xpos, ypos))
			//cout<<"Found " << board[xpos][ypos] << " at " << xpos << ',' << ypos << '\n';
			cout<<"Cannot place move in this square.. try one that's empty.\n";

		else
			UpdateBoard(board, 3, currentPlayer, currentMove);

		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][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)
{
	cout<<"\n";
	cout<<"Your move:\n\n";
	cout<<"Player "<<player<<" (1-9): ";
	cin>>currentMove; //Store move of designated player into currentMove
}

void UpdateBoard(char array[3][3], int /*size*/, char player, char currentMove)
{
	if (currentMove > '0' && currentMove <= '9')
		array[0][currentMove - '1'] = player;
}

bool checkTile(const char array[XPOS][YPOS], char value, size_t& xpos, size_t& ypos)
{
	for (xpos = 0; xpos < XPOS; ++xpos)
		for (ypos = 0; ypos < YPOS; ++ypos)
			if (array[xpos][ypos] == value) return true;

		return false; //Return false if value not found
			
}


I feel all I'm missing is an extra parameter in the checkTile boolean function for where they placed the move and compare that instead
JLBorges (13770)
1
2
3
4
5
6
7
8
9
10
11
 
GrabInput(currentPlayer);
if( currentMove < '1' || currentMove > '9' )  cout<<"there is no such square..\n";
else
{
    char tile = board[0][ move - '1' ] ; // since you already play this jazz

    if( tile == player1 || tile == player2 )
        cout<<"Cannot place move in this square.. try one that's empty.\n";
    else
        UpdateBoard( board, 3, currentPlayer, currentMove );
}
Last edited on
Fourc00h (44)
Hmm I don't get this one, and it doesn't work for me.

So I don't need the bool function I was trying to use?
JLBorges (13770)
> So I don't need the bool function I was trying to use?

You could write a function if you want; but to check what is there at row x, col y, all that is required is:
examine the char at board[x][y]. If it is not an 'X' or an 'O', the tile is available.



Fourc00h (44)
Ahh ok then I need another conditional checking to see if it already has an X or an O making it unwritable to the next player
Fourc00h (44)
I thought the conditional you suggested would check if the tile is an 'X' or a 'O' but shouldn't it be stored in an array or somewhere temporary as reference as to what tiles have been used?

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
 
#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);

const size_t XPOS = 3, YPOS = 3;
bool checkTile (const char array[XPOS][YPOS], char value, size_t& xpos, size_t& ypos);

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 board[XPOS][YPOS] =
	{
		{'1','2','3'},
		{'4','5','6'},
		{'7','8','9'}
	};

	size_t xpos, ypos;

	DisplayBoard(board, 3);

	for (int move = 0; move < 9; ++move)
	{
		
		GrabInput(currentPlayer);
		if (currentMove < '1' || currentMove >	'9')
			cout<<"No such square.\n";

		else
		{
			char tile = board[0][move - '1'];

			if (tile == player1 || tile == player2)
				cout<<"Cannot place move here.\n";
			else
				UpdateBoard(board, 3, currentPlayer, currentMove);
		}

		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][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)
{
	cout<<"\n";
	cout<<"Your move:\n\n";
	cout<<"Player "<<player<<" (1-9): ";
	cin>>currentMove; //Store move of designated player into currentMove
}

void UpdateBoard(char array[3][3], int /*size*/, char player, char currentMove)
{
	if (currentMove > '0' && currentMove <= '9')
		array[0][currentMove - '1'] = player;
}

bool checkTile(const char array[XPOS][YPOS], char value, size_t& xpos, size_t& ypos)
{
	for (xpos = 0; xpos < XPOS; ++xpos)
		for (ypos = 0; ypos < YPOS; ++ypos)
			if (array[xpos][ypos] == value) return true;

		return false; //Return false if value not found
			
}
JLBorges (13770)
> check if the tile is an 'X' or a 'O'. but shouldn't it be stored in an array or
> somewhere temporary as reference as to what tiles have been used?

This information is already there in the array board.

What is the need to duplicate the same information in another place?
Fourc00h (44)
Here's the working code, not completely debugged but does what it has to. I haven't been online to post this before so here it is:

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
 
#include <iostream>

using namespace std;

void displayBoard(char b[][3], int size);
void grabInput(char player);
void updateBoard(char b[3][3], int /*size*/, char player, char currentMove);
void checkWin();
void checkDraw();
bool isPlaying = true; //Not necessary but I'll keep it for future changes
bool hasWon = false;
bool hasDrawn = false;

char player = 'X';
char player2 = 'O';
char activePlayer = player;
char currentMove;

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

int main()
{
	displayBoard(b,3);

	while (isPlaying && !hasWon && !hasDrawn)
	{
		grabInput(activePlayer);
		char tile = b[0][currentMove - '1'];
		
		if (currentMove < '1' || currentMove >	'9')
			cout<<"No such square.\n";

		else
		{
			if (tile == 'X' || tile == 'O')
			{
				cout<<"Invalid Move\n";
			}
			else
			{
				updateBoard(b,3,activePlayer,currentMove);
				checkWin();
				checkDraw();
			}
			
		}

		if (hasWon)
			system("pause");
		else
			displayBoard(b,3);

		if (activePlayer == player) activePlayer = player2;
		else activePlayer = player;
	}

}

void displayBoard(char b[3][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<<b[x][y];
			cout<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
}

void grabInput(char player)
{
	cout<<"Enter your move "<<player<<": ";
	cin>>currentMove;
}

void updateBoard(char b[3][3], int /*size*/, char player, char currentMove)
{
	if (currentMove > '0' && currentMove <= '9')
		b[0][currentMove - '1'] = player;
}

void checkWin()
{
	if (b[0][0] == 'X' && b[0][1] == 'X' && b[0][2] == 'X')
	{
			cout<<"\nPlayer 1 Wins!\n\n";
			hasWon = true;
	}
	if (b[1][0] == 'X' && b[1][1] == 'X' && b[1][2] == 'X')
	{
			cout<<"\nPlayer 1 Wins!\n\n";
			hasWon = true;
	}
	if (b[2][0] == 'X' && b[2][1] == 'X' && b[2][2] == 'X')
	{
			cout<<"\nPlayer 1 Wins!\n\n";
			hasWon = true;
	}

	if (b[0][0] == 'X' && b[1][0] == 'X' && b[2][0] == 'X')
	{
			cout<<"\nPlayer 1 Wins!\n\n";
			hasWon = true;
	}
	if (b[0][1] == 'X' && b[1][1] == 'X' && b[2][1] == 'X')
	{
			cout<<"\nPlayer 1 Wins!\n\n";
			hasWon = true;
	}
	if (b[0][2] == 'X' && b[1][2] == 'X' && b[2][2] == 'X')
	{
			cout<<"\nPlayer 1 Wins!\n\n";
			hasWon = true;
	}

	if (b[0][0] == 'X' && b[1][1] == 'X' && b[2][2] == 'X')
	{
			cout<<"\nPlayer 1 Wins!\n\n";
			hasWon = true;
	}
	if (b[0][2] == 'X' && b[1][1] == 'X' && b[2][0] == 'X')
	{
			cout<<"\nPlayer 1 Wins!\n\n";
			hasWon = true;
	}


	if (b[0][0] == 'O' && b[0][1] == 'O' && b[0][2] == 'O')
	{
		cout<<"\nPlayer Wins!\n\n";
		hasWon = true;
	}
	if (b[1][0] == 'O' && b[1][1] == 'O' && b[1][2] == 'O')
	{
		cout<<"\nPlayer Wins!\n\n";
		hasWon = true;
	}
	if (b[2][0] == 'O' && b[2][1] == 'O' && b[2][2] == 'O')
	{
		cout<<"\nPlayer Wins!\n\n";
		hasWon = true;
	}

	if (b[0][0] == 'O' && b[1][0] == 'O' && b[2][0] == 'O')
	{
		cout<<"\nPlayer Wins!\n\n";
		hasWon = true;
	}
	if (b[0][1] == 'O' && b[1][1] == 'O' && b[2][1] == 'O')
	{
		cout<<"\nPlayer Wins!\n\n";
		hasWon = true;
	}
	if (b[0][2] == 'O' && b[1][2] == 'O' && b[2][2] == 'O')
	{
		cout<<"\nPlayer Wins!\n\n";
		hasWon = true;
	}

	if (b[0][0] == 'O' && b[1][1] == 'O' && b[2][2] == 'O')
	{
		cout<<"\nPlayer Wins!\n\n";
		hasWon = true;
	}
	if (b[0][2] == 'O' && b[1][1] == 'O' && b[2][0] == 'O')
	{
		cout<<"\nPlayer Wins!\n\n";
		hasWon = true;
	}

}

void checkDraw()
{
	if (b[0][0] != '1' && b[0][1] != '2' && b[0][2] != '3' && b[1][0] != '4' && b[1][1] != '5' && b[1][2] != '6' &&
		b[2][0] != '7' && b[2][1] != '8' && b[2][2] != '9' && !hasWon)
	hasDrawn = true;
	if (hasDrawn)
	{
		cout<<"\nThe game is a draw!\n\n";
		system("pause");
	}
}


Thanks for your help JLBorges, I learnt a lot! =]

EDIT: By the way, is there an easier way to check for wins and draws? I found this quite long and unnecessary but didn't know what other approach to take.
Last edited on
JLBorges (13770)
> is there an easier way to check for wins and draws?

1. We only need to check for a win by the player ( 'O' or 'X' ) who has just moved.

2. Divide and conquer.

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
 
bool check_row( const char b[3][3], char p, int row )
{
    for( int col = 0 ; col < 3 ; ++col ) if( b[row][col] != p ) return false ;
    return true ;
}

bool check_col( const char b[3][3], char p, int col )
{
    for( int row = 0 ; row < 3 ; ++row ) if( b[row][col] != p ) return false ;
    return true ;
}

bool check_diags( const char b[3][3], char p )
{
    return b[1][1] == p &&
        ( ( b[0][0] == p && b[2][2] == p ) ||  ( b[0][2] == p && b[2][0] == p ) ) ;
}

bool check_win( const char b[3][3], char p )
{
    for( int row = 0 ; row < 3 ; ++row ) if( check_row( b, p, row ) ) return true ;
    for( int col = 0 ; col < 3 ; ++col ) if( check_col( b, p, col ) ) return true ;
    return check_diags( b, p ) ;
}

bool check_any_win( const char b[3][3] )
{ return check_win( b, 'X' ) || check_win( b, 'O' ) ; }

Fourc00h (44)
Cool man, I was able to use this in my connect 4 game as well.
Really useful!
Topic archived. No new replies allowed.
Pages: 12