1. Welcome to TechPowerUp Forums, Guest! Please check out our forum guidelines for info related to our community.

N-Puzzle Solvability

Discussion in 'Programming & Webmastering' started by Jizzler, Nov 9, 2012.

  1. Jizzler

    Jizzler

    Joined:
    Aug 10, 2007
    Messages:
    3,404 (1.33/day)
    Thanks Received:
    635
    Location:
    Geneva, FL, USA
    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:
    $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 );

    //use validated range for board
  2. Kreij

    Kreij Senior Monkey Moderator Staff Member

    Joined:
    Feb 6, 2007
    Messages:
    13,881 (5.04/day)
    Thanks Received:
    5,615
    Location:
    Cheeseland (Wisconsin, USA)
    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.
  3. FordGT90Concept

    FordGT90Concept "I go fast!1!11!1!"

    Joined:
    Oct 13, 2008
    Messages:
    13,415 (6.27/day)
    Thanks Received:
    3,394
    Location:
    IA, USA
    Could try $permutations % 2 instead. It would return 0 on even, something else on everything else.
    Crunching for Team TPU
  4. Jizzler

    Jizzler

    Joined:
    Aug 10, 2007
    Messages:
    3,404 (1.33/day)
    Thanks Received:
    635
    Location:
    Geneva, FL, USA
    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.
  5. Kreij

    Kreij Senior Monkey Moderator Staff Member

    Joined:
    Feb 6, 2007
    Messages:
    13,881 (5.04/day)
    Thanks Received:
    5,615
    Location:
    Cheeseland (Wisconsin, USA)
    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. :toast:
  6. Jizzler

    Jizzler

    Joined:
    Aug 10, 2007
    Messages:
    3,404 (1.33/day)
    Thanks Received:
    635
    Location:
    Geneva, FL, USA
    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).

    [​IMG]
    (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.

    Attached Files:

    Last edited: Nov 10, 2012
  7. Kreij

    Kreij Senior Monkey Moderator Staff Member

    Joined:
    Feb 6, 2007
    Messages:
    13,881 (5.04/day)
    Thanks Received:
    5,615
    Location:
    Cheeseland (Wisconsin, USA)
    How's this going, Jizz?
    What you are doing is really interesting (although crazily inefficient :D).
  8. Jizzler

    Jizzler

    Joined:
    Aug 10, 2007
    Messages:
    3,404 (1.33/day)
    Thanks Received:
    635
    Location:
    Geneva, FL, USA
    Didn't have much time to look it over yesterday, but did alter it to be able to loop X number of times.

    Code:
    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! :laugh:

    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.
  9. Jizzler

    Jizzler

    Joined:
    Aug 10, 2007
    Messages:
    3,404 (1.33/day)
    Thanks Received:
    635
    Location:
    Geneva, FL, USA
    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.

    Code:
    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.
  10. Jizzler

    Jizzler

    Joined:
    Aug 10, 2007
    Messages:
    3,404 (1.33/day)
    Thanks Received:
    635
    Location:
    Geneva, FL, USA
    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:

    Code:
    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.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guest)

Share This Page