• (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)

    Not all possibilities are solvable:

    http://en.wikipedia.org/wiki/Fifteen_puzzle#Solvability

  • 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

    "If I remember correctly, half of the possible configurations are unsolvable."

    Yes. Loosely speaking: if the puzzle order can be created from the original order with an even number of tile swaps, it is solvable; an odd number of swaps it is not. Rigorously speaking: http://mathworld.wolfram.com/15Puzzle.html

    I just to annoy my older brother by removing and swapping two tiles from my 15 puzzle and watching him struggle...

  • 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.

  • (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.

  • (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?

  • (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.

  • (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."

  • (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!

  • (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.
  • (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?

  • (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.

  • (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.

  • (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)

    Yeah, we did this recently in my AI class. I had a lot of fun with it, we did it using lisp.

    We implemented different algorithms/techniques (though our final state was 1 2 3 | 8 0 4 | 7 6 5, in order clockwise, with blank in the middle).

    It's been some time, I remember loving this project but don't remember exactly everything about the code structure (I do remember the algorithmic approaches though).

    BFS:

    (load "eight-util.lisp")

;(append list node)

(defun bfs (start)
  (let* ((queue (list (list start '0 '0 '()))))
    (do ((i 0 (+ i 1))) (nil)
      (setq current-node (first queue))
      (if (goalp current-node)
	(return (fourth current-node))
	(let ()
	  (setq queue (append (rest queue) (expand current-node))))))))

    DLS:

    (load "eight-util.lisp")

(defun dls (start &optional (limit 10))
  (recursive-dls (list start 0 0 nil) limit))

(defun recursive-dls (node limit)
  (if (goalp node)
    (return-from recursive-dls (fourth node))
    (if (= (third node) limit)
      (return-from recursive-dls nil)
      (dolist (newnode (expand node))
	(setq response (recursive-dls newnode limit))
	(if (not (eq response nil))
	  (return-from recursive-dls response))))))

    GREEDY:

    (load "eight-util.lisp")

(setq *heuristic-func* 'out-of-place)

(defun greedy (start)
  (let* ((node (list start 0 0 nil)))
    (do ((i 0 (+ i 1))) (nil)
      (if (goalp node)
	(return (fourth node))
	(setq node (first (expand node)))))))

    IDS:

    (load "dls.lisp")

(defun ids (start &optional (limit 20))
  (do ((i 1 (+ i 1))) ((= i limit))
    (setq result (dls start i))
    (if (not (eq result nil))
      (return result))))

    IDA*:

    (load "a-star.lisp")

(defun ida-star (start &optional (depth 20))
  (do ((i 0 (+ i 1))) ((= i depth))
    (setq result (ida-star-sub start i))
    (if (not (eq result nil))
      (return-from ida-star result))))

(defun ida-star-sub (start depth)
  (let* ((queue (list)) (visited (list)))
    (setq queue (list (list start 0 0 nil)))
    (while (not (= (list-length queue) 0))
      (setq n (first queue))
      (setq queue (rest queue))
      (if (goalp n)
	(return-from ida-star-sub (fourth n))
	(dolist (new (expand n))
	  (if (and (not (hasstate new visited)) (< (third new) depth))
	    (setq queue (sort (append `(,new) queue) #'< :key #'second))))))))

    A*:

    (load "eight-util.lisp")

(setq *heuristic-func* 'composite)

(defun composite (state)
  (+ (out-of-place state) (manhatten-distance-sum state)))

(defun hasstate (item var)
  (dolist (state var)
    (if (eq (first state) (first item))
      (return T)
      (return nil))))

(defun a-star (start)
  (let* ((queue (list)) (visited (list)))
    (setq queue (list (list start 0 0 nil)))
    (while (not (= (list-length queue) 0))
      (setq n (first queue))
      (setq queue (rest queue))
      (if (goalp n)
	(return-from a-star (fourth n))
	(dolist (new (expand n))
	  (if (not (hasstate new visited))
	    (setq queue (sort (append `(,new) queue) #'< :key #'second))))))))

    Our utility file:

    ;-------------------------------------------------------------------------------
; global variable: goal state
;-------------------------------------------------------------------------------
(defvar *goal-state* '(1 2 3 8 0 4 7 6 5))
;(defvar *goal-state* '(1 2 3 4 0 5 6 7 8))

;-------------------------------------------------------------------------------
; global variables: number of tiles
;-------------------------------------------------------------------------------
(defvar *num-tile* 9)
(defvar *num-node* 0)

;-------------------------------------------------------------------------------
; global variables: operations
;-------------------------------------------------------------------------------
(defvar *operations* '(up down left right))

;-------------------------------------------------------------------------------
; global variables: expansion function
;-------------------------------------------------------------------------------
(defvar *expand-func* 'eight-expand)

(defun eight-expand (node)
  (let (successors)
    (dolist (op *operations* successors)
      (if (and (applicable op node) (notreversep (car (last (fourth node))) op))
	(setq successors (cons (apply-op op node) successors))))
    (setq successors (sort successors #'< :key #'second))))

; check to see if new operation isn't a backstep from the previous operation
(defun notreversep (old new)
  (cond ((and (eq old 'right) (eq new 'left)) nil)
	((and (eq old 'left) (eq new 'right)) nil)
	((and (eq old 'up) (eq new 'down)) nil)
	((and (eq old 'down) (eq new 'up)) nil)
	(T T)))

;-------------------------------------------------------------------------------
; global variables: heuristic function
;-------------------------------------------------------------------------------
(defvar *heuristic-func* 'static-heuristic)

(defun static-heuristic (state)
  '1000)

;-------------------------------------------------------------------------------
; find location of number in state (0 1 2 3 4 .. 8)
;-------------------------------------------------------------------------------
(defun location (number state)
  (let (loc)
     (dotimes (i *num-tile* loc)
        (if (= (nth i state) number)
           (setq loc i)
	   nil))))

;-------------------------------------------------------------------------------
; Swap values in two locations
;-------------------------------------------------------------------------------
(defun swap (loc1 loc2 lst)
  (let ((new nil))
     (dotimes (i *num-tile* (reverse new))
	(cond ((= i loc1) (setq new (cons (nth loc2 lst) new)))
	      ((= i loc2) (setq new (cons (nth loc1 lst) new)))
	      (T (setq new (cons (nth i lst) new)))))))

;-------------------------------------------------------------------------------
; Look if op is applicable to state
;-------------------------------------------------------------------------------
(defun applicable (op node)
  (let* ((state (first node)) (blank (location 0 state)))
       (cond ((eq op 'up)
 	      (if (and (<= 0 blank) (>= 2 blank)) nil T))
	     ((eq op 'down)
	      (if (and (<= 6 blank) (>= 8 blank)) nil T))
	     ((eq op 'left)
	      (if (eq 0 (mod blank 3)) nil T))
	     ((eq op 'right)
	      (if (eq 2 (mod blank 3)) nil T))
	     (T 'failure))))

;-------------------------------------------------------------------------------
; Apply op to state
;-------------------------------------------------------------------------------
(defun apply-op (op node)
  (let* (new (state (first node)) (blank (location 0 state)))
   (setq *num-node* (+ *num-node* 1))
   (list (setq new 
            (cond ((eq op 'up)    (swap blank (- blank 3) state))
	          ((eq op 'down)  (swap blank (+ blank 3) state))
	          ((eq op 'left)  (swap blank (- blank 1) state))  
	          ((eq op 'right) (swap blank (+ blank 1) state))))
            (+ (third node) (h new)) 
            (+ (third node) 1)
	    (append (fourth node) (list op)))))
            ;(cons op (fourth node)))))

; this is a dummy heuristic function. write your own
; this function is needed in (apply-op ..) above
(defun h (state) 
  (funcall *heuristic-func* state))

;-------------------------------------------------------------------------------
; Check if current state is goal state
;-------------------------------------------------------------------------------
(defun goalp (node)
  (if (equal (first node) *goal-state*) T nil))

;-------------------------------------------------------------------------------
; check for duplicate states
;-------------------------------------------------------------------------------
(defun dupe (state node-list)
  (dolist (node node-list nil) 
     (if (equal state (first node)) 
         (return-from dupe T))))

;-------------------------------------------------------------------------------
; call a function to expand 
;-------------------------------------------------------------------------------
(defun expand (node)
  (funcall *expand-func* node))

;-------------------------------------------------------------------------------
; Print result 
;-------------------------------------------------------------------------------
(defun print-result (node)
  (print (format NIL 
		 "~%~%PATH: ~A ~%DEPTH: ~D ~%" 
		 (reverse (fourth node)) 
		 (third node)))
   T) 

;-------------------------------------------------------------------------------
; Print puzzle 
;-------------------------------------------------------------------------------
(defun print-tile (state)
   (print (format NIL "~%"))
   (dotimes (i 3 T)
      (print (format NIL
                     " ~A ~A ~A"
                     (nth (* 3 i) state)
                     (nth (+ (* 3 i) 1) state)
                     (nth (+ (* 3 i) 2) state)))))

;-------------------------------------------------------------------------------
; Print answer
;-------------------------------------------------------------------------------
(defun print-answer (state path)
   (let ((blank (location 0 state)))
      (print-tile state)
      (cond ((null path) T)
            ((eq 'up (first path))
             (print-answer (swap blank (- blank 3) state) (rest path)))
            ((eq 'down (first path))
             (print-answer (swap blank (+ blank 3) state) (rest path)))
            ((eq 'left (first path))
             (print-answer (swap blank (- blank 1) state) (rest path)))
            ((eq 'right (first path))
             (print-answer (swap blank (+ blank 1) state) (rest path))))))

;------------------------------------------------------------------------------
; While loop: just use it!
;------------------------------------------------------------------------------
(defmacro while (test &rest forms) `(loop (unless ,test (return)) ,@forms) )


;------------------------------------------------------------------------------
; Heuristic functions
;------------------------------------------------------------------------------

(defun out-of-place (state)
  (let* ((diff 0))
    (do ((i 0 (+ i 1))) ((= i (list-length *goal-state*)))
       (if (not (= (nth i *goal-state*) (nth i state)))
	 (setq diff (+ diff 1))))
    (return-from out-of-place diff)))

(defun manhatten-distance-sum (state)
  (let* ((sum 0))
    (do ((loc 0 (+ loc 1))) ((= loc (- (list-length *goal-state*) 1)))
      (setq mh (manhatten-distance (nth loc state) loc))
      ;(format t "~d at location ~d: MH of ~d~%" (nth loc state) loc mh)
      (setq sum (+ sum mh)))
    (return-from manhatten-distance-sum sum)))

(defun manhatten-distance (tile loc)
  (let (mh)
    (setq final-loc (location tile *goal-state*))
    (setq mh (abs (+ (- (floor (/ loc 3)) (floor (/ final-loc 3))) (- (mod loc 3) (mod final-loc 3)))))))

    And finally, my file to run the testing:

    (setq boards '((1 3 4 8 6 2 7 0 5) (2 8 1 0 4 3 7 6 5)))

(format t "Beginning Tests:~%~%")

(dolist (board boards)

(format t "Board: ~a~%~%" board)

(load "dls.lisp")

(format t "DLS:~%----~%~%")

(setq answer (time (dls board)))
(format t "~%~%Answer: ~a~%~%" answer)

;---------------------------------------------------

(load "bfs.lisp")

(format t "BFS:~%----~%~%")

(setq answer (time (bfs board)))
(format t "~%~%Answer: ~a~%~%" answer)

;---------------------------------------------------

(load "ids.lisp")

(format t "IDS:~%----~%~%")

(setq answer (time (dls board)))
(format t "~%~%Answer: ~a~%~%" answer)

;---------------------------------------------------

(load "greedy.lisp")

(format t "GREEDY:~%-------~%~%")

(setq answer (time (dls board)))
(format t "~%~%Answer: ~a~%~%" answer)

;---------------------------------------------------

(load "a-star.lisp")

(format t "A*:~%---~%~%")

(setq answer (time (a-star board)))
(format t "~%~%Answer: ~a~%~%" answer)

;---------------------------------------------------

(load "ida-star.lisp")

(format t "IDA*:~%-----~%~%")

(setq answer (time (ida-star board)))
(format t "~%~%Answer: ~a~%~%" answer)
)
  • 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.

  • (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?

  • (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.
  • (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...

  • (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...)

  • (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 #:

Log Out

« Return to Article