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.

4

2 回答 2

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.

于 2013-10-23T09:31:24.887 回答
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.

于 2013-10-23T09:24:13.623 回答