# Stringing a Pearl Necklace

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

• You didn't put the solution for the last test case... – mbomb007 Apr 20 '15 at 21:00
• @mbomb007 Correct. – Geobits Apr 20 '15 at 21:47
• So there's no solution? – mbomb007 Apr 21 '15 at 13:45
• There is a solution. I left it open so answers would have something to show for their effort. Also, it may help to solve a puzzle or two by hand to get a feel for the rules, and that's hard to do if all the examples are pre-solved. – Geobits Apr 21 '15 at 13:47
• Is a grid 2x2 or larger grid with no Pearls considered valid (second sentence suggests not, and the point about the input being unsolved (if there are no unstrung pearls, it must be solved))? If so, would you expect a loop, just with no pearls in it, or what exactly? Presumably there is no requirement for any of a particular color to be present? – VisualMelon Apr 22 '15 at 9:15

# 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).

• s/Brute force is quite fast/C is quite fast/ – kirbyfan64sos Apr 27 '15 at 20:36

# 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

• @Geobits Oh it seems I didn't read the rules carefully enough. Updated answer with what I believe is correct now – KSab Apr 22 '15 at 18:31
• The new path looks good to me! +1 – Geobits Apr 22 '15 at 18:35

# Lua, 830810765752739729 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