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:


Bridges must run either vertically or horizontally between two islands.
Bridges may not cross each other.
A pair of islands may be connected by at most two parallel bridges.
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.
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


Additional puzzles can be found here.
Haskell, 1074 characters

main=interact$unlines.(\f@(l:_)-&gt;let a=(length l,length f)in head.filter(網(0,0)a).計(0,0)a$f).lines
橋=結"─═"数;結=zip;網 置@(右,下) 域@(幅,高) 地|下&gt;=高=實|右&gt;=幅=網(0,下+1)域 地|目 置 地`含`島
 =折((&amp;&amp;).折((&amp;&amp;).not.(`含`島))實)實(潔 置 域 地)|實=網(右+1,下)域 地
導=[(種,動)|動&lt;-[1,-1],種&lt;-"─═│║"];潔 置 域 地=折(拡 置 域)(換 地 置 '0')導
拡 置 域(種,動)地|([地],置)&lt;-続(行 置 種 動)域 種 動 種 地=潔 置 域 地|實=地
計 置@(右,下)域@(幅,高)地|下&gt;=高=[地]|右&gt;=幅=計(0,下+1)域 地|[価]&lt;-目 置 地`価`島
 =見込(価-環 置 域 地)&gt;&gt;=折(\種-&gt;(fst.続(行 置 種 1)域 種 1' '=&lt;&lt;))[地]&gt;&gt;=計(右+1,下)域
 |實=計(右+1,下)域 地;見込 価|価&lt;0=[]|価&gt;4=[]|實=[[""],["─","│"],["─│","║","═"],["─║","═│"],["═║"]]!!価
続 置 域 種 動 空 地|存 置 域=建 置 域 種 動 空 地|實=([],置)
建 置 域 種 動 空 地|目 置 地`含`島=([地],置)|目 置 地==空=続(行 置 種 動)域 種 動 空(換 地 置 種)
 |實=([],置);存(右,下)(幅,高)|右&gt;=0,幅&gt;右,0&lt;=下=高&gt;下|實=not 實;環 置 域 地=折(環行 置 域 地)0導
環行 置 域 地(種,動)数|置&lt;-行 置 種 動,存 置 域,事&lt;-目 置 地,事==種,[価]&lt;-事`価`(橋++桥)=数+価|實=数
行(右,下)種 数|種`含`橋=(右+数,下)|實=(右,下+数);目(右,下)地=地!!下!!右;島=結"12345678"数
換 地(右,下)事|(上に,線:下に)&lt;-捌 下 地,(左,古:右)&lt;-捌 右 線=上に++(左++(事:右)):下に
折=foldl.flip;捌 0覧=([],覧);捌 数(物:覧)|(一覧,他)&lt;-捌(数-1)覧=(物:一覧,他);實=1&gt;0;数=[1..]
価 _[]=[];価 事((物,数):覧)|事==物=[数]|實=価 事 覧;含 事 覧|[_]&lt;-価 事 覧=實|實=1&lt;0;桥=結"│║"数



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

Haskell, 1192

main=interact$unlines.(\f@(l:_)-&gt;let a=(length l,length f)in head.filter(網(0,0)a).計(0,0)a$f).lines
橋=結合"─═"数;結合 []_=[];結合(事:覧)(物:一覧)=(事,物):結合 覧 一覧
網 置@(右,下) 域@(幅,高) 地|下&gt;=高=實|右&gt;=幅=網(0,下+1)域 地|目 置 地`含`島
 =折る((&amp;&amp;).折る((&amp;&amp;).反対.(`含`島))實)實(潔 置 域 地)|實=網(右+1,下)域 地
