15
I really love sliding tile puzzles, but recently, I haven't had time for them. Hence, I need a program to give me my fix of sliding-tile puzzles, specifically Klotski puzzles.
Your input will be in the following format:
#######
#001gg#
##.222#
.######
where #
represents walls, .
represents an open area, g
represents the goal, and adjacent numbers represent different blocks. You can assume that:
- There will be no more than 10 blocks
- There won't be two blocks with the same number
- All blocks will be enclosed by walls
- The grid is rectangular
- The
0
block is large enough to cover all of the goal squares. - There is a valid solution
You need to return a sequence of moves that will put the 0
block so that it covers all of the goal squares. Blocks cannot pass through walls or other blocks. For the above puzzle, an appropriate sequence would be
2L,1R,1R,1D,0R,0R,0R
while represents moving the 2
block 1 square left, the 1
block 2 squares right (on top of the goal) then 1 square down, and then 0
block 3 squares right.
There are actually several sequences that will work for the above problem, and producing any of them is acceptable. Your solution should be optimal, meaning that it should produce a sequence that solves the puzzle in as few as steps as possible.
The sequence should be printed out as above, but can be comma, newline, or space separated. I don't care if there are trailing commas or whitespace. You should produce the output in reasonable time (maximum 120 seconds on the puzzles below).
Puzzle 1:
..####..
..#00#..
###00###
#......#
#.1122.#
##3124##
.#3344#.
.##55##.
..#gg#..
..####..
Puzzle 2:
######
#1002#
#1002#
#3445#
#3675#
#8gg9#
######
Puzzle 3:
.####.
##1g##
#22g3#
#4255#
#4.56#
#.006#
#7008#
######
Puzzle 4:
.####.
##00##
#.00g#
#.0.1#
#..g2#
######
This is code-golf, so the shortest solution (in bytes) wins!
Just a thought - as I read this, I found something a bit confusing. The goals, being "hidden" were hard to see sometimes. In the example you have, they can be "guessed" with resonable accuracy, however, in the event a block is covering the goal entirely, you should have a way to clearly denote the entire goal. What if: Letters for blocks, Upper case when that spot is on a goal? . for space, * for goal ? everything else same ? would that be more clear ? – Ditto – 2015-03-27T19:45:38.570
@Ditto there is never a case where a block starts on a goal square. The last example simply has two disconnected goal squares. – Nathan Merrill – 2015-03-27T20:42:40.353
Can we assume every input puzzle has a solution? – orlp – 2015-03-27T23:31:08.937
@orlp yes, I'll add that to the problem statement. – Nathan Merrill – 2015-03-27T23:36:12.390
@NathanMerrill To make sure we're doing things correct, could you add the optimal amount of moves for puzzle 1-4? – orlp – 2015-03-28T01:28:49.343
@orlp, I don't want to post all of them, but the first one should take 87 moves if my program is accurate. – Nathan Merrill – 2015-03-28T03:11:47.600
@NathanMerrill If you mean Puzzle 1, then I've got a solution in 70 steps. This is a big problem, seeing as we now have no way of making sure an entry is correct.
– orlp – 2015-03-28T03:52:07.200@orlp I'm assuming that multiple entries will provide a reasonable consensus of what the shortest solution actually is. – Nathan Merrill – 2015-03-28T04:19:28.427
Puzzle 1, 70 steps in 67 seconds. Now golfing – edc65 – 2015-03-28T19:00:55.650
@edc65 Need to optimize more then, question states a limit of 30 seconds. – orlp – 2015-03-28T23:42:06.453
For puzzle 2 & 3, I dubt an optimal solution can be found in 30 second of less – edc65 – 2015-03-30T00:19:38.777
I'm raising the time limit. I simply don't want dumb brute forcing solutions. – Nathan Merrill – 2015-03-30T02:35:57.970
@edc65 You're wrong, my answer solves all optimally in < 30 seconds. – orlp – 2015-04-03T18:21:57.117
Why unaccepting? Did you spot some mistake in my answer? – edc65 – 2017-08-05T08:30:09.243
@edc65 My current opinion is that all questions are open, and so no answer should be accepted :) I upvoted your answer so you at least can redeem some of that rep. – Nathan Merrill – 2017-08-05T15:51:21.873