The Sphinx's Lair

TheGreatEscaper

12:08 AM

@Randal'Thor, posted a solution to your question.

I'm pretty sure breadth first search is the simplest way to solve flood.

So there doesn't really exist an 'algorithm' as such.

Rand al'Thor

@TheGreatEscaper Nice!

What is a breadth first search?

(I've never studied these algorithmic optimisation things much.)

TheGreatEscaper

In programming terms, a breadth first search means that the program will check all possible first moves that will increase no. of squares, then check all possible second moves from there, then all third moves, etc. When the program first reaches a monochromatic board, it's found the optimal solution.

Breadth first search is pretty easy to program but it's bashy.

Sphinx

1

Q: Will a greedy algorithm solve Tatham's Flood?

I was just investigating some of the puzzles on Simon Tatham's website, and came across Flood, in which we start with an $n\times n$ grid of cells each of which is filled with one of $k$ predetermined colours, and (quoting the game instructions): Try to get the whole grid to be the same colou...

Rand al'Thor

Oh. So essentially considering all possibilities at every stage, and solving the whole thing in one go rather than step by step.

That could only be optimal if the game is essentially unsolvable?

TheGreatEscaper

Not sure I quite understand your question

Well, it's technically a 'solve'

Chess programs that beat world masters use breadth first search

Rand al'Thor

12:19 AM

@TheGreatEscaper Yes, but that method of 'solving' would work with any game as long as there are finitely many possibilities at each step.

@TheGreatEscaper But not exploring possibilities all the way to the end, presumably?

TheGreatEscaper

Well, it depends on what kind of breadth first search you're doing.

In chess they don't need to go all the way to the end

Because chess is just about win/draw/lose; if a certain move will lead to a lot of 'good' positions 10 or so moves down the track, then the computer will take it and still have a huge advantage.

But your question on flood is about optimization

So if you want to be 100% it's optimised, you do every single move from step 1 to step m where m is the optimal number of moves

Breadth first just means you don't need to take every single possibility all the way to the end

And yeah it'll work with any finite grid

Here's an example which will hopefully clear things up

In the puzzle I posted, the optimal solution is OYgGbBR

7 moves

The program would try every possible first move that adds area; none of those make a monochromatic grid

the program would then, for each possible first move, try every possible second move

None of those solve the grid

Rand al'Thor

@TheGreatEscaper So at what point does it stop considering a possibility?

Given that something which seems non-optimal at first may end up being part of the optimal solution.

TheGreatEscaper

Well, when it considers every possible set of 7 moves

One of those will be the optimal solution to my puzzle, no?

Rand al'Thor

Oh right.

TheGreatEscaper

So they don't need to search any more

Like I said its bashy, but it's surprisingly easy to program

Rand al'Thor

12:26 AM

So it does consider every single possibility until one of them gets all the way to the end?

TheGreatEscaper

Yup

Because when one of them does, it's the first one to get there. Since you're looking for the optimal solution, you don't care about all the ones that might take more moves

There are ways to cut it down

And make it more efficient

But the central idea remains the same

Some ways of cutting it down is getting rid of a: duplicates and b: 'backwards'

Oops, didn't mean to send that

But for example, RO has the same result as OR

So you don't need to store them both

Now consider OY and YO

The area of YO is a subset of the area of OY

So YO is 100% certainly disadvantageous

So while it seems super bashy at first, some small steps can be taken to improve the program and suddenly it can solve my puzzle optimally without having to consider many cases at all

Rand al'Thor

@TheGreatEscaper Are you certain? After YO the area would be orange but after OY it would be yellow ... does that make a difference?

Nah, maybe not.

TheGreatEscaper

Well if you think about it the only thing that is important is same colour to adjacent squares, or not same colour

If the White area was green or blue it wouldn't make a difference

Because the colour of your area stops mattering once it's infected all that it can

So really you could just imagine that your area is always white

And each move, you can gobble up adjacent squares of the same colour and turn them white too!

It's equivalent

The colour of your area is basically irrelevant

I think for Flood, breadth first search is actually quite efficient

Rand al'Thor

12:41 AM

Hmm, I'll have to think about this some more.

And get more practice with playing it.

(Tatham's site is really addictive once you get into it!)

TheGreatEscaper

Yeah those kinds of logic puzzles are really great aren't they?

Not sure if this counts as 'promotion' but in any case it's not my app:

itunes.apple.com/us/app/100-logic-games-time-killers/…

^That is basically the best portable puzzle book you could ever wish for

Transcript for