Puzzle 15 solver ?

[Crazyboss]

Hi.

For quite some time I have been thinking to make a Puzzle 15 game, both for Memotech but also for other systems, I recall in the 80s I did, Not sure if I ever got the Memotech to work, but for sure I did a Spectravideo 328 version.

Back then I did not think about how to solve it, and I even now know it could have created impossible puzzles, cause I did it random back then.

I have tried diffirent Algoritms, but none seems to work that great, most of the solutions out there are coded in languages or systems that have tons of memory.

I have tried to make something but its not very clever, and sometimes get stock looping around.

I used something a point system, where the algoritm tries the possible moves, up,down,left,right (ofcause some can be impossble if in corner og edge), but then I calculate how far away to pieces are from the space they should be in, and the lowest score, I pick that move. I think thats called the A* Search, and online I see alot of people explain them, but either I dont understand them, or they make the puzzles so simple so it works.

If anyone have any suggestions please share your ideas I am quite sure a 8bit processor can solve those if its just coded the right way.

https://en.wikipedia.org/wiki/15_puzzle

[Bill B]

Curse you for diverting me onto yet another problem

The Wikipedia page you reference includes a link to this page. The algorithm described is not optimal, but is explicit and should be possible to implement on an MTX,

[Crazyboss]

Hi Bill.

Thanks for you input, yes its a "human" way to solve it, I think it can be solved, I see alot of other solvers out at the internet written in Phyton and C but I dont know those languages but as I understand they use some kind of recursive functions which is not great for a stack-based 8-bit computer.

The problem with any try I done so far is to tell the computer not to mess up the numbers already in place, and sometimes you need to mess up to get better result later. So its not a simple task, maybe anoter was is to search any possible move, in depth of 4-5 moves and compare which is the best one and pick that track. Hmmmm not sure what is best here..

I have been searching for 80s programlistings, but found none, to solve the problem, I would assume some C64/Amstrad/Spectrum version was created in the 80s, but maybe it was to complex.

[Bill B]

I have coded a prototype version of the 'human' algorithm.

For me it was easiest to do this in Python, and enabled me to identify and solve the edge cases. Hopefully I have found them all.

Having got this to work I should not find it too difficult to translate into MTX BASIC.

If anyone is interested, my Python version is attached. Keep pressing the <Enter> key to step through the solution process.

[Bill B]

MTX version of the Fifteen Puzzle solver attached. Run the program and keep on pressing the space bar to step through the solution. Hopefully I have got all the typos out.

It used the 'human' algorithm, which is almost certainly not the most efficient in terms of number of moves, but does not require any deep searching.

The implementation in BASIC is a bit slow, but not too bad except perhaps for the initial board setup. It would not be too difficult to do in machine code, but I was too lazy to invent a method of picking a random number seed.

Just out of interest, why do you want a solver? You don't need one to check that a problem is solvable. To do that you just need to check the parity, see lines 1110-1220 in the listing.

[Crazyboss]

Hi Bill

Thanks, great work, i will take a look at the code, I already tried it it works quite good, and not to slow even in Basic.

If you allow me I will continue the project for a Finished game later I have been thinking about that for some time, and actually started the project using Intellivision Basic I got to the point where I saw it could be nice to have a solver, so if the player want a bit help its possible.

About using assembler, I always just use the refresh register, like LD A,R - its random enought I guess, lot of games use this too. I think it returns a 7bit value, I recall Andy Key and me found a bug in Memu (cause it returned a 8bit value), I guess i found out cause when I ported Telebunny over to the Memotech, some strange things happened, like place fruits/hearts etc outside the Maze. Andy have corrected that bug long time ago

So the plan is to release Memotech (Maybe a ColecoVision version too), and also a Intellivision version, if possible. Lets see first I have to understand your code. I plan that those games would have 2x2,3x3 and 4x4 puzzles even 2x2 is not that of a challenge

I assume your code know how to skip steps, e.g if a number is already placed where it should be. E.G if 1,2,3,4 already is there from the start.

[Bill B]

As to skipping steps yes and no. There are routines to move a tile to a given row or column. These will get called for every tile, but if the tile is already in the correct position they will not have anything to do, and will return immediately.

When trying to understand the code, you might find it useful to look at my earlier Python code. The BASIC very closely follows the Python (I could not have written the BASIC without the Python). Python is not that difficult to read, and "self.TileLeft" is a little easier to understand than "GOSUB 6000".

For providing a hint to a user (e.g. placing the next tile) the fact that it uses the 'human' algorithm is probably better than the more efficient but less obvious solutions found by optimising solvers.