Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

Re: Challenge: Box Blackout

by traveler (Parson)
on Jan 24, 2006 at 00:09 UTC ( [id://525086]=note: print w/replies, xml ) Need Help??


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 . . ."
      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.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://525086]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others surveying the Monastery: (4)
As of 2024-03-29 11:24 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found