Unsolvable 15pieces

[dszimmerman]

From the start of a new game the initialized state is not able to be solved. Closest solution has 14 & 15 swapped. Other close solutions have similar lateral swap. After a "restart desklet" from this almost solution, it results in a solvable layout.

Tags from the source:
  <meta author="Robert Pastierovic, Bjoern Koch"
        version="0.6"
        category="Fun/Amusements"
        name="15pieces"
        description="15 pieces puzzle game."
        dependency="0.36.1"
        preview="Numbers/15.png"/>

[dszimmerman (zimmerman-ds)]

I looks as if the solvablity is random after initialization. Take a look at the attached.

[Joe Sapp (sappj)]

It looks as if you've analyzed this pretty well. Could you try to put it into code? It will probably get resolved faster that way and you seem to have a good understanding of the algorithm needed to fix it.

[dszimmerman (zimmerman-ds)]

I'd like to. Never programmed in Python. I've downloaded SPE, have no idea what other people use or best practices.. have placed a copy of gdesklets into a local projects folder.. fired things up. Resolved a broken relative link to a png file in the "shared" folder and the local version of gDesklets starts up (with just a warning..

/home/dave/projects/gdesklets/utils/ErrorFormatter.py:118: DeprecationWarning: the md5 module is deprecated; use hashlib instead
module = _old_imp(*args, **kwargs)

Okay, now I can do some damage. Can't yet find setting breakpoints, stepping, variable expression.. The algorithmic expression in Python will be fun, once I learn enough. I tried to let my description, and the thought behind it, be one step removed from pseudocode.

If you think I can learn Python, the desklet architecture, and the tools faster than someone already familiar with the aforementioned can understand what I wrote.. then I reeeeally suck at writing!! Ha! Okay. I'm game.

If my setup sounds good, I'll fumble toward epiphany. Otherwise, give me a couple of pointers/links to set my feet down the path.

Thanks, Dave.

[Bjoern Koch (h.humpel)]

Wow! Great! Thanks for all the input.

Shame on me... I have to admit I pulled in this bugs when changing the order to be random.
Before that the order has always been the same (hard-coded) and I thought it might be better to be randomized (that's why I wrote the IRamdom Control). Sad but true: I have never been thinking about if it would still be solvable or not :/. And I must have been lucky to have played solvable puzzles when testing... again: shame on me :(.

Anyway, as it looks like you have all the needed code already made up in your mind it would be nice (and much faster) if you could help out here ;).

[Bjoern Koch (h.humpel)]

If it can be fixed sooner than later we should have it fixed in 0.36.2, too.

[Bjoern Koch (h.humpel)]

Maybe there is some kind of algorithm to find out if the random distribution is solvable or not ?
This might be easier than building your own (ARS) random function.
Maybe this here helps ?! http://en.wikipedia.org/wiki/Fifteen_puzzle#Solvability

[dszimmerman (zimmerman-ds)]

Thanks Bjoern for your response! It's all good. It's just that puzzle has a nice place in my memory. ;-)

What environment do you use while coding? Just the shell? ActivePython looks interesting, but I don't want to be locked into a proprietary solution. I'd be happy to help, just as I'd like to look over your experienced work to help me transition into the language and to ramp up as quickly as possible.

[Bjoern Koch (h.humpel)]

Hi again,

it looks like it is quite simple to see if a puzzle can be solved or not (German only):

http://www.mathematische-basteleien.de/15erspiel.htm#Etwas%20Mathematik

As far as I can tell all we have to do is count the number of inversions and see if this number is even or odd ?!
This would be very easy to put into code... it would just take "a little while" to be calculated for 15 pieces ;).

Still thinking about it...

[dszimmerman (zimmerman-ds)]

If that's the case, Awesome! Let greater minds prevail!
<chagrin> I should have done some searching before posting.. my bad!

On a different note, is there a reason that the 16th position should always be the empty one after initialization?

[Bjoern Koch (h.humpel)]

Well, first we should check if this is a solution to the problem
It's been a long time since I had to deal with things like thisand I am quite not sure if it really is that simple ;).

About the empty piece on start up.... I am not sure about it eitrher. I don't see any reasons why it has to be on the 16th position on start up, but I haven't been thinking about this, too ;).
But if it is NOT on the 16th position we will have to treat it as a 16th piece in the calculation, right?

[dszimmerman (zimmerman-ds)]

I took a look at the site, had google translate it, and it looks good at first pass (see attached). As far as the empty spot, I think a value of zero would for the inversion method you pointed to with the link.

[dszimmerman (zimmerman-ds)]

Opps, put that "zero in the empty spot" thought on hold.

