Sign in to follow this  
  • entries
    195
  • comments
    198
  • views
    103870

Playing games

Sign in to follow this  
SiCrane

88 views

I've been playing a lot of Honeycomb, one of TANSTAAFL's flash games. Of course, at the higher levels, pretty much anything past 40, it's incredibly hard, especially with the move limitation that got added in the last version.

It occurred to me that there's got to be an easier way to solve a given level than my current combination of pattern recognition and brute force. My previous thought experiments ran toward traditional searching techniques, but they seemed somewhat doomed to failure given that at any given time there's a branching factor of (256 - number of bees) * (number of bees). This can be reduced by eliminating bees that have already been moved, but even so, the best I could think of would reduce the search space to about 6 x 1089 states for level 40.

Then it struck me, if you consider instead of a move being "move a bee from one place to another", but instead "toggle the 'beeness' of a given hex", then the order of moves would then be unimportant, making the set of moves an abelian group. This can be categorized by simple matrix operations.

Ignore for a moment the existance of the bees, and consider each cell to have a binary state: either light or dark. You can then represent the effect of placing or removing a given bee by a 256 element vector, with a 1 representing the color changes, and a 0 represnting no change. If you then create a matrix formed from the vectors that represent a bee in each different cell, you can represent the the concatonation of any given set of moves by that matrix. So given a starting position, multiplying the the matrix by the vector representing the moves and adding the starting position, all mod 2, you should be able to categorize the final state. So if you have the matrix, then inverting the matrix should be able to determine the set of moves necessary to solve the puzzle.

Now this leaves a complication: what if the matrix is non-invertible? In theory it seems like in that case, if you use gaussian reduction to determine the inverse, and the matrix proves non-invertible, there should be a series of column vectors in the right hand side, which represent in linear combination equivalent sets of moves. (Combinations of moves that will cancel themselves out). The resulting pseudo-inverse could be used to determine a base set of moves necessary to solve the puzzle, and linear combinations of equivalent states should be able to increase the number of moves to match the number of needed bee movements in order to determine a solution to the puzzle.

edit: spelling
Sign in to follow this  


1 Comment


Recommended Comments

I have uploaded a new version with more statistics here. I have included the number of moves made, the number of normal moves made, and the number of bonus moves made per level. I also added total number of moves made, total number of normal moves made, and total number of bonus moves made.

This should make it relatively easy to spot the problem.

Total Moves should never be greater than ((level)*(level+1)/2+level)

Total Normal Moves should never be greater than ((level)*(level+1)/2)

Total Bonus Moves should never be greater than (level)


Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now