Stringing a Pearl Necklace

Question

Overview

Pearls (or Masyu) is a logic game played on a grid. There are black and white pearls placed on the grid. The object is to form a single, closed loop that travels through each pearl using only straight line segments and right angles.

There are some rules that govern how the loop interacts with pearls:

• White pearls must be traveled straight through, but the loop must turn in the previous and/or next cell in its path.
• Black pearls must be turned upon, but the loop must travel straight through the next and previous cells in its path.
• The loop must not cross or otherwise intersect itself. All cells have exactly zero or two loop entry/exits.

An example puzzle from Wikipedia (and its solution):

Your objective is to solve a given puzzle. If there are multiple possible solutions, it does not matter which one you give.

Input

Input will be an unsolved square grid. The example shown above would look like this:

..w.w.....
....w...b.
..b.b.w...
...w..w...
b....w...w
..w....w..
..b...w...
w...b....w
......ww..
..b......b

w is a white pearl, b is a black pearl, and . is an empty cell.

Assume input is valid. This means it is well formed, and at least one solution is possible. All valid puzzles are at least 3x3, and contain at least one pearl.

Output

Output is a string of coordinates representing the path. The upper left corner of the grid is 0 0, upper right is n-1 0, where n is the width of the grid.

A path is simply a series of ordered coordinates:

x1 y1 x2 y2 x3 y3 ...

The path is assumed to be closed, so you do not need to repeat the first coordinate at the end, but there is no penalty for doing so.

The output should consist of at least all corners in the path. You do not have to output every cell on the path if there is no turn. For instance, the output for the example could start with:

1 0 5 0 5 1 ...

or

1 0 2 0 3 0 4 0 5 0 5 1 ...

Output should not contain any cell not in the path. You may start at any cell in the path.

---

Snippet

Here's a snippet you can use to visualize your solution. Just paste in the grid you're working on and the path you output. I'm aware that it's painful to look at my code, so I just suggest you don't ;)

function draw(){document.getElementById("output").innerHTML=gridSVG+pathSVG}function drawCoords(){coords=document.getElementById("coords").value;var e=prefix+'<path fill="none" d="';if(nums=coords.match(/[^\s]+/g),!(nums.length<2)){for(e+="M "+(nums[0]*scale+offset)+" "+(nums[1]*scale+offset),i=2;i<nums.length;i+=2)e+=" L "+(nums[i]*scale+offset)+" "+(nums[i+1]*scale+offset);e+=" L "+(nums[0]*scale+offset)+" "+(nums[1]*scale+offset),e+='" stroke="black" stroke-width="2"/>'+suffix,pathSVG=e,draw()}}function drawPath(){path=document.getElementById("path").value;var e=prefix+'<path fill="none" d="'+path+'" stroke="black" stroke-width="2"/>'+suffix;pathSVG=e,draw()}function drawGrid(){grid=document.getElementById("grid").value;var e=prefix;for(lines=grid.match(/[^\s]+/g),width=lines[0].length*scale,height=lines.length*scale,i=0;i<=lines.length;i++)e+='<path stroke="gray" d="M 0 '+i*scale+" L "+width+" "+i*scale+'"/>',e+='<path stroke="gray" d="M '+i*scale+" 0 L "+i*scale+" "+height+'"/>';for(j=0;j<lines.length;j++)for(line=lines[j],i=0;i<line.length;i++)"w"==line.charAt(i)&&(e+='<circle cx="'+(i*scale+offset)+'" cy="'+(j*scale+offset)+'" r="'+.8*offset+'" stroke="black" fill="white"/>'),"b"==line.charAt(i)&&(e+='<circle cx="'+(i*scale+offset)+'" cy="'+(j*scale+offset)+'" r="'+.8*offset+'" stroke="black" fill="black"/>');e+=suffix,gridSVG=e,draw()}var prefix='<svg height="400" width="400">',suffix="</svg>",scale=30,offset=scale/2,pathSVG="",gridSVG="";

svg{position: absolute;left: 50px;}

Paste grid input here<br><input id="grid" type="textarea" size="80" oninput='drawGrid()' /><br><br>Paste path output here<br><input id="coords" type="textarea" size="80" oninput='drawCoords()' /><br><br><div id="output"></div>

---

Test Cases

These test cases show one possible output for each input (except the last, which is shown unsolved). There may be other valid paths, you might go CW or CCW or start at a different point, etc. Solutions should be able to solve the test cases in seconds/minutes/hours, not days/weeks/eons.

...
w..
..b

0 0 1 0 2 0 2 1 2 2 1 2 0 2 0 1

.wb..b
......
..b...
w.ww..
......
b....b

0 0 2 0 2 2 4 2 4 1 3 1 3 0 5 0 5 5 3 5 3 4 4 4 4 3 1 3 1 4 2 4 2 5 0 5 0 2 1 2 1 1 0 1

