|example of 30b program|
Message #1 Posted by Don Shepherd on 21 Jan 2010, 1:03 p.m.
Another poster mentioned writing a program to determine the solvability of the famous 15 puzzle, based upon the ordering of the number tiles initially and the position of the empty square. Essentially, the puzzle is solvable if the row number of the empty square + the number of "inversions" is even, otherwise it is not solvable. Inversions are the number of cases in which a number to the right of a given cell are less than that cell. For example, for cell values 9, 8, 7, 10, there are 3 inversions (8<9, 7<9, and 7<8).
The 30b code is below. Prior to running, you must fill the stats registers 0-15 with the arrangement of the number tiles, and the empty space has value 0. The program uses indirect addressing to get the values of the cells.
Note: I edited the code on 1/23/2010 to use the ISG looping instruction, which reduced the size of the code from 127 bytes to 119 bytes, which is not insignificant when you only have 290 bytes total. Note also that if R0 contains a fractional part, the fractional part is ignored when you use R0 for indirect addressing, which is great.
sto 0 determine the row# of the empty cell (=0)
rcl data get cell(r0 index)
gf 01 found the empty cell
sto + 0
goto 00 keep looking
rcl + 0 row# of empty cell = IP((index+4)/4)
sto 3 r3 contains the number of inversions, starts with row# of empty cell
sto 1 loop 1 goes from 0 to 14
sto 2 loop 2 goes from (loop 1 index + 1) to 15, you're going to compare two cells to check for inversions
rcl data get cell value in loop 2
input necessary because next command will pop the stack and you need this value in x
gf 04 if loop 2 value is 0, ignore it
sto 0 get loop 1 value now
roll down need to get loop 2 value back in x
rcl data get cell value in loop 1
gf 04 no inversion, continue loops
1 yes, an inversion was detected, add 1 to inversion count
sto + 3
lbl 04 test to end loop 2
isg 1 test to end loop 1
rcl 3 done looping, if #inversions is even, puzzle is solvable, else not
rcl 3 so inversions will be in x when you get the message (fyi)
msg Unsolv. (limited to 8 characters)
Edited: 23 Jan 2010, 6:40 a.m. after one or more responses were posted