# Hashiwokakero: Build bridges!

Hashiwokakero ("build bridges" in Japanese) is a puzzle where you are tasked with connecting a group of islands with bridges. The rules are:

1. Bridges must run either vertically or horizontally between two islands.
2. Bridges may not cross each other.
3. A pair of islands may be connected by at most two parallel bridges.
4. Each island is marked with a number between 1 and 8, inclusive. The number of bridges connected to an island must match the number on that island.
5. The bridges must connect the islands into a single connected group.

Your task is to write a program that will solve Hashiwokakero puzzles.

You may assume that any given puzzle is solvable and that there is only one solution.

The program should be reasonably efficient. For example, solving the 25x25 puzzle below shouldn't take more than 10 minutes on an average PC and it shouldn't use more than a gigabyte of memory. Solving smaller puzzles like the 7x7 one should take seconds.

Input:

The puzzle will be given as a 2D map of characters, with the digits 1 to 8 representing islands, and spaces representing water. The lines will be padded with spaces if necessary to make them all the same length.

Islands will always be separated horizontally and vertically by at least one square of water so that there is room to place the potential bridge between them. There will always be at least two islands in a puzzle.

Your program should preferably read the puzzle map from standard input, but you may specify an alternate input method if your programming language requires it.

Output:

The output should be like the input, except with spaces replaced by bridges as necessary. The bridges should be drawn using Unicode box drawing characters ─ (U+2500), │ (U+2502), ═ (U+2550) and ║ (U+2551) to represent horizontal and vertical single and double bridges.

If Unicode characters are a problem, you may use the ASCII characters -, |, = and H instead.

Winning criteria:

This is code golf. The shortest correct and reasonably efficient solution wins.

Examples:

Puzzle (7x7):

2 2  1
1  4 3
3  2
4
3 2  3
1
3  4 2


Solution:

2─2──1
│1──4─3
3──2║ ║
│  │4 ║
│3─2║ 3
1║  ║ │
3──4─2


Puzzle (25x25):

2 2 2  2  1 1 2 2  2  2 2
1 3 5  4  4 2
2  2 4 5  5 4 2 2  1    3
2   1  1 3 3 2       2
3 4 4  4 4 5 4 3  2  3
2 4 5 4            2   3
2 1   4 2  4 3   1  1  2
2 1 3     1  1  6  4   2
3 2  4  3  6 3         2
2 2 3  3  2     5 2  4 3
2 1               1    2
1 3 3 3 3 5 8 7 6  5 4
2  3   1 1 2
1   1  5 1   4 5 6 3 1 2
1   1  2    2        3 4
3 5 4  4  3  3 8 7 5 1 2
2      3  1 2  2     1 1
2      2  2  2 5 7 6 3 3
3  3 6 3  5 3  2   2 2 3
2            1 2 3 2   2
3  4 6  4 5 5  3 3 5  1
2    1    2 2  1   1  3
2    1    1 2 3  6 5 2  2
2 3  4 4  4 2         1
2 2  2 2  2 2 2  1  1 3 2


Solution:

2─2─2──2  1 1─2─2──2──2─2
│      │  │1─3═5══4══4─2│
2  2─4─5══5═4═2│2──1 │ │3
│ 2│ ║1│ 1─3═3─2│    │ 2║
│ ║3═4│4══4─4═5─4─3──2 │3
2 4═5─4│  │ │ ║ │ │2───3│
│2─1║ ║4─2│ 4─3 │ 1│ 1 │2
2│1─3 ║║ │1 ║1──6══4 │ 2│
│3─2──4║ 3══6─3 ║  │ │ │2
2│2═3 │3──2 │ ║ 5─2│ 4─3│
│2─1│ │   │ │ ║ ║ │1 ║ │2
│ 1─3─3─3─3─5═8═7═6──5═4│
2──3───1│1─2│ ║ │ ║    ││
1 │ 1──5─1││ 4─5─6─3─1│2
1│ │1──2║  │2 │ ║ ║ │3═4│
│3─5═4 │4──3│ 3═8═7═5│1│2
2│ │ ║ 3│ 1│2──2║ │ ║1│1│
│2 │ ║ ║2 │2──2│5═7═6─3─3
3│ 3─6─3│ 5═3 │2│ ║2│2─3│
║2 │ ║  │ ║ │ 1│2─3║2│ ║2
3│ 4═6──4─5─5──3─3─5││1║│
│2 │ │1 │ │2║2──1│ ║1││3│
2│ │ 1│ │ 1║2│3══6═5─2││2
│2─3──4═4──4─2│  │    │1│
2─2──2─2──2─2─2  1  1─3─2

