Friday, 1 April 2011

Solumns



I have written an evil variant of the classic columns game, I call it solumns. It attempts to give you columns that you don't want.

It's not quite ready for everyone (no binaries yet) but developers may be interested in trying it out.

The rules are a little different from regular columns in that squares of similar colour are eliminated whenever they touch two others, without having to be in any particular alignment.

Poor columns are found by a brute force search of every single possible new column in every possible place.

With 7 colours, and noting that each column cannot contain three identical elements, that gives us (7 ^ 3) - 7 = 336 individual columns
Each of these needs to be positioned in one of 6 possible new positions, so that gives us 336 * 6 = 2016 possible next grids!

That's not a whole lot but then you need to then eliminate congruent squares, until no more are eliminated. That's not a trivial calculation, but it can be done in O(w*h) time where w is the width of the grid and y the height. The basis of the algorithm is that if a square is neighbours with 3 others of the same colour, then it, one of its immediate neighbours, is next to at least 1 square which has 2 neighbours of the same colour.

However, solumns is written in racket, so even with a good algorithm, it's still not going to be fast enough. It takes around 500ms to find the next column on my phenom 2.

The algorithm has some problems too. It can become stuck in a two cycle; the worst columns now implies the worst column next which implies the first again. If this happens a canny player can gain many points.

Next steps are:
rewrite the square elimination in C
deal with repetition

No comments:

Post a Comment

Post a Comment