- Code Golf: Solving the 8-puzzle problem
- 02 Apr 2020 04:11:44 pm
- Last edited by PT_ on 07 Apr 2020 07:22:43 am; edited 1 time in total
Good evening guys! With this pandemic going around, I guess many people have more time to spend on programming, so that's why I'm happy to announce the next code golf problem: solving a scrambled 8-puzzle game! If you don't know what that is, take a look at the Wikipedia page for the 15-puzzle game, which is similar but a bit bigger.
In this challenge, I dare you to write an optimal program that takes a scrambled 8-puzzle as input and output a list of steps to solve it! A solved puzzle looks like this:
Code:
As you might notice, 0 is the "empty" slot, and it should be moved to the bottom-right corner, and the other pieces in the right place as well. Input is given in a 3x3 matrix in Ans, and your program should output a list with which pieces to shift. Since there is always 1 empty slot, a piece X can slide in 1 way to the empty spot. Note that 0 is never allowed as the output, as you can't slide the empty piece.
Example:
Code:
As you can see, first piece 5 and then piece 6 had to be moved for the puzzle to be solved, so in this case your program should output {5,6}.
Requirements:
Leaderboard:
Good luck everyone, I'd love to see some entries!
In this challenge, I dare you to write an optimal program that takes a scrambled 8-puzzle as input and output a list of steps to solve it! A solved puzzle looks like this:
Code:
1 2 3
4 5 6
7 8 0
As you might notice, 0 is the "empty" slot, and it should be moved to the bottom-right corner, and the other pieces in the right place as well. Input is given in a 3x3 matrix in Ans, and your program should output a list with which pieces to shift. Since there is always 1 empty slot, a piece X can slide in 1 way to the empty spot. Note that 0 is never allowed as the output, as you can't slide the empty piece.
Example:
Code:
1 2 3 -> 5 -> 1 2 3 -> 6 -> 1 2 3
4 0 5 4 5 0 4 5 6
7 8 6 7 8 6 7 8 0
As you can see, first piece 5 and then piece 6 had to be moved for the puzzle to be solved, so in this case your program should output {5,6}.
Requirements:
- Input: 3x3 matrix in Ans with integers in [0..8] (every number appears once)
- Freshly reset calc (every variable reset to 0/not defined)
- Puzzle is solvable
- Output: list in Ans with integers in [1..8] which corresponds to the pieces to slide to the empty slot. If the piece can't slide (i.e. not surrounded with the empty spot), your program is invalid and not qualified.
- The program is allowed to end with a crash, as long as the right answer is in Ans
- Multiple (sub)programs are allowed, all together is the total size
- All solvable inputs should get the right output
- Lowest score wins
- Score counter: [size on calc] - 9 - [program name length], as usual
Leaderboard:
- Zeroko (128 bytes)
Good luck everyone, I'd love to see some entries!