.....w.b.w..
ww..b...b...
.w.....b....
...wbww..b.b
....b.......
w.w.........
..w......b.b
.....bb.....
.....b.....w
w.ww..b.....
...w......w.
b..w.....b..

Answer 1

C, 590 640 760 880 963 1018

Brute force is quite fast for this. The 12x12 test runs under 10ms. Knowing that could opt for some language more appropriate for golfing.

I don't assume the board is square as the larger puzzles tend not to be square.

The W define sets the limit on the board dimensions. The actual limit is smaller W - 2 as I use extra rows for borders to avoid boundary checks.

#define W 40
int Y,X,T,P,Q[W*W],D[]={-W,-1,1,W};char B[W*W],K[W*W],I[W];
t(x,d,s){for(P=0;B[x];x*=x!=*Q)s-=K[Q[P++]=x]-1,
d=(54202126527627840ll>>2*(d*7+B[x+=D[d]]%8))&3;return x?0:s;}
m(x){int c=K[x],u=B[x-W],U=u&7,l=B[x-1],L=l&7,r=0,
i=U!=3&U!=4&L!=2&L!=4,o=(39>>U)&1?57:70;o&=(52>>L)&1?42:85;
if(x/W>Y+1){for(;P--;)printf("%d %d ",Q[P]%W-1,Q[P]/W-1);exit(0);}
if(u>7)o&=U>4?~64:~6;if(l>7)o&=L>4?~32:~10;
for(o&=c?c>1?c>2?(r=8*i,96):(r=8,i*30):~0:1;o;r++,o/=2)
if(o&1)if(B[x]=r,r%8!=1||!t(x,0,T))m(x+1);B[x]=0;}
main(){for(;gets(I);Y++)for(X=0;I[X];X++)
T+=(K[X+1+Y*W+W]=I[X]/36)-1;m(W);}

Test me.

Here is a more challenging test case:

.b.....b.b.......b..
.....w.....b.w....w.
....w.........w.....
..bb.....w.w.b....b.
.w.....b..b......w..
.....b..............
.b..........b.b..bw.
....w....w....b...w.
.......bb...b...w...
..b.......w.........
....b.w.....w.b...b.
w...b...w..b.w.w....
b.w....w............
...b.w......b..b...b
w......w.b.ww.......
.b....b..........b..
....b....w.bb.w...w.
w..b......w...b.....
b.....w.........w...
...b....w..w..b...w.
...................b
.b..w..bb.b..b..w...
........w......b....
b....w......b..b.b..
...b..bb.w.w........
...b.......w......w.
w...w.b.w.....b....b
............w..ww...
..b.b..b....b.......
....b.........w...b.
.ww.......b.w.w.....
b.....w..w.w...b....
....ww..b.b.w....w.w
.............bb..w..
.b....w.b.b........w
....bw..........b...

I was lucky my code finds the solution quite early in the run (<5min), but the full search takes much longer (67min).

Answer 2

Python - 1669

Still pretty long, but fast enough to run the last example in under a second on my computer. It's probably possible to make shorter at the cost of speed, but for now it is pretty much equivalent to the ungolfed code.

Example output for last test case:

0 11 1 11 2 11 3 11 4 11 4 10 3 10 2 10 1 10 1 9 2 9 3 9 4 9 4 8 3 8 3 7 4 7 5 7 5 6 5 5 6 5 6 6 6 7 7 7 8 7 8 8 7 8 6 8 5 8 5 9 5 10 5 11 6 11 6 10 6 9 7 9 8 9 8 10 7 10 7 11 8 11 9 11 9 10 9 9 10 9 10 10 10 11 11 11 11 10 11 9 11 8 11 7 10 7 10 8 9 8 9 7 9 6 10 6 11 6 11 5 11 4 11 3 10 3 9 3 9 4 9 5 8 5 8 4 8 3 8 2 8 1 9 1 10 1 10 0 9 0 8 0 7 0 7 1 7 2 6 2 5 2 5 1 6 1 6 0 5 0 4 0 3 0 2 0 2 1 3 1 4 1 4 2 4 3 5 3 6 3 7 3 7 4 6 4 5 4 4 4 4 5 4 6 3 6 3 5 3 4 3 3 3 2 2 2 2 3 1 3 1 2 1 1 1 0 0 0 0 1 0 2 0 3 0 4 0 5 0 6 1 6 1 5 1 4 2 4 2 5 2 6 2 7 1 7 1 8 0 8 0 9 0 10

Code:

