1

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
  • 3
    Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask – gnat Feb 13 '14 at 7:00
  • And transformed_board[64][8]. I never understood the layout of multi-dimensional arrays in C. I would choose none of them. I would create a class representing a chessboard and make an array of those. That would ensure that a single board stays contiguous in memory. And leave you some leeway to choose between indirection and no indirection for the storage of a single board. – Laurent LA RIZZA Oct 2 '15 at 8:17
3

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
  • 1
    You'd probably do better to have your accessor permute indices, rather than store 8 copies of the board – Eric Feb 13 '14 at 8:31
  • @Eric: you are probably right, I was mainly adressing the fact that the OP did not consider to put the 64 squares into an 8x8 array, or to postpone this decision by encapsulating it. – Doc Brown Feb 13 '14 at 14:19
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

0

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])

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.