Optimally solve the Flux Puzzle

Question

Flux is very similar to the Fifteen Puzzle.

However, instead of numbers, the squares are colors.

• There are 4 colors: Red, Yellow, Blue, and Gray.
  • There are exactly 4 red squares, 4 yellow squares, 2 blue squares, 1 gray square, and 1 empty square.
• The grid has 3 rows and 4 columns
• A grid configuration is solved when the top row is exactly the same as the bottom row.
• The middle row is not relevant when considering whether the board is solved.
• You do not have to handle invalid input. Trust that there will be the correct number of each of the input symbols.

Input

• You must accept an input of twelve of these characters that use these symbols to represent a square on the board:
  • RYGB_
• These input characters must be interpreted to go across, then down.
• It is your choice whether you require some other character (newline, EOF, whatever) to terminate input, or just go as soon as you've received 12 characters.

Example:

YRGYB_BRRYYR

which corresponds to to the board:

YRGY
B_BR
RYYR

Output

• You must output the moves required for an OPTIMAL solution
• These will use the characters LRUD for Left, Right, Up, Down. This is considered to be the "piece moves to the left", not the "emptiness moves to the left"

Example:

LURDRDLULDLU

And then print out the resulting board. For the example we've used so far:

RBYR
YYG_
RBYR

Other rules

• Your program must run in under 15 seconds or it is disqualified.
  • Make sure to try it with the following board: RRRRBG_BYYYY
  • That board, with it's three symmetries, is the "hardest" possible board.
• You may not use any external resources, or have any input data files.

Some stats

• There are exactly 415,800 possible boards
• There are exactly 360 "solution" boards
• My program that I wrote to test this out runs in about 2 seconds in Java, without much optimization.
  • This program, with minimal golfing, is 1364 bytes.

Scoring

• This is code-golf, fewest characters that meets the other requirements wins!

Answer 1

Smalltalk 497

|b R M s g a|
b:=Stdin nextLine.R:='D--R-L--U'.
M:=#((6 9)(4 6 9)(4 6 9)(4 9)(1 6 9)(1 4 6 9)(1 4 6 9)(1 4 9)(6 1)(4 6 1)(4 6 1)(4 1)).
s:=Set new.q:=OrderedCollection new.
a:=[:p :m|(s includes:p)ifFalse:[s add:p.q add:p->m]].
a value:b value:''.
[|x i n p|
x:=q removeFirst.p:=x key.i:=(p indexOf:$_).
(M at:i)do:[:m||v|
n:=p copy.n at:i put:(p at:i+m-5);at:i+m-5put:$_.
v:=(x value,(R at:m)).
(n to:4)=(n from:9)ifTrue:[
v printCR.(n splitForSize:4)map:#printCR.^self].
a value:n value:v]]loop.

Input:

YRGYB_BRRYYR

Output:

DLURRULDDLLU
YBYR
RGR_
YBYR

Exec. Time (bytecode, not jitted): 100ms

Input:

RRRRBG_BYYYY

Output:

DRRUULLDLURDDRRULULD
YBRR
GY_Y
YBRR

Exec. Time 2s unjitted; 0.8s jitted (most time spent in collection code)

Here is an ungolfed version for readability:

|b R M s g add|
b:=Stdin nextLine.
R:='D--R-L--U'.
M:=#((6 9)(4 6 9)(4 6 9)(4 9)
     (1 6 9)(1 4 6 9)(1 4 6 9)(1 4 9)
     (6 1)(4 6 1)(4 6 1)(4 1)).
s := Set new.
queue := OrderedCollection new.

add := [:p :m |
  (s includes:p) ifFalse:[
    s add:p.
    queue add:(p->m).
  ]].

add value:b value:''.

[
  |x i n p|

  x := queue removeFirst.
  p := x key.
  i := (p indexOf:$_).
  (M at:i) do:[:m |
    |v|
    n := p copy.
    n at:i put:(p at:i+m-5); at:i+m-5 put:$_.
    v:=(x value,(R at:m)).
    (n to:4)=(n from:9) ifTrue:[
      v printCR.
      (n splitForSize:4) map:#printCR.
      ^ self
    ].
    add value:n value:v]
] loop.

Answer 2

Python 372

This was longer than I expected, I might go back later and see if I can optimize more. It uses a pretty inefficient method of brute-forcing the answer, but it seems to consistently run at no more than 8 seconds on my relatively old laptop.

A=lambda s,i,n:s[:i]+n+s[i+1:]
def M(b):                  
 i=b.find('_')
 for d,n in([('L',i+1)]if i%4<3 else[])+([('R',i-1)]if i%4>0 else[])+([('D',i-4)]if i>4 else[])+([('U',i+4)]if i<8 else[]):yield d,A(A(b,i,b[n]),n,'_')
def F():
 c=[('',raw_input())]
 while 1:
    for (m,b)in c:
     if b[:4]==b[8:]:return m,b
    c=[(m+d,n)for(m,b)in c for(d,n)in M(b)]
print F()

Answer 3

Java 1364