I=raw_input().split('\n');X=len(I[0]);Y=len(I);R=range
def S(g=0,c=0,x=0,y=0):
    if y>=Y:return 0
    if g==0:g=[[-1]*X for i in R(Y)];c=[[-1]*X for i in R(Y)]
    o={'.':set(R(7)),'w':{1,2},'b':{3,4,5,6}}[I[y][x]].copy()
    o&={0,1,3,4}if y<1 or g[y-1][x]in[0,1,5,6]else{2,5,6}
    o&={0,2,4,5}if x<1 or g[y][x-1]in[0,2,3,6]else{1,3,6}
    if y>Y-2:o&={0,1,5,6}
    if x>X-2:o&={0,2,3,6}
    if y>0 and g[y-1][x]in[2,3,4]:
        if'b'==I[y][x]and g[y-1][x]!=2:return 0
        if'b'==I[y-1][x]:o&={2}
        elif'w'==I[y-1][x]and g[y-2][x]==2:o&={5,6}
    if x>0 and g[y][x-1]in[1,4,5]:
        if'b'==I[y][x]and g[y][x-1]!=1:return 0
        if'b'==I[y][x-1]:o&={1}
        elif'w'==I[y][x-1]and g[y][x-2]==1:o&={3,6}
    h=[r[:]for r in c]
    if y>0 and g[y-1][x]in[2,3,4]:
        if x>0 and g[y][x-1]in[1,4,5]:
            if c[y-1][x]==c[y][x-1]:
                if(6 not in o)+any(any(i!=c[y-1][x]and i!=-1 for i in r)for r in c)+any(I[v][u]!='.'and(v>y)+(u>x)for v in R(y,Y)for u in R(X)):return 0
                g[y][x]=6
                for v in R(y,Y):
                    for u in R(X):
                        if v!=y or u>x:g[v][u]=0
                for y in R(Y):
                    for x in R(X):
                        if g[y][x]>0:break
                f=[];d=-1;u,v=p,q=x,y
                while(u,v)!=(p,q)or-1==d:f+=[u,v];d=([0,{0,2},{1,3},{2,3},{0,3},{0,1},{1,2}][g[v][u]]-{(d+2)%4}).pop();i,j={0:(u+1,v),1:(u,v-1),2:(u-1,v),3:(u,v+1)}[d];u,v=i,j
                return f
            else:
                for v in R(y+1):
                    for u in R(X):
                        if h[v][u]==c[y][x-1]:h[v][u]=c[y-1][x]
                h[y][x]=c[y-1][x]
        else:h[y][x]=c[y-1][x]
    elif x>0 and g[y][x-1]in[1,4,5]:h[y][x]=c[y][x-1]
    else:h[y][x]=max(max(r)for r in c)+1
    for n in sorted(list(o))[::-1]:
        if n==0:h[y][x]=-1
        if x>X-2:i,j=0,y+1
        else:i,j=x+1,y
        g[y][x]=n;r=S(g,h,i,j)
        if r!=0:return r
    return 0
for i in S():print i,

Ungolfed:

