Most efficient way to decide if there are no moves left in a grid game?

Question

I have a simple game where you can move a game piece 1 square vertically or horizontally in a grid to make a row of three pieces of the same type.

The game grid is 8 squares wide and 7 squares high, I want to find the most efficient way of checking if there are no moves left which will result in 3 in a row.

What I have so far is :

http://i.imgur.com/jY6wJvZ.png

My thinking is to test horizontally I just need to check column C isn't the same piece type as either side and the same for column F.

Vertically - I thought row 2 only needs to be compared with row 3 to make sure nothing matches and column 5 should be compared with rows 4 and 6 for matches.

So if none of those match then there can't possibly be any more moves?

I'm not sure if this is the most efficient way or if it could miss possible matches, can anyone with a better brain than mine please point me in the right direction?

Answer 1

Your check does not guarantee that there are no moves. For example, suppose the top-left corner were:

      *     *
  a a b c . . . .
* c c a b . . . .
  b b d a . . . .
  . . . . . . . .
* . . . . . . . .
  . . . . . . . .
  . . . . . . . .

Indeed, no cell in column C is equal to either left or right of it, and no cell in row 2 is equal to either above or below it. Yet, we can swap C1 and C2 to create a 3-in-a-row.

As @Patashu suggested, a naive solution may be best here, especially for conceptualization, e.g. if someone else were to read your code. I would track three cells at a time (in a bounded FIFO queue), first by rows, then by columns, and when two of the three match, check the 2 to 6 surrounding cells that can possibly be swapped into filling the third. For example,

  . . . . . . . .
  . . * . . * . .
  . * . a a . * .
  . . * . . * . .
  . . . . . . . .
  . . . . . . . .
  . . . . . . . .

or

  . . . . . . . .
  . . . . * . . .
  . . . a . a . .
  . . . . * . . .
  . . . . . . . .
  . . . . . . . .
  . . . . . . . .

or

  . . . . . . . .
  . . . . . . . .
  . . . . . . . .
  . . . . . . . .
  . . . . . . . .
  . . . . . * . .
  . . . . * . a a

If any of these *'ed cells match (e.g. a), then you know another 3-in-a-row is possible.

Answer 2

Here's my naive algorithm. Obviously all array access should respect bounds checking.

1) Check each checkboard colour of the grid, as in xs only then .s only in the following pattern:

x.x.x.
.x.x.x
x.x.x.
.x.x.x

Scan it in reading lines (every x horizontally, then descend a row) (hint: % 2 and * 2 will be your friend here) doing the following:

1a) If the current tile is the same colour as the tile one lower and to the right of me, if any of the following Xs are also the same colour, that's a three in a row:

.....
..XX.
.Xx.X
.X.xX
..XX.

1b) For one lower and to the left is similar:

.....
.XX..
X.xX.
Xx.X.
.XX..

(I would encode the positions of the Xs as offsets from the central tile you are checking - as in an array like {0, -1},{-1, 0},{-1, 1} etc)

(Alternatively, you could implement each as a 5 by 5 array of 1 for check here, 0 for don't - similar to how it looks in this answer - and then scan the 5 by 5 array while scanning the play field. This might be faster. No idea! You'd have to test.)

2) Now descend down every column, top to bottom If two adjacent tiles are the same colour, check the tile two higher or three lower - if either is the same colour, that's a three in a row:

.
X
.
x
x
.
X

3) Similar for rows, reading left to right:

.X.xx.X

Note: I have no idea if this is faster than the naive algorithm of checking every possible swap to see if it makes a three in a row! After all, both algorithms are O(n^2), so which is faster will depend on implementation details. As such I recommend two things:

1) Don't optimize until you've implemented a solution, and the solution is too slow for the real cases it is being used in, for the people who are using it.

2) When you optimize, check that you made it faster! (And also make sure it still works - nothing is worse than an optimization that breaks code :) )

Of course, this doesn't mean that optimization isn't fun, but don't be fooled into thinking optimizing already fast enough code is doing anything but exercising your mind ;)