4

Suppose I have an algorithm that can play chess on a chessboard which is n-dimensional, using {1,...,8}^n n-dimensional squares.

The algorithm itself has no problem working in n dimensions, given an n-dimensional array or ArrayList for chessboard representation. The problem is that n is to be specified at runtime.

Is there any elegant way to generate and use such an n-dimensional chessboard?

What came to my mind was a recursive function to create an n-dimensional ArrayList, returning an ArrayList of Integers if n == 1, and returning an ArrayList of ArrayLists where each ArrayList of the second set of ArrayLists has dimension n-1.

But this does not seem to be elegant at all...

[edit]

An answer which seems to have been deleted before I could comment suggested the generation of one List, containing other lists of size 8. If I use 8 ^ numberOfDimensions many list inside the first list, this would probably work, but it would force me to manually keep track of dimensions.

Improve this question

2 Answers 2

Reset to default
2

I think a nice data structure for the chessboard could use a Map. This makes it possible to look up a position based on an List of n integer indices:

Map<List<Integer>, BoardCell> chessboard;

The BoardCell class will probably want to have a reference to its index too so that you can check which pieces threaten other pieces etc:

class BoardCell {
   private final List<Integer> index;
   private final Figure figure;
}

Generating the chessboard is of course slow (exponential asymptotically) and done through enumerating all possible board positions, which you can do recursively.

This feels more elegant than a List of List of List of etc.

As Viliam Búr suggested in the comments section, using a Map data structure allows you to keep track of only relevant board cells. This type of data structure is called a Sparse representation.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Elegant, and with good implementation it may save a lot of memory if the array is mostly empty. The "null" values on the chessboard should not be stored in the map; instead the absence of a key should be interpreted as the map having a "null" value at given place. Then even if you have 100 dimensions and 1000 pieces on the chessboard, you don't run out of memory! Now to do this properly, the whole Map should be encapsulated in a class, which would provide accessor methods. The method for reading should return a "null" value in absence of the key; and writing "null" should remove the key.
Thank you cyon and Viliam Búr, I think that is exactly what I need!
1

I don't think this is particularly elegant, but it should do the trick:

List makeBoard(int dim) {
    List res = new ArrayList(8);
    for (int i = 0 ; i != 8 ; i++) {
        if (dim != 1) {
            res.add(makeBoard(dim-1));
        } else {
            res.add(0);
        }
    }
    return res;
}

The idea is to generate the board recursively. When dim is 1, add eight zeros to the list; otherwise, add eight boards of dimension dim-1.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.