8puzzle

INTRODUCTION
This is a submission to the ASCII BASIC Game 10Liner Jam. I was intrigued with the challenge and came up with this. More detail about the original game is given at the end of this text. I doubt this will set the world on fire, but it was a fun exercise and something that can run on just about anything capable of running Applesoft. 

I chose this game as something that could potentially run on an even wider variety of platforms, provide real and  authentic gameplay (vs. a hobbled ASCII version of a graphical game). It doesn't require a high-speed serial link to do realtime pseudo-graphics. I also chose the 8 tile version vs. the 15 so that game play wouldn't take all day. It actually makes a nice short puzzle break - you might be pleasantly surprised.

With a minor modification it should run fine on any floating-point BASIC (see program notes). It would be fun to see this operate on an Altair clone. It would even work on a Teletype as a display! Not that anybody cares these day :). UPDATE: I have recently modified it to run on CP/M's MBASIC. If anyone is interested in a copy, leave a comment and I'll post it. Otherwise, I'll stick with the Applesoft version.

PLATFORM: 
Applesoft - Any Apple ][ variant capable of running Applesoft should work. I actually developed this on an Apple I emulator running Applesoft-Lite that I recently created for some Adafruit boards (https://github.com/rkincaid/a1plus). I also verified the game with a number of other Apple II emulators. The Apple II+ was the first computer I personally owned.

Note: The DSK image is a DOS3.3 image that automatically loads the program if run from and Apple II emulator. You can simply drag and drop this file onto Apple2js (https://www.scullinsteel.com/apple2/).

DIRECTIONS:
Starting: Load and run the program (8puzzle.bas). It will ask for "SEED" to start the random number generator. Enter any number shy of +/-32766 (but avoid large numbers initially). NOTE! The seed also sets the difficulty, so start with a low number ~10-100 to get used to the game play and keep the initialization short. See CODE NOTES for details about this.  You can enter floating point numbers as well as integers so there are an infinite number of SEEDS to use. Very low numbers might sometimes result in no scramble, so just exit the program and try again with a higher number.

Moves: Type the number you want to move into the "empty" spot shown by the asterisk(*) and press return/enter. You can only choose numbers adjacent to this spot. In the screen shot shown above you could choose 2 or 1. Any other choice will simply be ignored. If you just press return the program will disapprovingly exit.

Completion: You "win" by completing the puzzle which requires you to order the numbers as:

1 2 3
4 5 6
7 8 *

CODE NOTES:

Porting to other platforms:

The most critical issue is how the RND function is used. There are a lot of variations between versions of BASIC as to what seed values look like (for Applesoft they are negative, some use non-zero values, etc.). Also, what value you enter to get a new random value after the seed varies. So lines 2 and 7 may need changing for your platform. 

Here are some line-by-line annotations:

This initializes the "board" and is pretty straightforward. S is used later and initialized here for line length reasons.
1DIMB$(5,5):K=1:FORI=1TO3:FORJ=1TO3:B$(I,J)=STR$(K):K=K+1:NEXT:NEXT:S=0

We set the empty spot to "*" and remember where it is. We also set the random number. We are going to dual-use the seed as a difficulty level. We take the log to make this difficulty value D between 0 and 4 depending on the seed.
2B$(3,3)="*":X=3:Y=3:INPUT"SEED?";D:D=ABS(D)+1:Z=RND(-D):D=INT(LOG(D)) 

Here we scramble the board. This was the first real challenge. How to do the without lots more lines. Line 7 will make random moves to scramble the board just like a human would do IRL. We do this until we have make D*10 moves. An asterisk is displayed each time we perform the GOSUB.
3Z=D*10:?".";:M$="X":GOSUB7:N=0:IFS<ZGOTO3 

We fall through to the board display, and a check if we completed the puzzle.
4?:FORI=1TO3:FORJ=1TO3:?B$(I,J);:NEXT:?:NEXT:IFN=8THEN?:?"YOU WIN!":END 

Here we ask for a move and get huffy if the player chooses to quit.
5N=0:K=1:?:INPUT"MOVE? ";M$:IFM$=""THEN?:?"BOO! YOU GAVE UP...":END 

GOSUB8 makes the move and the loop checks to see if we've solved the puzzle.
6GOSUB8:FORI=1TO3:FORJ=1TO3:N=N+(B$(I,J)=STR$(K)):K=K+1:NEXT:NEXT:GOTO4 

This is the line that scrambles the board by looking for moves around the empty spot (i.e. the asestrisk).
7FORK=1TO20:M$=B$(X+INT(RND(1)*3-1),Y+INT(RND(1)*3-1)):GOSUB8:NEXT 

Unfortunately, we have to eliminate diagonal moves.
8FORI=X-1TOX+1:FORJ=Y-1TOY+1:IFABS(I-X)=ABS(J-Y)GOTO10 

This line actually swaps the pieces that constitute the move. We also increment the number of valid moves for line 3, and we remember where the asterisk is now.
9IFB$(I,J)=M$ANDM$<>""THENB$(X,Y)=M$:B$(I,J)="*":X=I:Y=J:S=S+1:RETURN 

And finally we finish the scramble/move loop.  I had room so I left a dated credit...
10NEXT:NEXT:RETURN:REM R.KINCAID 2021

Tricks used:

1. Double use of the random seed for the difficulty level.

2. Reuse the move loop for the scramble loop depending on which line you start on.

3. Initializing some values in odd places to make the lines short enough

4. The usual BASIC stuff of eliminating spaces, using ? for PRINT,  etc.

Challenges:

1. The way most BASICs handle IF statements, you can only have one IF per line and everything after the IF is conditional.

2. You can't simply generate a random ordering of numbers as some orders are not solvable with the legally allowed moves. It's a common Comp Sci problem to write code to "prove" an ordering is solvable or not. But there's no way to get that to fit in the 10 lines. Hence, I solved this by simply mimicking what a human would do with a real physical puzzle - make a series of reverse moves to scramble the ordering.

PUZZLE NOTES:

If you aren't familiar with this kind of puzzle, they exist IRL with toys like this:

 

There is also an 8-number version of this. The game play is:

1. You can only move 1 tile at a time and there is only one place to put that tile - where the empty spot is.

2. The object is to order the numbers from 1 to 15 (or 1 to 8) left to right, top to bottom. (maybe other directions of ordering are possible, but I'm not sure).

Either yourself, or someone else randomly moves the tiles around to get a scrambled order, and the the object is to reorder them correctly. Sounds simple, and maybe pointless, but this was really an early Rubik's Cube kind of toy with a bit of Tetris-like addiction thrown in.