• Dividius (unregistered)

    What is that horrible language JAVA 6 has posted in? Looks a bit like c#, but isn't. Java, maybe?

    I'd like to know so I can avoid RIDICULOUS ANONYMOUS FLAMEBAITERS in my online life.

  • sadnessbowl (unregistered)

    I rather liked my solution, which simulates reality by randomly moving the blank square around until you happen upon a solved puzzle.

    Only took it 68 seconds real time the first time to solve it!

  • (cs)

    DailyWTF people (Alex, et al): I respect you for this. If I was unemployed, I would probably try to solve these puzzles just to put my skilz out there. As it is, I do have a job, and therefore cannot devote my time to this trivia. Sorry.

    Addendum (2009-09-02 17:51): Sorry also for those who can.

  • Keith Brawner (unregistered)

    I'm not going to lie, if I didn't have an existing (provably optimal) solution sitting around, I wouldn't be solving trivia problems either.

  • big brain (unregistered)

    Pascal rocks, its just a lot better than C as language. And the Delphi compiler generates smallest and faster binaries than the C++ compiler. I had to say it, benchmarks dont lie.

  • Fubar (unregistered) in reply to randy

    He is leet ... the rest of us only understand XOR swap !

  • (cs) in reply to big brain
    big brain:
    Pascal rocks, its just a lot better than C as language. And the Delphi compiler generates smallest and faster binaries than the C++ compiler. I had to say it, benchmarks dont lie.
    I gotcher benchmark right here.
  • (cs)

    One of the solutions on page 2 made my browser (firefox 3.0.x, haven't upgraded to 3.5 because it crashes thanks to my workplace's "monitoring" software) show a huge black square instead of the person's post, which turns into readable text sometimes if you do a select all. Weird.

  • (cs)

    I bet none of you can solve this in LOGO. By having the turtle draw the entire thing.

  • (cs) in reply to Keith Brawner
    Keith Brawner:
    I'm not going to lie, if I didn't have an existing (provably optimal) solution sitting around, I wouldn't be solving trivia problems either.
    Gotta respect you even more for that, Keith.
  • Frank Wales (unregistered) in reply to Zapp Brannigan

    I prefer a Pandora of WTFs; it sounds inappropriately erudite.

  • anonymous (unregistered) in reply to Dividius
    Dividius:
    What is that horrible language JAVA 6 has posted in? Looks a bit like c#, but isn't. Java, maybe?

    I'd like to know so I can avoid RIDICULOUS ANONYMOUS FLAMEBAITERS in my online life.

  • Yeah! Got it! (unregistered)

    This finds the optimal solution by a width-first search.

    Because many boards have no solution, the generateInput() method creates a board by starting with a solved board and sliding up to 50 times at random.

    Sample output:

    START FROM |1|2|3| |4|5|6| |7|8|-|

    RANDOMIZE INPUT |8|1|-| |4|2|5| |3|6|7| ------- -> (33 moves) 8,5,2,3,6,2,3,6,2,8,5,3,6,1,4,6,1,2,8,1,3,7,6,3,2,8,1,5,7,6,3,4,8,1 OUTPUT |1|2|3| |4|5|6| |7|8|-| ------- -> (21 moves) 5,2,6,3,4,8,1,5,2,6,3,7,6,3,8,4,7,8,5,2,3,6

    Code:

    package byoc;
    
    import java.util.HashSet;
    import java.util.Random;
    import java.util.TreeMap;
    
    public class NumberSlider {
    	final static char SLIDER_C = '-';
    	final static String GOAL = "12345678"+SLIDER_C;
    	final static int BOARD_SIZE = GOAL.length();
    	final static int META_DATA_INDEX = BOARD_SIZE+1;
    	final static int[][] legalMoves = new int[][]{
    		{1,3},{0,2,4},{1,5},{0,4,6},{1,3,5,7},{2,4,8},{3,7},{4,6,8},{7,5}
    	};
    	public static void main(String[] args) {
    		System.err.println("START FROM");
    		printBoard(GOAL);
    		String input = generateInput();
    		System.err.println("RANDOMIZE INPUT");
    		printBoard(input);
    		String output = solve(input.substring(0,9));
    		System.err.println("OUTPUT");
    		printBoard(output);
    	}
    	private static String generateInput() {
    		String input = GOAL;
    		Random r = new Random(System.currentTimeMillis());
    		int position = GOAL.indexOf(SLIDER_C);
    		int oldPosition = position;
    		int newPosition;
    		for (int i = 0; i < 50; i++) {
    			newPosition = legalMoves[position][r.nextInt(legalMoves[position].length)];
    			if (newPosition != oldPosition) {
    				input = slide(input,position,newPosition);
    				oldPosition = position;
    				position = newPosition; 
    			}
    		}
    		return input;
    	}
    	private static String solve(String board) {
    		HashSet<String> examinedBoards = new HashSet<String>();
    		TreeMap<Double,String> unexaminedBoards = new TreeMap<Double,String>();
    		int i = 0;
    		unexaminedBoards.put(qualityScore(board, i++), board);
    		while (!board.startsWith(GOAL)) {
    			board = unexaminedBoards.remove(unexaminedBoards.firstKey());
    			final int position = board.indexOf(SLIDER_C);
    			for (int newPosition : legalMoves[position]) {
    				final String newBoard = slide(board,position,newPosition);
    				final String newBoardKey = newBoard.substring(0,BOARD_SIZE);
    				if (examinedBoards.contains(newBoardKey)) {
    					continue;
    				}
    				examinedBoards.add(newBoardKey);
    				unexaminedBoards.put(qualityScore(newBoard,i++),newBoard);
    			}
    		}
    		return board;
    	}
    	private static double qualityScore(String board, int dec) {
    		int unmatchedPieces = BOARD_SIZE;
    		for (int i = 0; i < BOARD_SIZE; i++) {
    			if (board.charAt(i) == GOAL.charAt(i)) {
    				unmatchedPieces--;
    			}
    		}
    		unmatchedPieces += 1000*board.length();
    		return Double.parseDouble(unmatchedPieces+"."+dec);
    	}
    	private static String slide(String board, int position, int newPosition) {
    		char[] c = board.toCharArray();
    		c[position] = c[newPosition];
    		c[newPosition] = SLIDER_C;
    		return new String(c) + "," + c[position];
    	}
    	private static void printBoard(String board) {
    		System.err.println("|"+board.charAt(0)+"|"+board.charAt(1)+"|"+board.charAt(2)+"|");
    		System.err.println("|"+board.charAt(3)+"|"+board.charAt(4)+"|"+board.charAt(5)+"|");
    		System.err.println("|"+board.charAt(6)+"|"+board.charAt(7)+"|"+board.charAt(8)+"|");
    		System.err.println("-------" + (board.length() > BOARD_SIZE ? " -> (" + board.substring(META_DATA_INDEX).length()/2 + " moves) " + board.substring(META_DATA_INDEX): ""));
    	}
    }
    
  • (cs) in reply to evilspoons
    evilspoons:
    One of the solutions on page 2 made my browser (firefox 3.0.x, haven't upgraded to 3.5 because it crashes thanks to my workplace's "monitoring" software) show a huge black square instead of the person's post, which turns into readable text sometimes if you do a select all. Weird.

    Quite normal for Firefox. It does that often on such long pages.

  • me (unregistered)

    the real WTF is why are you putting exercises on this website? Create a new category, stick them in there, and keep up with the real WTF.

  • (cs)

    For an interesting experiment I first tried solving this using the "methinks it's a weasel" sort of evolution simulation, but I couldn't find a good way of scoring the comparisons well. They kept getting stuck in a situation where all of the spots surrounding the blank were solved so it'd move away from that and then right back to it; there was no incentive to deviate further away from the solution in order to get it solved.

    Anyway, abandoned that eventually and made an inefficient iterative optimal path algorithm. So it's "DIFFICULT" but not "FAST". It does at least make sure it's not repeating its work.

    This is the single character variable names version that keeps a bit of formatting but still sneaks in under 800 bytes ;)

    Ruby:
    def solve(x)
      p "Puzzle: #{x}"
      z="12345678 "
      t=Hash.new
      t[x]=""
      a=[x]
    

    while (a.index(z)==nil && a.size > 0) b=[] a.each do |p| v=[] i=p.index(" ") v << "U" if i < 6 v << "D" if i > 2 v << "L" if (i+1) % 3 != 0 v << "R" if i % 3 != 0 v.each do |d| n=p.dup i=n.index(" ") n[i], n[i+3]=n[i+3], n[i] if d=="U" n[i], n[i-3]=n[i-3], n[i] if d=="D" n[i], n[i+1]=n[i+1], n[i] if d=="L" n[i], n[i-1]=n[i-1], n[i] if d=="R" if t[n]==nil t[n]=t[p] + d b << n end end end a=b end

    t=t[z] raise "Impossible puzzle." if t==nil p "#{t.length} steps: #{t}" end

    solve(ARGV[0]) #solve(" 87654321")

  • anonymous (unregistered) in reply to me
    me:
    the real WTF is why are you putting exercises on this website? Create a new category, stick them in there, and keep up with the real WTF.

    the real WTF is to write something before reading anything

    ...

    Sliding Around 2009-09-02 by Alex Papadimoulis in Bring Your Own Code

  • Hatterson (unregistered) in reply to Bim Job
    Bim Job:
    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.

    Brute force solutions don't magically stop working....they just require exponentially more and more time as the solution space grows larger.

    Further, you seem to be dividing solutions into 2 categories polynomial-time (efficient) and brute force. This is nowhere close to reality. Many advanced search techniques cut dramatically down on the algorithmic complexity, but still remain non-polynomial time. Specifically I can think of several SAT solvers that can return, in a matter of minutes solutions that would take a brute force algorithm several universelifes to stumble upon.

    Even in computer science an algorithm is called 'efficient' when it performs reasonably well in comparison with other options, regardless of its actual running time.

  • Fubar (unregistered) in reply to EngleBart
    EngleBart:
    Bonus 1: What IS the maximum number/depth of scrambles? Bonus 2: How many different starting positions exist at this depth?

    Quickly hashed together code gives me these answers.

    When the empty tile is in one of the 4 corners, then the maximum depth is 31 moves, and there are 2 starting states at this depth. As there are 4 corners, then this means 8 starting states.

    When the empty tile is in one of the 4 edges, then the maximum depth is 31 moves, and there are 2 starting states at this depth. As there are 4 edges, then this means 8 starting states.

    When the empty tile is in the center square, then the maximum depth is 30 moves, and there are 26 starting positions at this depth.

  • Fubar (unregistered) in reply to Fubar

    I hate replying to myself, but I just noticed these ...

    8 = 3^2 - 1 26 = 3^3 - 1

    I wonder if this is a formula for stating states that could be expanded to larger dimensions like 4x4 and 5x5 ? Maybe something to do with the distance that the empty square is from the center of the puzzle ?

  • Mr.'; Drop Database -- (unregistered)

    Here's a slowish Python program that finds the shortest solution. If the starting position is unsolvable, it transposes the goal.

    def slide(s):
    assert len(s) == 9 and set('12345678.') == set(s)
    parity = sum(s[i] < s[j]
    for i in range(8)
    for j in range(i+1,9)
    if s[i] != '.' != s[j])
    if parity & 1: goal = list('14725836.')
    else: goal = list('12345678.')
    g = list(s)
    if g == goal: return []
    def bfs(g):
    edge = [(g, g.index('.'), [])]
    found = set([tuple(g)])
    while edge:
    ne = []
    for g, ep, moves in edge:
    deltas = []
    if ep >= 3: deltas.append(-3)
    if ep <  6: deltas.append(3)
    if ep % 3 != 0: deltas.append(-1)
    if ep % 3 != 2 : deltas.append(1)
    for d in deltas:
    ng = g[:]; ng[ep] = g[ep + d]; ng[ep + d] = '.'
    tg = tuple(ng)
    if tg not in found:
    nxt = ng, ep + d, moves + [ep + d]
    if ng == goal: return nxt[2]
    ne.append(nxt)
    found.add(tg)
    edge = ne
    raise Exception('Logic error')
    path = bfs(g)
    ep = g.index('.')
    for i in [ep] + path:
    g[ep] = g[i]; g[i] = '.'; ep = i
    print(3 * '%s%s%s\n' % tuple(g))

    def random(): import random lst = list('12345678.') random.shuffle(lst) s = ''.join(lst) slide(s)

  • anon (unregistered) in reply to big brain
    big brain:
    Pascal rocks, its just a lot better than C as language. And the Delphi compiler generates smallest and faster binaries than the C++ compiler. I had to say it, benchmarks dont lie.

    Which C++ compiler? There are a great many.

  • Bored mathematician (unregistered)

    Mathematical proof that there are impossible starting configurations:

    We will impose a linear ordering upon the pieces in the puzzle: we'll treat it as a paragraph of text, reading row by row top-to-bottom, left-to-right within each row. The solved puzzle state can be read as "123/456/78#". With this order, we can naturally say that the "3" piece comes "before" the "4" or the "6", but not the "2"; and we can say that the "5" is "inbetween" the "2" and the hole.

    For any state of the sliding puzzle, you can give a "score" to an unordered pair of two pieces as follows: if the lower-numbered piece comes "before" the higher-numbered one, the pair has a score of 1; otherwise, it has a score of 0.

    We define the score of a 3-by-3 puzzle state as the sum of the scores of the 28 pairs. For example, the solution state "123/456/78#" has a score of 28. The puzzle state "876/543/21#" has a score of 0, and the puzzle state "135/7#2/468" has a score of 22.

    If I transition from state P to state Q by a single horizontal slide, then each of the 28 pairs in state P is in exactly the same scoring orientation as the 28 pairs in state Q. For example, "123/456/78#" has the same score as "123/456/7#8".

    Now consider the transition from state P to state Q by a single vertical slide of piece A. In state P, there are two pieces "inbetween" piece A and the hole; call them B and C. Both of the pairs (A,B) and (A,C) flip their scoring orientation between states P and Q; the other 26 pairs keep their scoring orientation.

    Therefore, if one can move from state P to state Q as the result of a single slide, then the difference "score(P)-score(Q)" must be one of -2, 0, or 2.

    Therefore, as the result of any number of slides, the score of the initial state and the score of the final state must have the same parity modulo 2.

    As shown earlier, the solution state's score is 28.

    The score of the state "123/456/87#" is 27.

    Therefore, no sequence of slides can convert "123/456/87#" to "123/456/78#".

  • Buzzard (unregistered)

    I should send the requirements to our Indian outsourcing team... Those fuckers write ( read cut 'n paste ) beautiful solutions and get it right first time!!!!!!!!!!!!

  • Proteolysis (unregistered)

    Here's a python version that's under 800 bytes. Sample usage: python unscramble.py '67143528 '

    import sys
    
    def unscramble(s):
        n_idx = ((1,3),(0,2,4),(1,5),(0,4,6),(1,3,5,7),(2,4,8),(3,7),(4,6,8),(5,7))
        queue = [s]
        prev = {s: 0}
        while queue:
            x = queue.pop(0)
            i = x.find(' ')
            for j in n_idx[i]:
                y = list(x)
                y[i] = y[j]
                y[j] = ' '
                y = ''.join(y)
                if y not in prev:
                    prev[y] = x
                    if y=='12345678 ' or y=='12345687 ':
                        path = []
                        while y:
                            path.insert(0,y)
                            y = prev[y]
                        return path
                    queue.append(y)
        return []
    
    if __name__ == '__main__':
        path = unscramble(sys.argv[1])
        if path:
            for step in path:
                print(step)
    
  • (cs)

    I propose the collective noun for WTFs should be 'swamp'.

  • Tyr (unregistered)

    One way of solving it is to see that the numbers can still be in the right order, only rotated. Reading clockwise 1, 2, 3, 6, 8, 7, 4 around the edges with 5 in the center is almost completly solved. 4,1,2, 7,5,3, 8,_,6, is almost totally solved.

    Once an edge row or col. has been finished. It can be left alone.

    You can use the center to store a peice and then insert it (counter)clockwise of the proper piece. (Note: my puzzle has a gap in the top left, not bottom right. And its a frog. The clockwise order is 1,2,5,8,7,6,3, with 4 in center) _,7,6, 8,1,5, 4,3,2,

    7,6,5, 8,_,1, #1 and 2 and now in order. 4,3,2

    5 is not in the best spot right now, so I'll go for 8 I slide 8 into the center.

    7,6,5, _,8,1, 4,3,2,

    then free up the spot clockwise of 2.

    7,6,5, 4,8,1, 3,_,2,

    and slide 8 in

    7,6,5, 4,_,1, 3,8,2,

    remember I want the order to be 1,2,5,8,7,6,3 6 will fit in nicely now.

    7,_,5, 4,6,1, 3,8,2,

    7,5,1, 4,6,2, 3,_,8,

    7,5,1, 4,_,2, 3,6,8,

    5 is now is a spot where it can slide into the center.

    7,_,1, 4,5,2, 3,6,8,

    I want the order to be 1,2,5,8,7,6,3 so

    7,1,2, 4,_,5, 3,6,8,

    Almost there, I have one vertical row done. (2,5,8) I can leave this intact and only move the 5 pieces on the right

    I bring 1 and 4 to the top and leave them there while I fix the other pieces

    7,1,2, _,4,5, 3,6,8,

    1,4,2, 7,_,5, 3,6,8,

    I rotate the three bottom left pieces untill they are like this

    1,4,2, 3,_,5, 6,7,8,

    I bring down 1 and 4 to finish

    _,1,2, 3,4,5, 6,7,8,

    Now I'm off to try and get that to work in python.

  • Shredder (unregistered) in reply to RBoy
    RBoy:
    Shredder:
    By the way what is this "Bring your own code"? I was sue that it was called Programming Praxis before.

    Well, now you are Shredder, not Sue, and it's called Bring Your Own Code, not Programming Praxis.

    That must have been a Freudian typo! I just remembered that I read that some guy threatened to sue Alex for using the name Programming Praxis, which must be why he changed it.

    captcha: zucchinifelatio

  • Zost (unregistered)

    The function assumes a string input of the numbers 1-8, and a 0 representing the empty spot. It outputs which number you should slide. Using an iterative version of a BFS (it did say write a function, not functions :) it finds the fastest way to solve the entered puzzle.

    And yes, it's in C#. THE HORROR!

        public static string SolveNineSlider(string input)
        {
            string solution = "123456780";
    
            int[][] spotshifts = {  new int[] {1,3},      new int[] {0,2,4},    new int[] {1,5},
                                    new int[] {0,4,6},    new int[] {1,3,5,7},  new int[] {2,4,8},
                                    new int[] {3,7},      new int[] {4,6,8},    new int[] {5,7}};
    
            List<string> Visited = new List<string>();
    
            Dictionary<string, string> Actives = new Dictionary<string, string>();
    
            Actives.Add(input, string.Empty);
    
            while (!Actives.ContainsKey(solution))
            {
                Dictionary<string, string> TempActives = new Dictionary<string, string>();
                foreach (KeyValuePair<string, string> kvp in Actives)
                {
                    int index = kvp.Key.IndexOf('0');
                    int[] spots = spotshifts[index];
                    for (int i = 0; i < spots.Length; i++)
                    {
                        string next = kvp.Key.Clone().ToString();
                        string nextpath = kvp.Value.Clone().ToString();
                        char c = next[spots[i]];
                        next = next.Replace('0', '*');
                        next = next.Replace(c, '0');
                        next = next.Replace('*', c);
                        nextpath += c;
                        if (!Visited.Contains(next))
                        {
                            if (TempActives.ContainsKey(next))
                            {
                                if (TempActives[next].Length > nextpath.Length)
                                    TempActives[next] = nextpath;
                            }
                            else
                                TempActives.Add(next, nextpath);
                        }
                    }
                    Visited.Add(kvp.Key);
                }
    
                Actives.Clear();
                foreach (KeyValuePair<string, string> kvp in TempActives)
                    Actives.Add(kvp.Key, kvp.Value);
            }
    
            return Actives[solution];
        }
    }
    
  • Dave (unregistered)

    Imho recommending a less structured programming language to someone because they don't understand the syntax of a more modern language is bad advice.

    In the realm of practical languages, Excluding any esolang and parser written for fun, a more interesting question is why would someone bother to write a syntactic construct like that ?

    How did they manage to convince anyone else to use it ?

    Perhaps the problem is common enough and someone else has thought about it before ?

    What were they thinking ?

  • Mike5 (unregistered)

    Well, I didn't bring my own code, but anyway, this one is from Bratko's Prolog programming for AI. The heuristic is simple but pretty good, so I guess it falls into the difficult category.

    % Figure 12.6  Problem-specific procedures for the eight 
    % puzzle, to be used in best-first search of Figure 12.3.
    
    
    /* Problem-specific procedures for the eight puzzle
    
    Current situation is represented as a list of positions of the tiles, 
    with first item in the list corresponding to the empty square.
    
    Example:
    
                               This position is represented by:
    3        1    2    3
    2        8         4       [2/2, 1/3, 2/3, 3/3, 3/2, 3/1, 2/1, 1/1, 1/2]
    1        7    6    5
              
             1    2    3
    
    "Empty' can move to any of its neighbours which means 
    that "empty' and its neighbour interchange their positions.
    */
    
    % s( Node, SuccessorNode, Cost)
    
    s( [Empty | Tiles], [Tile | Tiles1], 1)  :-  % All arc costs are 1
      swap( Empty, Tile, Tiles, Tiles1).         % Swap Empty and Tile in Tiles 
    
    swap( Empty, Tile, [Tile | Ts], [Empty | Ts] )  :-
      mandist( Empty, Tile, 1).                  % Manhattan distance = 1
    
    swap( Empty, Tile, [T1 | Ts], [T1 | Ts1] )  :-
      swap( Empty, Tile, Ts, Ts1).
    
    mandist( X/Y, X1/Y1, D)  :-          % D is Manhhattan dist. between two squares
      dif( X, X1, Dx),
      dif( Y, Y1, Dy),
      D is Dx + Dy.
    
    dif( A, B, D)  :-              % D is |A-B|
      D is A-B, D >= 0, !
      ;
      D is B-A.
    
    % Heuristic estimate h is the sum of distances of each tile
    % from its "home' square plus 3 times "sequence' score
    
    h( [Empty | Tiles], H)  :-
      goal( [Empty1 | GoalSquares] ), 
      totdist( Tiles, GoalSquares, D),      % Total distance from home squares
      seq( Tiles, S),                       % Sequence score
      H is D + 3*S.
    
    totdist( [], [], 0).
    
    totdist( [Tile | Tiles], [Square | Squares], D)  :-
      mandist( Tile, Square, D1),
      totdist( Tiles, Squares, D2),
      D is D1 + D2.
    
    % seq( TilePositions, Score): sequence score
    
    seq( [First | OtherTiles], S)  :-
      seq( [First | OtherTiles ], First, S).
    
    seq( [Tile1, Tile2 | Tiles], First, S)  :-
      score( Tile1, Tile2, S1),
      seq( [Tile2 | Tiles], First, S2),
      S is S1 + S2.
    
    seq( [Last], First, S)  :-
      score( Last, First, S).
    
    score( 2/2, _, 1)  :-  !.              % Tile in centre scores 1
    
    score( 1/3, 2/3, 0)  :-  !.            % Proper successor scores 0
    score( 2/3, 3/3, 0)  :-  !.
    score( 3/3, 3/2, 0)  :-  !.
    score( 3/2, 3/1, 0)  :-  !.
    score( 3/1, 2/1, 0)  :-  !.
    score( 2/1, 1/1, 0)  :-  !.
    score( 1/1, 1/2, 0)  :-  !.
    score( 1/2, 1/3, 0)  :-  !.
    
    score( _, _, 2).                       % Tiles out of sequence score 2
    
    % goal( [2/2,1/3,2/3,3/3,3/2,3/1,2/1,1/1,1/2] ).  % The original goal squares for tiles
    goal( [3/1,1/3,2/3,3/3,1/2,2/2,3/2,1/1,2/1] ).  % TDWTF goal squares for tiles
    
    % Display a solution path as a list of board positions
    
    showsol( [] ).
    
    showsol( [P | L] )  :-
      showsol( L),
      nl, write( '---'),
      showpos( P).
    
    % Display a board position
    
    showpos( [S0,S1,S2,S3,S4,S5,S6,S7,S8] )  :-
      member( Y, [3,2,1] ),                           % Order of Y-coordinates
      nl, member( X, [1,2,3] ),                       % Order of X-coordinates
      member( Tile-X/Y,                               % Tile on square X/Y
              [' '-S0,1-S1,2-S2,3-S3,4-S4,5-S5,6-S6,7-S7,8-S8] ),
      write( Tile),
      fail                                            % Backtrack to next square
      ;
      true.                                           % All squares done
    
    % Starting positions for some puzzles
    
    start1( [2/2,1/3,3/2,2/3,3/3,3/1,2/1,1/1,1/2] ).  
    
    start2( [2/1,1/2,1/3,3/3,3/2,3/1,2/2,1/1,2/3] ).  
    
    start3( [2/2,2/3,1/3,3/1,1/2,2/1,3/3,1/1,3/2] ).  
    
    % An example query: ?- start1( Pos), bestfirst( Pos, Sol), showsol( Sol).
    
    % - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
    
    % Figure 12.3  A best-first search program.
    % bestfirst( Start, Solution): Solution is a path from Start to a goal
    
    bestfirst( Start, Solution) :-
      expand( [], l( Start, 0/0),  9999, _, yes, Solution).
    	%  Assume 9999 is greater than any f-value
    
    % expand( Path, Tree, Bound, Tree1, Solved, Solution):
    %   Path is path between start node of search and subtree Tree,
    %   Tree1 is Tree expanded within Bound,
    %   if goal found then Solution is solution path and Solved = yes
    
    %  Case 1: goal leaf-node, construct a solution path
    
    expand( P, l( N, _), _, _, yes, [N|P])  :-
       goal(N).
    
    %  Case 2: leaf-node, f-value less than Bound
    %  Generate successors and expand them within Bound.
    
    expand( P, l(N,F/G), Bound, Tree1, Solved, Sol)  :-
      F  =<  Bound,
      (  bagof( M/C, ( s(N,M,C), not member(M,P) ), Succ), 
         !,                                    % Node N has successors
         succlist( G, Succ, Ts),               % Make subtrees Ts
         bestf( Ts, F1),                       % f-value of best successor
         expand( P, t(N,F1/G,Ts), Bound, Tree1, Solved, Sol)
         ;
         Solved = never                        % N has no successors - dead end
      ) .
    
    %  Case 3: non-leaf, f-value less than Bound
    %  Expand the most promising subtree; depending on 
    %  results, procedure continue will decide how to proceed
    
    expand( P, t(N,F/G,[T|Ts]), Bound, Tree1, Solved, Sol)  :-
      F  =<  Bound,
      bestf( Ts, BF), min( Bound, BF, Bound1),          % Bound1 = min(Bound,BF)
      expand( [N|P], T, Bound1, T1, Solved1, Sol),
      continue( P, t(N,F/G,[T1|Ts]), Bound, Tree1, Solved1, Solved, Sol).
    
    %  Case 4: non-leaf with empty subtrees
    %  This is a dead end which will never be solved
    
    expand( _, t(_,_,[]), _, _, never, _) :- !.
    
    %  Case 5:  f-value greater than Bound
    %  Tree may not grow.
    
    expand( _, Tree, Bound, Tree, no, _)  :-
      f( Tree, F), F > Bound.
    
    % continue( Path, Tree, Bound, NewTree, SubtreeSolved, TreeSolved, Solution)
    
    continue( _, _, _, _, yes, yes, Sol).
    
    continue( P, t(N,F/G,[T1|Ts]), Bound, Tree1, no, Solved, Sol)  :-
      insert( T1, Ts, NTs),
      bestf( NTs, F1),
      expand( P, t(N,F1/G,NTs), Bound, Tree1, Solved, Sol).
    
    continue( P, t(N,F/G,[_|Ts]), Bound, Tree1, never, Solved, Sol)  :-
      bestf( Ts, F1),
      expand( P, t(N,F1/G,Ts), Bound, Tree1, Solved, Sol).
    
    % succlist( G0, [ Node1/Cost1, ...], [ l(BestNode,BestF/G), ...]):
    %   make list of search leaves ordered by their F-values
    
    succlist( _, [], []).
    
    succlist( G0, [N/C | NCs], Ts)  :-
      G is G0 + C,
      h( N, H),                             % Heuristic term h(N)
      F is G + H,
      succlist( G0, NCs, Ts1),
      insert( l(N,F/G), Ts1, Ts).
    
    % Insert T into list of trees Ts preserving order w.r.t. f-values
    
    insert( T, Ts, [T | Ts])  :-
      f( T, F), bestf( Ts, F1),
      F  =<  F1, !.
    
    insert( T, [T1 | Ts], [T1 | Ts1])  :-
      insert( T, Ts, Ts1).
    
    
    % Extract f-value
    
    f( l(_,F/_), F).        % f-value of a leaf
    
    f( t(_,F/_,_), F).      % f-value of a tree
    
    bestf( [T|_], F)  :-    % Best f-value of a list of trees
      f( T, F).
    
    bestf( [], 9999).       % No trees: bad f-value
      
    min( X, Y, X)  :-
      X  =<  Y, !.
    
    min( X, Y, Y).
    

    Mike5

  • An Angel (unregistered)

    Collective noun

    A ==== of WTFs

    puddle mess crapload sadness woeful

  • Planar (unregistered) in reply to Bim Job
    Bim Job:
    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.

    Yeah, that's why you should not only fire people who can't read requirements, you also need to fire people who can't write requirements.

  • fgb (unregistered)

    A* with ruby:

    class Puzzle
        def initialize(tiles)
            @tiles = tiles
            @hole = [0, 0]
            @moves = 0
        end
    
        def nextStates
            dx = [-1, 1, 0, 0]
            dy = [0, 0, 1, -1]
            (0..3).map { |d| move(dx[d], dy[d]) }.compact
        end
    
        def finished?
            @tiles == [[nil, 1, 2], [3, 4, 5], [6, 7, 8]]
        end
    
        def move(dx, dy)
            p = Marshal.load(Marshal.dump(self))
    
            x = p.hole[0] + dx
            y = p.hole[1] + dy
    
            if x >= 0 and y >= 0 and x < 3 and y < 3
                p.tiles[y][x], p.tiles[hole[1]][hole[0]] = [p.tiles[hole[1]][hole[0]], p.tiles[y][x]]
                p.hole = [x, y]
                p.moves += 1
                return p
            end
        end
    
        def goalDistance
            distance = 0
            0.upto(2) { |y|
                0.upto(2) { |x|
                    n = (@tiles[y][x] or 0)
                    distance += (x - (n % 3))**2 + (y - (n / 3))**2
                }
            }
            return distance
        end
    
        def hash
            @tiles.flatten.inject(0) { |h, x| h * 9 + (x or 0) }
        end
    
        attr_accessor :tiles, :hole, :moves
    end
    
    def shuffle(p)
        500.times {
            n = p.nextStates
            p = n[rand(n.length)]
        }
        p.moves = 0
        return p
    end
    
    def solve(initState)
        queue = [[initState, initState.goalDistance]]
    
        visited = Hash.new
        loop {
            p = queue.shift[0]
            return nil if not p
            return p if p.finished?
            if not visited[p.hash]
                p.nextStates.each { |s| queue << [s, s.moves + s.goalDistance] }
                queue = queue.sort_by { |x| x[1] }
                visited[p.hash] = true
            end
        }
    end
    
    initState = shuffle(Puzzle.new([[nil, 1, 2], [3, 4, 5], [6, 7, 8]]))
    startTime = Time.now
    goal = solve(initState)
    if goal
        puts "Solved in #{goal.moves} moves (#{Time.now - startTime} seconds)"
    end
    
  • wsinda (unregistered) in reply to 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.
    The clever student just taught the professor something: the importance of writing good specifications.

    Teaching the professor something always gets you an F.

  • Go Figure (unregistered) in reply to Buzzard
    Buzzard:
    I should send the requirements to our Indian outsourcing team... Those fuckers write ( read cut 'n paste ) beautiful solutions and get it right first time!!!!!!!!!!!!
    Another racist pig scared for his pathetic job
  • Bacaran Radu (unregistered) in reply to Buddy

    Easy.

    He didn't have to write the algorithm for solving the thing.

  • Marlon (unregistered)

    This should work.... Puzzle class not included, but you'll get the idea.

    public class SmartSolver implements Runnable
    {
    	/**
    	 * Width an height of the puzzle.
    	 */
    	private int WIDTH, HEIGHT;
    	
    	/**
    	 * Current puzzle.
    	 */
    	private Puzzle p;
    	
    	/**
    	 * These hold the calculation step and the output speed.
    	 */
    	private int calculations;
    	
    	/**
    	 * Constructor. Initiates the number of calculations,
    	 * sets the starting puzzle, sets the width and height
    	 * 
    	 * @param p
    	 */
    	public SmartSolver(Puzzle p)
    	{
    		this.p = p;
    		calculations = 0;
    		WIDTH = p.getWidth();
    		HEIGHT = p.getHeight();
    	}
    
    	/**
    	 * Moves the hole of the puzzle in the given
    	 * direction.
    	 * 
    	 * @param d
    	 */
    	private void move(Direction d)
    	{
    		calculations++;
    		p.moveHole(d);
    	}
    
    	/**
    	 * Moves a certain number in the puzzle to the
    	 * gives coordinates without disturbing the rows
    	 * above or equal to the row of the coordinate.
    	 * 
    	 * @param number	Number to move
    	 * @param y			Y coordinate
    	 * @param x			X coordinate
    	 */
    	private void moveNumber(int number, int y, int x)
    	{
    		int num_x = 0, num_y = 0;
    		boolean stop = false;
    		//find position of number and store the goal coordinates
    		//in num_x and num_y
    		for(int n_x = 0; n_x < WIDTH && !stop; n_x++) {
    			for(int n_y = 0; n_y < HEIGHT && !stop; n_y++) {
    				if(p.getNumber(n_x, n_y) == number) {
    					num_x = n_x;
    					num_y = n_y;
    					stop = true;
    				}
    			}
    		}
    
    		//move down to not disturb any pieces
    		if(num_x < x && p.getHoleY() == y) {
    			move(Direction.DOWN);
    		}
    
    		//move the number to the left side
    		while(num_x > x) {
    		    if(p.getHoleY() == num_y && p.getHoleX() > num_x) {
    		        if(num_y == HEIGHT - 1) {
    		        	move(Direction.UP); 
    		        } else {
    		        	move(Direction.DOWN);
    		        }
    		    }
    		    //move blank to the correct position
    		    while(p.getHoleX() >= num_x)  move(Direction.LEFT);
    		    while(p.getHoleX() < num_x - 1) move(Direction.RIGHT);
    		    while(p.getHoleY() < num_y)   move(Direction.DOWN);
    		    while(p.getHoleY() > num_y)   move(Direction.UP);
    		    //do the move move
    		    move(Direction.RIGHT);
    		    num_x--;
    		}
    
    		//move the numer to the right side
    		while(num_x < x) {
    		    if(p.getHoleY() == num_y && p.getHoleX() < num_x) {
    		        if(num_y == HEIGHT - 1) {
    		        	move(Direction.UP); 
    		        } else {
    		        	move(Direction.DOWN);
    		        }
    		    }
    		    //move the blank to te corect position
    		    while(p.getHoleX() <= num_x)    move(Direction.RIGHT);
    		    while(p.getHoleX() > num_x + 1) move(Direction.LEFT);
    		    while(p.getHoleY() < num_y)     move(Direction.DOWN);
    		    while(p.getHoleY() > num_y)     move(Direction.UP);
    		    //do the move
    		    move(Direction.LEFT);
    		    num_x++;
    		}
    		
    		//move number up
    		while(num_y > y) {
    		    if(y < num_y - 1) {
    		    	//when to lower than one row under the goal position
    		        while(p.getHoleY() < num_y - 1) move(Direction.DOWN);
    		        if(p.getHoleX() == num_x) {
    		        	if(num_x == WIDTH - 1) {
    		        		move(Direction.LEFT);
    		        	} else {
    		        		move(Direction.RIGHT);
    		        	}
    		        }
    		        //move blank to the correct position
    		        while(p.getHoleY() > num_y - 1) move(Direction.UP);
    		        while(p.getHoleX() < num_x)   move(Direction.RIGHT);
    		        while(p.getHoleX() > num_x)   move(Direction.LEFT);
    		        //do the move
    		        move(Direction.DOWN);
    		    } else {
    		    	//when the number is one row under the goal position
    		        if(num_x != WIDTH - 1) {
    		        	//when the goal position is not in the last column 
    		            if(p.getHoleY() == num_y && num_y != HEIGHT - 1) {
    		            	move(Direction.DOWN);
    		            }
    		            //move blank to the cocrect position
    		            while(p.getHoleX() < num_x + 1) move(Direction.RIGHT);
    		            while(p.getHoleX() > num_x + 1) move(Direction.LEFT);
    		            while(p.getHoleY() > num_y - 1) move(Direction.UP);
    		            while(p.getHoleY() < num_y - 1) move(Direction.DOWN);
    		            //do the move
    		            move(Direction.LEFT);
    		            move(Direction.DOWN);
    		        } else {
    		        	//when the goal position is in the last column
    		            if(p.getHoleY() < num_y && p.getHoleX() == num_x) {
    		            	//when you're lucky
    		                while(p.getHoleY() < num_y)     move(Direction.DOWN);
    		            } else {
    		            	//place blank in the correct position
    		                while(p.getHoleY() > num_y + 1) move(Direction.UP);
    		                while(p.getHoleY() < num_y + 1) move(Direction.DOWN);
    		                while(p.getHoleX() < num_x)     move(Direction.RIGHT);
    		                while(p.getHoleX() > num_x)     move(Direction.LEFT);
    		                //make a complicated sequence of moves to place the 
    		                //number in the last column.
    		                move(Direction.UP);
    		                move(Direction.UP);
    		                move(Direction.LEFT);
    		                move(Direction.DOWN);
    		                move(Direction.RIGHT);
    		                move(Direction.DOWN);
    		                move(Direction.LEFT);
    		                move(Direction.UP);
    		                move(Direction.UP);
    		                move(Direction.RIGHT);
    		                move(Direction.DOWN);
    		            }
    		        }
    		    }
    		    num_y--;
    		}
    		
    		//move blank down
    		while(num_y < y) {
    		    if(p.getHoleX() == num_x && p.getHoleY()<num_y){
    		        if(num_x == WIDTH-1) {
    		        	move(Direction.LEFT);
    		        } else {
    		        	move(Direction.RIGHT);
    		        }
    		    }
    		    //move blank to the correct position
    		    while(p.getHoleY() > num_y+1) move(Direction.UP);
    		    while(p.getHoleY() < num_y+1) move(Direction.DOWN);
    		    while(p.getHoleX() < num_x)   move(Direction.RIGHT);
    		    while(p.getHoleX() > num_x)   move(Direction.LEFT);
    		    //do the move
    		    move(Direction.UP);
    		    num_y++;
    		}
    	}
    
    	/**
    	 * Solve a puzzle on a structured way without searching
    	 * for the solution.
    	 * 
    	 * This method will be called when the thread is started.
    	 */
    	public void run() {
    		//start with the first number
            int number = 1;
            //solve to the top rows without the bottom two rows
            for(int r = 0; r < HEIGHT - 2; r++) {
                for(int c = 0; c < WIDTH; c++) {
                	moveNumber(number + c, r, c);
                }
                number += WIDTH;
            }
            //solve the bottom two rows without the last two by two square
            for(int c = 0; c < WIDTH - 2; c++) {
            	moveNumber(number, HEIGHT - 2, c);
                if(p.getHoleX() == c) {
                	move(Direction.RIGHT);
                }
                if(p.getNumber((number + WIDTH - 1) % WIDTH, (number + WIDTH - 1) / WIDTH) != (number + WIDTH)) {
                	moveNumber(number + WIDTH, HEIGHT - 1, c + 1);
                    if(p.getHoleY() != HEIGHT - 1) {
                        //A.X or AX.
                        //XBX    XBX
                        if(p.getHoleX() == c + 1) {
                        	move(Direction.RIGHT);
                        }
                        move(Direction.DOWN);
                    }
                    //AXX
                    //XB.
                    while(p.getHoleX() > c + 2)  move(Direction.LEFT);
                    move(Direction.LEFT);
                    move(Direction.LEFT);
                    move(Direction.UP);
                    move(Direction.RIGHT);
                    move(Direction.DOWN);
                    move(Direction.RIGHT);
                    move(Direction.UP);
                    move(Direction.LEFT);
                    move(Direction.LEFT);
                    move(Direction.DOWN);
                    move(Direction.RIGHT);
                }
                number++;
            }
            //solve the last two by two square
            if(p.getHoleX() < WIDTH - 1)  move(Direction.RIGHT);
            if(p.getHoleY() < HEIGHT - 1) move(Direction.DOWN);
            number = (WIDTH * HEIGHT - 1) - WIDTH;
            if(p.getNumber((number - 1) % WIDTH, (number - 1) / WIDTH) == number + 1) {
            	move(Direction.UP);
            	move(Direction.LEFT);
            	move(Direction.DOWN);
            	move(Direction.RIGHT);
            }
            if(p.getNumber((number - 1) % WIDTH, (number - 1) / WIDTH) == number + WIDTH) {
            	move(Direction.LEFT);
            	move(Direction.UP);
            	move(Direction.RIGHT);
            	move(Direction.DOWN);
            }
    	}
    }
    
  • yeah (unregistered)

    "interesting"

  • Alfredo (unregistered)

    dijkstra in c++

    #include <stdio.h>
    #include <queue>
    #include <map>
    #include <set>
    int d[]={-1, 1, -3, 3};
    
    std::set<int> visited;
    std::map<int, int> prev;
    std::queue<int> q;
    
    int getPos(int num, int x)
    {
    	for(int i=0; i<9; i++)
    	{
    		if(num%10 == x) return i;
    		num/=10;
    	}
    	return 10;
    }
    
    int swap0(int num, int pos0, int posx)
    {
    	if(posx<0||posx>8) return 0;
    	if(posx/3 != pos0/3 && posx%3!=pos0%3) return 0;
    	int x=num;
    	int sub=1;
    	for(int i=0; i<posx; i++)
    	{
    		sub*=10;
    		x/=10;
    	}
    	x=x%10;
    	int add=1;
    	for(int i=0; i<pos0; i++)
    	{
    		add*=10;
    	}
    	return num+(add-sub)*x;
    }
    
    int main()
    {
    	int num = 123456780;
    
    	int a,b,c, finish;
    	scanf("%d%d%d", &a, &b, &c);
    	finish=a*1000000+b*1000+c;
    
    	for(int i=0; i<9; i++)
    	{
    		if(getPos(finish, i) == 10) 
    		{
    			printf("invalid number\n");
    			return 1;
    		}
    	}
    	q.push(num);
    	while(!q.empty())
    	{
    		num=q.front();
    		q.pop();
    		
    		if(visited.count(num)) continue;
    		visited.insert(num);
    
    		if(num==finish)
    		{
    			while(num!=123456780) 
    			{
    				printf("\n%03d\n%03d\n%03d\n", prev[num]/1000000, prev[num]/1000%1000, prev[num]%1000);
    				num=prev[num];
    			}
    			getchar();getchar();
    			return 0;
    		}
    		int pos0=getPos(num, 0);
    
    		for(int i=0;i<4;i++)
    		{
    			int next=swap0(num, pos0, pos0+d[i]);
    			if(next && !prev[next]) {
    				prev[next]=num;
    				q.push(next);
    			}
    		}
    	}
    
    	printf("unsolvable\n");
    	getchar();getchar();
    	return 2;
    }
    </pre>
    
  • mr X (unregistered)

    So what are the chances of Alex sending a WTF mug to the first person to offer a solution using Brainfuck? ;)

  • Alfredo (unregistered)
    Alfredo:
    dijkstra in c++
    I meant BFS, of course
  • SR (unregistered) in reply to Harrow
    Harrow:
    SR:
    ...what is the collective noun for WTFs?...
    Cluster.

    :oD I like cluster!

  • SR (unregistered) in reply to Moss
    Moss:
    I bet none of you can solve this in LOGO. By having the turtle draw the entire thing.

    My turtle's hard at work on the problem right now. I'll let you know how he gets on when he's finished in around 215 years' time.

  • C=64 is best (unregistered)
    10 CLS
    20 INPUT "ENTER THE STATE", A$
    30 IF A$="12345678" THEN GOTO 60
    40 PRINT "WRONG!! MAKE YOUR MOVE"
    50 GOTO 20
    60 PRINT "CORRECT!!"
    70 END
  • dv (unregistered) in reply to WhiskeyJack

    Even using INT21h? You're doing it wrong. Shouldn't be more than about 20-30B, compiled. Or about 80 bytes of source.

  • Calum (unregistered)

    So how fast do these "optimal" solutions go?

    I've done an A* implementation in C++ which completes in 0.34 seconds. Is that good or bad?

  • Keith Brawner (unregistered)

    How fast your solution goes is highly dependent on your processor and how far away the solution is away from the goal.

    .34 seconds is about on par for an A*, IIRC. I want to say that I've seen .16 worst time for the 3x3. A better test, however, is to test your solution on a 21x21.

  • (cs)

    I'm too lazy to see if this works in all cases, so I'll do what MS does:

    Here's the public release, and it will be the richest and most secure Sliding Problem solution ever. (Service Pack 1 to follow)

    In SQL.

    SET NOCOUNT ON

    -- User defined variables DECLARE @GiveUp int -- When to give up DECLARE @OpeningPosition varchar(9)

    -- Making-life-easier variables DECLARE @ZeroPos int -- Current position of the space DECLARE @CurrVal varchar(255) -- The current board DECLARE @LastMove int -- The last move taken (so you don't just move the same piece over and over) DECLARE @moveNum int -- The current move number (loop variable)

    -- Play history DECLARE @CharBoard table (vals varchar(9), lastMove int, moveNum int identity (0,1) primary key) -- feel free to turn this into a perm table to use an index on vals

    -- Set variables here SET @GiveUp = 50 -- how many moves to try before the program gives up SET @OpeningPosition = '123456708' -- The initial position of the 3x3 board, from top left, with 0 being the empty space

    -- Initilize board

    INSERT INTO @CharBoard values(@OpeningPosition, 0)

    SET @LastMove = 0 set @moveNum = 0

    -- If we haven't given up, and a solved board doesn't exist yet WHILE @moveNum < @GiveUp and not exists (select top 1 1 from @Charboard where vals = '123456780' order by moveNum desc) BEGIN

    SELECT top 1 @CurrVal =  vals, @LastMove = lastMove, @MoveNum = moveNum from @Charboard order by moveNum desc
    SELECT @ZeroPos = CHARINDEX('0', @CurrVal)
    
    -- Order of preference of spot selection, most desirable to least
    -- Piece can be moved into it's own spot
    -- The closest piece to the spot can be moved (high wins ties) without being moved out of it's own spot
    -- The highest number piece moves
    
    -- use this to switch 0 and the value at position pos
    INSERT INTO @CharBoard (vals, lastMove)
    --set @moveNum = 99
    select top 1 replace(replace(replace(@CurrVal, val, 'X'), '0', val), 'X', '0'), val
    from
    (
    	select val, pos, abs(@ZeroPos-val) as distance,
    		case	when val = @ZeroPos then 1
    				when val = @LastMove then 4
    				when val = pos then 5
    				else 2
    			end as [desire]
    	from
    	(
    		SELECT cast(substring(@CurrVal, @ZeroPos-3,1) as int) as [Val], @ZeroPos-3 as [Pos]
    		UNION
    		SELECT cast(substring(@CurrVal, @ZeroPos+3,1) as int), @ZeroPos+3
    		UNION
    		SELECT case when @ZeroPos not in (1,4,7) then cast(substring(@CurrVal, @ZeroPos-1,1) as int) else 0 end, @ZeroPos-1
    		UNION
    		SELECT case when @zeroPos not in (3,6,9) then cast(substring(@CurrVal, @ZeroPos+1,1) as int) else 0 end, @ZeroPos+1
    	) side
    	where 
    			 val > 0
    ) desire
    order by desire, distance, val desc
    

    END

    select case when @MoveNum >= @GiveUp then 'Fuck it, I''m done' else 'Victory is mine!' end as [Result] select moveNum as [Move Number], lastMove as [Piece moved], vals as [Resulting board] from @CharBoard

  • Texas Jack (unregistered)

    Using breadth-first search:

    #include <string>
    #include <iostream>
    #include <queue>
    #include <set>
    #include <cstdio>
    #include <cmath>
    
    using namespace std;
    
    class Nine {
    
    public:
    
      typedef pair<Nine, string> bfsqitem_t;
      typedef queue<bfsqitem_t>  bfs_queue_t;
      typedef vector<bfsqitem_t>  bfs_vec_t;
    
      Nine(const string &in, size_t _dim=3) :
        dim(_dim),
        size(dim*dim),
        board(new char[size+1])
      {
        if (in.length() != size) {
          dim=size=0;
          return;
        }
        for (size_t i=0; i<size; i++) {
          board[i] = in.at(i);
          if (board[i]=='0')
    	zpos=i;
        }
        board[size]=0;
      }
    
      ~Nine() {
      }
    
      static string search(Nine &b) {
        set<string> seen;
        bfs_queue_t q;
        q.push( bfs_queue_t::value_type(b,"") );
        while (q.size()) {
          bfs_queue_t::value_type f = q.front();
          q.pop();
          
          bfs_vec_t nextq;
          try_moves(f, nextq);
    
          for (bfs_vec_t::iterator i=nextq.begin();
    	   i != nextq.end();
    	   i++) {
    	if (i->first.completed())
    	  return i->second;
    	if (seen.find(i->first.board) != seen.end()) 
    	  continue;
    	q.push(*i);
    	seen.insert(i->first.board);
          }
          
          
        }
        return "";
      }
    
      static void try_moves( const bfsqitem_t &f,
    			 bfs_vec_t &q ) {
        string how=f.second;    
        if (f.first.zpos % f.first.dim != 0) {
          q.push_back( bfs_vec_t::value_type(Nine(f.first, 
    					      f.first.zpos-1),
    					 how+'L') );
        }
    
        if ((f.first.zpos+1) % f.first.dim != 0) {
          q.push_back( bfs_vec_t::value_type(Nine(f.first, 
    					      f.first.zpos+1),
    					 how+'R') );
        }
    
        if (f.first.zpos >= f.first.dim) {
          q.push_back( bfs_vec_t::value_type(Nine(f.first, 
    					      f.first.zpos-f.first.dim),
    					 how+'U') );
        }
    
        if (f.first.zpos < f.first.size-f.first.dim) {
          q.push_back( bfs_vec_t::value_type(Nine(f.first, 
    					      f.first.zpos+f.first.dim),
    					 how+'D') );
        }
      }
    
    
      Nine(const Nine &other, int swap) :
        zpos(other.zpos),
        dim(other.dim),
        size(other.size),
        board(new char[size+1])
      {
        for (size_t i=0; i<size; i++) {
          board[i]=other.board[i];
        }
        board[zpos]=other.board[swap];
        board[swap]='0';
        zpos=swap;
        board[size]=0;
      }
    
      bool completed() {
        static const char* soln="123456789abcdefghijklmnopqrstuvwxyz";
        return ! strncmp(soln, board, size-1);
      }
    
      size_t zpos;
      size_t dim;
      size_t size;
      char *board;
    };
    
    
    int main (int argc, char *argv[]) {
      if (argc<2)
        exit(-1);
    
      Nine b(argv[1], (int)sqrt(strlen(argv[1])));
      cout << Nine::search(b) << endl;
      return 0;
    }
    </pre>
    

    Using best-first search:

    #include <string>
    #include <iostream>
    #include <queue>
    #include <set>
    #include <cstdio>
    #include <cmath>
    
    using namespace std;
    
    class NineSearchItem;
    
    class Nine {
    
    public:
    
      typedef vector<NineSearchItem>  bfs_vec_t;
    
      Nine(const string &in, size_t _dim=3) :
        dim(_dim),
        size(dim*dim),
        board(new char[size+1])
      {
        if (in.length() != size) {
          dim=size=0;
          return;
        }
        for (size_t i=0; i<size; i++) {
          board[i] = in.at(i);
          if (board[i]=='0')
    	zpos=i;
        }
        board[size]=0;
      }
    
      ~Nine() {
      }
    
      Nine(const Nine &other, int swap) :
        zpos(other.zpos),
        dim(other.dim),
        size(other.size),
        board(new char[size+1])
      {
        for (size_t i=0; i<size; i++) {
          board[i]=other.board[i];
        }
        board[zpos]=other.board[swap];
        board[swap]='0';
        zpos=swap;
        board[size]=0;
      }
    
      bool completed() {
        static const char* soln="123456789abcdefghijklmnopqrstuvwxyz";
        return ! strncmp(soln, board, size-1);
      }
    
      size_t zpos;
      size_t dim;
      size_t size;
      char *board;
    };
    
    class NineSearchItem : public Nine {
    public:
      typedef priority_queue<NineSearchItem> bfs_pq_t;
    
      NineSearchItem(const string &in,
    		 size_t _dim=3,
    		 string _how="") :
        Nine(in, _dim),
        how(_how)
      {
        fitness = eval_fitness();
      }
    
      NineSearchItem(const NineSearchItem &other,
    		 int swap,
    		 string _how)
        : Nine(other, swap),
          how(_how)
      {
        fitness = eval_fitness();
      }
    
      void try_moves( bfs_vec_t &q ) {
        if (zpos % dim != 0) {
          q.push_back( NineSearchItem(*this, 
    				  zpos-1,
    			  how+'L') );
        }
    
        if ((zpos+1) % dim != 0) {
          q.push_back( NineSearchItem(*this, 
    				  zpos+1,
    				  how+'R') );
        }
    
        if (zpos >= dim) {
          q.push_back( NineSearchItem(*this,
    				  zpos-dim,
    				  how+'U') );
        }
    
        if (zpos < size-dim) {
          q.push_back( NineSearchItem(*this,
    				  zpos+dim,
    				  how+'D') );
        }
      }
    
      int eval_fitness() {
        static const char* soln="123456789abcdefghijklmnopqrstuvwxyz";
        int f = 0;
        int d = dim;
        for (int i=0; i<(int)size; i++) {
          int place;
          if (board[i]=='0')
    	place=size-1;
          else
    	place=strchr(soln,board[i])-soln;
          f -= abs(i%d-place%d)+abs(i/d-place/d);
        }
        return f;
      }
    
      string search() {
        set<string> seen;
        bfs_pq_t q;
        q.push( *this );
        while (q.size()) {
          NineSearchItem f = q.top();
          q.pop();
          bfs_vec_t nextq;
          f.try_moves(nextq);
    
          for (bfs_vec_t::iterator i=nextq.begin();
    	   i != nextq.end();
    	   i++) {
    	if (i->completed())
    	  return i->how;
    	if (seen.find(i->board) != seen.end()) 
    	  continue;
    	q.push(*i);
    	seen.insert(i->board);
          }
          
        }
        return "";
      }
    
      bool operator< (const NineSearchItem &other) const {
        return (fitness == other.fitness) ?
          (how.length() > other.how.length()) : 
          (fitness < other.fitness);
      }
    
      string how;
      int fitness;
    
    };
    
    int main (int argc, char *argv[]) {
      if (argc<2)
        exit(-1);
      
      NineSearchItem b(argv[1], (int)sqrt(strlen(argv[1])));
      cout << b.search() << endl;
      return 0;
    }
    
    

Leave a comment on “Sliding Around”

Log In or post as a guest

Replying to comment #:

« Return to Article