I’m implementing the Chessboard class to represent the chessboard. I’ve to implement the transformations (reflections and rotations) on the chess board possible.
The possible transformations includes the combination of:
1. Vertical Reflection
2. Horizontal Reflection
3. Diagonal Reflection
Thus, we’ve 8 possible transformations for chess board.
There are 64 squares on the Chessboard numbered [0..63].
Thus, to represent the total resulting values after the transformations is 8*64 (No.of Transformations * Chessboard_Size).
There are two fundamental ways to represent the transformed_board using Arrays:
One-Dimensional Array with transformed_board[8*64]
Two-Dimensional Array with transformed_board[8][64]
Questions:
- Which approach is better?
- What are the pros and cons of each approach?
- How will effect the performance with respect to time factor?
2
Well, in your problem space the 64 squares are formed from the 8 x 8 size of your board, so the most adequate design would be to use a 3 dimensional array:
transformed_board[8][8][8]
Performance will depend on your implementation, the operations you will do on that array and the compiler you are using. Don’t fall into the trap of premature optimization. Best approach here probably is to provide accessor functions like
SQUARE_TYPE GetSquare(int row,int column, int symmetry)
{
assert(0<=row && row<MAX_ROWS);
assert(0<=column && column <MAX_COLUMNS);
assert(0<=symmetry&& symmetry<MAX_SYMMETRIES);
return transformed_board[row][col][symmetry];
}
and restrict all access to the board to the use of that accessors. Then it will be easy to change the decision about the array dimensions used for transformed_board later, just by changing your accessor functions.
2
you probable don’t need to store all possible transformations so you can just compute them as needed when you access them
If you want to get clever in accessing the boards then you can use a variant of matrix transformations:
int[6][MAX_SYMMETRIES] transforms={{ 1, 0, 0,
0, 1, 0},
{ 0, 1, 0,
1, 0, 0},
{-1, 0, 7,
0, 1, 0},...};
SQUARE_TYPE GetSquare(int[8][8]& board, int row, int column, int symmetry)
{
assert(0<=row && row<MAX_ROWS);
assert(0<=column && column <MAX_COLUMNS);
assert(0<=symmetry&& symmetry<MAX_SYMMETRIES);
int newRow = transforms[symmetry][0]*row+ transforms[symmetry][1]*column+ transforms[symmetry][2]
int newCollumn = transforms[symmetry][3]*row+ transforms[symmetry][4]*column+ transforms[symmetry][5]
return board[newRow][newCollumn];
}
you can also do this with the 64 length array if needed
1 dimension or 2 dimension arrays actually have same data structure in memory.
The elements will be in contiguous memory block. So, performance wise, it will be the same, if you use same indexing.
2 dimensions is probably easier to read, and manipulate (easier to write board[1][3] than board[1*64 + 3])