導=[(種,動)|動&lt;-[1,-1],種&lt;-"─═│║"];潔 置 域 地=折る(拡 置 域)(換 地 置 '0')導
拡 置 域(種,動)地|([地],置)&lt;-続(行 置 種 動)域 種 動 種 地=潔 置 域 地|實=地
計 置@(右,下)域@(幅,高)地|下&gt;=高=[地]|右&gt;=幅=計(0,下+1)域 地|[価]&lt;-目 置 地`価`島
 =見込(価-環 置 域 地)&gt;&gt;=折る(\種-&gt;(一.続(行 置 種 1)域 種 1' '=&lt;&lt;))[地]&gt;&gt;=計(右+1,下)域
 |實=計(右+1,下)域 地;見込 価|価&lt;0=[]|価&gt;4=[]|實=[[""],["─","│"],["─│","║","═"],["─║","═│"],["═║"]]!!価
続 置 域 種 動 空 地|存 置 域=建 置 域 種 動 空 地|實=([],置)
建 置 域 種 動 空 地|目 置 地`含`島=([地],置)|目 置 地==空=続(行 置 種 動)域 種 動 空(換 地 置 種)
 |實=([],置);存(右,下)(幅,高)|右&gt;=0,幅&gt;右,0&lt;=下=高&gt;下|實=反対 實;環 置 域 地=折る(環行 置 域 地)0導
環行 置 域 地(種,動)数|置&lt;-行 置 種 動,存 置 域,事&lt;-目 置 地,事==種,[価]&lt;-事`価`結 橋 桥=数+価|實=数
行(右,下)種 数|種`含`橋=(右+数,下)|實=(右,下+数);一(第,第二)=第;目(右,下)地=地!!下!!右;島=結合"12345678"数
換 地(右,下)事|(上に,線:下に)&lt;-捌 下 地,(左,古:右)&lt;-捌 右 線=結 上に(結 左(事:右):下に);変 関[]=[]
変 関(物:覧)=関 物:変 関 覧;折る 関 物[]=物;折る 関 物(事:覧)=折る 関(関 事 物)覧;捌 0覧=([],覧)
捌 数(物:覧)|(一覧,他)&lt;-捌(数-1)覧=(物:一覧,他);實=1&gt;0;反対 真|真=1&lt;0|實=實;数=[1..];結=(++)
価 _[]=[];価 事((物,数):覧)|事==物=[数]|實=価 事 覧;含 事 覧|[_]&lt;-価 事 覧=實|實=1&lt;0;桥=結合"│║"数




$ make ;   def0 +RTS -M1g &lt; 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:_)
  -&gt;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
島=結合"12345678"数;  橋=結合"─═"数;  桥=結合"│║"数;               数=[1..]
 -- each with the associated "value" from the natural numbers _↗



     -- plan &amp; commit the building of bridges
計 :: Location -&gt; BoardDimensions -&gt; Board -&gt; [Board]
計    置@(右,下)   域@(幅,高)          地
 |下&gt;=高=[地]        -- Walk over the board until every location was visited.
 |右&gt;=幅=計(0,下+1)域 地
 |[価]&lt;-目 置 地`価`島      -- 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
     &gt;&gt;=折る(\種-&gt;(一.続(行 置 種 1)域 種 1' '=&lt;&lt;))[地]  -- for each of these ways, try to build a bridge.
      &gt;&gt;=計(右+1,下)域    -- for every possibility where that was successful, go on with the resultant board.
 |實=計(右+1,下)域 地

  -- Ways to build bridges with value 価:
見込 :: Int -&gt; [[Char]]
見込    価
 |価&lt;0=[]   -- not possible to build bridges with negative value
 |価&gt;4=[]   -- nor with value &gt;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 種
続 :: Location -&gt; BoardDimensions -&gt; Char -&gt; Int -&gt; Char -&gt; Board -&gt; ([Board],Location)
続    置          域                  種      動      空      地
 |存 置 域=建 置 域 種 動 空 地
 |實=([],置)

      -- build that bridge, 
建 :: Location -&gt; BoardDimensions -&gt; Char -&gt; Int -&gt; Char -&gt; Board -&gt; ([Board],Location)
建    置          域                  種      動      空      地
 |目 置 地`含`島=([地],置)  -- 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 置
