Bridges (Hashi) [duplicate]

Question

This question already has an answer here:

• Hashiwokakero: Build bridges! 3 answers

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 

Answer 1

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

Answer 2

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

Answer 3

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
a=sys.stdin.read().split()
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('.',' '))