• Is there a option that input is impossible to solve? – Hauleth Jan 30 '12 at 17:46
• @Hauleth: You may assume that any given puzzle is solvable and that there is only one solution. – hammar Jan 30 '12 at 17:47
• Awww, I haven't seen that. My fault. – Hauleth Jan 30 '12 at 18:10
• Is there a minimum puzzle size or number of nodes, or do we need to worry about odd cases like 1 1 being input? – captncraig Jan 30 '12 at 18:38
• @CMP: There is no explicit minimum, although the rules imply that there is no smaller puzzle than 1 1, which is a valid puzzle and it should be handled correctly. – hammar Jan 30 '12 at 18:46

main=interact$unlines.(\f@(l:_)->let a=(length l,length f)in head.filter(網(0,0)a).計(0,0)a$f).lines

=折((&&).折((&&).not.(含島))實)實(潔 置 域 地)|實=網(右+1,下)域 地

=見込(価-環 置 域 地)>>=折(\種->(fst.続(行 置 種 1)域 種 1' '=<<))[地]>>=計(右+1,下)域
|實=計(右+1,下)域 地;見込 価|価<0=[]|価>4=[]|實=[[""],["─","│"],["─│","║","═"],["─║","═│"],["═║"]]!!価

|實=([],置);存(右,下)(幅,高)|右>=0,幅>右,0<=下=高>下|實=not 實;環 置 域 地=折(環行 置 域 地)0導



Originally, I had it even more purely Japanese by also implementing the primitive functions in terms of simple pattern matching and list combinations:

main=interact$unlines.(\f@(l:_)->let a=(length l,length f)in head.filter(網(0,0)a).計(0,0)a$f).lines

=折る((&&).折る((&&).反対.(含島))實)實(潔 置 域 地)|實=網(右+1,下)域 地

=見込(価-環 置 域 地)>>=折る(\種->(一.続(行 置 種 1)域 種 1' '=<<))[地]>>=計(右+1,下)域
|實=計(右+1,下)域 地;見込 価|価<0=[]|価>4=[]|實=[[""],["─","│"],["─│","║","═"],["─║","═│"],["═║"]]!!価

|實=([],置);存(右,下)(幅,高)|右>=0,幅>右,0<=下=高>下|實=反対 實;環 置 域 地=折る(環行 置 域 地)0導



$make ; def0 +RTS -M1g < test-25x25.txt ghc -o bin/def0 golfed0.hs -rtsopts -O2 [1 of 1] Compiling Main ( golfed0.hs, golfed0.o ) Linking bin/def0 ... 2─2─2──2 1 1─2─2──2──2─2 │ │ │1─3═5══4══4─2│ 2 2─4─5══5═4═2│2──1 │ │3 │ 2│ ║1│ 1─3═3─2│ │ 2║ │ ║3═4│4══4─4═5─4─3──2 │3 ...  runs in ≈3 minutes on my i5. Commented version: type Board = [[Char]] type Location = (Int,Int) type BoardDimensions = (Int,Int) main=interact$unlines.(\f@(l:_)
->let a=(length l,length f)  -- dimensions of the field from the input
in head.filter(網(0,0)a)   --   ↙−   determine all possible ways to build bridges
{-                ↑      -}   .計(0,0)a \$ f                                         ).lines
-- and use the first that is simply connected.

--  islands,            bridges

-- each with the associated "value" from the natural numbers _↗

-- plan & commit the building of bridges

|下>=高=[地]        -- Walk over the board until every location was visited.
|右>=幅=計(0,下+1)域 地
|[価]<-目 置 地価島      -- When there is an island, read it's "value" 価
=見込(価-環 置 域 地)  -- substract the value of the already-built bridges; fetch the ways to build bridges with the remaining value
>>=折る(\種->(一.続(行 置 種 1)域 種 1' '=<<))[地]  -- for each of these ways, try to build a bridge.
>>=計(右+1,下)域    -- for every possibility where that was successful, go on with the resultant board.
|實=計(右+1,下)域 地

