See bottom of post for updates…

I’m working on a new game which involves developing an algorithm that I’m struggling with a bit.  I thought it would be interesting to share the challenge and work it out with the larger community.

Here is a the challenge:

I’m trying to figure out an algorithm for determining the maximum score that can be generated for a game board with the following rules:

1) Game board is 3 tiles x 3 tiles
2) Each tile has four numbers on it that are between 1 and 9
3) Each number is on a side of the tile
4) Tiles can be rotated
5) Tile location can not be changed (you can’t pick up a tile and move it to the location of another tile and have them swap locations)
6) Game Score is determined by multiplying adjacent numbers on different tiles.  (see example calculations below)

To help illustrate the rules here is how the score is claculated for gameboard 1 below starting from top left tile:

(4 * 9) + (2 * 2) + (4 * 8) + (6 * 2) + (1 * 9) + // first row of tiles
(6 * 9) + (3 * 5) + (3 * 5) + (1 * 8) + (3 * 6) + // second row of tiles
(3 * 7) + (4 * 3)                                 // third row of tiles
= 236

gameboard 1

And here is the calculation for gameboard 2 starting from top left tile:

(9 * 3) + (4 * 3) + (7 * 6) + (6 * 4) + (7 * 5) + // first row of tiles
(6 * 5) + (2 * 1) + (9 * 6) + (2 * 2) + (1 * 4) + // second row of tiles
(6 * 7) + (6 * 9)                                 // third row of tiles
= 330

gameboard 2

So, given that the numbers are variable and each tile can be rotated how do I figure out what the max possible value is for a board with any give arrangement of tiles and numbers?

Please add your ideas and questions as comments.  I’m sure I’m forgetting some rules or other information and I will update this post as things come up.

I’ll also update the post with sudo code as the algorithm starts to come together.

————-
Updated

Here are some initial thoughts:
There are 24 number positions that count toward the score
There are 9 possible values for each number position
There are 4 possible arrangements for each tile
So there are 24 x 9 x 4 = 864 possible arrangements for the game board.

So, which of these 864 arrangements gives the highest score? Do we need to test them all? I sure hope not, because I need to scale this algorithm to a 4 x 4 , 5 x 5 , 6 x 6 and 7 x 7 grid as well!

If not, then there must be some rules we can apply to reduce the set we need to test…