Re: a challenge related to the 15 puzzle
Message #13 Posted by Don Shepherd on 16 Jan 2011, 3:35 p.m.,
in response to message #1 by Don Shepherd
Here is the program I wrote for the HP-32sii. It is not terribly fast; it takes around 40 seconds to return VALID or INVALID. One thing I learned from writing it is how to store multiple numbers in a register and then retrieve them one at a time. I didn't want to use 16 out of 27 registers just to hold the tile values, so the method I chose used only 4 registers for the 16 values. Thanks to Katie for advising me on that.
Program for HP-32sii to check an initial arrangement of number tiles
for the 15 puzzle to see if that configuration is solvable or not.
Prior to running, enter the initial arrangement (with 00 representing the
empty position) into registers A-D with 4 2-digit numbers per register, as follows:
A = 11051407
B = 15020904
C = 06000113
D = 10031208
(this arrangement is solvable, by the way, with 60 inversions)
Then XEQ A. If the arrangement is solvable, the program will display
VALID, otherwise INVALID. Press R/S to see the inversion count.
Register usage:
A-D - preset with initial arrangement of tiles
E - count of number of inversions
F - loop counter
G - loop counter
H&I - values of current cells in loops F and G
X - temp use in routine X
Subroutines:
M - returns value of cell character x (1-4) row (i)
X - returns value of cell pointed to in loops F and G
Code:
lbl a entry point
1.004 begin loop to find row with empty cell
sto i i will point to register A, B, C, or D
lbl b outer loop
1.004 begin loop to iterate through 4 numbers in A, B, C, and D
sto f get value 1, 2, 3, or 4 in A, B, C, D
lbl c inner loop
rcl f get value 1, 2, 3, or 4
ip
xeq m return the value of that cell
x=0 looking for the cell with 00, need that row number
goto d found it
isg f inner loop
goto c
isg i outer loop
goto b
rtn won't get here unless you goof and don't put 00 in a cell
lbl d found the 00, use row number to initialize inversion counter
rcl i row number containing empty cell
ip
sto e inversion count starts with row# of empty cell
1.015 now start looping to count inversions
sto f outer loop goes from 1 to 15
lbl e
rcl f
xeq x
x=0 if outer loop value is 0, iterate outer loop (no need to see
goto j if inner loop values are less than 0 since it's impossible)
sto h store outer loop current cell value in h
rcl f now establish inner loop counter, g goes from f+1 to 16
ip
1.016
+
sto g inner loop counter
lbl f
rcl g
xeq x
sto I store inner loop current cell value in I
x=0 if I is 0, ignore this iteration
goto g
rcl h
x<y if second cell is less than first cell, increment inversions
goto g
1
sto + e inversion count incremented
lbl g
isg g inner loop iterate
goto f
lbl j go here if outer loop value was 0 so don't waste time
isg f outer loop iterate
goto e
sf 10 to enable message in equation to appear
rcl e inversion count
2
/ if even, valid else invalid
fp
x=0
goto h
INVALID
rcl e and display inversion count before stopping
cf 10 clear flag 10
rtn stop
lbl h
VALID
rcl e
cf 10
rtn stop
lbl m subroutine returns value of number in x (1,2,3, or 4) in var (i)
enter
enter adjust input 1,2,3,4 to get to the correct
1 digit number since you need 2 digits, so 1 points to digit 1,
- 2 points to digit 3, 3 points to digit 5, and 4 points to digit 7
+
9
x<->y
-
rcl (i) i must be set prior to entering routine m
x<->y to point to vars A,B,C, or D
10^x
/
fp
100 so you get the 2-digit number, like 05 or 12
x
ip
rtn returns with the appropriate value in x
lbl x this subroutine converts numbers 1-16 in the main loops
ip to the appropriate variable (i) (1,2,3,4) and index (1,2,3,4)
sto x and then returns the value of that character
3
+
4
/
ip
sto i so correct variable A,B,C,D will be referenced
rcl x
enter
enter
4
/
ip
4 this will give x mod 4, but if it is 0
x it needs to be 4
-
x=0
4
xeq m now that i and x mod 4 are set, call m to get the value
rtn
| 
Go back to the main exhibit hall