Re: a challenge related to the 15 puzzle
Message #1 Posted by Don Shepherd on 19 Jan 2011, 4:53 a.m.
Well, the HP-32sii version takes a while to run because it has to decode registers A-D in which 4 numbers are stored in each register. I did that to avoid using so many registers. This version stores a single cell value in each register A-P. While it uses many more registers than the other version, it runs much quicker (about 7 seconds versus 40 seconds).
Life (and programming) is all about trade-offs!
Program to determine solvability of 15 puzzle for 32s.
This one is faster than the one that stores 4 numbers in each register A-D.
Register usage:
A-P - 16 cell values, entered after XEQ A
Q - number of inversions, including row number of empty cell
R - current outer loop cell value
i - indirect addressing and inner loop index
T - outer loop index
Usage:
XEQ A
enter 16 cell values (0 for empty cell) R/S after each
program displays number of inversions; if even, puzzle is solvable
Code:
lbl a entry point
1.016 loop to get cell values
sto i
lbl b
r/s enter each of 16 values
sto (i) stores in A-P
x<>0 if 0 calc row#
goto c
3
rcl+i
4
/
ip
sto q inversion count starts with row# of empty cell
lbl c
isg i
goto b
1.015 outer loop goes from 1 to 15
sto t outer loop index
lbl d
rcl t get current outer loop cell value
sto i and store in R
rcl (i)
sto r
rcl t
ip
1.016
+ inner loop goes from t+1 to 16
sto i inner loop index
lbl e
rcl (i)
x=0 if inner loop cell value is 0, ignore
goto f
rcl r current outer loop cell value
x<y
goto f
1
sto + q increment inversion counter
lbl f
isg i
goto e iterate inner loop
isg t
goto d iterate outer loop
rcl q display inversion counter, even means puzzle is solvable
rtn
Edited: 19 Jan 2011, 10:23 a.m.
| 
Go back to the main exhibit hall