環 :: Location -&gt; BoardDimensions -&gt; Board -&gt; Int
環 置 域 地=折る(環行 置 域 地)0導  -- for all neighbouring positions
環行 置 域 地(種,動)数
 |置&lt;-行 置 種 動,存 置 域   -- if they're on the board
 ,事&lt;-目 置 地,事==種    --   and there's a bridge in the correct direction
 ,[価]&lt;-事`価`結 橋 桥=数+価  -- check its value and sum it to the previous ones
 |實=数   -- if there's no bridge there, don't sum anything


導=[(種,動)|動&lt;-[1,-1],種&lt;-"─═│║"]     -- directions to go

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

     -- test for connectedness:
網 :: Location -&gt; BoardDimensions -&gt; Board -&gt; Bool
網    置@(右,下)      域@(幅,高)         地      -- Walk over the board until an island is
 |下&gt;=高=實                                    -- found. 潔 marks all islands connected to
 |右&gt;=幅=網(0,下+1)域 地                        -- that island; then check if any unmarked
 |目 置 地`含`島=折る((&amp;&amp;).折る((&amp;&amp;).反対.(`含`島))實)實(潔 置 域 地)  -- islands are left in the
 |實=網(右+1,下)域 地                                                          -- result.

         -- mark islands connected to the one at 置:
潔 :: Location -&gt; BoardDimensions -&gt; Board -&gt; Board
潔    置           域                 地    =折る(拡 置 域)(換 地 置 '0')[(種,動)|動&lt;-[1,-1],種&lt;-"─═│║"]
 -- mark the island at 置 with '0', then, for all the possible ways to go...
     -- Proceed with the marking in some direction
拡 :: Location -&gt; BoardDimensions -&gt; (Char,Int) -&gt; Board -&gt; [[Char]]
拡 置 域(種,動)地     -- if an island is found in the given direction, give control to 潔 there
 |([地],置)&lt;-続(行 置 種 動)域 種 動 種 地=潔 置 域 地
 |實=地   -- if none is found (i.e. there was no bridge), just return the board without further marking


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

存 :: Location -&gt; BoardDimensions -&gt; Bool
存(右,下)(幅,高)|右&gt;=0,幅&gt;右,0&lt;=下=高&gt;下|實=反対 實  -- check if (右,下) is on the board

行 :: Location -&gt; Char-&gt;Int -&gt; Location
行(右,下)種 数|種`含`橋=(右+数,下)|實=(右,下+数)   -- go in some direction (determined by where 種 leads to)

目 :: Location -&gt; Board -&gt; Char
目(右,下)地=地!!下!!右          -- lookup what's at location (右,下)

   -- replace what's at (右,下) with 事
換 :: Board -&gt; Location -&gt; Char -&gt; Board
換 地(右,下)事|(上に,線:下に)&lt;-捌 下 地,(左,古:右)&lt;-捌 右 線=結 上に(結 左(事:右):下に)




変 :: (a -&gt; b) -&gt; [a] -&gt; [b]
変 関[]=[]                       -- Standard Haskell map function (just noticed I didn't actually use it at all)
変 関(物:覧)=関 物:変 関 覧

折る :: (b -&gt; a -&gt; a) -&gt; a -&gt; [b] -&gt; a
折る 関 物[]=物                            -- equivalent 折る=foldl.flip
折る 関 物(事:覧)=折る 関(関 事 物)覧

捌 0覧=([],覧)
捌 数(物:覧)|(一覧,他)&lt;-捌(数-1)覧=(物:一覧,他)   -- splitAt

實=1&gt;0           --true

反対 真|真=1&lt;0|實=實  -- not


結=(++)     -- list linking

一(第,第二)=第    -- fst

価 :: Eq a =&gt; a -&gt; [(a,b)] -&gt; [b]
価 _[]=[]                             -- lookup function
価 事((物,数):覧)|事==物=[数]|實=価 事 覧

含 :: Eq a =&gt; a -&gt; [(a,b)] -&gt; Bool
含 事 覧|[_]&lt;-価 事 覧=實|實=1&lt;0      -- equivalent 含 x = elem x . map fst


結合 []_=[]                          -- zip
結合(事:覧)(物:一覧)=(事,物):結合 覧 一覧