a challenge related to the 15 puzzle



#17

I'm sure most of us have seen the famous 15 puzzle, the little square plastic (usually) 4 by 4 puzzle with the 15 sliding pieces, and the goal is to get the pieces in the correct order. Most versions of the puzzle have interlocking pieces which cannot be removed from the puzzle board, but some versions allow you to remove the pieces and place them back randomly and try to solve the puzzle. However, if the pieces are removeable it turns out that there is a 50/50 chance that the puzzle will be unsolveable, depending upon the mathematics behind the order of the pieces.

The challenge: write a calculator program to determine whether the puzzle is solveable or unsolveable based upon a specific starting arrangement of pieces.

Here are two links that may help (there are many more):

Wikipedia

Wolfram Mathworld

Essentially, the puzzle is solveable if the row number (1-4) of the empty cell plus the number of "inversions" is even. An inversion occurs when a piece to the "right" of a piece has a lesser value. For example, for the arrangement of six pieces:

5, 8, 3, 2, 12, 10

there are 6 inversions: 2 numbers to the right of 5 are less than 5; 2 numbers to the right of 8 are less than 8; 1 number to the right of 3 is less than 3; 0 numbers to the right of 2 are less than 2; 1 number to the right of 12 is less than 12; 2+2+1+0+1 = 6.

This is a fairly simple problem to implement using BASIC. Using RPN and indirect addressing it is, of course, more complex, but I've written a HP-32sii program for it that works.

I'd like to see some RPL solutions to this problem because I have a feeling that a 4 or 5-liner may do the trick.


#18

Hi Don, I thought this might be more fun on the 35s, with the indirect
registers, but then thought about the "GET" function, and I was too lazy to look back in the manual for the details of "GETI", hence I produced a very "brute force", multi-line program to get the job done.

I just let "0" be the empty space, and then accounted for all the inversions it would cause depending on its "POS", then subtracted that out. Also, I would have liked to use local variables, but in a "RPN" manner used the variables C, E and P then purged them.

