in reply to Challenge: Box Blackout

Great game. My first thought at a solution would be a classic inverse backtrack: start with a full board and work backward.

Note that boards with just one piece missing are solutions (not optimal!) and so are all predecessors to a full board in a path such as you show. So, working back from boards with one empty square (each of the N*N possibilities) one can find optimal starting points (which will be a symmetric family).

If I were still teaching advanced programming, I would probably use this game.

--traveler

Replies are listed 'Best First'.
Re^2: Challenge: Box Blackout
by loris (Hermit) on Jan 24, 2006 at 11:41 UTC

    I'm not too familiar with algorithm nomenculature, but if starting with a full board and working backward is an inverse backtrack, what would a non-inverse backtrack entail?

    Thanks,

    loris

    "It took Loris ten minutes to eat a satsuma . . . twenty minutes to get from one end of his branch to the other . . . and an hour to scratch his bottom. But Slow Loris didn't care. He had a secret . . ."
[reply]
      Well, a backtracking algorithm means working toward a solution, and, when you reach a dead end, going back to the last time you made a "choice". In many computer science classes students learn to implement a backtracking algorithm by solving the "Eight Queens Problem". You can google for that or check a CS text.

      The reason this is "inverse" is because you are starting with the "solution". I think that would be faster and easier to write, personally, but I might be wrong.

[reply]

In Section Seekers of Perl Wisdom