# Bridges (Hashi) [duplicate]

Unsolved puzzle:

Solved Puzzle:

### Rules

• Each circle with number must have as many lines from it as the number in the circle.
• It is not allowed to have more than two lines between two circles.
• The lines can not cross each other.
• All the lines must either be horizontal or vertical. It is not allowed to draw lines diagonally.
• All lines must be connected.

### Program Description

Write a program to input a bridges puzzle from a text file and output the solution

### Input file guidelines

The input file must display a number for the number of bridges connected and . for whitespace.

Example:

2.2.5.2.
.....1.3
6.3.....
.2..6.1.
3.1..2.6
.2......
1.3.5..3
.2.3..2.


### Output guidelines

Replace periods with

• - single horizontal line
• = double horizontal line
• | single vertical line
• $ double vertical line From the data file above, you should get this as output: 2 2-5=2$ | $1-3 6=3$  2--6-1$3|1$2=6
|2| 
1|3=5--3
2-3==2


## marked as duplicate by Peter Taylor, Hasturkun, primo, Geoff Reedy, grcFeb 23 '13 at 2:45

• You marked this as code golf, but I assume this is instead a programming challenge? – AardvarkSoup Feb 16 '13 at 21:03
• The person with the smallest letter count wins, it is a codegolf challenge – Will Sherwood Feb 16 '13 at 23:56
• Is a unique solution guaranteed? – Gordon Bailey Feb 17 '13 at 1:17
• Yes, a unique solution is guaranteed – Will Sherwood Feb 17 '13 at 2:14
• looks like an exact duplicate of codegolf.stackexchange.com/q/4790/367 – Geoff Reedy Feb 21 '13 at 3:52

# Python 3/ 1780C

This problem can be converted to the exact cover problem. We can use Knuth's AlgorithmX to solve the exact cover problem.

I'll post the details about converting from input data to a 0-1 matrix later. It's very interesting.

Solving exact cover problem with AlgorithmX is very fast. On my machine, the example was solved within 0.09 second, in 310 iterations. And the program can output all solutions.

import sys
from itertools import product as I
V=list
L=len
Z=enumerate
W=range
P=V(I(W(L(a)),W(L(a[0]))))
E={p:[]for p in P}
Q={(i,j):int(a[i][j])for i,j in P if'.'!=a[i][j]}
J=Q.items()
F=[]
for p,c in J:
for i,j in((0,1),(1,0)):
q=p[0]+i,p[1]+j;e=[p,0]
while q in P:
E[q]+=[e]
if q in Q:e[1]=q;E[p]+=[e];F+=[e];break
q=q[0]+i,q[1]+j
E={x:[x for x in y if x[1]!=0]for x,y in E.items()}
C=[E[p] for p in P if p not in Q and L(E[p])>1]
m=[]
T=L(Q)+4*L(F)+L(C)
s=0
l={}
for p,c in J:
e=E[p];u=L(e)*2
for t in I(*((0,1,2)for x in e)):
if sum(t)!=c:continue
r=[0]*T;r[s+u]=1
for i,x in Z(t):k=s+i*2;r[k:k+2]=((1,1),(0,1),(0,0))[x]
m+=[r]
l[p]=s;s+=u+1
z=L(m)
for e in F:
p,q=e;r=[0]*T;c,d=l[p]+E[p].index(e)*2,l[q]+E[q].index(e)*2;t=r[:];r[c]=r[d]=1
for i,u in Z(C):r[T-L(C)+i]=int(e in u)
t[c+1]=t[d+1]=1;m+=[r,t]

