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:

• 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:

1. Zeroko (128 bytes)

Good luck everyone, I'd love to see some entries!

138 bytes on-calc with 1-character name, for a score of 128

Code:

Note that this may take a very long time to complete, because it moves randomly & then resets if it does not reach the goal soon enough. It would be correct if "rand" were truly random, but TI's RNG may or may not be sufficient. I put 99 instead of 31 in for the upper bound on the step count, which makes it slower on average but more likely to be correct.

EDIT: On a pre-M TI-84 Plus CE with OS 5.3.0.0037, there exists at least one input that should take around a year to solve, but all instances that have solutions at all can be solved by this code (determined via simulation that was verified against the calculator on runs that did not take too long).
EDIT: I made it 39 bytes smaller & re-verified it with a correspondingly modified simulation. It ended up with a significantly faster iteration time, but the total time for the worst-case input is greater (around 600 days) anyway.
EDIT: I made it another 8 bytes smaller & re-verified it. It is again faster, with ~8 days being the worst case on pre-M. The algorithm is different, in that it moves deterministically except when the blank is at (1,2).
EDIT: I made it another 12 bytes smaller & faster (~4¾ days worst-case on pre-M) by converting the matrix to a list, storing the step choice in a string, & changing the random step to be at (3,2).
EDIT: I accidentally removed line that makes the random choice at some point. Oops.
EDIT: I made it another 14 bytes smaller & once again faster (~2⅔ days worst-case on pre-M) by changing the way it finds the 0 & checks for completion.
EDIT: kg583 pointed out that "ClrList L₁" is smaller than "0→dim(L₁" (by 2 bytes). (I did not make said modification because I did independently find it.)
EDIT: After some discussion (with LogicalJoe (especially the long line that encodes the move strategy) & possibly others I forgot), I made it another 20 bytes shorter & slightly faster (~2½ days worst-case on pre-M).
EDIT: Removed an unnecessary character in the code (which does not affect the length because I only made it in the post).

I always like a code golf challenge, but don't have time right now. I'll try to attack this in a week without looking at the other answer, but don't think I'll be able to match it without significant effort. 128 bytes seems too small for A* search-- I know a priority queue doesn't need to be a heap, but A* still requires computing a heuristic good enough to find the answer within 999 iterations. Props to Zeroko for whatever efficient approach was taken, whether it's well-optimized A* or something else clever.

Also, I'm assuming we just need to find a solution to the puzzle, not the optimal solution? Can it be a randomized algorithm?

EDIT: I think I'm overthinking this because there's no time limit.

First attempt with a brute-force recursive approach using 4 programs, 51+106+16+22=195 bytes. I don't expect this approach to go below 160, but I'll post it regardless once it's reasonably optimized. Most of the inefficiency has to do with working around the fact that there's no call stack, and so my program is structured around using a list and pushing only one element per call. Since I'm not very good at recursion there should be some improvements.

EDIT: 48+101+16+20=185 bytes now.

EDIT: now three programs with 48+86+39=173 bytes

This generates the list in reverse, starting from the solution and searching towards the input. It's fairly fast on easy inputs, but since the worst-case solution is 30 steps and this is exponential time, worst-case runtime is in the thousands of years.

Variables: |LS is the stack; |LI is {1,..., 9}; |LT is the solved board; |LX is the input


Code:


Code:


Code:


EDIT: Working on a version that uses the brute forcer from my code-golf guide, which should be closer to 160 bytes.

Update: Estimated difficulty of finding a working expression is 2^36 = 6.9*10^10 and I've searched 1.2*10^9 expressions so far. Optimized the expression finder a bit, but some test expressions are beginning to fail due to numerical instability.

EDIT: minor improvements, 37+99+26 = 162 bytes

EDIT: I'm down to 26+92+25=143 bytes.


Code:

Code:

Code:

The following cleaned-up version of Zeroko's answer weighs 116 bytes and seems to be equivalent, though I haven't verified.


Code:

That needs "ClrList ʟA" replaced by "0→dim(ʟA" (making it 2 bytes larger) to avoid an undefined error, at least on OS 5.3.0.0037. Nice work with making the inner loop use For...my own attempts at doing so made it bigger.

With that fix, plus saving one byte due to breaking up the long line (which I am not sure why I did not realize was possible before), I get 127 bytes on-calc / score of 117.

Code:

It appears to execute the inner loop (& thus rand) 729 (9³) times for each pass through the outer loop, while my previous submission executes it 730 times (due to the ≥ in the size comparison & starting at 0), so while it very probably still works, the number of passes it takes to find a solution generally will be different.

EDIT: It never stores to one of the lists, so replacing it with L₁ allows returning to using ClrList & saving those 2 bytes, for a score of 115.

EDIT: I verified that it still works for all valid inputs. The worst case should take around 5 days.