-- Ways to build bridges with value 価:

|価<0=[]   -- not possible to build bridges with negative value
|価>4=[]   -- nor with value >4  (we're always building south- / eastwards)
|實=[ [""]      -- value 0
,["─","│"]  -- value 1
,["─│","║","═"],["─║","═│"],["═║"]]!!価  -- ... and so on

-- continue, if Location is on the board, with the building of a bridge of type 種

|存 置 域=建 置 域 種 動 空 地
|實=([],置)

-- build that bridge,

|目 置 地含島=([地],置)  -- but if we've reached an island we're done
|目 置 地==空 -- if we're in water or what else (空, can also take on the value of 種 if we only want to check if the bridge is already there)
=続(行 置 種 動)域 種 動 空(換 地 置 種) -- place (換) the bridge and go (行く) to the next location
|實=([],置)  -- if we've reached something else (i.e. crossing bridges), return no result.

-- number of connections present at location 置

|置<-行 置 種 動,存 置 域   -- if they're on the board
,事<-目 置 地,事==種    --   and there's a bridge in the correct direction
,[価]<-事価結 橋 桥=数+価  -- check its value and sum it to the previous ones
|實=数   -- if there's no bridge there, don't sum anything

--     --     --     --     --     --     --     --     --     --     --     --

-- test for connectedness:

|下>=高=實                                    -- found. 潔 marks all islands connected to
|右>=幅=網(0,下+1)域 地                        -- that island; then check if any unmarked
|目 置 地含島=折る((&&).折る((&&).反対.(含島))實)實(潔 置 域 地)  -- islands are left in the
|實=網(右+1,下)域 地                                                          -- result.

-- mark islands connected to the one at 置:

-- mark the island at 置 with '0', then, for all the possible ways to go...
-- Proceed with the marking in some direction

|([地],置)<-続(行 置 種 動)域 種 動 種 地=潔 置 域 地
|實=地   -- if none is found (i.e. there was no bridge), just return the board without further marking

--     --     --     --     --     --     --     --     --     --     --     --
-- Primitives:

-- replace what's at (右,下) with 事


• Wow. Care to explain what the chinese is all about? – captncraig Feb 2 '12 at 16:47
• @CMP: it's actually supposed to be Japanese... not really though, I just looked up stuff that seemed to have roughly the correct meaning at Wiktionary. — Allright, added a commented version of the code. – ceased to turn counterclockwis Feb 2 '12 at 20:24

## Python, 1079 chars

import sys,re,copy
W=A.find('\n')+1
r=range
V={}
E=[]
for i in r(len(A)):
if'0'<A[i]<'9':V[i]=int(A[i])
for d in(1,W):m=re.match('[1-8]( +)[1-8]',A[i::d]);E+=[[i,i+len(m.group(1))*d+d,d,r(3)]]if m else[]
def S(E):
q,t=0,1
while q!=t:
for e in E:
if any(d[0]and e[3][0]==0and any(i in r(a+c,b,c)for i in r(e[0]+e[2],e[1],e[2]))for a,b,c,d in E):e[3]=[0]
for i in V:
m=sum(min(e[3])for e in E if i in e[:2]);n=sum(max(e[3])for e in E if i in e[:2])
if m>V[i]or n<V[i]:return
for e in E:
if m+2>V[i]and i in e[:2]:e[3]=e[3][:V[i]-m+1]
if n-2<V[i]and i in e[:2]:e[3]=e[3][V[i]-n-1:]
t=q;q=sum(len(e[3])for e in E)
Q=[min(V)]
i=0
while Q[i:]:
x=Q[i];i+=1
for e in E:
if x in e[:2]:
if sum(e[3]):
for y in e[:2]:
if y not in Q:Q+=[y]
if len(Q)!=len(V):return
U=[e for e in E if e[3][1:]]
if U:
for w in U[0][3]:U[0][3]=[w];S(copy.deepcopy(E))
else:
B=A
for a,b,c,d in E:
if d[0]:
for i in r(a+c,b,c):B=B[:i]+[{1:'─',W:'│'},{1:'═',W:'║'}][d[0]-1][c]+B[i+1:]
print(B)
sys.exit(0)
S(E)


The code does a pretty straightforward exhaustive search in S, using some constraint propagation to make it run in a reasonable time. E represents the current set of edges, in the format [from,to,delta,possible weights]. from and to are island identifiers and delta is either 1 for horizontal edges or W (=width of lines) for vertical edges. possible weights is a sublist of [0,1,2] encoding the current known state of that edge (0=no bridge, 1 = single bridge, 2 = double bridge).

S does three things. First it propagates information, like if one edge no longer has a 0 weight as a possibility, then all edges that cross it are eliminated (their possible weights are set to [0]). Similarly, if the sum of the minimum weight for edges incident on an island equals the island's weight, then all of those edges are set to their minimum.

Second, S checks that the graph is still connected using non [0] edges (the Q computation).

Finally, S picks an edge that is still not fully determined and calls itself recursively, setting that edge to one of its remaining possibilities.

Takes about 2 minutes for the biggest example.

• you can lose some characters using tabs instead of spaces in some places, and combining some things into one line (like print(B);sys.exit(0) – Blazer Feb 7 '12 at 6:51
• I hacked it up and got it down to 1041 chars, still working – Blazer Feb 7 '12 at 7:01

## C# - 66015661 2225

using System;using System.Collections.Generic;using Google.OrTools.ConstraintSolver;
using System.Linq;namespace A{class N{public int R,C,Q;public bool F;public N(int r,
int c,int q){R=r;C=c;Q=q;}}class E{private static int i;public N A,B;public int I;
public E(N a,N b){A=a;B=b;I=i++;}}class H{public void G(string i){var o=P(i);var g=
new List<E>();foreach(var m in o){var r=o.Where(x=>x.R==m.R&&x.C>m.C).OrderBy(x=>x.C)
;int n=g.Count;var k=s.MakeIntVarArray(n,0,2);foreach(var j in o){var w=j;var y=g.Where
foreach(var u in g.Where(x=>x.A.R==x.B.R)){var e=u;var v=g.Where(x=>x.A.R<e.A.R&&x.B.R
>e.A.R&&x.A.C>e.A.C&&x.A.C< e.B.C);foreach (var f in v){s.Add(s.MakeEquality(k[e.I]*k[f.
(k,0,0);s.NewSearch(z);int c=0;while(s.
NextSolution()){if(C(k,o,g)){N(k,o,g);Console.WriteLine();c++;}}Console.WriteLine(c);}
bool C(IntVar[]t,List<N>d,List<E>g){var a=d[0];a.F=true;var s=new Stack<N>();s.Push(a);
while(s.Any()){var n=s.Pop();foreach(var e in g.Where(x=>x.A==n||x.B==n)){var o=e.A==n?
e.B:e.A;if(t[e.I].Value()>0&&!o.F){o.F=true;s.Push(o);}}}bool r=d.All(x=>x.F);foreach
(var n in d){n.F=false;}return r;}void N(IntVar[]t,IList<N>n,List<E>e){var l=new
.ToCharArray());}foreach(var o in n){l[o.R][o.C]=o.Q.ToString()[0];N d=o;foreach(var
g in e.Where(x=>x.A==d)){var v=t[g.I].Value();if(v>0){char p;int c;if(g.B.R==o.R){p=v==1
?'─':'═';c=o.C+1;var r=l[o.R];while(c<g.B.C){r[c]=p;c++;}}else{p=v==1?'│':'║';c=o.R+1;
while(c<g.B.R){l[c][o.C]=p;c++;}}}}}foreach(var r in l){Console.WriteLine(new string(r))
;}}List<N>P(string s){var n=new List<N>();int r=0;foreach(var l in s.Split(new[]{'\r',
'\n'},StringSplitOptions.RemoveEmptyEntries)){for(int c=0;c<l.Length;c++){if(l[c]!=' '


Not particularly well-golfed. Uses constraint programming library from google or-tools. Builds constraints for total edge counts and to eliminate crossing bridges, but it is a bit harder to define constrains to ensure they are all connected. I did add logic to prune 2=2 and 1-1 components, but I still have to go through the final list (39 on the large one) and eliminate those which are not fully connected. Works pretty fast. Takes only a couple seconds on largest example. Ungolfed:

using System;
using System.Collections.Generic;
using System.Linq;
namespace Hashi
{
public class Node
{
public int Row, Col, Req;
public bool Flag;

public Node(int r, int c, int q)
{
Row = r;
Col = c;
Req = q;
}
}
public class Edge
{
private static int idx = 0;
public Node A, B;
public int Index;
public Edge(Node a, Node b)
{
A = a;
B = b;
Index = idx++;
}
}
public class HashiSolver
{
public void Go(string input)
{
IList<Node> nodes = Parse(input);
var edges = new List<Edge>();
foreach (var node in nodes)
{
var r = nodes.Where(x => x.Row == node.Row && x.Col > node.Col).OrderBy(x => x.Col).FirstOrDefault();
if (r != null)
{
}
var d = nodes.Where(x => x.Col == node.Col && x.Row > node.Row).OrderBy(x => x.Row).FirstOrDefault();
if (d != null)
{
}
}
var solver = new Solver("Hashi");
int n = edges.Count;
var toSolve = solver.MakeIntVarArray(n, 0, 2);
//add total node edge total constraints
foreach (var node in nodes)
{
var node1 = node;
var toConsider = edges.Where(x => x.A == node1 || x.B == node1).Select(x => toSolve[x.Index]).ToArray();
}
foreach (var ed in edges.Where(x => x.A.Row == x.B.Row))
{
var e = ed;
var conflicts = edges.Where(x => x.A.Row < e.A.Row &&
x.B.Row > e.A.Row &&
x.A.Col > e.A.Col &&
x.A.Col < e.B.Col);
foreach (var conflict in conflicts)
{
}
}
if (nodes.Count > 2)
{
//remove 2=2 connections
foreach (var e in edges.Where(x => x.A.Req == 2 && x.B.Req == 2))
{
}
//remove 1-1 connections
foreach (var e in edges.Where(x => x.A.Req == 1 && x.B.Req == 1))
{
}
}
var db = solver.MakePhase(toSolve, Solver.INT_VAR_DEFAULT, Solver.INT_VALUE_DEFAULT);
solver.NewSearch(db);
int c = 0;
while (solver.NextSolution())
{
if (AllConnected(toSolve, nodes, edges))
{
Print(toSolve, nodes, edges);
Console.WriteLine();
c++;
}
}
Console.WriteLine(c);
}
private bool AllConnected(IntVar[] toSolve, IList<Node> nodes, List<Edge> edges)
{
var start = nodes[0];
start.Flag = true;
var s = new Stack<Node>();
s.Push(start);
while (s.Any())
{
var n = s.Pop();
foreach (var edge in edges.Where(x => x.A == n || x.B == n))
{
var o = edge.A == n ? edge.B : edge.A;
if (toSolve[edge.Index].Value() > 0 && !o.Flag)
{
o.Flag = true;
s.Push(o);
}
}
}
bool r = nodes.All(x => x.Flag);
foreach (var n in nodes)
{
n.Flag = false;
}
return r;
}
private void Print(IntVar[] toSolve, IList<Node> nodes, List<Edge> edges)
{
var l = new List<char[]>();
for (int i = 0; i <= nodes.Max(x => x.Row); i++)
{
l.Add(new string(' ', nodes.Max(x => x.Col) + 1).ToCharArray());
}
foreach (var node in nodes)
{
l[node.Row][node.Col] = node.Req.ToString()[0];
Node node1 = node;
foreach (var edge in edges.Where(x => x.A == node1))
{
var v = toSolve[edge.Index].Value();
if (v > 0)
{
//horizontal
if (edge.B.Row == node.Row)
{
char repl = v == 1 ? '─' : '═';
int col = node.Col + 1;
var r = l[node.Row];
while (col < edge.B.Col)
{
r[col] = repl;
col++;
}
}
//vertical
else
{
char repl = v == 1 ? '│' : '║';
int row = node.Row + 1;
while (row < edge.B.Row)
{

l[row][node.Col] = repl;
row++;
}
}
}
}
}
foreach (var r in l)
{
Console.WriteLine(new string(r));
}
}
private IList<Node> Parse(string s)
{
var n = new List<Node>();
int row = 0;
foreach (var line in s.Split(new[] { '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries))
{
for (int col = 0; col < line.Length; col++)
{
if (line[col] != ' ')
{
n.Add(new Node(row, col, line[col] - '0'));
}
}
row++;
}
return n;
}

}
}