• Alex Papadimoulis (cs)

    While I'm sure I would fail CS101 with this code, this solves in miliseconds on my machine (takes a few hundred thousand iterations, though).

    static int[] solvePuzzle(int[] puzzleNumbers)
        {
            Random rand = new Random();
    
            while (true)
            {
                // Solved Yet?
                bool solved = true;
                for (int i = 0; i < puzzleNumbers.Length; i++)
                    if (puzzleNumbers[i] != i && puzzleNumbers[i] > 0) return false;
                if (solved) break;
    
                // Find the Empty Square
                int emptyIdx = 0; 
                for (int i = 0; i < puzzleNumbers.Length; i++) 
                    if (puzzleNumbers[i] < 0) emptyIdx = i;
    
                // Determine Possible Moves (there is probably a formula for this)
                int[] avaiableMoves =
                    emptyIdx == 0 ? new int[] { 1, 3 } :
                    emptyIdx == 1 ? new int[] { 0, 2, 4 } :
                    emptyIdx == 2 ? new int[] { 1, 5 } :
                    emptyIdx == 3 ? new int[] { 0, 4, 6 } :
                    emptyIdx == 4 ? new int[] { 1, 3, 5, 7 } :
                    emptyIdx == 5 ? new int[] { 2, 4, 8} :
                    emptyIdx == 6 ? new int[] { 3, 7 } :
                    emptyIdx == 7 ? new int[] { 4, 6, 8 } :
                    emptyIdx == 8 ? new int[] { 5, 7 } :
                    new int[0];
    
                // Pick one Move at random
                int swapIdx = avaiableMoves[rand.Next(0, avaiableMoves.Length)];
    
                // Make The Move (at least I know how to XOR)
                puzzleNumbers[swapIdx] = puzzleNumbers[swapIdx] ^ puzzleNumbers[emptyIdx];
                puzzleNumbers[emptyIdx] = puzzleNumbers[swapIdx] ^ puzzleNumbers[emptyIdx];
                puzzleNumbers[swapIdx] = puzzleNumbers[swapIdx] ^ puzzleNumbers[emptyIdx];
            }
    
            return puzzleNumbers;
        }
    
  • ajw (unregistered)

    If I remember correctly, half of the possible configurations are unsolvable. The original sliding puzzle was an unsolvable 4x4, which sparked a worldwide craze for trying to solve it before people finally caught on.

  • Meh (unregistered)

    How about...

    function ItsLikeMagic( $input ) { return '12345678 '; }

    That seems to match perfectly the requested output, for any input :)

  • some guy (unregistered)

    OBLIGITORY OPTIMIZED SOLUTION

    public String solve(String in) { return "12345678 "; }

  • Kalle (unregistered)

    This fulfills the requirements, partial Java.

    public int[] solve( int[] original state ) { return new int[] { 1,2,3,4,5,6,7,8,0 }; }

  • dmas (unregistered)
    Comment held for moderation.
  • Anonymous (unregistered)

    In my AI class we had to solve this. The professor gave us a starting position. We also had to demo our code to the class.

    One clever student was called on. He walked up to the front and loaded his application onto the instructor workstation. He ran the code, it printed out a list of moves to build a solution. The teacher then asked him to show the code.

    It was something like this:

    public static void main(String[] argv)
    {
         System.out.println("Move 3 to position 6");
         System.out.println("Move 2 to position 3");
         ...
    }
    

    The student tried to argue that the program technically solved the problem, but the teacher told him he was completely missing the point of the class and gave the assignment an F.

    You may be thinking that the student was just trying to prove a point or something, but judging from other classes he was in, he just couldn't code and probably couldn't figure it out. He was probably expecting the professor to run it without checking the source code.

  • Carl (unregistered) in reply to ajw
    Comment held for moderation.
  • Anonymous (unregistered) in reply to Carl
    Carl:
    I just to annoy my older brother by removing and swapping two tiles from my 15 puzzle and watching him struggle...

    You accidentally a word here.

  • pitchingchris (cs) in reply to Anonymous
    Anonymous:
    In my AI class we had to solve this. The professor gave us a starting position. We also had to demo our code to the class.

    One clever student was called on...

    A clever student would have expected an F if he didn't actually code the solution. Trying to take shortcuts in life always comes back on you.

  • ullamcorper (unregistered)

    For what it's worth, finding the fewest-move solution to the general NxN problem is NP-complete. That means that, even if it's not a new problem, anyone who can solve DIFFICULT and whose code generalizes to beyond 3x3 should immediately:

    1. Patent algorithm.
    2. Profit!
  • Anonymous (unregistered) in reply to pitchingchris
    pitchingchris:
    Anonymous:
    In my AI class we had to solve this. The professor gave us a starting position. We also had to demo our code to the class.

    One clever student was called on...

    A clever student would have expected an F if he didn't actually code the solution. Trying to take shortcuts in life always comes back on you.

    Yeah, I think that was the point. 'Clever' being used sarcastically.

  • AMiller (unregistered) in reply to pitchingchris
    pitchingchris:
    Anonymous:
    In my AI class we had to solve this. The professor gave us a starting position. We also had to demo our code to the class.

    One clever student was called on...

    A clever student would have expected an F if he didn't actually code the solution. Trying to take shortcuts in life always comes back on you.

    Or it gets you promoted.

    :)

  • ullamcorper (unregistered) in reply to ullamcorper
    ullamcorper:
    anyone who can solve DIFFICULT and whose code generalizes

    solve efficiently. solve efficiently. that's important.

  • seconddevil (cs)
    /* Solves the puzzle in the fastest possible time *
     * Its even written in C to make it fasterest     */
    #include <stdio.h>
    #include <stdlib.h>
    int main(char argc, char**argv){
        printf("+---+---+---+\n"
               "| 1 | 2 | 3 |\n"
               "+---+---+---+\n"
               "| 4 | 5 | 6 |\n"
               "+---+---+---+\n"
               "| 7 | 8 |   |\n"
               "+---+---+---+\n");
        return 0;
    }
    
  • Kris (unregistered)

    How many almost-identical versions of the "12345678" "solution" are we going to see before people realise it's not that funny?

  • Anguirel (cs) in reply to seconddevil

    Most of the solutions posted so far remind me of when I was much younger and tried to solve a Rubik's cube. I got frustrated with it: half twist, pop reassemble, done.

    I'll try solving the problem later when I get some more free time.

  • Atticus (cs)

    RE: All the folks posting stuff like return "12345678"

    That's very clever, but you forgot to read the end of the text: "and your function should be able to process any series of nine numbers."

  • seconddevil (cs) in reply to Atticus
    Atticus:
    RE: All the folks posting stuff like return "12345678"

    That's very clever, but you forgot to read the end of the text: "and your function should be able to process any series of nine numbers."

    in that case...

    perl -le 'print join ",", sort @ARGV"
    
  • Dotan Cohen (unregistered)

    The input should be a series of nine numbers (string, integer array, etc) that represent the eight pieces and the empty square.

    The output should be a series of numbers that represent a solved puzzle.

    <html><body><form action="page.php"><input type="text" name="in"><input type="submit"></form></body></html> <?php print "<html><body>123
    456
    78*
    </body></html>"; ?>

    It works great!

  • mbvlist (cs) in reply to ullamcorper
    ullamcorper:
    For what it's worth, finding the fewest-move solution to the general NxN problem is NP-complete. That means that, even if it's not a new problem, anyone who can solve DIFFICULT and whose code generalizes to beyond 3x3 should immediately: 1. Patent algorithm. 3. Profit!
    You're wrong: the way the assignment is given it allows brute-forcing all options until you found the shortest list of transformations. With only 3^2 positions that should be done pretty fast. And otherwise you use the A* algorithm to shorten the time.
  • bjolling (cs) in reply to seconddevil
    seconddevil:
    Atticus:
    RE: All the folks posting stuff like return "12345678"

    That's very clever, but you forgot to read the end of the text: "and your function should be able to process any series of nine numbers."

    in that case...

    perl -le 'print join ",", sort @ARGV"
    
    That's very clever, but you forgot to read the 3rd requirement: "The sort logic should follow the sliding puzzle rules"
  • ullamcorper (unregistered) in reply to mbvlist

    key phrase: "generalizes to beyond 3x3"

    Even using an A* algorithm on the NxN doesn't remove the NP-completeness. Shall I find a citation?

  • NSCoder (cs) in reply to seconddevil
    seconddevil:
    Atticus:
    RE: All the folks posting stuff like return "12345678"

    That's very clever, but you forgot to read the end of the text: "and your function should be able to process any series of nine numbers."

    in that case...

    perl -le 'print join ",", sort @ARGV"
    

    Apparently you also didn't read 'The sort logic should follow the sliding puzzle rules'.

  • Mike (unregistered)

    These are fun, but WTF is up with the lack of a WTF whenever these are posted? I can go to project euler or codechef for stuff like this.

    I want my WTFs.

  • lolwtf (cs)

    char s[10]; while(strcmp(s, "1234567890")) for(int i=0; i<10; i++) s[i] = (rand() % 10) + '0'; printf("%s\n", s);

    Pardon the lack of indentation.

    Post attempt 3 is this ever going to be fixed? TRWTF is TDWTF.

  • zre (unregistered) in reply to Mike
    Mike:
    I want my WTFs.

    Create them yourself! Just get hired by a small shabby business and make some horrible code for some poor soul to put on this site...

  • Oxyd (unregistered)

    We had this as homework in the first semester at my Uni. I've still got the solution that finds the shortest possible sequence of moves or concludes the original configuration is unsolvable. I've still got the code around here somewhere -- but it's a few hundred lines of Pascal and it only works for 3x3 grids.

  • CaptainSmartass (cs) in reply to Anonymous
    Anonymous:
    In my AI class we had to solve this. The professor gave us a starting position. We also had to demo our code to the class.

    One clever student was called on. He walked up to the front and loaded his application onto the instructor workstation. He ran the code, it printed out a list of moves to build a solution. The teacher then asked him to show the code.

    It was something like this:

    public static void main(String[] argv)
    {
         System.out.println("Move 3 to position 6");
         System.out.println("Move 2 to position 3");
         ...
    }
    

    The student tried to argue that the program technically solved the problem, but the teacher told him he was completely missing the point of the class and gave the assignment an F.

    You may be thinking that the student was just trying to prove a point or something, but judging from other classes he was in, he just couldn't code and probably couldn't figure it out. He was probably expecting the professor to run it without checking the source code.

    Sounds like he should've switched majors from CS to prelaw.

  • Adam V (unregistered)

    Maybe we could stop the idiots posting "12345678" by changing the second rule from:

    The output should be a series of numbers that represent a solved puzzle.

    to

    The output should be a series of numbers that represent the moves necessary to create a solved puzzle.

    Considering that the pieces are uniquely identifiable, it's not hard to determine whether the solution is AFU.

  • Daniel Cousineau (unregistered)
    Comment held for moderation.
  • Anon (unregistered)

    What is that horrible language the OP has posted? Looks a bit like Java, but isn't. C# maybe?

  • Everett (unregistered) in reply to Daniel Cousineau

    Reading lisp always makes me feel like someone kicked me in the back of the head.

  • amischiefr (cs) in reply to zre
    zre:
    Mike:
    I want my WTFs.

    Create them yourself! Just get hired by a small shabby business and make some horrible code for some poor soul to put on this site...

    What makes you think he isn't doing that right now?

  • whereiseljefe (cs) in reply to Daniel Cousineau

    Meh, naturally I post without logging in, ooooh well

  • SR (unregistered) in reply to Mike
    Mike:
    I want my WTFs.

    These coding challenge things produce herds* of WTFs.

    Like this:

    Oxyd:
    Pascal

    :o)

    • what is the collective noun for WTFs? I'll open the bidding with a PHB of WTFs.
  • whereiseljefe (cs) in reply to Daniel Cousineau
    Yeah, we did this recently in my AI class.

    And looking through the timestamps in my old assignments, by recently I mean almost exactly a year ago...

  • SenTree (cs) in reply to SR
    SR:
    * what is the collective noun for WTFs? I'll open the bidding with a PHB of WTFs.
    ...but surely you could also have a WTF of PHBs. Is this the first example of a symmetric collective noun?
  • DrSolar (unregistered) in reply to SR
    SR:
    what is the collective noun for WTFs? I'll open the bidding with a PHB of WTFs.

    I'll go with a horror or a plummet. I'm trying to get a word that get's across that dolly-zoom feeling when you realise what's happening. Any ideas?

  • Chuck (unregistered)

    I vote we hunt Daniel Cousineau down and string him up by his balls ;)

  • by (unregistered) (unregistered)
    As far as I'm aware, there are no impossible starting configurations and your function should be able to process any series of nine numbers.
    Right... if you have nine numbers, how do you slide them? You need eight numbers plus an empty square.
  • Chuck (unregistered) in reply to DrSolar
    DrSolar:
    SR:
    what is the collective noun for WTFs? I'll open the bidding with a PHB of WTFs.

    I'll go with a horror or a plummet. I'm trying to get a word that get's across that dolly-zoom feeling when you realise what's happening. Any ideas?

    I like "plummet" :)

    I was thinking along the lines of "palpitation" - trying to capture the 'feeling' of that crushing realization that something is horribly wrong.

  • Chuck (unregistered)

    Maybe "suicide" would be apt.

    A murder of crows

    A suicide of WTFs

  • Anon (unregistered)

    Apparently nobody can tell what the OP's language is. I'd really like to know, so that I can avoid it in my professional life.

  • Bim Job (unregistered) in reply to mbvlist
    mbvlist:
    ullamcorper:
    For what it's worth, finding the fewest-move solution to the general NxN problem is NP-complete. That means that, even if it's not a new problem, anyone who can solve DIFFICULT and whose code generalizes to beyond 3x3 should immediately: 1. Patent algorithm. 3. Profit!
    You're wrong: the way the assignment is given it allows brute-forcing all options until you found the shortest list of transformations. With only 3^2 positions that should be done pretty fast. And otherwise you use the A* algorithm to shorten the time.
    See, the thing about NP-complete problems is that they admit of brute-force solutions ... up to a problem size of about ten or twenty.

    And the other thing about NP-complete problems is that brute-force suddenly hits brick wall and stops working for a small increment of the problem size.

    And the other, other thing about any problem at all is that you should read the rubric: in this case, "For what it's worth, finding the fewest-move solution to the general NxN problem is NP-complete."

    I think I'm going to stop worrying about whether C++ or VB or Whitespace is the silver bullet for my next project, and just fire anybody who clearly fails to read the requirements. Perhaps this is the silver bullet. It certainly happens often enough in real life.

    Anonymous:
    In my AI class we had to solve this. The professor gave us a starting position. We also had to demo our code to the class.

    One clever student was called on. He walked up to the front and loaded his application onto the instructor workstation. He ran the code, it printed out a list of moves to build a solution. The teacher then asked him to show the code.

    It was something like this:

    public static void main(String[] argv)
    {
         System.out.println("Move 3 to position 6");
         System.out.println("Move 2 to position 3");
         ...
    }
    

    The student tried to argue that the program technically solved the problem, but the teacher told him he was completely missing the point of the class and gave the assignment an F.

    It's not helped by pointy-headed professors, either. Given the requirement ("the professor gave us a starting position"), this code is an A, not an F.

    It's not up to the student to work out what the point of the assignment is. It's up to the "professor" to make it clear.

  • katre (unregistered)

    Here we go, shell script version:

    echo "12345678 "

    Oh, you wanted the moves it takes?

  • immitto (unregistered) in reply to DrSolar
    DrSolar:
    SR:
    what is the collective noun for WTFs? I'll open the bidding with a PHB of WTFs.

    I'll go with a horror or a plummet. I'm trying to get a word that get's across that dolly-zoom feeling when you realize what's happening. Any ideas?

    I vote for a murder of WTFs, in the same spirit as a murder of crows. Because, with lots and lots of WTFs you are in essence murdering the code. (Kindof akin to creating a zombie. Your creation hobbles along, sure, but... yeah...)

  • Maurits (cs) in reply to immitto
    immitto:
    DrSolar:
    SR:
    a PHB of WTFs.

    I'll go with a horror or a plummet

    a murder of WTFs

    A spaghetti of WTFs

  • ullamcorper (unregistered)

    Bib Job: Thanks, you rock, and read my mind. Reading the requirements probably is the silver bullet. Of course, then, I wouldn't have any coworkers.

    I vote for "plummet" of WTFs, and the person who said "dolly-sliding" gets undying adoration.

  • Bri (unregistered)

    If I recall correctly, 123/456/87_ is an impossible starting configuration.

Leave a comment on “Sliding Around”

Log In or post as a guest

Replying to comment #:

« Return to Article