N-Puzzle Solvability

[Jizzler]

With all the talk about n-puzzle, I wanted to start playing around with a PHP implementation. I've gotten a solver in place, but it only solves it some of the time. Want to get my validator looked at to see if I understood the parity calculation correctly. If it looks sound, then I know the problem is later in the code.

- I'm using explanation given here about how to calculate parity.

- "total" is considered the space square.

- While permutations parity is odd, reshuffle the order until even parity is achieved.

- Loop through the range and for each square, test if value is greater than value of squares further in the sequence. If so, increment the counter.

PHP Code:

$tall = 3;
$wide = 3;

$total = $tall * $wide;

$range = range(1, $total);

do {

    shuffle($range);

    $permutations = 0;
    for ( $i = 0; $i < ($total - 1); ++$i ) {
        for ( $j = ($i + 1); $j < $total; ++$j ) {
            if ( $range[$i] > $range[$j] ) {
                ++$permutations;
            }
        }
    }

} while ( $permutations & 1 );

//use validated range for board 


[Kreij]

The validator looks sound to me.
It should never exit the do loop when the value of $permutations is odd.

Disclaimer : I could be wrong.

[FordGT90Concept]

Could try $permutations % 2 instead. It would return 0 on even, something else on everything else.

[Jizzler]

Good disclaimer Kriej

So far the numbers it comes up with are even {10, 12, 14, ...} so from that perspective it works.

Expanding on my method, I wanted to do n-puzzle the worst way possible: random moves. AKA give the puzzle to a monkey (a monkey that can do ~300,000 moves/second). When they do get solved, it's always between .5 and 2 seconds. Otherwise, the script can run for 10 minutes and not get an answer. I suppose it's possible when talking about randomness, but I should be getting times in between 2 seconds and 10 minutes, right?

OH... to narrow down the problem, I could try validating the board after every move to make sure it's still solvable.

(10 minutes later)

Hmm, still getting "solves" in a short period of time or not at all. I'll give the code a look-over in the morning.

[Kreij]

If the state of the board begins in a solvable manner, random movement should not produce an unsolvable result. You may have to backtrack on the moves, but it should always be solvable.
After you start to solve the puzzle from a solvable solution, what determines (or stops) the code from completing it? If you are using the same criteria as a starting state (the validity test), and not considering that the puzzle could be backtracked, then I suppose it is possible the program would determine that it was impossible.

Interesting take on it, Jizzler.

[Jizzler]

Right, just wanted to make sure that my code was handling the movements correctly. It seems to be doing that. I've outputted samples and watched it shift values. That, and the validator seems to agree that no incorrect movements are happening (at least no moves that would make the board unsolvable).


(Click: y, x)

In in each loop it's randomly choosing one of the four possible squares to "click" then shifting the number(s) from that point towards the space.

The goal state is reached when the board is in order, starting with 1 in the top-left corner and 9(space) in the bottom-right.

[Kreij]

How's this going, Jizz?
What you are doing is really interesting (although crazily inefficient ).

[Jizzler]

Didn't have much time to look it over yesterday, but did alter it to be able to loop X number of times.

C:\php>php puzzle.php 20
Time: 0.394s    Moves: 83998
Time: 1.102s    Moves: 236531
Time: 60.000s   Moves: 12626534
Time: 60.000s   Moves: 12811238
Time: 1.034s    Moves: 215050
Time: 60.000s   Moves: 12276046
Time: 60.000s   Moves: 12754828
Time: 2.386s    Moves: 510520
Time: 1.234s    Moves: 263973
Time: 60.000s   Moves: 12806750
Time: 0.346s    Moves: 73623
Time: 1.000s    Moves: 210736
Time: 60.000s   Moves: 12830742
Time: 1.515s    Moves: 325494
Time: 60.000s   Moves: 12602517
Time: 60.000s   Moves: 12329020
Time: 60.000s   Moves: 12433728
Time: 60.000s   Moves: 12634548
Time: 1.552s    Moves: 332954

Uh huh... timed out 10 of 20 runs, and half of all sequences are unsolvable. There might be something to that!

Either the parity calculation I linked to was wrong or I implemented it incorrectly. Either way, going to look for another way to do it. Definitely need that working before going on to 4x4 or greater sized puzzles.

[Jizzler]

Those parity calculations and other methods were just too fancy for such a random brute force approach to n-puzzle. Changed it up so that it starts from the goal state and runs 10,000 moves before it is allowed to break loop when it reaches the goal state again.

C:\php>php puzzle.php 5 3 3
Time: 1.063s    Moves: 197761
Time: 3.327s    Moves: 617154
Time: 3.246s    Moves: 589875
Time: 1.562s    Moves: 290963
Time: 1.308s    Moves: 243138

C:\php>php puzzle.php 5 3 4
Time: 631.760s  Moves: 107567139
Time: 3004.540s Moves: 501030478

(var order is loops/height/width)

Nice. Time to run this on my desktop when I get home. Faster than this laptop and can run puzzles 3x4, 4x4, 4x5, and 5x5 simultaneously.

[Jizzler]

While I could have continued to optimize my script, there's no way I could have it match a compiled program. So I wrote it up C++ style:

Projects\Puzzle\Release>Puzzle.exe 10 3 4
L1: 31.201s,	Moves: 431331490
L2: 22.865s,	Moves: 313645354
L3: 54.819s,	Moves: 751440362
L4: 7.02s,	Moves: 99313507
L5: 2.73s,	Moves: 38240275
L6: 38.14s,	Moves: 523117195
L7: 8.424s,	Moves: 115969315
L8: 4.695s,	Moves: 64458998
L9: 10.483s,	Moves: 146073973
L10: 53.599s,	Moves: 753855436

At an average of 13.8M moves/second, that's one fast monkey! I have him busily working on a 4x4 puzzle now.

Next up, have the program spawn multiple monkey processes and if possible, make them semi-intelligent. Ideally it would involve them learning number order, and learning from each other. The time each one takes to solve the puzzle should go down as the numbers of monkeys increase.