However, Using the 2x2 model show at the link towards counting the inversions in the 4x4 seems to work.

just cat row1 row2 row3 row4 into a result array, (may not be needed in Python.. depending on implementation)
use two indexes into the result, i & j, compare i & j as j is incremented up the result
  and increment a inversionCounter if (value at i) > (value at j)
 when j reaches the end increment i and set j back equal to i+1

[Joe Sapp (sappj)]

To set up a programming environment, it's actually a bit simpler than what you've done. You just have to use your favorite editor to tweak the 15pieces.display (probably in "/usr/lib/gdesklets/Displays/15pieces"); it's a combination of XML and Python. `gdesklets restart` after each change (assuming you have the display open) and you're hacking :)

[Robert Kubík (Pastierovič) (just-me)]

Hi all,

another method would be just to shuffle the pieces randomly starting
from the already solved puzzle. This is the method I was thinking to
implement before Bjoern came up with the randomizer :)
But inversions method looks like a better challenge, so don't let be
discouraged ;-)

Regards,

Robo

[dszimmerman (zimmerman-ds)]

It is great to see responsiveness like this. Please pardon me if I seem slow in the uptake on some things, technically or collaboratively. I fear some of my comments may veer off-topic; I'll look for a better home for these.

@#15
Hi Robo, I like the random shuffle idea too; just take a look at page two of my attachment in post #2 for my take on it. Highlights would be: the empty space must hit all locations at least once; purely random movement of the empty space won't insure mixing; a couple of methods to randomly apply that will mix it up okay. The inversion method was a cool insight though.

@#14
Thanks Joe. My reason for not editing the files off of "/usr/lib/.." were twofold -- (1) root ownership and (2) doing a poor-man's RCS, a quick and dirty way to exercise the source without worrying about changing my copy of the main line. As far as the working environment, I've been used to looking at registers and variables as I step through code and setting break points. I'd be interested in doing so while learning Python.. if it's possible. Maybe it's built into the native interpreter, I don't know. Is what you suggested I do what you do? I've downloaded some tools for evaluation. I don't have a favorite code editor yet.

How about the rest of you? What are your top tools that you use day in day out to get/put, edit and test your Python code?
 -- vim, gedit, emacs, activeedit, winpdb, codeblocks, netbeans, eclipse.. pros and cons.. whatever you'd like to share.

 I guess I'll have to put further questions like this in a different thread.. not sure where yet...

[Joe Sapp (sappj)]

If you want to do your poor-man's RCS, copy the 15pieces directory somewhere (i.e. ~/.gdesklets/Displays) and edit those files directly. You will have to make sure to open that copy of the desklet though. For example:
-Copy the 15pieces dir to ~/.gdesklets/Displays
-Switch to a new profile with `gdesklets profile test`
-Open the new copy of the desklet with `gdesklets open ~/.gdesklets/Displays/15pieces/15pieces.display`
-Edit ~/.gdesklets/Displays/15pieces/15pieces.display
-When you want to test your changes, restart gdesklets with `gdesklets restart`

The difficulty with developing desklets is that, mainly since they run in a sandbox, you will have a very difficult time debugging them with a debugger. Breakpoints, stepping through code, etc. is very tricky at best. It works best (for me, at least) to use 'print' statements and check ~/.gdesklets/logs/*.log .

[Bjoern Koch (h.humpel)]

OK, just found some time to play around with the 15 pieces desklet. An updated version (0.8_beta2) can be found in the "desklets-basic" branch at rev. #55.

Please be aware that this version produces a lot of "debugging output" in the logfile and is for investigating this problem and testing purposes only !
Furthermore I have changed the name of the free tile from "free.png" to "0.png" for further work on the display file like e.g. simplifying check_layout(). Now the free tile can be anywhere on startup.

So, I have added the calculation of the inversions to the display file. The value will be displayed on top of the puzzle.
Strange thing: when moving the free tile vertically the number of inversions changes from even to odd (or odd to even). As far as I understood the website mentioned in comment #9 this shouldn't (should never) happen.
Maybe I made an error when integrating the free tile ?!
But everything looks fine if you take a look at the output in the logfile.

Any ideas ???

[Bjoern Koch (h.humpel)]

Ahhh... OK, I forgot to add the number of the row of the empty tile to the inversions .. :(.
So, now it seems to work.
Just feel free to play a bit with the updated version (0.8_beta3) in rev. #56 to see if this is a way to find out if the puzzle can be solved or not. So far it looks very promissing.

[Bjoern Koch (h.humpel)]

Fixed in v0.8 of 15 pieces puzzle.
Released with gDesklets 0.36.2.