Just put the puzzle as a 4x4 matrix in the stack, and hit 'FIFTN':
(sorry I don't know how to make paragraphs in this forum)

<<0 'C' STO 1 15 FOR j j GET LASTARG DROP SWAP 'E' STO j 1 +
16 FOR n n GET LASTARG DROP SWAP E IF < THEN 1 'C' STO+ END
NEXT NEXT OBJ-> OBJ-> DROP * ->LIST 0 POS DUP 1 - 'C' STO- 'P'
STO IF P 4 <= THEN 1 ELSE IF P 8 <= THEN 0 ELSE IF P 12 <=
THEN 1 ELSE 0 END END END C IF 2 MOD NOT THEN "SOLVABLE"
SWAP DROP ELSE "NOT SOLVABLE" SWAP DROP END {C E P} PURGE >>


#19

Don, I am so sorry, I didn't beta-test this program (called 'FIFTN'),
but to get it to work it needs the matrix stored in a variable called
'PUZZL' which will be saved at the end. Also forgot to add the row test result to C (duh!) So one more try:

<<DUP 'PUZZL' STO 0 'C' STO 1 15 FOR j j GET LASTARG DROP SWAP
'E' STO j 1 + 16 FOR n n GET LASTARG DROP SWAP E IF < THEN 1 'C'
STO+ END NEXT NEXT PUZZL OBJ-> OBJ-> DROP * ->LIST 0 POS DUP 1 - 'C' STO- 'P' STO IF P 4 <= THEN 1 ELSE IF P 8 <= THEN 0 ELSE IF
P 12 <= THEN 1 ELSE 0 END END END C + IF 2 MOD NOT THEN "SOLVABLE"
SWAP DROP ELSE "NOT SOLVABLE" SWAP DROP END {C E P} PURGE >>

Regards, Glenn

#20

Don, here's my listing partially optimized at 87.5 Bytes

Input: 16 element list (left to right top to bottom of the 15 square, using 0 for the space)
Output: 0 if the list is unsolvable otherwise 1

« 0 SWAP REVLIST ' start a 0 counter
-7 7 FOR N ' -> loop over the list
DUP HEAD DUP2 < SUMLIST - ROT + ' | Subtract from N the number of entries < N
SWAP TAIL NEXT ' | set up list for next loop
EVAL + 2 MOD » ' add box 1, check for parity


Edited: 16 Jan 2011, 2:49 a.m.


#21

Allen, where is the test for the position of the blank? And you output a 1 if solvable, but isn't odd parity a sign of unsolvability?
Didn't know about the list comparison capability, that's great, but your program says that these two lists are solvable, but are they?
{1 8 9 0 2 7 10 15 3 6 11 14 4 5 12 13} and {1 2 3 4 8 7 6 5 9 10 11 12 0 15 14 13} cheers, Glenn


#22

If you wish to impose the GRID parity for the invariant, add the top two lines to the above program ( Total 134.5 Bytes)

 « DUP 0 POS                          ' (ADDED) Check for space
1 - DUP #4d / SWAP #1d * XOR B->R ' (ADDED) Impose GRID Parity
SWAP REVLIST ' start counter using the GRID parity above
-7 7 FOR N ' -> loop over the list
DUP HEAD DUP2 < SUMLIST - ROT + ' | Subtract from N the number of entries < N
SWAP TAIL NEXT ' | set up list for next loop
EVAL + 2 MOD » ' add box 1, check for parity


Edited: 16 Jan 2011, 3:52 a.m.

#23

Thanks Allen and Glenn.

Glenn, the way to format code listings on the forum is to precede the code with [pre] and put [/pre] after the code. Then your code listing will look great.

The two sequences you listed are, according to my program, not solvable, with inversion counts 37 and 13 respectively (this count includes the row number of the empty cell). I'll double-check that with another program I have running on the Casio 9860g slim.

Don


#24

Here are some test outputs I get with the two programs

#P - Parity program (earlier version)
#G - Grid parity program (later version)
#GS - Glen version program
0= "NOT SOLVABLE"
1= Can be Solved


Input #P #G #GS**
--------------------------------------------------------------
{1 8 9 0 2 7 10 15 3 6 11 14 4 5 12 13} 1 0 0
{1 2 3 4 8 7 6 5 9 10 11 12 0 15 14 13} 1 1 0
{1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0} 1 1 1
{1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 0} 0 0 0
{13 9 2 3 14 0 4 15 10 11 1 7 12 5 6 8} 0 1 0
{13 10 11 6 5 7 4 8 1 12 14 9 3 15 2 0} 0 0 0

** NOTE: I use a <<EVAL {4 4} ->ARRAY >> to convert list to square matrix before running 'FIFTN'.

Edited: 16 Jan 2011, 8:55 a.m.


#25

Thanks Allen. Here is what I get when I run your six configurations (in order, inversions includes the row number [1-4] of empty cell):

not solvable, 37 inversions
not solvable, 13 inversions
solvable, 4 inversions
not solvable, 5 inversions
not solvable, 57 inversions
not solvable, 63 inversions

The best way to test these results is with a real 15 puzzle with removeable tiles. I ordered one a couple of days ago, it should arrive on Tuesday and I'll check these out.

thanks, Don

#26

Hi Don, this is a 50g solution.

Input: A list with the numbers, replace the hole with 0.

I use local variables because I just learning the stack programming. I use the STREAM command to come along the lists only. I tested it with Glenn's and Allen's lists (thanks) and it seems the program is correct.

\<< 0. 0. 0.  \-> lst he res pos
\<< lst 0. POS 4. /
DUP IP SWAP FP
IF THEN
1. + 'pos' STO
ELSE
'pos' STO
END
1. 15. FOR n
lst
HEAD DUP 'he' STO
IF THEN
lst
\<< DUP
IF he < AND 0. > THEN
1. 'res' STO+
END \>>
STREAM DROP
END
lst TAIL 'lst' STO
NEXT
res pos + 2 MOD
IF THEN \"Not solvable\"
ELSE \"Solvable\" END
\>>
\>>


Note:

To launch a difficulter chat in english with me: With your own personal risk only, please. :-)


George

#27

