1 of 12
nutki
  • 3.7k
  • 10
  • 12

C, 1021

Brute force is quite fast for this. The 12x12 test runs under 10ms. Still can be golfed to get to under 1K chars.

int Y,X,T;char B[32][32],K[32][32],Ks[32][32],px[2048];
int tr(int x,int y){int i=0,d=0;
for(;B[x][y];i++){px[i*2]=x;px[i*2+1]=y;x+=(d==2)-(d==1);y+=(d==3)-(d==0);
d="XXX12X0XX0X31XX0X3X2XX12XXX3"[d*7+B[x][y]]-'0';
if(x==px[0]&&y==px[1])return i;
}return T;}
m(int x,int y) {
int i,o,c=K[x][y];
if(y>Y){for(i=0;i<T*2;i++)printf("%d ",px[i]-1);return;}
o=((39>>B[x][y-1])&1?57:70)&((52>>B[x-1][y])&1?42:85);
if(x==X)o&=75;
if(y==Y)o&=39;
if(c==2)o&=96;
if(K[x][y-1]==2)o&=~64;
if(K[x-1][y]==2)o&=~32;
if(c==1)o&=30;
if(c==1&&(B[x][y-1]==3||B[x][y-1]==4))o=0; 
if(c==1&&(B[x-1][y]==2||B[x-1][y]==4))o=0;
if(K[x][y-1]==1)o&=~6;
if(K[x-1][y]==1)o&=~10;
for(i=0;i<7;i++)if(o&(1<<i)){
B[x][y]=i;
if(i==1&&T!=tr(x,y))continue; 
if(c==2&&(i==5&&B[x-1][y]!=5||i==6&&B[x][y-1]!=6))K[x][y]=0;
T+=i&&!c;
x==X?m(1,y+1):m(x+1,y);
T-=i&&!c;
K[x][y]=c;
}
B[x][y]=0;
}
main(){int i,j;for(;gets(Ks[Y]);Y++);X=strlen(*Ks);
for(i=1;i<=Y;i++){for(j=1;j<=X;j++){
K[j][i]=Ks[i-1][j-1]=='w'?2:Ks[i-1][j-1]=='b';
T+=K[j][i]>0;
}}m(1,1);return 0;}

Test me.

nutki
  • 3.7k
  • 10
  • 12