Re: a challenge related to the 15 puzzle

[Don Shepherd]

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.