search

chrisboyle / sgtpuzzles

Android port of Simon Tatham's Puzzles
https://chris.boyle.name/puzzles
Other
597 stars 168 forks source link

Flood: Calculations for least possible number of moves seem faulty #556

Open dat-atr-ash opened 2 years ago

dat-atr-ash commented 2 years ago

Describe the bug A clear and concise description of what the bug is.

I play flood with custom config of 6 colors in a 8 by 8 grid and no extra moves permitted and I frequently beat the calculated number of moves needed to flood the grid.

This suggests that either I misinterpreted the rule set or the calculations for the least possible moves to beat the puzzle are faulty. This at least sporadically results in a higher number of moves calculated for the puzzle than what is in fact possible.

I play the game casually without calculating or thinking hard about my way to solving the puzzle. So it might also be possible that the calculations are off the other way in some cases which I can't verify or falsify by the way I play the game.

To Reproduce Steps to reproduce the behavior:

  1. Go to '...'
  2. Click on '....'
  3. Scroll down to '....'
  4. See error

The error can only sporadically be observed. To reproduce solve the puzzle in less moves than are calculated by the software.

Expected behavior A clear and concise description of what you expected to happen.

Calculation for least possible moves are correct. Screenshot_20220703-185329_57594183e98acbd5c528e733d62aa74f

Screenshots If applicable, add screenshots to help explain your problem. You can also attach a saved game (checkerboard menu -> Save or Share).

See attachment.

Version info (optional, but sometimes helpful)

Version 2022-04-30-1100-c43a34fb-fdroid

Additional context Add any other context about the problem here.

rorySomething commented 2 years ago

In main/app/src/main/jni/flood.c

It's solved with a recursive algorithm. Currently set to a max depth of 3 guesses deep as good enough from a comment. For your use case might need that set to 4 or 5 for near perfection without burning through battery checking every possible move. I have no idea how costly it would be to add that extra depth waiting for so many more trial moves.

In my extremely limited experience, the recursive solvers are quicker than a 'smart' (or my dumb) human style solver so I don't think we'd have any luck with an alternative solver. ...anyone with donor supercomputer time to train a neural network for an arbitrary number of colors filling up to some max grid size?

Maybe there's room for optimization in the current solver I only skimmed it.