Re: [Enigma-devel] level submission: minesweeper

[Ronald Lamprecht]

Hi,

Brian Huffman wrote:
> Quoting Ronald Lamprecht <address@hidden>:
>
> > The problem of unsolvable bomb distributions can be fixed by a simple
> > algorithm. All bomb free fields must be connected to the outside area
> > by direct path. For all bomb free fields of the border mark all
> > reachable fields by a recursive depth run. Marking all visited fields
> > allows to limit the recursive depth run to those border fields that are
> > not yet marked.
>
> I have now implemented such a reachability check. Unreachable tiles do 
> not occur very often, but the check does occasionally reject a mine 
> distribution.
>
> > This would reduce the problem to bomb distributions that are not
> > "solvable" due to the intrinsic ambiguity.

Andreas wrote:
> Not exactly, as you can't reach the diagonal tiles
> without stepping on the directly adjacent ones.

Eliminating distributions that cannot be reached as they would require 
diagnal moves is the main idea of the above algorithm. Throwing away 
these occasional distributions should solve the problem for sure.

> > A simple solution would be to set enigma.ConserveLevel to TRUE and
> > provide a panelty that keeps players from misusing it. E.g. an it-weight
> > on each resurrection would be fair. That would be o.k. for solving one
> > or two last ambiguities by trial. But it should keep players from using
> > it on a regular basis.
>
> I am experimenting with using it-cross to trigger a hint mechanism that 
> will uncover a single random tile. I figured that having to wait 10 
> seconds would discourage people from using it too much. However, I found 
> what seems to be a bug: You can touch the cross briefly, then go 
> somewhere else; the cross will be triggered 10 seconds later, whether 
> you stay there or not. This behavior does not agree with the description 
> on the wiki, which says that you need to stay on the cross for 10 seconds.

Indeed, it is a bug in 1.01. It will be fixed with the reengineering of 
the cross item in 1.10 - the interval will be a free configurable attribute.

As a workaround you can compare the actor position with the cross 
position when the alarm goes off after 10 seconds.

> > Of course you are welcome to write an algorithm that rejects ambiguos
> > bomb distributions. This would allow you to give the user a solvable
> > start of a few opened fields, too. But the algorithm might be more
> > complex.
>
> Yes, I think an algorithm to test for solvability would be too complex; 
> minesweeper problems are NP-complete, after all. I think a hint 
> mechanism with a time penalty would be a better approach.

The solvability check would be too complex, but providing a solvable 
distribution is a problem that is of limited complexity.

Nevertheless a hint/penalty would give your level a more Enigma like 
touch :-)

Greets,

Ronald