class Grid:
    def __init__(self,input):
        self.input = input.split('\n')
        self.x = len(self.input[0])
        self.y = len(self.input)
        self.options = {'.':{0,1,2,3,4,5,6},'w':{1,2},'b':{3,4,5,6}}

    def convert(self,grid):
        directions = [None,{0,2},{1,3},{2,3},{0,3},{0,1},{1,2}]

        for y in range(self.y):
            for x in range(self.x):
                if grid[y][x] != 0:
                    break

        chain = []
        start_pos = (x,y)
        dir = -1
        pos = start_pos
        while dir == -1 or pos != start_pos:
            chain.extend(pos)
            x,y = pos
            next_dir = (directions[grid[y][x]]-{(dir+2)%4}).pop()
            if next_dir == 0: nx,ny = x+1,y
            elif next_dir == 1: nx,ny = x,y-1
            elif next_dir == 2: nx,ny = x-1,y
            elif next_dir == 3: nx,ny = x,y+1
            dir = next_dir
            pos = (nx,ny)

        return chain

    def solve(self,grid=None,chain_ids=None,pos=(0,0)):
        x,y = pos
        if y >= self.y:
            return None

        if grid is None:
            grid = [[-1]*self.x for i in range(self.y)]
        if chain_ids is None:
            chain_ids = [[-1]*self.x for i in range(self.y)]

        options = self.options[self.input[y][x]].copy()
        if y == 0 or grid[y-1][x] in [0,1,5,6]:
            options &= {0,1,3,4}
        else:
            options &= {2,5,6}
        if y == self.y-1:
            options &= {0,1,5,6}

        if x == 0 or grid[y][x-1] in [0,2,3,6]:
            options &= {0,2,4,5}
        else:
            options &= {1,3,6}
        if x == self.x-1:
            options &= {0,2,3,6}

        if y != 0 and grid[y-1][x] in [2,3,4]:
            if self.input[y][x] == 'b' and grid[y-1][x] != 2:
                return None
            if self.input[y-1][x] == 'b':
                options &= {2}
            elif self.input[y-1][x] == 'w':
                if grid[y-2][x] == 2:
                    options &= {5,6}
        if x != 0 and grid[y][x-1] in [1,4,5]:
            if self.input[y][x] == 'b' and grid[y][x-1] != 1:
                return None
            if self.input[y][x-1] == 'b':
                options &= {1}
            elif self.input[y][x-1] == 'w':
                if grid[y][x-2] == 1:
                    options &= {3,6}


        new_chain_ids = [[i for i in row] for row in chain_ids]
        if y != 0 and grid[y-1][x] in [2,3,4]:
            if x != 0 and grid[y][x-1] in [1,4,5]:

                if chain_ids[y-1][x] == chain_ids[y][x-1]:
                    if 6 not in options:
                        return None

                    if any(any(i != chain_ids[y-1][x] and i != -1 for i in row) for row in chain_ids) or \
                    any(self.input[v][u] != '.' and (v!=y or u>x) for v in range(y,self.y) for u in range(self.x)):
                        return None

                    grid[y][x] = 6
                    for v in range(y,self.y):
                        for u in range(self.x):
                            if v != y or u > x: 
                                grid[v][u] = 0

                    return self.convert(grid)

                else:
                    for v in range(y+1):
                        for u in range(self.x):
                            if new_chain_ids[v][u] == chain_ids[y][x-1]:
                                new_chain_ids[v][u] = chain_ids[y-1][x]
                    new_chain_ids[y][x] = chain_ids[y-1][x]

            else:
                new_chain_ids[y][x] = chain_ids[y-1][x]
        elif x != 0 and grid[y][x-1] in [1,4,5]:
            new_chain_ids[y][x] = chain_ids[y][x-1]
        else:
            new_chain_ids[y][x] = max(max(row) for row in chain_ids)+1

        for n in sorted(list(options),key=lambda n: -n):
            grid[y][x] = n
            if n == 0:
                new_chain_ids[y][x] = -1

            if x == self.x-1:
                nx,ny = 0,y+1
            else:
                nx,ny = x+1,y

            result = self.solve(grid,new_chain_ids,(nx,ny))
            if result is not None:
                return result

input = """

.....w.b.w..
ww..b...b...
.w.....b....
...wbww..b.b
....b.......
w.w.........
..w......b.b
.....bb.....
.....b.....w
w.ww..b.....
...w......w.
b..w.....b..

""".strip()

def print_grid(grid):
    for y,row in enumerate(grid):
        s = ""
        for i in row:
            s += {-1:'xxx',0:'   ',1:'   ',2:' | ',3:'   ',4:'   ',5:' | ',6:' | '}[i]
        s += '\n'
        for x,i in enumerate(row):
            s += {-1:'x%sx',0:' %s ',1:'-%s-',2:' %s ',3:'-%s ',4:' %s-',5:' %s-',6:'-%s '}[i] % input.split('\n')[y][x]
        s += '\n'
        for i in row:
            s += {-1:'xxx',0:'   ',1:'   ',2:' | ',3:' | ',4:' | ',5:'   ',6:'   '}[i]
        s += '\n'
        print s

result = Grid(input).solve()
print result

Answer 3

Lua, 830 810 765 752 739 729 710

Runs board1 and board2 just fine, but takes a while on board3.

It could save 9 bytes by outputting every path instead of just the first...

b={}s={0,0,0}R=table.insert Z=unpack for l in io.lines()do w=#l for i=1,w do
c=({b=1,w=2,['.']=3})[l:sub(i,i)]R(b,c)s[c]=s[c]+1 end end h=#b/w for e=0,w*h-1
do function g(p,d,X,t)local function G(I,r)T={Z(t)}a=b[I+1]T[a]=T[a]+1
P={Z(p)}D={Z(d)}R(P,I%w)R(P,I/w-I/w%1)R(D,r)l=#D for U=2,#p,2 do if
I==p[U-1]+w*p[U]then return end end if I==e then if T[1]==s[1]and T[2]==s[2]then
for k=1,l do K=D[k]M=D[(k-2)%l+1]N=D[k%l+1]O=D[(k+1)%l+1]if({K==N or K~=M or
N~=O,K~=N or(K==M and N==O)})[b[1+P[2*k-1]+w*P[2*k]]]then return end end
os.exit(print(table.concat(P,' ')))end else g(P,D,I,T)end end _=X%w<w-1 and
G(X+1,1)_=X/w-X/w%1<h-1 and G(X+w,2)_=X%w>0 and G(X-1,3)_=X/w-X/w%1>0 and
G(X-w,4)end g({},{},e,{0,0,0})end