Make a move on a Go board

Question

You are given a board position for a Go game and a move to play. You need to output whether the move is legal or not, and the new board position if it is legal.

A brief explanation of Go moves: the game consists of alternatively placing black and white pieces ("stones") in empty places on a square board. Sets of pieces of the same color that are connected to each other (4-way) are called groups. Empty places on the board that are adjacent to a group (also 4-way) are considered to be that group's "liberties". A group with 0 liberties is captured (removed from the board). A move that would cause its own group to be captured ("suicide") is illegal, unless it is capturing one or more opponent's groups (gaining liberties in the process so it is not actually captured).

For those concerned, you don't need to deal with ko (and superko), i.e. you can assume a ko capture is legal. If you don't know what that means, just follow the rules above and it will be fine.

Input: a number n between 2 and 19 (inclusive) representing the board size, followed by n lines of n numbers between 0 and 2 (inclusive) representing the board position, followed by 3 numbers separated by space, representing the move to make. In the board position, 0 means empty place, 1 means black stone and 2 means white stone. The move gives the column, the row and the color (1 or 2) of the stone to place. The column and row are 0-based, ranging from 0 to n-1 (inclusive) and counted in the same order as the board input.

You can assume that the given board position is legal (all groups have at least one liberty).

Output: a line containing 1 or 0 (or true/false if you prefer) if the move is legal or not, followed (only in case of a legal move) by the new board position in the same format as the input.

Score: Number of bytes of the complete source code, smaller is better. 20% additional penalty for use of non-ascii characters, and 20% additional penalty if your code can't be tested in Linux using freely available software.

Rules: No network connections and no 3rd party libraries. Your program should use the standard input and output streams, or the standard equivalent for your programming language.

Examples:

1) Input:

2
10
01
1 0 2

Output:

0

2) Input:

2
10
11
1 0 2

Output:

1
02
00

3) Input:

5
22122
22021
11211
02120
00120
2 1 1

Output:

1
00100
00101
11011
02120
00120

4) Input:

6
000000
011221
121121
122221
011110
000000
4 0 1

Output:

1
000010
011221
121121
122221
011110
000000

Answer 1

Python 3 (557 504 488)

import sys
s=sys.stdin
M=int(next(s))+1
j=Z=M*M-M
S=s.read(Z)
P=0
b=[0]*3
while j>0:j-=1+(j%M<1);b[int(S[j])]|=1<<j;P|=1<<j
N=lambda x:(x<<1|x>>1|x<<M|x>>M)&P&~x
def h(a,b):t=a|N(a)&b;return h(t,b)if t!=a else a
c,r,m=map(int,next(s).split())
o=m%2+1
p=1<<M*r+c
b[m]|=p
for n in(p<<1,p>>1,p<<M,p>>M):
 e=h(n&P,b[o])
 if~b[m]&N(e)<1<=n&b[o]:b[o]&=~e
_,B,W=b
g=~b[o]&N(h(p,b[m]))>=1>~_&p
print(+g)
q=''
while j<Z:
 r=1<<j
 if g*j%M>M-2:print(q);q=''
 else:q+='012E'[(r&B>0)+(r&W>0)*2]
 j+=1

Uses 3 bitfields to represent the board - one each for black, white, and empty spaces. Makes the find neighbors N and get chain h operations very concise.

An ungolfed version with lots of comments: https://gist.github.com/airfrog/8429006

Answer 2

Python (9121004)

def o():
 n=int(raw_input(''))
 i=[raw_input('') for r in range(n+1)]
 b=[map(int,list(r)) for r in i[:n]]
 u,v,w=map(int,i[n].split(' '))
 if b[v][u]!=0:return 0
 b[v][u]=w
 if w==1:q=2
 elif w==2:q=1
 else:return 0
 f=[[],[],[]]
 h=[[],[],[]]
 g=[range(z*n,(z+1)*n) for z in range(n)]
 d=[(1,0),(-1,0),(0,1),(0,-1)]
 m=lambda z:max(0,min(n-1,z))
 t=[0,1,2,0,1]
 for j,s in enumerate(t):
  for r in range(n):
   for c in range(n):
    for y,x in map(lambda p:(m(r+p[0]),m(c+p[1])),d):
     if s==0:
      if b[y][x]==b[r][c]:
       if g[y][x]!=min(g[y][x],g[r][c]):
        t.insert(j+1,0)
       g[y][x]=g[r][c]=min(g[y][x],g[r][c])
     elif s==1:
      if g[r][c] not in h[b[r][c]]:
       h[b[r][c]].append(g[r][c])
      if b[y][x]==0 and g[r][c] not in f[b[r][c]]:
       f[b[r][c]].append(g[r][c])
    if s==2:
     if b[r][c]==q and g[r][c] not in f[b[r][c]]:
      b[r][c]=0
 h[w].sort()
 f[w].sort()
 if h[w]!=f[w]:return 0
 return "1\n"+'\n'.join([''.join(map(str,r)) for r in b])
print o()

Walk through: parse input, check if move is on an empty spot, make move, init "group" grid, simplify/minimize group grid by checking color of adjacant stones (s=0) and keep repeating until it is fully minimized, check for group liberties (s=1), remove opponent stones for groups with no liberties (s=2), repeat s=0 and s=1, check that all player groups have liberties, return result.

This can probably be shortened significantly...

Interactive Example runs:

2
10
01
1 0 2
0

2
10
11
1 0 2
1
02
00

5
22122
22021
11211
02120
00120
2 1 1
1
00100
00101
11011
02120
00120

6
000000
011221
121121
122221
011110
000000
4 0 1
1
000010
011221
121121
122221
011110
000000