(HP-67/97) a little fun with the fifteen puzzle

[Don Shepherd]

When I started this thread, I didn't think it was possible to implement a solution to this problem on the HP-65. That's because I was unable to "think outside the box." Dave Britten developed and showed me a solution on the TI-80 that did not require lots of variables, that the 65 does not have. It requires only a couple of variables by setting and checking bits from 2^1 to 2^15, where 1-15 are the tiles encountered thus far, and entering the tile values from left to right, top to bottom. After the entry of each tile, the number of inversions is calculated by seeing how many higher tiles are already present, each one of these being an inversion.

So the HP-65 can solve this problem if the programmer thinks about it long enough. I am indebted to Dave for his elegant solution and help in getting it to work on the 65. I never would have thought that this problem could be solved on the 65, much less using only 3 registers and 45 lines of code. The capabilities of the HP-65 continue to amaze me.

Enter the row number (1-4) of the row containing the empty cell and press A. Then enter each tile value and press B (after each one). After all 15 tiles have been entered, it will show the number of inversions. If this number is even, the puzzle is solvable.

Code:


lbl a
clr reg
sto 2
rtn
lbl b
2
x<->y
y^x
sto+1
rcl 1
x<->y
/
2
/
int
sto 4
lbl 1
2
/
int
sto 4
lst x
frac
2
x
sto+2
0
rcl 4
x=/=y
goto 1
rcl 2
rtn

r1 contains the bit fields
r2 contains the running tally of inversions
r4 keeps track of bits higher than the current tile