I golfed this some but I'm sure there's plenty more I could do. For example I close the input stream which is not necessary ;) I just wanted to put something up.

import java.util.*;class F{enum D{R{B b(B i){return i.z==3?null:g(i,1);}},L{B b(B i){return i.z==0?null:g(i,-1);}},D{B b(B i){return i.y==2?null:g(i,4);}},U{B b(B i){return i.y==0?null:g(i,-4);}};abstract B b(B i);B g(B i,int f){f+=4*i.y+i.z;char[]s=i.s.toCharArray();s[i.e]=s[f];s[f]='_';return w.get(new String(s));}}enum C{_,G,B,R,Y;}class B{C[][]a=new C[3][4];String s;int y,z,e,c;B p;D d;B(String p){int i,j,q;for(i=0;i<3;i++){for(j=0;j<4;j++){q=4*i+j;a[i][j]=C.valueOf(p.substring(q,q+1));if(a[i][j]==C._){y=i;z=j;e=q;}}}s=p;}boolean v(){return Arrays.equals(a[0],a[2]);}void p(B b,D n){p=b;d=n;c=p.c+1;}String g(){String u="\n";for(int i=0;i<3;i++,u+="\n")for(int j=0;j<4;j++)u+=a[i][j];return u;}}Set<B>b=new HashSet<B>(),p;static Map<String,B>w=new HashMap<>();void p(String f,String s){int n=s.length();if(n==0){B o=new B(f);w.put(f,o);if(o.v())b.add(o);}else{Set e=new HashSet();for(int i=0;i<n;i++){char c=s.charAt(i);if(!e.contains(c)){p(f+c,s.substring(0,i)+s.substring(i+1,n));e.add(c);}}}}public static void main(String[]a){new F().r();}void r(){Scanner c=new Scanner(System.in);String t=c.nextLine();p("",t);for(int i=0;i<20;i++,b=p){p=new HashSet<>(b);for(B o:b)if(o.c==i)for(D d:D.values()){B n=d.b(o);if(n!=null&&!p.contains(n)){n.p(o,d);p.add(n);}}}B q=w.get(t);while(!q.v()){System.out.print(q.d);q=q.p;}System.out.println(q.g());c.close();}}

Ungolfed:

import java.util.*;

class F {
    enum D {
        R {
            B b(B i) {
                return i.z == 3 ? null : g(i, 1);
            }
        },
        L {
            B b(B i) {
                return i.z == 0 ? null : g(i, -1);
            }
        },
        D {
            B b(B i) {
                return i.y == 2 ? null : g(i, 4);
            }
        }, 
        U {
            B b(B i) {
                return i.y == 0 ? null : g(i, -4);
            }
        };
        
        abstract B b(B i);

        B g(B i, int f) {
            f += 4*i.y + i.z;
            char[] s = i.s.toCharArray();
            s[i.e] = s[f];
            s[f] = '_';
            
            return w.get(new String(s));
        }
    }
    
    enum C {
        _, G, B, R, Y;
    }
    
    class B {
        C[][] a = new C[3][4];
        String s;
        
        int y,z,e,c;
        
        B p;
        D d;
        
        B(String p) {
            int i,j,q;
            for(i = 0; i < 3; i++) {
                for(j = 0; j < 4; j++) {
                    q=4*i+j;
                    a[i][j] = C.valueOf(p.substring(q,q+1));
                    if(a[i][j] == C._) {
                        y = i;
                        z = j;
                        e = q;
                    }
                }
            }

            s = p;
        }
        
        boolean v() {
            return Arrays.equals(a[0], a[2]);
        }
        
        void p(B b, D n) {
            p = b;
            d = n;
            c = p.c + 1;
        }
        
        String g() {
            String u = "\n";
            for(int i = 0; i < 3; i++,u+="\n")for(int j = 0; j < 4; j++) u += a[i][j];
            return u;
        }
    }
    
    Set<B> b = new HashSet<B>(),p;
    static Map<String, B> w = new HashMap<>();
    
    void p(String f, String s) {
        int n = s.length();
        if (n == 0) {
            B o = new B(f);
            w.put(f, o);
            if(o.v()) b.add(o);
        }
        else {
            Set e = new HashSet();
            for (int i = 0; i < n; i++) {
                char c = s.charAt(i);
                if(!e.contains(c)) {
                    p(f + c, s.substring(0, i) + s.substring(i+1, n));
                    e.add(c);
                }
            }
        }
    }
    
    public static void main(String[] a) {
        new F().r();
    }
    
    void r() {
        Scanner c = new Scanner(System.in);
        String t = c.nextLine();
        
        p("", t);

        for(int i = 0; i < 20; i++, b=p) {
            p = new HashSet<>(b);
            
            for(B o : b)
                if(o.c == i)
                    for(D d : D.values()) {
                        B n = d.b(o);
                        if(n != null && !p.contains(n)) {
                            n.p(o, d);
                            p.add(n);
                        }
                    }
        }

        B q = w.get(t);
        while(!q.v()) {
            System.out.print(q.d);
            q = q.p;
        }
        System.out.println(q.g());
            
        c.close();
    }
}