Here's an implementation of the sliding block puzzle 'Hua Rong Dao', otherwise known as 'Klotski'. It has has been adopted in a number of countries, each giving it a different story. You can read about it here: @
(EDIT: updated to be solvable!)
[code] Title: Hua Rong Dao Author: Unknown Difficulty: 5 Wall: 4 Floor: 3 Validation: 7a501b4 ----------------------------- . # # # # # # # # # # # # # . . # # # # # # # # # # # # # . . # # # F F W W W W D D # # . . # # # F F W W W W D D # # . . # # # F F W W W W D D # # . . # # # F F W W W W D D # # . . # # # 0 0 0 0 0 0 S S # # . . # # # 0 0 0 0 0 0 S S # # . . # # # 0 0 0 0 0 0 S S # # . . # # # 0 0 0 0 0 0 S S # # . . # # # 0 0 . . . . 0 0 # # . . # # # 0 0 . . . . 0 0 # # . . # # # # # . . . . # # # # . . # # s d W W # # W W w f # . . # # # # # # # # # # # # # . ----------------------------- Groups: AABBBBAABBBBAACCDDAACCDDEEFFEEFF ----------------------------- [/code]
Has anyone solved this one? I believe the level posted above is impossible. I wrote a computer program to do an exhaustive search for the solution, and it verified the puzzle is impossible (if I'm not mistaken).
The above level is not an entirely faithful implementation of Hua Rong Dao, I think, because the White chocolate can stick in the lower left or lower right corners.
I made a small modification (shown below) to make the puzzle solvable.
[code] Title: Hua Rong Dao Author: Unknown Difficulty: 5 Wall: 4 Floor: 3 Validation: 7a501b4 ----------------------------- . # # # # # # # # # # # # # . . # # # # # # # # # # # # # . . # # # F F W W W W D D # # . . # # # F F W W W W D D # # . . # # # F F W W W W D D # # . . # # # F F W W W W D D # # . . # # # 0 0 0 0 0 0 S S # # . . # # # 0 0 0 0 0 0 S S # # . . # # # 0 0 0 0 0 0 S S # # . . # # # 0 0 0 0 0 0 S S # # . . # # # 0 0 . . . . 0 0 # # . . # # # 0 0 . . . . 0 0 # # . . # # # # # . . . . # # # # . . # # s d W W # # W W w f # . . # # # # # # # # # # # # # . ----------------------------- Groups: AABBBBAABBBBAACCDDAACCDDEEFFEEFF ----------------------------- [/code]
You're completely right, Carbuncle! My profuse apologies to anyone who tried to solve it manually! I've copied the solvable version over the original post to avoid confusion.
That's neat that you could do an exhaustive search - I would have thought the state space would be massive at that depth. Does your program work for arbitrary chocolate-only CC puzzles? (-:>
My program doesn't work for arbitrary Chocolate Castle puzzles. It only searches to see if the white chocolate can be brought to the bottom centre of the rectangle, so the search doesn't involve eating any chocolate. The number of possible states before the white chocolate gets eaten is definitely small enough to search through, since the pieces are so tightly packed into the rectangle.
The number of possible states after eating the white chocolate is pretty immense, but finishing the puzzle once you've successfully eaten all the white chocolate is pretty easy, so I didn't search past the eating of the white chocolate.
Chocolate Castle is a wonderful (and well-implemented) framework for many interesting puzzles. I seem to remember there was a post about a "Rush Hour" puzzle implemented in Chocolate Castle, but I can't seem to find it anymore. Was it just my imagination?
Ah, that's interesting. I was contemplating writing a solver to use as a design tool, but let it go for fear of large search spaces (and tricky heuristics). Can I ask - how long did it take to solve Hua Rong Dao? I have an idea for generating a batch of similar puzzles automatically (:
I can't remember the post, but the Rush Hour puzzle would be level 20 in the hard set. It has pieces which can only move along one axis.
It solved Hua Rong Dao fairly quickly, in less than a second. Just a few simple optimisations will cut the whole search down to less than 30,000 states. For example, for the purpose of eliminating permutations of identical blocks, I considered the four vertical 2 by 4 blocks to be identical, even though they are made of different materials.
Hey that's not bad at all. I might have a go at a simple puzzle generator after all. I know there are some players hungy for more puzzles lurking around here. (:
So we're hungry for more Chocolate, are we? I dunno, that pun might have spoilt my appetite...
The correction was a moot point for me, as I couldn't solve even the fixed version without looking at the available solution; I'd find it easier to write a solver like Carbuncle's. As for generated puzzles, I find the variety and ingenuity of the CC sets to be a lot of the charm. Then again, I still play Neko, so what do I know?
Argh, I don't mean to keep making those puns, really!
Yes, generated puzzles are likely to be quite bland ( <-- !pun ), but it might be possible in this case to inject some human guidance into it. For example - choosing some piece shapes that might be interesting.
Hmnn.. maybe it would be easier just to create a 'shuffle' tool that you can use during the game, and then keep the modified puzzle in the editor as Gray suggested a while ago. That way you can put the pieces in a good ending position and work backwards.
[Please log in to post a comment]
