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

[Don Shepherd]

Everyone knows the fifteen puzzle; fifteen little numbered tiles, 1-15, in a little 4 by 4 container with one position empty, usually interlocking pieces that cannot be removed from the container. But what if the pieces are not interlocking and are removable, allowing you to setup your own random start position? Is every such configuration solvable (solvable meaning being able to arrange the pieces, by sliding only, into order 1-15)? Surprisingly, the answer is, "no." It turns out that half of the possible initial configurations are not solvable. How can you tell if a given initial configuration of the tiles is solvable? That's what this program is about.

There is this thing called "number of inversions." If the number of inversions is an even number, the configuration is solvable, else it is not. How do you determine the number of inversions? You run this program!

Imagine all 15 tiles in a single row. Start at the tile in the leftmost position; how many tiles to its right have values that are less than the value of this tile? Those are called inversions. If the leftmost tile was number 7, then the number of inversions for the first tile would be 6, obviously. Then move to the second tile; how many tiles to its right are less than its value? Keep doing this for all tiles, and that sum is the number of inversions (plus the row number of the empty space).

I have a nice wooden fifteen puzzle that came with a great book describing everything about the puzzle. The pieces are removable, so this program will let me create an initial configuration that is solvable.

To run this HP-67 program, press A (initialization). Then enter the tile piece in the leftmost position of the first row, followed by pressing B. Then continue along the first row, pressing B for each of the other 3 values. Then enter the first number in the second row and press B, and so on. For the empty space, press 0 then B. After all 16 values are entered, press C. The program will run for about two and one-half minutes before it displays the number of inversions. If this number is even, great, the puzzle is solvable. If the number is odd, simply switch any two tiles with each other and it will be solvable.

I always wanted to create this program for my HP-65, but it was impossible due to only 9 variables (really 8 unless you have no conditionals) and lack of indirect addressing. The HP-67 works fine, however, with its extended programming capabilities.

I am aware of the fact that, in the time the program takes to run, you could have calculated the number of inversions manually. But I generally make a mistake when I do it that way, and the program never makes a mistake, like all good computers.

Remember, A is initialization, B enters the 16 values, and C calculates the number of inversions.

Code:


LBL A
1
ST I
RTN
LBL B
STO (i)
ISZ
RTN
LBL C
16
ST I
LBL 1
RCL (i)
X <> 0
GOTO 2
RCL I
3
+
4
/
INT
STO 0
GOTO 3
LBL 2
DSZ
GOTO 1
LBL 3
1
STO A
LBL 4
RCL A
ST I
RCL (i)
STO C
RCL A
1
+
STO B
LBL 5
RCL B
ST I
RCL (i)
X=0
GOTO 6
RCL C
X<=Y
GOTO 6
1
STO+0
LBL 6
RCL B
1
+
STO B
16
RCL B
X<=Y
GOTO 5
RCL A
1
+
STO A
15
RCL A
X<=Y
GOTO 4
RCL 0
RTN

[Dieter]

(12-03-2016 09:26 PM)Don Shepherd Wrote:  The HP-67 works fine, however, with its extended programming capabilities.

Hmmm.... even the 67's capabilities do not offer a X<Y? test or a X<>0 command.
Is this program designed for an emulator with extended instruction set?

Dieter

[Gene]

The X NE 0 or X <> 0 conditional is f + or yellow shift +.

It is the X < Y ? conditional that is not on the keyboard. Unless Don meant that one to be X <= Y ? :-)


The best approaches to supplying the missing conditionals are found in this PPC booklet: Better Programming on the HP-67/97

[Don Shepherd]

Thanks Dieter and Gene. I changed the x<y to x<=y in the code above.

Yes, I remember as I was entering the program that there was no x<y, so as Gene suggested I tried x<=y and that worked (it works because, in this instance, the two values in x and y can never be equal). I created the HP-67 program from a solver equation I had on the 17b which runs much faster than the 67 code (20 seconds versus 2 and a half minutes).

Thanks for that link Gene, it appears to be a treasure trove of good information on the 67. I plan on studying that document over the holidays.

[SlideRule]

Maybe post the 17b solver equation if anyone shows an interest? {hint}

SlideRule

[Don Shepherd]

(12-06-2016 01:43 AM)SlideRule Wrote:  Maybe post the 17b solver equation if anyone shows an interest? {hint}

SlideRule

Sure, SlideRule, here it is:

Code:


FIFTEEN:SIGMA(I:1:16:1:IF(ITEM(C:I)=0:IDIV(I+3:4):0))+SIGMA(I:1:15:1:SIGMA(J:I+1​:16:1:IF(ITEM(C:J)<>0 AND ITEM(C:J)<ITEM(C:I):1:0)))-INV

