2008:GalaxyGameSolver

• SVN - https://kram.no-ip.com/svn/GalaxyGame/

This outlines my approach to creating a solver for the Galaxy Game.

1. The problem made me think of the eight-queens problem because of the directions and extent of what each tile can see. To find the mines in an 8x8 grid, one of the solutions to the eight-queens puzzle would give complete coverage with the board with the least number of checked tiles (At least I suspect. It would be pretty good regardless.).
2. Using this set of eight hints, every tile unobstructed by a bomb may be seen at least twice which I am thinking will give a fairly good set of information to find the bombs. It may even be the case that enough information is gathered before flipping all 8 tiles or the bombs are all on the initial 8.
3. Using this information, any tiles that see 0 bombs can be used to discard all the tiles they see. All the tiles that can see a bomb give a likelihood weighting to all the tiles in its path of vision (unless of course they have been discarded from a 0 weighting). The likelihood rating for each tile will be the sum of all its observers weightings. The first tile with the highest weighting will be tested and then the weightings will be recalculated and the next tile guessed unless all tiles are found.

It is possible to get full coverage of the board with seven queens (starting at say the top left and choosing each square on a diagonal except for the bottom right square) however this will give information that is symmetric, giving no distinction to which half of the board the goals are lost in. The nine queens solutions seem to give a lot more information and it may be worth investigating which solution gives the most overlap of squares and if this will infact help.