a challenge related to the 15 puzzle - Printable Version +- HP Forums (https://archived.hpcalc.org/museumforum) +-- Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum-1.html) +--- Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum-2.html) +--- Thread: a challenge related to the 15 puzzle (/thread-177080.html) a challenge related to the 15 puzzle - Don Shepherd - 01-15-2011 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): 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. Re: a challenge related to the 15 puzzle - Glenn Shields - 01-16-2011 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 >> Re: a challenge related to the 15 puzzle - Glenn Shields - 01-16-2011 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: < 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 Re: a challenge related to the 15 puzzle - Allen - 01-16-2011 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. Re: a challenge related to the 15 puzzle - Glenn Shields - 01-16-2011 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 Re: a challenge related to the 15 puzzle - Allen - 01-16-2011 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. Re: a challenge related to the 15 puzzle - Don Shepherd - 01-16-2011 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 Re: a challenge related to the 15 puzzle - Allen - 01-16-2011 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 <ARRAY >> to convert list to square matrix before running 'FIFTN'. ``` Edited: 16 Jan 2011, 8:55 a.m. Re: a challenge related to the 15 puzzle - George Litauszky - 01-16-2011 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 Re: a challenge related to the 15 puzzle - Don Shepherd - 01-16-2011 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 Re: a challenge related to the 15 puzzle - Glenn Shields - 01-16-2011 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 Re: a challenge related to the 15 puzzle - Don Shepherd - 01-16-2011 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 xy - 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 ``` Re: a challenge related to the 15 puzzle - Allen - 01-16-2011 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 <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 ``` Re: a challenge related to the 15 puzzle - Don Shepherd - 01-16-2011 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. Re: a challenge related to the 15 puzzle - Don Shepherd - 01-17-2011 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. Re: a challenge related to the 15 puzzle - Allen - 01-17-2011 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.