solve for INV, sum list C contains the 16 values, 0=empty cell

[Don Shepherd]

Here is a link to a version of the fifteen puzzle that has removable pieces. It includes a small book that is very well illustrated and gives the interesting history of the puzzle.

book

[Dieter]

(12-05-2016 10:07 PM)Gene Wrote:  The X NE 0 or X <> 0 conditional is f + or yellow shift +.

Ah, so this is supposed to be a *test*!
I read this as an X exchange R0 command!

(12-05-2016 10:07 PM)Gene Wrote:  The best approaches to supplying the missing conditionals are found in this PPC booklet: Better Programming on the HP-67/97

Thank you for the link. The technique itself (two or more consecutive tests) is well known, I once wrote about this in the old forum.

Dieter

[SlideRule]

(12-06-2016 03:46 AM)Don Shepherd Wrote:  

(12-06-2016 01:43 AM)SlideRule Wrote:  Maybe post the 17b solver equation if anyone shows an interest? {hint}
SlideRule

Sure, SlideRule, here it is:

Thanks!
SlideRule

[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

[PedroLeiva]

(12-05-2016 10:07 PM)Gene Wrote:  The X NE 0 or X <> 0 conditional is f + or yellow shift +.

It is the X < Y ? conditional that is not on the keyboard. Unless Don meant that one to be X <= Y ? :-)


The best approaches to supplying the missing conditionals are found in this PPC booklet: Better Programming on the HP-67/97

Dear Gene, I discover "Better Programming on the HP-67/97" today, is not available in Dropbox any more, can you uploaded again for those who have just discovered of its existence. The jewels in programming for HP-67 are always welcome. If not possibble, I will send an email
Many thanks in advance, Pedro

[Gene]

See if this will work:

HP 67 / 97 Better Programming PPC

If not, send me your email and I will get it to you.

Dropbox recently changed how their public folder links work. Argh.

[PedroLeiva]

(04-27-2017 02:01 AM)Gene Wrote:  See if this will work:

HP 67 / 97 Better Programming PPC

If not, send me your email and I will get it to you.

Dropbox recently changed how their public folder links work. Argh.

It took me several minutes to download the file, after two attempts. Thank you very much for answering my request. TYVM, Pedro

[Dave Britten]

Here's a quick 16C version of Don's 65 program. The bit manipulation/counting instructions make this algorithm pretty trivial on this model: you don't have to implement any kind of loop for bit counting, just mask them off and use #B to get a count. Of course, the lack of register arithmetic adds a few unnecessary steps. But 25 steps and 2 registers ain't bad!

For this version, enter the row with the blank, GSB A, then enter each tile number followed by R/S. Make sure your word size is set to at least 16.

Code:

43,22,A         LBL A
42 34           CLEAR REG
44 2            STO 2
31              R/S
43,22,B         LBL B
1               1
34              X><Y
42 E            RLn
43 36           LSTx
34              X><Y
45 1            RCL 1
42 40           OR
44 1            STO 1
34              X><Y
1               1
40              +
42 8            MASKR
42 30           NOT
42 20           AND
43 7            #B
45 2            RCL 2
40              +
44 2            STO 2
31              R/S
22 B            GTO B

[Don Shepherd]

(05-02-2017 03:03 PM)Dave Britten Wrote:  Here's a quick 16C version of Don's 65 program. The bit manipulation/counting instructions make this algorithm pretty trivial on this model: you don't have to implement any kind of loop for bit counting, just mask them off and use #B to get a count. Of course, the lack of register arithmetic adds a few unnecessary steps. But 25 steps and 2 registers ain't bad!

For this version, enter the row with the blank, GSB A, then enter each tile number followed by R/S. Make sure your word size is set to at least 16.

Code:

43,22,A         LBL A
42 34           CLEAR REG
44 2            STO 2
31              R/S
43,22,B         LBL B
1               1
34              X><Y
42 E            RLn
43 36           LSTx
34              X><Y
45 1            RCL 1
42 40           OR
44 1            STO 1
34              X><Y
1               1
40              +
42 8            MASKR
42 30           NOT
42 20           AND
43 7            #B
45 2            RCL 2
40              +
44 2            STO 2
31              R/S
22 B            GTO B

Thanks Dave, the 16c is a great calculator. In fact it was the first HP I ever owned, back in the early 80's.

Yes, I was thinking as I was looking at the 65 code that a loop would be unnecessary if we could only sum the bit range rather than looping through all the bits looking for a 1, but I didn't see an easy way to do that.