Checking tic tac toe winner on a board NxN (1D array)

[httpvictor]

So, previously I made a tic tac toe game with a normal 3x3 board. My teacher assigned us to make a tic tac toe game with a board size of 4x6 to 12x15 and in addition, the game needs to keep track of 2 - 5 players. In my previous 3 x 3 tic tac toe game I just wrote down every single winning solution. But since this board can be any size that algorithm won't work. I am keeping track of the positions in a normal array NOT 2D Array. I do not know of a method to check if a player has won without writing each winning solution. I am sure one of you guys know how to check pieces consecutively horizontally, vertically or diagonally regardless of where it is on the board (array).


Here are sections of the code


// part where program asks user for information
int userRows;
int userColumns;

cout << "Enter the number of rows -> ";
cin >> userRows;
cout << "Enter the number of columns -> ";
cin >> userColumns;
cout << endl;

// play board space being made
int boardAmount = 180;
char * boardSpace = NULL;
boardSpace = new char[boardAmount];
for(int i = 0; i < userRows; i++){
for(int y = 0; y < userColumns; y++){
boardSpace[i*userColumns+y] = ' ';
}
}


// checking for game win (issue)
void checkWin(bool & gameOver, char *& boardSpace, int & userRows, int & userColumns){
int size = userRows * userColumns;
for(int i = 0; i < userRows; i+=3){
if(boardSpace[i] == 'a' and boardSpace[i+1] == 'a' and boardSpace[i+2] == 'a' ){
gameOver = true;
}
}
}

[doug4]

Draw out a board. Fill in the array indices for each space on the board. For instance, on a 4-by-5 board, you might have:

  1  2  3  4 
  5  6  7  8
  9 10 11 12
 13 14 15 16
 17 18 19 20

Horizontal wins would be numbers like 9, 10, 11.

Vertical wins would be number like 3, 7, 11.

Diagonal wins would be numbers like 6, 11, 16 and 7, 10,13.

Try this with a different size grid. How is each type of winning combination related?

[dhayden]

Personally, I'd start by modifying the existing program to use a 2D array for the board. I think the coding later on will be easier that way.

Then change it so the board size is a parameter.

Then change it so that you can have more than 2 players. Maybe use the letters A-E to mark the spaces for players 1-5? Or just use the numbers?

Now change the board size parameters to 4x4 and debug.

[jonnin]

access of a 1-d array as if 2-d is simply

array[desired_row*numcols+desiredcol]

and from there you just need to go to the last move made and check that row, that column, and that diagonal, all 3 of which can be computed locations using the above.

the transposition tables can be used (every possible winning combo reduced to avoid repetition of mirrors/rotates/etc ) but that is a huge amount of comparisons etc while what I said costs you approximately only N*3 comparisons where N is the diagonal (depending on your game, is it like connect 4, TTT, or something else?)