CODEWITHSUNDEEP
algorithmdata-structuresunity-game-engine
Leo Jweda
Leo Jweda

Reputation: 2487

What data structure should I use to represent this board?

enter image description here

 --- --- --- ---
| o | o | o | o |
 --- --- --- ---
| o | o | o | o |
 --- --- --- ---
| o | o | o | o |
 --- --- --- ---
| o | o | o | o |
 --- --- --- ---

Pieces go between the circles. The goal is to fill the entire board. I need a way to represent the board's contents. The pieces can be rotated and flipped. I tried using a matrix but that didn't work out very well.

Edit: Example pieces:

enter image description here enter image description here enter image description here

Upvotes: 4

Views: 535

Answers (4)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 727047

Since the board is so tiny, one way to approach this problem would be to represent the board as a list of piece+placement pairs.

Think of each piece as a sequence of drawing commands in turtle graphics:

  • D for "draw"
  • R for "turn right"
  • L for "turn left"
  • T for "turn around".

The pieces from your post would be represented like this:

D-L-D-R-D-T-D-R-D
D-L-D-R-D-R-D
D-L-D-T-D-L-D-T-D-L-D

A placement of a piece adds information about the starting point for the piece, starting direction of the turtle, and whether or not the piece has been flipped, in which case the turtle needs to replace right turns with left turns, and vice versa.

Given a list of individual piece+placement pairs it is easy to verify that they do not intersect by "drawing" them on a temporary board. It is also easy to verify that a list of piece+placement pairs covers the entire board by "drawing" all pieces, and checking for empty spaces between the cells.

Upvotes: 2

Escualo
Escualo

Reputation: 42172

I can see some resemblance between your problem and the Exact Cover Problem.

In particular, Scott's Pentomino Problem as discussed in detail in one of Donald Knuth's seminal papers: Dancing Links (links to compressed PostScript format... you know the guy). The data structure used in that paper is a four-way linked representation of the Exact Cover Problem.

The Scott's Pentomino Problem looks like this (notice that the four locations in the middle are empty):

Scott's Pentomino Problem

and was solved by first describing it in terms of an Exact Cover Problem.

Essentially Knuth defined a matrix with 72 columns: one for each of the 12 pentominoes, and one for each of the 60 cells of the board minus the four in the center.

Then he constructed all possible rows for that matrix with a one (1) in the column corresponding to the piece, and a 1 in each column occupied by the piece; there are 1568 rows for the pentomino presented in the figure.

Once he had that matrix representation, he solved the exact cover problem on that sparse matrix using his Algorithm X (dancing links).

Of course, there are many more details in the paper.

This is an image of the Welded Tetrasticks Problem also addressed in the paper.

Welded Tetrasticks Problem by Donald Knuth

Upvotes: 1

r3mainer
r3mainer

Reputation: 24587

I think a matrix would work OK, but you need to be careful how you fit the pieces together. Here's an illustration of how the pieces shown above might fit into a 3×3 puzzle:

puzzle pieces represented as combinations of quadrant arcs

I've coloured the circles alternately yellow and blue in a checker-board fashion, but you should actually consider each circle as a set of four quadrants so you'll need a 6×6 matrix in this case. The puzzle pieces can then be represented as 8-connected collections of cells that follow the colouring of the cells where they are placed, but have the ability to flip between blue and yellow (e.g., the "diamond" piece is coloured Y B / B Y as shown, but would flip to B Y / Y B if you moved it to the next gap below):

         Y Y B B Y Y
         Y Y B B Y Y    Diamond:  Moustache:   Snake:
         B B Y Y B B
         B B Y Y B B      Y B          Y         Y Y
         Y Y B B Y Y      B Y          B       B
         Y Y B B Y Y                 Y

So this is what your matrix would look like with these pieces added to it. You can see that the "moustache" and "snake" pieces have the same shape, but are coloured differently:

same pieces represented as blocks

It should then be quite straightforward to solve the puzzle by using a constraint satisfaction algorithm.

Upvotes: 4

Jayson Ash
Jayson Ash

Reputation: 709

Consider using a graph; although, the example uses flight paths it is still useful in that each position (node in the graph) can have multiple connected nodes, which is what the question in this post describes. Checking to see if the game board is full would be just a matter of ensuring that every position (node in the graph) on the board is connected to every other position (node in the graph). Each board piece could span across multiple board positions and thus connect those nodes in the graph.

Upvotes: 0

Related Questions