Data structure for optimal-solution calculations

Want to calculate something or share your results?
Post Reply
qqwref
Posts: 125
Joined: Thu Sep 23, 2010 4:17 pm

Data structure for optimal-solution calculations

Post by qqwref »

This is an outline of a way to store the data in a board, for use in calculating optimal solutions (or sub-optimal solutions, etc.). The idea is to preprocess the board so that we only keep track of the data we need to and don't have to run floodfill algorithms. It may also be an easier representation to run algorithms on. This topic is partly for my own use and partly to put this info out there in case people want to work on the problem of optimally solving boards themselves.

First, we find the 3BV's and number them #1, 2, ..., N. We would also want to store its location (in the case of openings, the first square associated with the opening) to help with setting all this stuff up. Each one is assigned a bit to keep track of whether it's been opened or not, initially false.
Second, we do the same thing with mines, so we have mine #1, 2, ..., M, and also assign each one a bit to keep track of whether it's been flagged or not, initially false.
Third, keep an array of bits the same size as the board. This will just keep track of whether each square has been chorded or not, initially false (which will be useful for returning a report of what happened, but also for checking when chords are open...). If you're clever you can amalgamate this with the array of mine flags.

Now, for each possible chordable square, we keep track of the following:
- 'location', an integer or integer pair describing the actual location of this square.
- '3bv-location', an integer array (max size 2) with the IDs of any 3BVs which would open up this square. If it's sitting on a 3BV this would just be that 3BV's ID; otherwise it includes the IDs of the one or two openings that open this square.
- 'mine', an integer array (max size 8) of the IDs of mines that are around it.
- '3bvs', an integer array (max size 8) of the IDs of 3BVs that must be opened after this square is chorded, including the 3BV it is sitting on.

We can do all possible moves with this:
- Left-click a square: pointless if that square isn't a 3BV (see later); if it is, twiddle that 3BV's opened bit.
- Flag a mine: twiddle that mine's flagged bit.
- Chord a square: first, if none of the 3bv-locations have been opened, AND none of the adjacent squares on the board have been chorded, that means we need to start with a click to open this square. Next, flag all of the mines if they haven't been done (and spend any necessary clicks to do so). Finally, open all 3BV in 3bvs (for free) and set this square to chorded.

So to simulate the effect of solving the board using a set of chords, it would go like this:
- Re-initialize all the flags.
- Repeat until all chords have been applied:
--- If there is a chord which doesn't need to start with a click (one of its 3bv-locations is opened or an adjacent square has been chorded, that is, that square of the board is opened), apply it now.
--- Otherwise, apply the first un-applied chord in our list.
- Add one click for any unopened 3BV in the list.
NF player. Best scores 1-10-39.
Post Reply