HP Forums
Re: 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: Re: a challenge related to the 15 puzzle (/thread-177185.html)



Re: a challenge related to the 15 puzzle - Allen - 01-17-2011

Here's a quick RPL program based on the article you posted above. It uses a flag for parity tracking, and indrect addressing from the stack to scroll through the loops. Here are the program
41c
barcodes
(including 2 programs to input 2 test matrices.)

Credit Note: Program was written using Free42, output to RAW and converted to barcodes using HP41UC program.

Inputs:
Register 00 - 1 (a pointer to first cell)
Register 01 - First number of grid
...
Register 15 - Last number of grid
Register 16 - 00 (assumes the space is in location 16)
Outputs:
Clear stack except for 1 in ST X if solution exists, 0 otherwise


00 { 53-Byte Prgm }
01>LBL "AQ"
02 CF 01 ' clears the parity flag
03 CLST ' clear stack
04 RCL 00 '
05>LBL 01 ' Loop for checking results
06 RCL IND ST X
07 X<0? ' Check the pointer to see if it's neg
08 GTO 02 ' if so, go to next loop
09 -1
10 STOƗ IND ST Z ' Otherwise negate and recall next value
11 RCL IND ST Z
12 +/-
13 GTO 01 ' repeat loop
14>LBL 02 ' Flip the parity flag- (starts even)
15 FS? 01
16 FC?C 01
17 SF 01
18>LBL 03 ' begin counting through the values
19 RCL IND 00
20 X=0? ' until you find a positive one to loop on
21 GTO 04 ' 00 value indicates end of matrix
22 X>0?
23 GTO 01 ' new loop found, go to main loop
24 ISG 00 ' increment reg 00 counter
25 CLX ' NOP
26 GTO 03 ' counter to check for the first pos. number
27>LBL 04 ' end program
28 CLST ' cleanup the stack
29 FS? 01
30 1 ' return parity based on Flag 1
31 END

Note: edited to add inputs/outputs section


Edited: 18 Jan 2011, 9:16 a.m.


Re: a challenge related to the 15 puzzle - Don Shepherd - 01-18-2011

Great program Allen, thanks. Can you implement this unique algorithm in RPL on the 50g?

Don