def I(x,d):
y=d[x]
while y!=x:yield y;y=d[y]
def A(c):
L[R[c]],R[L[c]]=L[c],R[c]
for x in I(c,D):
for y in I(x,R):U[D[y]],D[U[y]]=U[y],D[y]
def B(c):
for x in I(c,U):
for y in I(x,L):U[D[y]],D[U[y]]=y,y
L[R[c]],R[L[c]]=c,c
def S():
c=R[h]
if c==h:yield[]
A(c)
for r in I(c,D):
for x in I(r,R):A(C[x])
for t in S():yield[r[0]]+t
for x in I(r,L):B(C[x])
B(c)
L,R,U,D,C={},{},{},{},{}
h=T
L[h]=R[h]=D[h]=U[h]=h
for c in W(T):
R[L[h]],R[c],L[h],L[c]=c,h,c,L[h];U[c]=D[c]=c
for i,l in Z(m):
s=0
for c in I(h,R):
if l[c]:
r=i,c;D[U[c]],D[r],U[c],U[r],C[r]=r,c,r,U[c],c
if s==0:L[r]=R[r]=s=r
R[L[s]],R[r],L[s],L[r]=r,s,r,L[s]
for s in S():
b=V(map(V,a))
for e in s:
if e<z:continue
(i,j),(x,y)=F[(e-z)//2]
if j==y:
for r in W(i+1,x):b[r][j]='|H'[b[r][j]=='|']
else:
for r in W(j+1,y):b[i][r]='-='[b[i][r]=='-']
print('\n'.join(''.join(l)for l in b).replace('.',' '))


# Python: 1303 Characters

This is some super ugly code, and it isn't particularly efficient, but I believe it works:

import sys
from itertools import product,combinations
e=[]
p=[[[0,(c,r,o,[])][c!='.'] for o,c in enumerate(l.strip())] for r,l in enumerate(open(sys.argv[1]))]
r=range(len(p))
c=range(len(p[0]))
for i,j in combinations(product(r,c),2):
if p[i[0]][i[1]] and p[j[0]][j[1]]:
if i[0]==j[0] and abs(i[1]-j[1])>1:
b=1
g=range(min(i[1],j[1])+1,max(i[1],j[1]))
for x in g:
if p[i[0]][x]:b=0
if b:e+=[(i,j,[i[0]],g,1)]
if i[1]==j[1] and abs(i[0]-j[0])>1:
b=1
g=range(min(i[0],j[0])+1,max(i[0],j[0]))
for x in g:
if p[x][i[1]]:b=0
if b:e+=[(i,j,g,[i[1]],0)]
def s(v,i,m):
if i>=len(v):
return None
for j in [2,1,0]:
v[i]=j
q=dict(m)
b=1
for l in [0,1]:
n=e[i][l]
if not n in q:q[n]=0
q[n]+=j
y=int(p[n[0]][n[1]][0])
if q[n]>y:b=0
if not b:continue
a=[d for b in range(i+1) for d in product(e[b][2],e[b][3]) if v[b]>0]
if len(a)!=len(set(a)):continue
if i==len(v)-1:
g=1
for l,z in product(r,c):
n=p[l][z]
if not n:continue
if q[(n[1],n[2])]!=int(n[0]):g=0
if g:return v
u=s(v,i+1,q)
if u:return u
for i,v in zip(e,s([None]*len(e),0,{})):
if v>0:
for j,k in product(i[2],i[3]):p[j][k]=[[['|','$'][v-1],['-','='][v-1]][i[4]]] for l in p: for c in l: if not c:c=[' '] sys.stdout.write(c[0]) print ""  Example: $ cat problem
4.4.1
.....
4.6.2
.....
..1..
$python bridges.py problem 4=4-1$ |
4=6=2
|
1

• why open(sys.argv[1])? sys.stdin save you some chars. – Ray Feb 21 '13 at 0:19
• The result in your example doesn't match the input. – Ray Feb 21 '13 at 3:14
• @Ray: I used open(sys.argv[1]) because the instructions specifically said to take input from a file. It's easy enough to change though. As for the example, thanks for catching my mistake: I edited the example to make it a bit more interesting, but I accidentally only copy/pasted the updated output. I'll fix that now. – ESultanik Feb 21 '13 at 13:48

### Ruby, 414 characters

h=->l,s,v{l[s.index(v)||s.size]}
c=->r,f{r[f].to_i-h[[1,2,0],'|$',r[f-N]]-h[[1,2,0],'-=',r[f-1]]-h[[1,2,0],'-=',r[f+1]]} s=->r{(f=r=~/\./)&&(m=h[[2,4,25,25,25,31],w='|$-= ',a=r[f-N]]&h[[7,7,8,16,7,31],w,r[f-1]]
a=~/\d/&&m&=(0>d=c[r,f-N])?0:d<1?25:d<2?2:d<3?4:0
' |$-='.chars{|k|m&1>0&&(r[f]=k;s[r]);m=m>>1};r[f]='.')||r[-N..-1]=~/^ +$/&&$><<r[N..-N].tr("0",$/)}
N=1+((t=STDIN.read)=~/$/) s[$/*N+t.tr($/,"0")+"."*N]  Example: 2.2.5.2. .....1.3 6.3..... .2..6.1. 3.1..2.6 .2...... 1.3.5..3 .2.3..2. 2 2-5=2$ | $1-3 6=3$  2--6-1$3|1$2=6
|2| 
1|3=5--3
2-3==2

• The program will output some incorrect answers. Try this case: 1.2. .... ..1.  – Ray Feb 21 '13 at 15:35
• @Ray You are right. Such strange things didn't happen in my tests. Will have a look into it. – Howard Feb 21 '13 at 17:03
• @Ray It's with the trailing newline of the input. If you omit that it works fine. I'll try to fix that. – Howard Feb 21 '13 at 17:09