The Museum of HP Calculators

HP Forum Archive 20

[ Return to Index | Top of Index ]

Re: a challenge related to the 15 puzzle
Message #1 Posted by Don Shepherd on 20 Jan 2011, 11:06 p.m.

I figured out that, rather than have two loops to calculate the inversion count (which takes about 40 seoonds on the 32sii), you can actually do it while you are entering the numbers if you keep track of the numbers you have previously entered. Then, when you enter the last number, you can see the inversion count immediately. This 32sii program implements that algorithm.

This version of the 15 puzzle solvability program is for the 32sii and not the 32s
because it uses the exchange x with a register command which is not on the 32s.
Since I got the 32sii I've been looking for a reason to use this command
and this is it!

This version calculates the cumulative inversion count as the 16 numbers are entered, so once you enter the last number it tells you the inversions instantly, with no waiting.

Usage:

XEQ A enter first number R/S enter second number R/S . . . enter 16th number R/S

it then displays the inversion count; even number means the puzzle can be solved.

Registers:

A-O - set to 1 when the corresponding number is entered P - inversion count (even means solvable) Q - main loop index i - indirect addressing and second loop index

Code:

lbl a entry point clrvars 1.016 initialize loop to enter 16 numbers sto q main loop index lbl b begin main loop r/s enter the next number (0 for empty space) x=/=0 if empty space, calc row number and update P goto c for 1-15 3 rcl+q 4 / ip sto+p update inversion count with row # of empty cell goto x iterate main loop lbl c handle 1-15 x<->i move # to i 1 sto (i) put a 1 in A-O when number is found x<->i get number back in x 1 add x-1 to p, max possible inversions - sto+p x=0 if 0 this is number 1, so nothing can be to it's left goto x so iterate main loop 1000 otherwise loop from 1 to (x-1) and subtract what / you find there from p 1 + sto i so input number 7 would cause loop from 1 to 6 lbl d begin loop rcl(i) will be 0 or 1 sto-p subtract from inversion count isg i iterate loop goto d lbl x iterate main loop now isg q goto b continue main loop to enter next number rcl p display inversion count rtn all done


[ Return to Index | Top of Index ]

Go back to the main exhibit hall