Hello George, thank you for your program, it has very interesting use
of stream (to skip 0.) and the use of IP/FP to check the row that 0. is in (I couldn't think of how to do that). Fast and efficient.
And thanks to Allen for his tabulation of the results, there is much to be learned from all. Don, I'm sure we'll hear more from this challenge (look at the last one!!) Cheers, Glenn


#28

Ahh... after some sleep, I found a bug in the Parity checker for the GRID, now the fixed the program agrees with Glen and Don's findings. Some interesting byte saving tricks I'd forgotten about. In any case noted below,

Here are some test outputs I get with the two programs

                  Input                    #P   #G  #GS**  #AT3  #DS
-------------------------------------------------------------------
{1 8 9 0 2 7 10 15 3 6 11 14 4 5 12 13} 1 0 0 0 0
{1 2 3 4 8 7 6 5 9 10 11 12 0 15 14 13} 1 1 0 0 0
{1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0} 1 1 1 1 1
{1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 0} 0 0 0 0 0
{13 9 2 3 14 0 4 15 10 11 1 7 12 5 6 8} 0 1 0 0 0
{13 10 11 6 5 7 4 8 1 12 14 9 3 15 2 0} 0 0 0 0 0

** NOTE: I use a <<EVAL {4 4} ->ARRAY >> to convert list to square matrix before running 'FIFTN'.

#P - Parity program (earlier version)
#G - Grid parity program (later version)
#GS - Glen version program
#AT3 - 3rd version with corrected GRID Parity (see below)
#DS1 - Don's solution

0= "NOT SOLVABLE"
1= "CAN BE SOLVED"


The final version which includes both parity checks for the Grid alignment of the space and the number of inversions necessary to permute the puzzle. (Total 104 Bytes on the stack, checksum #16245d)

« DUP 0 POS 1 - R->B DUP SR SR XOR B->R       ' (bug fixed) check for space GRID Parity and start the loop with it on the stack
' Grid Parity can be calculated by XOR(Y>>2,Y) where Y is the 0 position - 1 using SR saves bytes over #4d
SWAP REVLIST ' Reverse the list to use HEAD and TAIL to grab the end
-7 7 FOR N ' Loop Uses -7 to 7 to save 8 bytes compared to 1 to 15
DUP HEAD DUP2 < SUMLIST - ROT + SWAP TAIL 'Add the shifts and trim list
NEXT ' Loop
EVAL + 2 MOD » ' Add the last element

At first glance, it may seem that I'm being sloppy with the calculations, but although the numbers coming out of the loop are all off by 1, they are PREDICTABLY off by 1 (which over a 15-step loop is off by exactly 15). When dealing with parity, it's not necessary to have the right sum, only the right sum MOD2. Accordingly, the math behind the scenes is something like this:

                  Input                  DON  GRID  INV  PARITY 
-------------------------------------------------------------------
{1 8 9 0 2 7 10 15 3 6 11 14 4 5 12 13} 37 O 03 + 39 O+O=E
{1 2 3 4 8 7 6 5 9 10 11 12 0 15 14 13} 13 O 15 + 21 O+O=E
{1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0} 04 E 12 + 15 E+O=O
{1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 0} 05 O 12 + 16 E+E=E
{13 9 2 3 14 0 4 15 10 11 1 7 12 5 6 8} 57 O 04 + 60 E+E=E
{13 10 11 6 5 7 4 8 1 12 14 9 3 15 2 0} 63 O 12 + 74 E+E=E
#29

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


#30

The same program on the 32s takes about 32 seconds, a bit faster than the 32sii, which I have observed before. On the 32s, however, I can't display INVALID or VALID since it does not have the algebraic equation solver, so I just show the number of inversions; if the number is even the arrangement is solvable.


#31

I had a question about why the -7...7 loop is more memory efficient than going from 1 to 15. As it turns out, the 48G is not the only place one can use this trick. Several programmable calculators have an exploitable memory trick when it comes to byte conservation.

Calc   Memory Trick                                    Ref
-------------------------------------------------------------------
32S integers 0..99 use 1.5 bytes instead of 9.5 UM, p. 874
32SII integers 0..254 use 1.5 bytes instead of 9.5 UM, p. 12-22
48G Built-in objects (int. -9..9, pi) use 2.5 bytes
instead of 10.5 AUM, p. 3-41
48gii same as 48g AUM, p. 3-30
49G same as 48g AUM, p. 3-30
49G+ same as 48g AUM, p. 3-30
50G same as 48g AUM, p. 3-30

UM= USERS MANUAL
AUM= Advanced Users Manual

Edited: 17 Jan 2011, 7:57 a.m.

#32

Here is an interesting article from "The Mathematical Gazette" in 1926 that describes a rather unique way of determining whether a specific configuration is solvable. It assumes that the empty position is always the 16th position, so it won't work for every possible configuration (it seems to me). But it is interesting that somebody figured this out in 1926.


Possibly Related Threads...
Thread Author Replies Views Last Post
  Good puzzle for kids to solve on 35s? snaggs 11 2,555 09-18-2013, 10:40 PM
Last Post: David Hayden
  Second Batch of HP-15 LE calculators Namir 6 1,835 07-02-2013, 12:27 PM
Last Post: Kimberly Thompson
  HP-15 LE Key repair question Namir 2 1,137 06-10-2013, 10:42 PM
Last Post: Namir
  Party Puzzle: for your amusement hugh steers 2 938 05-28-2013, 03:00 PM
Last Post: hugh steers
  HP 41 Mcode related Questions Michael Fehlhammer 4 1,406 05-10-2013, 07:09 PM
Last Post: Michael Fehlhammer
  The answer to the second semi-mathematical puzzle Mike Reed 3 1,118 02-18-2013, 02:40 AM
Last Post: Derek Walker (UK)
  Answer to Mathematical Puzzle Mike Reed 2 930 02-08-2013, 12:11 AM
Last Post: LHH
  OT: a semi mathmatical puzzle 4 u Mike Reed 6 1,589 02-05-2013, 07:50 PM
Last Post: Mike Reed
  Calculator O.T., instead HP related. Luiz C. Vieira (Brazil) 1 935 08-17-2012, 06:57 AM
Last Post: Frank Boehm (Germany)
  A new firmware beyond 2.15 for 50g ever? mr-scorpio 3 1,285 07-24-2012, 07:25 AM
Last Post: Keith Midson

Forum Jump: