(16C) 15-Puzzle Solvability Checker

[Dave Britten]

Reference: https://www.geeksforgeeks.org/check-inst...-solvable/

In a nutshell, a configuration of the 15 puzzle is solvable if the number of inversions plus the row number of the blank space (starting at 1 and counting from the top) is an even number.

This is based on the program Don Shepherd wrote for the 65, which uses bit flag techniques to track which tiles have been "seen". Since the 16C has functions for directly setting and counting bits, it seemed like an ideal platform to implement this solution. It's longer than the 65 version, but mostly because I wasted a bunch of steps displaying a crude message using hex mode when the program finishes.

https://www.hpmuseum.org/forum/thread-7362.html

The 16C version must be run with WSIZE 16 or greater. Complement mode shouldn't matter.

Usage

Enter the row number containing the blank space, with row 1 being the top row, and row 4 being the bottom, and press GSB A to initialize the program.

Enter the tiles one by one, starting from the top row, and going left to right across each row. Press R/S after each tile entry. Skip over the blank space (i.e. only make 15 entries total). And if your 15 puzzle happens to be hexadecimal, you can switch to hex mode and use 1-F to make entries.

The display will show the total number of inversions so far after each entry. After entering all 15 tiles, the program will briefly display either "GOOD" or "BAD" to indicate if the puzzle can be solved, and leave the final inversion count in the X register.

Code:

001     LBL A   43,22,A
002     STO 2   44 2            #Store blank space row number
003     DEC     24              #Set up loop counter
004     1       1
005     5       5
006     STO I   44 32
007     CLx     43 35           #Clear bit flags (R0) and inversion count (R1)
008     STO 0   44 0
009     STO 1   44 1
010     LBL 1   43,22,1
011     R/S     31
012     RCL 0   45 0            #Recall the current bit flags,
013     x><y    34              #and set the bit for the tile number.
014     SB      42 4
015     STO 0   44 0
016     LSTx    43 36           #Get the tile number back,
017     1       1               #and add one...
018     +       40
019     MASKR   42 8            #...to mask off all the lower order bits.
020     NOT     42 30
021     AND     42 20
022     #B      43 7            #Count the higher order bits,
023     RCL 1   45 1            #and add to the current inversion count.
024     +       40
025     STO 1   44 1
026     DSZ     43 23           #Loop if there are more tiles.
027     GTO 1   22 1
028     RCL 2   45 2            #Add the blank space row number to the inversion count.
029     +       40
030     2       2
031     RMD     42 9            #See if the total is even or odd.
032     HEX     23              #Set hex mode for display later.
033     x!=0    43 48           #Odd? Go to LBL 2.
034     GTO 2   22 2
035     6       6               "GOOD"
036     0       0
037     0       0
038     D       d
039     GTO 9   22 9
040     LBL 2   43,22,2
041     B       b               "BAD"
042     A       A
043     D       d
044     LBL 9   42,22,9
045     CF 3    43,5,3          #Turn off zero-padding
046     PSE     43 34           #Display briefly
047     DEC     24
048     RCL 1   45 1            #Show the inversion total
049     RTN     43 21