12-03-2016, 09:26 PM

Everyone knows the fifteen puzzle; fifteen little numbered tiles, 1-15, in a little 4 by 4 container with one position empty, usually interlocking pieces that cannot be removed from the container. But what if the pieces are not interlocking and are removable, allowing you to setup your own random start position? Is every such configuration solvable (solvable meaning being able to arrange the pieces, by sliding only, into order 1-15)? Surprisingly, the answer is, "no." It turns out that half of the possible initial configurations are not solvable. How can you tell if a given initial configuration of the tiles is solvable? That's what this program is about.

There is this thing called "number of inversions." If the number of inversions is an even number, the configuration is solvable, else it is not. How do you determine the number of inversions? You run this program!

Imagine all 15 tiles in a single row. Start at the tile in the leftmost position; how many tiles to its right have values that are less than this tile? Those are called inversions. If the leftmost tile was number 7, then the number of inversions for the first tile would be 6, obviously. Then move to the second tile; how many tiles to its right are less than its value? Keep doing this for all tiles, and that sum is the number of inversions (plus the row number of the empty space).

I have a nice wooden fifteen puzzle that came with a great book describing everything about the puzzle. The pieces are removable, so this program will let me create an initial configuration that is solvable.

To run the program, press A (initialization). Then enter the tile piece in the leftmost position of the first row, followed by pressing B. Then continue along the first row, pressing B for each of the other 3 values. Then enter the first number in the second row and press B, and so on. For the empty space, press 0 then B. After all 16 values are entered, press C. The program will run for about two and one-half minutes before it displays the number of inversions. If this number is even, great, the puzzle is solvable. If the number is odd, simply switch any two tiles with each other and it will be solvable.

I always wanted to create this program for my HP-65, but it was impossible due to only 9 variables (really 8 unless you have no conditionals) and lack of indirect addressing. The HP-67 works fine, however, with its extended programming capabilities.

I am aware of the fact that, in the time the program takes to run, you could have calculated the number of inversions manually. But I generally make a mistake when I do it that way, and the program never makes a mistake, like all good computers.

Remember, A is initialization, B enters the 16 values, and C calculates the number of inversions.

There is this thing called "number of inversions." If the number of inversions is an even number, the configuration is solvable, else it is not. How do you determine the number of inversions? You run this program!

Imagine all 15 tiles in a single row. Start at the tile in the leftmost position; how many tiles to its right have values that are less than this tile? Those are called inversions. If the leftmost tile was number 7, then the number of inversions for the first tile would be 6, obviously. Then move to the second tile; how many tiles to its right are less than its value? Keep doing this for all tiles, and that sum is the number of inversions (plus the row number of the empty space).

I have a nice wooden fifteen puzzle that came with a great book describing everything about the puzzle. The pieces are removable, so this program will let me create an initial configuration that is solvable.

To run the program, press A (initialization). Then enter the tile piece in the leftmost position of the first row, followed by pressing B. Then continue along the first row, pressing B for each of the other 3 values. Then enter the first number in the second row and press B, and so on. For the empty space, press 0 then B. After all 16 values are entered, press C. The program will run for about two and one-half minutes before it displays the number of inversions. If this number is even, great, the puzzle is solvable. If the number is odd, simply switch any two tiles with each other and it will be solvable.

I always wanted to create this program for my HP-65, but it was impossible due to only 9 variables (really 8 unless you have no conditionals) and lack of indirect addressing. The HP-67 works fine, however, with its extended programming capabilities.

I am aware of the fact that, in the time the program takes to run, you could have calculated the number of inversions manually. But I generally make a mistake when I do it that way, and the program never makes a mistake, like all good computers.

Remember, A is initialization, B enters the 16 values, and C calculates the number of inversions.

Code:

LBL A

1

ST I

RTN

LBL B

STO (i)

ISZ

RTN

LBL C

16

ST I

LBL 1

RCL (i)

X <> 0

GOTO 2

RCL I

3

+

4

/

INT

STO 0

GOTO 3

LBL 2

DSZ

GOTO 1

LBL 3

1

STO A

LBL 4

RCL A

ST I

RCL (i)

STO C

RCL A

1

+

STO B

LBL 5

RCL B

ST I

RCL (i)

X=0

GOTO 6

RCL C

X<=Y

GOTO 6

1

STO+0

LBL 6

RCL B

1

+

STO B

16

RCL B

X<=Y

GOTO 5

RCL A

1

+

STO A

15

RCL A

X<=Y

GOTO 4

RCL 0

RTN