CODEWITHSUNDEEP
javaperformancecomplexity-theory
xrdty
xrdty

Reputation: 886

Most efficient datastructure to represent a NxN board

I was wondering if you guys could point me towards some more efficient datastructures in which I can represent a NxN puzzle board.

At this point, it's still a basic 2 dimensional matrix (int[][]). Although it serves its purpose, I feel it lacks on the whole performance aspect.

The puzzle itself is called "the sliding problem", e.g. 8puzzle, 15puzzle,..

an 8 puzzle looks like this:

  1 3         1 2 3
4 2 5   --->  4 5 6
7 8 6         7 8

One operation I am using is O(n^4), I'd like to find a "solution" for this. This operation tries to find, for every board entry, the coordinates of the value that should be there. (distance heuristics)

value = 1;
for(int i = 0; i <puzzle.length; i++)
   for(int j = 0; j < puzzle[0].length; j++)
      getPosition(value++)

with getPosition also using 2 for loops:

    for (int i = 0; i < puzzle.length; i++)
        for (int j = 0; j < puzzle[0].length; j++) 
            if(puzzle[i][j]==value)
                return new int[]{i,j};

I was thinking of using a HashMap, using new int[]{x_coord, y_coord} as key for each entry.

Looking forward to your suggestions, thanks in advance!

Upvotes: 3

Views: 650

Answers (1)

Marco13
Marco13

Reputation: 54709

In order to optimize the data structure in terms of complexity (assuming that you have boards of size 100x100 or so, where this is really worth thinking about) you first have to make clear which operations will be executed most frequently.

One operations that is probably required frequently in such a puzzle is

Given coordinates (r,c) : Which number is at these coordinates?

The array is already perfectly suited for this. One could consider using an 1D array to enforce more data locality, but detailed benchmarks would be necessary to justify this decision.

You mentioned another operation:

"This operation tries to find, for every board entry, the coordinates of the value that should be there"

This sounds a bit unusual, because I can't imagine what you might need this for - except, maybe, for sort of "distance measure". However, the core of this operation can be formulated as

Given a number x: Which are the coordinates (r,c) of this number?

This could again be solved by arrays, namely two arrays

int rows[] = new int[totalSize];
int cols[] = new int[totalSize];

So given the board from your example:

  1 3
4 2 5
7 8 6

These arrays could contain

rows = { 0, 0, 1, 0, 1, 1, 2, 2, 2 }
cols = { 0, 1, 1, 2, 0, 2, 2, 0, 1 }

That is, the coordinates of 5 are currently (rows[5], columns[5]) = (1,2)

Of course, you will have to update this data structure for every move that you apply to the board. This implies a constant (!) overhead for each move. But for larger boards, this will quickly pay out, because finding the coordinates of a certain value now only has O(1), in contrast to O(n²) as before.

Upvotes: 1

Related Questions