text:
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.

Is there a option that input is impossible to solve?

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

Awww, I haven't seen that. My fault.

Is there a minimum puzzle size or number of nodes, or do we need to worry about odd cases like 1 1 being input?

@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.

@CMP: Though, I guess it was somewhat ambiguous whether a puzzle with no islands was valid. I've clarified that it is not.

I can see how to reduce this to set cover (via multiset cover), but it's not an efficient reduction.

My first reaction is "Prolog FTW!", but I can't think of a good way to codify the single connected component constraint.

Haskell, 1074 characters
main=interact$unlines.(\f@(l:_)->let a=(length l,length f)in head.filter(網(0,0)a).計(0,0)a$f).lines
橋=結"─═"数;結=zip;網 置@(右,下) 域@(幅,高) 地|下>=高=實|右>=幅=網(0,下+1)域 地|目 置 地`含`島
 =折((&&).折((&&).not.(`含`島))實)實(潔 置 域 地)|實=網(右+1,下)域 地
導=[(種,動)|動<-[1,-1],種<-"─═│║"];潔 置 域 地=折(拡 置 域)(換 地 置 '0')導
拡 置 域(種,動)地|([地],置)<-続(行 置 種 動)域 種 動 種 地=潔 置 域 地|實=地
計 置@(右,下)域@(幅,高)地|下>=高=[地]|右>=幅=計(0,下+1)域 地|[価]<-目 置 地`価`島
 =見込(価-環 置 域 地)>>=折(\種->(fst.続(行 置 種 1)域 種 1' '=<<))[地]>>=計(右+1,下)域
 |實=計(右+1,下)域 地;見込 価|価<0=[]|価>4=[]|實=[[""],["─","│"],["─│","║","═"],["─║","═│"],["═║"]]!!価
続 置 域 種 動 空 地|存 置 域=建 置 域 種 動 空 地|實=([],置)
建 置 域 種 動 空 地|目 置 地`含`島=([地],置)|目 置 地==空=続(行 置 種 動)域 種 動 空(換 地 置 種)
 |實=([],置);存(右,下)(幅,高)|右>=0,幅>右,0<=下=高>下|實=not 實;環 置 域 地=折(環行 置 域 地)0導
環行 置 域 地(種,動)数|置<-行 置 種 動,存 置 域,事<-目 置 地,事==種,[価]<-事`価`(橋++桥)=数+価|實=数
行(右,下)種 数|種`含`橋=(右+数,下)|實=(右,下+数);目(右,下)地=地!!下!!右;島=結"12345678"数
換 地(右,下)事|(上に,線:下に)<-捌 下 地,(左,古:右)<-捌 右 線=上に++(左++(事:右)):下に
折=foldl.flip;捌 0覧=([],覧);捌 数(物:覧)|(一覧,他)<-捌(数-1)覧=(物:一覧,他);實=1>0;数=[1..]
価 _[]=[];価 事((物,数):覧)|事==物=[数]|實=価 事 覧;含 事 覧|[_]<-価 事 覧=實|實=1<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:_)->let a=(length l,length f)in head.filter(網(0,0)a).計(0,0)a$f).lines
橋=結合"─═"数;結合 []_=[];結合(事:覧)(物:一覧)=(事,物):結合 覧 一覧
網 置@(右,下) 域@(幅,高) 地|下>=高=實|右>=幅=網(0,下+1)域 地|目 置 地`含`島
 =折る((&&).折る((&&).反対.(`含`島))實)實(潔 置 域 地)|實=網(右+1,下)域 地
導=[(種,動)|動<-[1,-1],種<-"─═│║"];潔 置 域 地=折る(拡 置 域)(換 地 置 '0')導
拡 置 域(種,動)地|([地],置)<-続(行 置 種 動)域 種 動 種 地=潔 置 域 地|實=地
計 置@(右,下)域@(幅,高)地|下>=高=[地]|右>=幅=計(0,下+1)域 地|[価]<-目 置 地`価`島
 =見込(価-環 置 域 地)>>=折る(\種->(一.続(行 置 種 1)域 種 1' '=<<))[地]>>=計(右+1,下)域
 |實=計(右+1,下)域 地;見込 価|価<0=[]|価>4=[]|實=[[""],["─","│"],["─│","║","═"],["─║","═│"],["═║"]]!!価
続 置 域 種 動 空 地|存 置 域=建 置 域 種 動 空 地|實=([],置)
建 置 域 種 動 空 地|目 置 地`含`島=([地],置)|目 置 地==空=続(行 置 種 動)域 種 動 空(換 地 置 種)
 |實=([],置);存(右,下)(幅,高)|右>=0,幅>右,0<=下=高>下|實=反対 實;環 置 域 地=折る(環行 置 域 地)0導
環行 置 域 地(種,動)数|置<-行 置 種 動,存 置 域,事<-目 置 地,事==種,[価]<-事`価`結 橋 桥=数+価|實=数
行(右,下)種 数|種`含`橋=(右+数,下)|實=(右,下+数);一(第,第二)=第;目(右,下)地=地!!下!!右;島=結合"12345678"数
換 地(右,下)事|(上に,線:下に)<-捌 下 地,(左,古:右)<-捌 右 線=結 上に(結 左(事:右):下に);変 関[]=[]
変 関(物:覧)=関 物:変 関 覧;折る 関 物[]=物;折る 関 物(事:覧)=折る 関(関 事 物)覧;捌 0覧=([],覧)
捌 数(物:覧)|(一覧,他)<-捌(数-1)覧=(物:一覧,他);實=1>0;反対 真|真=1<0|實=實;数=[1..];結=(++)
価 _[]=[];価 事((物,数):覧)|事==物=[数]|實=価 事 覧;含 事 覧|[_]<-価 事 覧=實|實=1<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
島=結合"12345678"数;  橋=結合"─═"数;  桥=結合"│║"数;               数=[1..]
 -- each with the associated "value" from the natural numbers _↗

     -- plan & commit the building of bridges
計 :: Location -> BoardDimensions -> Board -> [Board]
計    置@(右,下)   域@(幅,高)          地
 |下>=高=[地]        -- 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 価:
見込 :: Int -> [[Char]]
見込    価
 |価<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 種
続 :: Location -> BoardDimensions -> Char -> Int -> Char -> Board -> ([Board],Location)
続    置          域                  種      動      空      地
 |存 置 域=建 置 域 種 動 空 地
 |實=([],置)

      -- build that bridge,
建 :: Location -> BoardDimensions -> Char -> Int -> Char -> Board -> ([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 -> BoardDimensions -> Board -> Int
環 置 域 地=折る(環行 置 域 地)0導  -- for all neighbouring positions
環行 置 域 地(種,動)数
 |置<-行 置 種 動,存 置 域   -- 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

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

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

     -- test for connectedness:
網 :: Location -> BoardDimensions -> Board -> Bool
網    置@(右,下)      域@(幅,高)         地      -- Walk over the board until an island is
 |下>=高=實                                    -- 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 置:
潔 :: Location -> BoardDimensions -> Board -> Board
潔    置           域                 地    =折る(拡 置 域)(換 地 置 '0')[(種,動)|動<-[1,-1],種<-"─═│║"]
 -- mark the island at 置 with '0', then, for all the possible ways to go...
     -- Proceed with the marking in some direction
拡 :: Location -> BoardDimensions -> (Char,Int) -> Board -> [[Char]]
拡 置 域(種,動)地     -- if an island is found in the given direction, give control to 潔 there
 |([地],置)<-続(行 置 種 動)域 種 動 種 地=潔 置 域 地
 |實=地   -- if none is found (i.e. there was no bridge), just return the board without further marking

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

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

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

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

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

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

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

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

實=1>0           --true

反対 真|真=1<0|實=實  -- not

結=(++)     -- list linking

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

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

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

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

Wow. Care to explain what the chinese is all about?

@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.

Python, 1079 chars
import sys,re,copy
A=sys.stdin.read()
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)

I hacked it up and got it down to 1041 chars, still working

C# - 6601 5661 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)
.FirstOrDefault();if(r!=null){g.Add(new E(m,r));}var d=o.Where(x=>x.C==m.C&&x.R>m.R)
.OrderBy(x=>x.R).FirstOrDefault();if(d!=null){g.Add(new E(m,d));}}var s=new Solver("H")
;int n=g.Count;var k=s.MakeIntVarArray(n,0,2);foreach(var j in o){var w=j;var y=g.Where
(x=>x.A==w||x.B== w).Select(x=>k[x.I]).ToArray();s.Add(s.MakeSumEquality(y,j.Q));}
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.
I],0));}}if(o.Count>2){foreach(var e in g.Where(x=>x.A.Q==2&&x.B.Q==2)){s.Add(k[e.I]<=1)
;}foreach(var e in g.Where(x=>x.A.Q==1&&x.B.Q==1)){s.Add(k[e.I]==0);}}var z=s.MakePhase
(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
List<char[]>();for(int i=0;i<=n.Max(x=>x.R);i++){l.Add(new string(' ',n.Max(x=>x.C)+1)
.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]!=' '
){n.Add(new N(r,c,l[c]-'0'));}}r++;}return n;}}}

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 Google.OrTools.ConstraintSolver;
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>();
            //add edges between nodes;
            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)
                {
                    edges.Add(new Edge(node, r));
                }
                var d = nodes.Where(x => x.Col == node.Col && x.Row > node.Row).OrderBy(x => x.Row).FirstOrDefault();
                if (d != null)
                {
                    edges.Add(new Edge(node, d));
                }
            }
            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();
                solver.Add(solver.MakeSumEquality(toConsider, node.Req));
            }
            //add crossing edge constraints
            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)
                {
                    solver.Add(solver.MakeEquality(toSolve[e.Index] * toSolve[conflict.Index], 0));
                }
            }
            if (nodes.Count > 2)
            {
                //remove 2=2 connections
                foreach (var e in edges.Where(x => x.A.Req == 2 && x.B.Req == 2))
                {
                    solver.Add(toSolve[e.Index] <= 1);
                }
                //remove 1-1 connections
                foreach (var e in edges.Where(x => x.A.Req == 1 && x.B.Req == 1))
                {
                    solver.Add(toSolve[e.Index] == 0);
                }
            }
            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;
        }

    }
}


text:
Print a Cantor Set
The Challenge
Build a N-Leveled Cantor Set.

The Cantor ternary set is created by repeatedly deleting the open
  middle thirds of a set of line segments.

The program receives one parameter N (a integer number) and then prints (in console or similar way) a Cantor Set of N levels. The print can only contain undescore (_) and whithe spaces characters. The parameter can be positive or negative and the sign indicates the Cantor Set construction orientation: If N > 0 the Cantor Set is constructed downwards and if N < 0 the Cantor Set is constructed upwards. If N = 0 then the program prints a single line (_).
For example:
N = 2
_________
___   ___
_ _   _ _

N = -2
_ _   _ _
___   ___
_________

N = 3
___________________________
_________         _________
___   ___         ___   ___
_ _   _ _         _ _   _ _

N = -3
_ _   _ _         _ _   _ _
___   ___         ___   ___
_________         _________
___________________________

Winning criteria
As it is a code golf challenge, the shortest code wins.
Edited: Modify 0 input by ugoren's suggestion.

Why print nothing when N=0? This makes 0 a special case, and makes it harder to use recursion. General handling would be to print a single _ (but print it downward when getting -0).

Right. I have modified the specs already.

GolfScript, 49 42 40 chars
~.abs.3\?'_'*\{.3%..,' '*\++}*](0>2*(%n*

With thanks to hammar for 42->40.
My best attempt yet at a more number-theoretic approach is sadly much longer:
~.abs:^3\?,{3^)?+3base(;1+1?.'_'*^@-)' '*+}%zip\0>2*(%n*

or
~.abs 3\?:^,{6^*+3base.1+1?.('_'*@,@-' '*+}%zip\0>2*(%n*

and I suspect that the length of base and zip will make it impossible to catch up.

~.abs.@/\.3\?'_'*\{.3%..,' '*\++}*](%n* is 39 chars, but crashes on input 0. :-(

@IlmariKaronen, yes, division by zero was a pain for the C implementation I wrote too, because it meant you can't do n/abs(n) to get signum(n).

https://tio.run/##S8/PSStOLsosKPn/v04vMalYzzjGXj1eXSumWs9YVU9PR10ByNbWrtWK1TCwM9LSUM3T@v/fFAA Output is a bit wonky at n=5.

Python, 116 113 104 103 chars
n=input()
d=n>0 or-1
for i in range(n*d+1)[::d]:
 s='_'*3**i
 while i<n*d:s+=len(s)*' '+s;i+=1
 print s

Older algorithm topped out at 113 characters
r=input()
u='_'
l=[u]
for _ in abs(r)*u:o=len(l[0]);l=[s+o*' '+s for s in l]+[u*o*3]
print'\n'.join(l[::r>0 or-1])

Ruby (97)
Based on Steven Rumbalski's python version:
n,r=$*[0].to_i,[?_]
n.abs.times{z=r[0].size;r=r.map{|s|s+' '*z+s}+[?_*z*3]}
puts n<0?r:r.reverse

Previous attempts, both same length (112)
Build lines from parts:
c=->x,n{n<1??_*x :(z=c[s=x/3,n-1])+' '*s+z}
r=(0..m=(n=$*[0].to_i).abs).map{|i|c[3**m,i]}
puts n<0?r.reverse: r

Start with one line, make holes in it:
r=[?_*3**a=(n=$*[0].to_i).abs]
a.times{|c|r<<r[-1].gsub((x=?_*o=3**(a-c-1))*3,x+' '*o+x)}
puts n<0?r.reverse: r

APL (Dyalog Unicode), 32 31 bytesSBCS
{' _'[⊖⍣(0>⍵)∧⍀1⍪1≠3⊥⍣¯1⍳3*|⍵]}

Try it online!
Saved 1 byte thanks to Adám by changing the conditional flipping ⊖⍣(0>⍵) to inside the indexing.
How it works:
This answer builds on the mathematical properties of the Cantor set itself. It is known that a number is in the Cantor set iff its ternary expansion contains no 1s. So what we do is discretize the interval [0, 1], compute the ternary expansion of the numbers in there, check which ones have a 1 in their ternary expansion and exclude them from the subsequent iterations of the drawing.
{' _'[⊖⍣(0>⍵)∧⍀1⍪1≠3⊥⍣¯1⍳3*|⍵]}   ⍝ dfn expecting an integer as right argument (e.g. 2)
                         ⍳3*|⍵     ⍝ discretize the interval (e.g. 0 1 2 3 4 5 6 7 8)
                   3⊥⍣¯1           ⍝ compute the ternary expansion in columns (e.g.
                                   ⍝    0 0 0 1 1 1 2 2 2
                                   ⍝    0 1 2 0 1 2 0 1 2 )
               1⍪1≠                ⍝ find which numbers are ≠ from 1 and
                                   ⍝ append a row of 1s (e.g.
                                   ⍝    1 1 1 1 1 1 1 1 1
                                   ⍝    1 1 1 0 0 0 1 1 1
                                   ⍝    1 0 1 1 0 1 1 0 1 )
             ∧⍀                    ⍝ propagate the 0s downwards (e.g.
                                   ⍝    1 1 1 1 1 1 1 1 1
                                   ⍝    1 1 1 0 0 0 1 1 1
                                   ⍝    1 0 1 0 0 0 1 0 1 )
      ⊖⍣(0>⍵)                     ⍝ mirror if the input number is negative
 ' _'[                        ]    ⍝ and index into ' _' to draw

^⍀ is a nice strategy.

@Razetime scans with <≤=≥>≠∨∧⍱⍲ are great to deal with Boolean vectors

30: {' _'[⊖⍣(0>⍵)×⍀1≠⍉↑,⍳1,3⍴⍨|⍵]}

28: 0∘>{' _'[⊖⍣⍺×⍀1≠⍉↑,⍳1,⍵⍴3]}|

Perl, 93 chars
@x=($t=$x=_ x 3**($a=abs($n=<>)),map$x.=$"x($x=~s/(.)../$1/g).$x,1..$a);say for$n<0?sort@x:@x

I thought I'd try to see how well Peter Taylor's GolfScript solution would port to Perl.  Notable features include the use of sort instead of reverse to save three chars, using the fact that a space sorts before _.

C, 219 193 179 143 136 131 characters
Followed another of Petyer Taylor's ideas, plus an improvement of my own, saved 6 more.
Integrated some tips from @PeterTaylor, plus copied his main function, with slight changes, which save a character (is it fair to copy it? Since neither of us will win this one, I guess it isn't too bad).
I thought of a significant improvement in how my recursion works, and after seeing Peter Taylor's answer, I implemented it to regain the lead. When reading his answer again, I saw that I did almost exactly what he did. So this seems like the hybridization he suggested.
Also simplified the loop in main, keeping the same length.
And took Peter's trick to print newline, instead of puts("") - saves a character.
Removed int from variable declaration - a warning, but saves 4 chars.
New algorithm doesn't calculate 3^x in advance, but uses a single loop to print 3^x characters.
Can save one more by defining int*v, but then 64bit won't work.
Characters count excludes whitespace (which can be removed).
o,i,n;
p(c) {
    n-- ?
        p(c),p(o>n?c:32),p(c)
    :
        putchar(c);
    n++;
}
main(c,v)int**v; {
    for(n=abs(c=atoi(v[1]));i<=n;i++)o=c+n?n-i:i,p(95),puts("");
}

Older algorithm, 219 chars:
p(l,o,i,m,c,j) {
    for(;i<(m=l);i++)
        for(j=0,c=95;m/o||!putchar(c);j++)
            i/m%3-1||(c=32),m/=3;
    puts("");
}
main(c,v,n,i,l,o)int**v;{
    (n=atoi(v[1]))<0?n=-n:(c=0);
    for(i=n,l=1;i;i--)l*=3;
    o=c?1:l;
    for (;i<=n;i++)p(l,o,0),c?o*=3:(o/=3);
}

@PeterTaylor, I can't remove the i parameter, because using the global would interfere with main. l-- will interfere with o>=l, and I'll have to replace it with > (so why do I write it as if it's a bad thing?) I could also copy you main, which is simpler and shorter than mine.

@PeterTaylor, you were right about i - I missed the fact that I really no longer use it (I thought you mean I don't pass it).

By the way, I don't mind you taking my main function. My rule of thumb is that copying someone else's solution to change a single character is overly aggressive, copying someone else's solution to rewrite half of it is perfectly fair, and there's a grey area somewhere in between. We should perhaps try to agree some community standards on meta.

@PeterTaylor, I think we reached a sort of stalemate. My p seems quite optimal now, and your main was better (I'm not sure it's optimal, but can't improve it further). So except for a new ingenious program structure, the only way to go was either of us copying the other's code.

BTW How are you counting your characters? Because I make your latest version 138 chars, not 136.

And I can see how to save one more to 137: o,i,l;p(c){l--?p(c),p(o>l?c:32),p(c):putchar(c);l++;}main(c,v,n)int**v;{for(;i<=(l=n=abs(c=atoi(v[1])));i++)o=c+n?n-i:i,p(95),l=0,p(10);}

After joining everything to one line, wc says 137, but it counts the \n. l++ is nice - makes me wonder what the stack is for. And I thought my p wasn't the place to make progress...

C (163 161 chars)
i,l,N;f(n,m,s){if(n){s=--n<l?m:s;f(n,m,s);f(n,s,s);f(n,m,s);}else
putchar(m);}main(n,v)int**v;{for(i=N=abs(n=atoi(1[v]));i+1;i--)l=n<N?N-i:i,f(N,95,32),f(0,10);}

Borrows a couple of tricks from ugoren's answer, but the core logic is quite different. I couldn't follow his for loop, so it may be possible to hybridise and save a few more.

Common Lisp, 217 210 characters
(defun m(x)(flet((c(n v)(if(= n 0)`((,v))(cons(substitute v nil(make-list(expt 3 n)))(mapcar #'append(c(1- n)v)(c(1- n)" ")(c(1- n)v))))))(format t "~{~{~a~}~%~}"(let((r(c(abs x)'_)))(if(< x 1)(reverse r)r)))))

Expanded:
(defun m(x)
  (flet((c(n v)
    (if(= n 0)
       `((,v))
       (cons(substitute v nil(make-list(expt 3 n)))
            (mapcar #'append
                    (c(1- n)v)
                    (c(1- n)" ")
                    (c(1- n)v))))))
   (format t "~{~{~a~}~%~}"(let((r(c(abs x)'_)))(if(< x 1)(reverse r)r)))))

I figure if the Lisp code manages to beat any initial count for another language (C, 219) I'm doing OK :)

J, 44 39 38 37 bytes
' _'{~0&>_&(]|.)(,:1)1&(,],.0&*,.])~|

Uses iteration to build the next set starting with 1 (representing _) initially.
Usage
   f =: ' _'{~0&>_&(]|.)(,:1)1&(,],.0&*,.])~|
   f 0
_
   f 1
___
_ _
   f _1
_ _
___
   f 2
_________
___   ___
_ _   _ _
   f _2
_ _   _ _
___   ___
_________
   f 3
___________________________
_________         _________
___   ___         ___   ___
_ _   _ _         _ _   _ _
   f _3
_ _   _ _         _ _   _ _
___   ___         ___   ___
_________         _________
___________________________

Explanation
' _'{~0&>_&(]|.)(,:1)1&(,],.0&*,.])~|  Input: integer n
                                    |  Absolute value of n
                (,:1)                  The array [1]
                     1&(          )~   Repeat abs(n) times starting with x = [1]
                                 ]       Identity function, gets x
                            0&*          Multiply x by 0
                               ,.        Join the rows together
                         ]               Identity function, gets x
                          ,.             Join the rows together
                     1  ,                Prepend a row of 1's and return
      0&>                              Test if n is negative, 1 if true else 0
         _&(   )                       If n is negative
             |.                          Reverse the previous result
            ]                            Return that
                                       Else pass the previous result unmodified
' _'                                   The string ' _'
    {~                                 Select from the string using the result
                                       as indices and return

Nice! I haven't personally tried,  but I love using the agenda @.--perhaps it, combined with $:, could be of some use here? E.g. something like (zero case)`(positive case)`(negative case)@.*, or even maybe ":@_:`(positive case)`(|."1@$:)@.*.

I haven't attempted a recursive solution, but I could try it.

R, 141 139 137 bytes
m=abs(n<-scan());write("if"(n<m,rev,c)(c(" ","_")[Reduce(`%x%`,rep(list(matrix(c(1,1,1,1,0,1),3)),m),t(1))[,1+2^m-2^(m:0)]+1]),1,3^m,,"")

Try it online!
-15 bytes thanks too Giuseppe's use of '(' as the identity function; write instead of cat to print output; clever use of%x%.
-2 bytes thanks to Kirill L. by using c instead of '(' as the identity function.

could a Kronecker product work here? %x%? There might be some issues with taking alternating rows perhaps...

@Giuseppe I tried, building on your "Create an “H” from smaller “H”s" answer... I'll give it another try.

Ah, so it was you who upvoted that. that's the only reason I thought of kron too! I'd imagine this should be able to go down to like 125 bytes if we can find the right approach.

you can use \(`as the identity function so you can usewritedirectly instead ofcatand afor` loop. 141 bytes

@Giuseppe I had no idea ( could be used this way, or that if  could be used to select from two functions. And I will start using write... saves a lot of "\n".

I think, you can also use just c instead of ( as identity for -2 bytes, like I did here

@KirillL. @Giuseppe c does work!

Aha! 137 bytes using %x%! Note that your above answer could be 137 bytes as a full program as well.

@Giuseppe this is just wow.

Python, 177 164 characters
N=input()
n=abs(N)
c=lambda x:0if x<1 else x%3==1or c(x/3)
r=["".join([["_"," "][c(x/3**i)]for x in range(3**n)])for i in range(n+1)]
print"\n".join(r[::N>0 or-1])

Since you are using Python 2 you don't need to cast the results of input as int.  Your last two lines could be shortened to print"\n".join(r[::N>0 or-1])

@Steven I made changes. Thank you.

Perl, 113 chars
$i=abs($I=<>);@w=$_='_'x3**$i;while($i--){$x=3**$i;s/(__){$x}/'_'x$x.' 'x$x/eg;push@w,$_}say for$I>0?reverse@w:@w

Expanded:
$i=abs($I=<>);
@w=$_='_'x3**$i;
while($i--){
    $x=3**$i;
    s/(__){$x}/'_'x$x.' 'x$x/eg;
    push@w,$_
}
say for$I>0?reverse@w:@w

Batch, 265 262 242 236 235 bytes
@echo off
set/pn=
set c=%n%,-1,0
if %n% lss 0 set c=0,1,%n:-=%
for /l %%i in (%c%)do call:l %%i
exit/b
:l
set s=_
for /l %%j in (1,1,%n:-=%)do call:m %1 %%j
echo %s%
:m
set t=%s%
if %1 lss +%2 set t=%s:_= %
set s=%s%%t%%s%

Edit: Saved 12 19 bytes thanks to @l4m2. Saved 8 bytes by removing the unnecessary %a% variable.

This for 247 bytes.

@ConorO'Brien Mind you it would be 261 if I counted all the CRs as well as the LFs (which I'm sure you're not required to do but I'm lazy like that).

So you're not removing CR's from your code? Even though it's not required by .BAT files and stripped by SE anyhow? :P

@ConorO'Brien It's a penalty I accept of using Notepad to write Batch files.

Can you do something like set c=%n%,-1,0 [LF]  if %n% lss 0 set c=0,1,%a% [LF]  for /l %%i in (%c%)do call:l %%i?

@l4m2 Thanks, in fact it turns out I don't even need %a%.

seems also fine to let l jump into m

@l4m2 Won't work because m expects %1 and %2 to be numeric.

@Neil If you decide to count crlf as 2 bytes you should turn some newline into &(should try to golf)

@l4m2 Numbers beginning with 0 are treated as octal.

@Neil what about https://paste.ubuntu.com/p/mWCTRrXf9Q/

@l4m2 Yes that works thanks.

Can if %1 lss +%2 set t=%s:_= % workwithout the added zero before?

@l4m2 Both +1 and -1 are greater than + and -... WTF?

Let us continue this discussion in chat.

JavaScript 121 bytes
Inner recursive function, then take care of backward output if needed
n=>(f=(n,t=n&&f(n-1),r=t[0])=>n?[r+r+r,...t.map(x=>x+t[n]+x)]:['_',' '],f=f(n<0?-n:n),f.pop(),n<0?f.reverse():f).join`\n`

Less golfed
n=>{
  var f = n => { // recursive function
    var t = n && f(n-1), r = t[0]
    return n
      ? [r+r+r, ...t.map(x => x+t[n]+x)]
      : ['_',' ']
  };
  f = f(n < 0 ? -n : n);
  f.pop(); // last row is all blanks
  if (n<0) f.reverse();
  return f.join`\n`
}

Test

var F=
n=>(f=(n,t=n&&f(n-1),r=t[0])=>n?[r+r+r,...t.map(x=>x+t[n]+x)]:['_',' '],f=f(n<0?-n:n),f.pop(),n<0?f.reverse():f).join`\n`

function go()
{
  var n=+I.value
  O.textContent = F(n)
}

go()
<input id=I type=number value=3 oninput='go()'>

PowerShell, 111 bytes
filter f{if($s=[math]::Sign($_)){($x=$_-$s|f|%{$_+' '*($l=$_|% Le*)+$_})|?{$s-1};'_'*3*$l;$x|?{$s+1}}else{'_'}}

Try it online!
Less golfed:
filter f{
    if($sign=[math]::Sign($_)){
        $x=$_-$sign|f|%{
            $_+' '*($length=$_|% Length)+$_
        }
        $x|?{$sign-1}  # output $x if $_ is negative
        '_'*3*$length
        $x|?{$sign+1}  # output $x if $_ is positive
    }
    else{
        '_'
    }
}

Husk, 31 bytes
*±¹↑→a¹¡oṁ§ṘȯJ' R2←o/3LgR'_`^3a

Try it online!
Doesn't really use the cantor set, just uses a replacement method (and an infinite list).
Now, you may ask: why is an infinite list useful here? Here's an explanation:
Explanation
¡oṁ§ṘȯJ' R2←o/3LgR'_`^3a
                       a take abs(n)
                 R'_`^3 repeat underscore n times(take n=3)
¡o                      iterate on this string, collecting results
                g       group the string into equal runs:
                        ["_________"]
  ṁ                     map each group to the following, and concatenate:
         R2←            repeat the first character twice
      J'                join with spaces
                        "_________" → "_ _"
            o/3L        take length /3 → 3
   §Ṙ                   Repeat each character that many times
                        "___   ___"

Then:
   ↑→a¹ take n+1 elements from the list
*±¹     multiply by sign(n) (reverse if negative)

JavaScript (Node.js), 148 bytes
n=>f=(L=n<0&&n,R=n>0&&n)=>[...Array(r=3**(n>0?n:-n))].map(_=>((j++).toString(3)+1).indexOf(1)>(L>0?L:-L)?'_':' ',j=r+r).join``+`
${L++<R?f(L,R):''}`

Try it online!

Python 2, 102 bytes
lambda n:'\n'.join(eval("[i+' '*len(i)+i for i in"*abs(n)+"'_'"+"]+['___'*len(i)]"*abs(n))[::n<1or-1])

Try it online!

Prolog (SWI), 265 232 213 bytes
S-E-R:-between(S,E,R).
[]/R/R.
[H|T]/B/R:-T/[H,32,H|B]/R.
N+R:-(N>0->O is N-1,O+S,S/[]/R;R=`_`).
N*[H|T]:-1-N-_,writef("%n",[H]);N*T.
_*[]:-nl.
-N:-(0-N-J,K is N-J;N-0-I,J is -I,K is I-N),L is 3^K,J+R,L*R,1=0;1=1.

Try it online!

Rust, 243 bytes
|i:i8|(0..i.abs() as usize).any(|j|print!("{}
",if i>0{f(j,3usize.pow(i as u32-1))}else{f(-i as usize-j-1,3usize.pow(-i as u32-1))})>());fn f(i:usize,j:usize)->String{if i<1{"_".repeat(j)}else{[f(i-1,j/3)," ".repeat(j/3),f(i-1,j/3)].concat()}}
Once again I win the prize for the longest answer
Attempt This Online!
Rust, 247 bytes
|x:i32|->String{let r=(0..x.abs() as u32).map(|d|{(0..3_usize.pow(x.abs() as u32-1)).map(move|w|if(0..d).all(|v|w/3_usize.pow(x.abs() as u32-2-v)%3!=1){'_'}else{' '}).chain(['\n'])});if x<0{r.rev().flatten().collect()}else{r.flatten().collect()}};
Attempt This Online!

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

authors: webknjaz -- Слава Україні

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
Build a code minifier
Pick a programming language.
In that language, write a function or program that takes as input a string of working code (in the same language).
It should return/output a minified version of the input code.  The output should be functionally equivalent to the input.
Answers should contain both

The code that does the minifying (should be readable/non-golfed)
The resulting output after passing your code (that is, the code that does the minifying) in to itself

The shortest output wins.
Edit: notes explaining the minification methods you used are appreciated.
Edit: obviously, minification methods could vary from language to language, but a good-faith attempt at writing a minifier for this challenge would most likely perform actions such as

Removing unnecessary whitespace
Removing unnecessary newlines
Removing comments
Shortening variable names

There is a definite tension between wanting the code to be "readable/non-golfed" and wanting it to minify to as short as possible. There's more to golfing than using one-character names and removing whitespace.

@PeterTaylor I agree.  Do you have any suggestions to help resolve that tension and encourage people to submit interesting results?

Duplicate of http://codegolf.stackexchange.com/questions/3652/write-a-code-golfer/4379#4379 ? I particularly like my BF answer there.

I think ugoren makes a good point. Your winning criterion encourages competitors to do as little as possible since doing stuff costs characters -- characters which expand the program which is the input. Best to do as little as possible so the input is not very big in the first place. To put it another way - the best minifiers will be big, even after minification. Testing the shortest output will not show the best minifier.

A better winning criterion might be to do the minification on the program as you've suggested, but to judge based on the difference between input and output. Although that might encourage competitors to stuff their programs with spaces and comments...

@CMP that question has general goals, but no metric for judging success.

@Gareth: Indeed, stricly according to the challenge as written, any sufficiently short implementation of cat has a good chance of winning.  (Note that, in GolfScript, the empty program acts as cat -- although the output ends up containing an extra trailing newline that puts its length at 1 char.)

This seems perfectly clear to me. There is (or is no longer) any non-objective requirement or winning criterion, and the spec is pretty clear. While "functionally equivalent" may be difficult to determine in all cases, the meaning isn't particularly unclear.

Brainfuck
I always had in mind to do this, so here we go:
>>>,
[
[->+>+<<]             copy input

<<<+++++++++++++      fill cell with 13 for subtraction
[->+>+>+<<<]          and duplicate some times

>>>[->---<]           sub 39
>----                 43

[                     plus
-
[                     comma
-
[                     minus
-
[                     dot

<<[->>-<<]>>-         60

[                     less than
--
[                     greater than

<<<[->>>--<<<]>>>     86
---                   91

[                     open square bracket
--
[                     closing square bracket

>[-]                  remove copy

]]]]]]]]

>[.[-]>]              the copy has not been removed; print

<<[-]<<<[-]>[-]>      clean up

,]

Compresses itself to (144 characters):
>>>,[[->+>+<<]<<<+++++++++++++[->+>+>+<<<]>>>[->---<]>----[-[-[-[<<[->>-
<<]>>-[--[<<<[->>>--<<<]>>>---[--[>[-]]]]]]]]]>[.[-]>]<<[-]<<<[-]>[-]>,]

The size of the compressing could probably still reduced a bit. The compression alogorithm itself is near perfect, it's hard to do any more than removing non-+-[]<>,..

Next easiest would be to compress any chain of +'s and -'s (or <>) to its equivalent. ex: ++-++ :: +++ or >>><< :: >

@CMP your code example should never be in real application, so this should not produce any more compression.

I have written code with that, mostly when I copy snippets from esolang that try to be independent of your memory layout. After substituting the proper number of pointer movements, sometimes such a situation can occur. Just a nice sanity check you could perform.

@TehShrike no, it simply preserves the 8 Brainfuck symbols.

Dang it, that was my idea as soon as I read the question! :(

Python 2.6
I tried to implement a basic Python minifier which does the following things:

Removing unnecessary whitespace
Removing unnecessary newlines
Removing comments
Shortening variable names

As others stated, the winning criteria (shortest output when run through itself) does not make a whole lot of sense for a minifier if you want to start with a non-golfed solution.
Original (2591 characters)
# imports
import keyword, tokenize, sys, token, itertools

# vars
line = ""
out = [] ; block = []
idx = 0 ; previdx = 0 ; prevdirection = 0
varnames = set() ; imports = set()
t = tokenize.generate_tokens(sys.stdin.readline)
newline = '\n'

# settings
replace_varnames = True

while 1:
    try:
        toknum, tokval, _, _, _ = t.next()
        iskwd = tokval in keyword.kwlist

        if toknum == 1:
            if ''.join(line).lstrip().startswith("import "):
                imports.add(tokval)
            else:
                if not (iskwd or line[-1]=="." or tokval in __builtins__.__dict__.keys() or tokval.startswith("_") or len(tokval) <=2 or tokval in imports):
                    varnames.add(tokval)

        if toknum == 53:
            continue

        if toknum == 4:
            block.append(' '.join(x for x in ("".join(l for l in line if l)).strip().split()))
            line = []

        if toknum == 5 or toknum == 6:
            if out and out[-1] != newline:
                out.append(newline)

            previdx = idx
            idx += (-1,1)[toknum==5]

            indenting = previdx < idx
            dedenting = previdx > idx
            prefix = " " * previdx
            base = ";".join(l for l in block)
            if dedenting and prevdirection == 1:
                out.pop()
                out.append(base)
            else:
                if len(block) > 1:
                    if indenting:
                        out.append(prefix + ";".join(l for l in block[:-1]))
                        out.append(newline)
                        out.append("".join(prefix + l for l in block[-1:]))
                    else:
                        out.append(prefix + base)
                elif len(block) == 1:
                    out.append(prefix + base)

            block = []
            prevdirection = [-1,1][indenting]
        space_if_needed = [""," "][iskwd and tokval not in ("else","try")]
        line += space_if_needed + tokval + space_if_needed
    except StopIteration:
        out.append(" " * idx + ";".join(l for l in block))
        break

total_out=''.join(out)+newline
if replace_varnames:
    wrappers = [";"," ", ":", "=", "(", "[", ")", "]", ".",",","*","+","-","/","<",">","!","\n"]
    wrl = list(itertools.permutations(wrappers,2)) + zip(wrappers, wrappers)

    for i, e in enumerate(varnames):
        # print i, e, "v"+str(i)
        for p, a in wrl:
            total_out = total_out.replace(p+e+a,p+"v"+str(i)+a)

print total_out[0:-1]

Minified (by itself), 1388 characters (a 46 % reduction)
import keyword,tokenize,sys,token,itertools;v16="";v20=[];v19=[];v4=0;v15=0;v17=0;v10=set();v6=set();t=tokenize.generate_tokens(sys.stdin.readline);v8='\n';v13=True
while 1:
 try:
  v18,v9,_,_,_=t.next();v2=v9 in keyword.kwlist
  if v18==1:
   if ''.join(v16).lstrip().startswith("import "):v6.add(v9)
   else:
    if not (v2 or v16[-1]=="." or v9 in __builtins__.__dict__.keys() or v9.startswith("_") or len(v9)<=2 or v9 in v6):v10.add(v9)
  if v18==53:continue
  if v18==4:v19.append(' '.join(x for x in ("".join(l for l in v16 if l)).strip().split()));v16=[]
  if v18==5 or v18==6:
   if v20 and v20[-1]!=v8:v20.append(v8)
   v15=v4;v4+=(-1,1)[v18==5];v5=v15<v4;v12=v15>v4;v11=" "*v15;v14=";".join(l for l in v19)
   if v12 and v17==1:v20.pop();v20.append(v14)
   else:
    if len(v19)>1:
     if v5:v20.append(v11+";".join(l for l in v19[:-1]));v20.append(v8);v20.append("".join(v11+l for l in v19[-1:]))
     else:v20.append(v11+v14)
    elif len(v19)==1:v20.append(v11+v14)
   v19=[];v17=[-1,1][v5]
  v3=[""," "][v2 and v9 not in ("else","try")];v16+=v3+v9+v3
 except StopIteration:v20.append(" "*v4+";".join(l for l in v19));break
v1=''.join(v20)+v8
if v13:
 v0=[";"," ",":","=","(","[",")","]",".",",","*","+","-","/","<",">","!","\n"];v7=list(itertools.permutations(v0,2))+zip(v0,v0)
 for i,e in enumerate(v10):
  for p,a in v7:v1=v1.replace(p+e+a,p+"v"+str(i)+a)
print v1[0:-1]

Known limitations:

Keyword arguments are problematic when variable name shortening is on.
The code is ugly and can probably break some of the more dynamic Python constructs. It does work fine for itself (and other simple scripts) though.

I think your wrappers list is incomplete. What about \t and ^? And you can shorten names more using letters (or at least hex: "v%x"%i)

Nice!  This is sweet!

To minify the indentation, you can replace pairs of spaces by tab characters. See this answer: http://codegolf.stackexchange.com/questions/54/tips-for-golfing-in-python/58#58

JavaScript, 562 → 334 bytes
40% reduction, but it's pretty compact to begin with.
Uses the Google Closure Compiler API in advanced optimization mode, which might rename certain variables but it is still functionally equivalent.
function minify(input) {
    // Closure Compiler API url:
    var url = 'http://closure-compiler.appspot.com/compile';

    // Create and initialize the Ajax request:
    var rq = new XMLHttpRequest();
    rq.open('POST', url, false);
    rq.setRequestHeader('Content-Type', 'application/x-www-form-urlencoded');

    // Send the request:
    rq.send('js_code=' + encodeURIComponent(input) +
        '&compilation_level=ADVANCED_OPTIMIZATIONS&output_format=text&output_info=compiled_code');

    // Return the result and just assume the code succeeded (hey, it's Google):
    return rq.responseText;
}

Here's a sample jsFiddle, and here's the code run on itself when compiled without a run:
window.a=function(c){var b=new XMLHttpRequest;b.open("POST","http://closure-compiler.appspot.com/compile",!1);b.setRequestHeader("Content-Type","application/x-www-form-urlencoded");b.send("js_code="+encodeURIComponent(c)+"&compilation_level=ADVANCED_OPTIMIZATIONS&output_format=text&output_info=compiled_code");return b.responseText};

lol.  Clever! Though the code here doesn't do any minifying, just calls another minifyer :-P

APL, 76 character output
{(~(n ↓ b) ∧ ' ' ⍷ d) / d←(n←- +/ ∨\ ('⍝'⍷⍵) ∧ b←~a∨ ≠\ a←(('''' ⍷ ⍵) ∧ {⍵ ∧ ¯1⌽⍵}~'''''' ⍷ ⍵)) ↓ ⍵}⍞   ⍝ This takes a line of APL as input and removes comments and unnecessary spaces!

This isn't really a serious attempt at golfing, but it was interesting to implement.. I think? It removes comments (⍝) and spaces. This works on Dyalog APL. (Note that it preserves spaces and ⍝ characters found in quoted strings.)
Example (first line is the code, second is the input, third is the output):
      {(~(n ↓ b) ∧ ' ' ⍷ d) / d←(n←- +/ ∨\ ('⍝'⍷⍵) ∧ b←~a∨ ≠\ a←(('''' ⍷ ⍵) ∧ {⍵ ∧ ¯1⌽⍵}~'''''' ⍷ ⍵)) ↓ ⍵}⍞   ⍝ This takes a line of APL as input and removes comments and unnecessary whitespace!
{(~(n ↓ b) ∧ ' ' ⍷ d) / d←(n←- +/ ∨\ ('⍝'⍷⍵) ∧ b←~a∨ ≠\ a←(('''' ⍷ ⍵) ∧ {⍵ ∧ ¯1⌽⍵}~'''''' ⍷ ⍵)) ↓ ⍵}⍞   ⍝ This takes a line of APL as input and removes comments and unnecessary whitespace!
{(~(n↓b)∧' '⍷d)/d←(n←-+/∨\('⍝'⍷⍵)∧b←~a∨≠\a←((''''⍷⍵)∧{⍵∧¯1⌽⍵}~''''''⍷⍵))↓⍵}⍞

APL (Dyalog APL), 2145 → 763 bytes (−64%)
 Minify←{
     ⍝ Minifies source code ⍵ — see examples at end
     ns←⎕NS ⍬  ⍝ namespace to keep names created by side-effects

     src←ns.(61 ⎕ATX ⎕FX) '_',⊆⍵  ⍝ get normalised source
     ⍝ make large magnitude numbers use exponential format:
     src←'\d+\.\d+' '\d00+'⎕R{⍵.PatternNum: (⊃,'E',∘⍕¯1+≢)⍵.Match ⋄ ⍵.Match} src

     (from to)←⍬ ⍬
     (from to),∘⊂←'''[^'']+''|\d+ [eEjJ]'       '&'      ⍝ preserve strings and space before e/j
     (from to),∘⊂←' ?⍬ ?'                       '⍬'      ⍝ remove spaces around ⍬
     (from to),∘⊂←'([^#]) # ([^#])'             '\1#\2'  ⍝ remove spaces around #
     (from to),∘⊂←'# ([^#])'                    '#\1'    ⍝ remove space after #
     (from to),∘⊂←'([^#]) #'                    '\1#'    ⍝ remove space before #
     (from to),∘⊂←' ([⎕:])'                     '\1'     ⍝ remove space before ⎕ and :
     (from to),∘⊂←' *⍝.*|^ +'                   ''       ⍝ remove comments and leading spaces
     (from to),∘⊂←'(\pL) 0\.'                   '\1.'    ⍝ make X 0.5 into X.5
     (from to),∘⊂←'(\d) (\pL)'                  '\1\2'   ⍝ make 1 X into 1X
     (from to),∘⊂←' ?(⋄ ?)+'                    '⋄'      ⍝ make 1 X into 1X
     (from to),∘⊂←'(:End)([DFHPRTW]|If|Sel)\w+' '\1'     ⍝ make :EndXYZ into :End where permitted
     (from to),∘⊂←':Return|:GoTo '              '→'      ⍝ Replace keywords with "→"

     src←from ⎕R to ⊢ src  ⍝ do it!

     ⍝ make small magnitude numbers use exponential format:
     src←'\b0\.00+(\d+)'⎕R{lead←-/⍵.Lengths ⋄ mantissa,'E',⍕10⍟⍵.Match÷⍥⍎mantissa←lead↓⍵.Match} src

     src←'\b0\.'⎕R'.' ⊢ src  ⍝ make 0.5 into .5

     _←'adic' ns.⎕CY 'dfns'  ⍝ import adic from dfns.dws
     from←' '(2⌽'\b\b',~)¨⍨' '~¨⍨↓ns.(⎕REFS ⎕FX)'\.[∆⍙\w]+'⎕R' '⍠'UCP' 1 ⊢ src  ⍝ get non-dotted names
     from{⍵,⍺,⍵}¨←⊂'\b'                ⍝ names have to be in isolation
     to←('_',⎕A,⎕C ⎕A)∘ns.adic¨⍳≢from  ⍝ generate short names
     (from to),⍨∘⊂←'''[^'']+''' '&'    ⍝ preserve strings
     from ⎕R to ⊢ 1↓src~⊂''            ⍝ minify names and remove blank lines

     More examples:
         Refs: ⎕SE # ## ⎕DMX #
         Numbers: 100000 0.000001 16 E3 16 F3
 }
Run it on its own source to get:
B←{
K←⎕NS⍬L←K.(61⎕ATX⎕FX)'_',⊆⍵
L←'\d+\.\d+' '\d00+'⎕R{⍵.PatternNum:(⊃,'E',∘⍕¯1+≢)⍵.Match⋄⍵.Match}L
(H M)←⍬⍬
(H M),∘⊂←'''[^'']+''|\d+ [eEjJ]' '&'
(H M),∘⊂←' ?⍬ ?' '⍬'
(H M),∘⊂←'([^#]) # ([^#])' '\1#\2'
(H M),∘⊂←'# ([^#])' '#\1'
(H M),∘⊂←'([^#]) #' '\1#'
(H M),∘⊂←' ([⎕:])' '\1'
(H M),∘⊂←' *⍝.*|^ +' ''
(H M),∘⊂←'(\pL) 0\.' '\1.'
(H M),∘⊂←'(\d) (\pL)' '\1\2'
(H M),∘⊂←' ?(⋄ ?)+' '⋄'
(H M),∘⊂←'(:End)([DFHPRTW]|If|Sel)\w+' '\1'
(H M),∘⊂←':Return|:GoTo ' '→'
L←H⎕R M⊢L
L←'\b0\.00+(\d+)'⎕R{I←-/⍵.Lengths⋄J,'E',⍕10⍟⍵.Match÷⍥⍎J←I↓⍵.Match}L
L←'\b0\.'⎕R'.'⊢L
F←'adic'K.⎕CY'dfns'
H←' '(2⌽'\b\b',~)¨⍨' '~¨⍨↓K.(⎕REFS⎕FX)'\.[∆⍙\w]+'⎕R' '⍠'UCP' 1⊢L
H{⍵,⍺,⍵}¨←⊂'\b'
M←('_',⎕A,⎕C⎕A)∘K.adic¨⍳≢H
(H M),⍨∘⊂←'''[^'']+''' '&'
H⎕R M⊢1↓L~⊂''
C G:
E:⎕SE# ##⎕DMX#
D:1E5 1E¯6 16 _ 16F3
}
Run this on itself to get something very similar (only names differ).
Removes:

All redundant spaces
Comments
Empty lines
Leading and trailing zeros in numbers

Abbreviates:

Numbers into exponential form (only when it actually saves characters)
Control structure keywords to their shorter alternate forms
All used names into _, A, B, C,… Z, a,… z, __, _A, _B,…

Fails on:

Evaluated strings
Global and to-be-imported names (abbreviates them)

Bash, 17 characters output
They say my Python solution below isn't a minimizer. So here's one that does minimize, and it's even shorter:
 sed -e '1 s/^ //'

It reduces its own size from 18 to 17 characters.
Python, 38 character output
I misunderstood the question a bit, so my 0 character attempt was incorrect.
So I have a new and improved solution. I'd start a new answer, but since it's in the same spirit, I prefer to edit.
I'm sure it can be much improved, especially if you switch the language. But as it is, I'm still way ahead of the competition:
import sys
for l in sys.stdin:print l,

When given itself as input, you get a 100% equivalent program, 38 characters long.

Python, 0 character output (but not when run on itself, so it doesn't count).
import sys
program = [ l for l in sys.stdin ]
if len(program)>1 or program[0]!="x=12345\n":
    print "".join(program),

Sample input (also Python):
x=12345

I admit, it isn't very effective on most programs.
However, it reduces my example to 0 chars, still keeping it equivalent.
"The shortest output wins" - I don't think anyone can top this.

But what is the output when you feed your program code in (instead of feeding in arbitrary example code)?

Also, even ignoring the fact that the input was incorrect, the output given there is not functionally equivalent to the input.

@TehShirke: My program accepts any program, and outputs an equivalent (and sometimes identical) program, in all cases. In one example, x=12345, the output is an empty program. Both input and output programs do nothing (i.e. no output or environment change), which makes them functionally equivalent. The fact that x changes is meaningless. If I wrote clever code that eliminates unused variables, would you object?

And also, if it isn't clear, I'm trying to make a point about your winning criterion.

I think by "output", he means "output given your minimizer program as input", not "shortest output given arbitrary input".

@KeithRandall, Yes, now it's clear. Though I did miss the "in to itself" part.

OK, I fixed it. The new version, run on itself, is much longer than 0 characters, but still shortest so far.

It's not a minimiser, though. The spec is rather loose, but this is stretching it beyond breaking point.

@PeterTaylor, I'm not sure where the breaking point is. I'm indeed stretching it, but I don't think the other solutions do significantly more than mine. Anyway, my newest version stretches a bit less, and returns an even shorter output.

Your bash solution can break scripts that contain strings which span multiple lines.

@hammar, good point. Fixed, at a cost of 2 characters. I wonder if other solutions are susceptible to similar problems (if I could read APL or BrainF*ck, I'd try to figure it out).

@ugoren Brainfuck beats you anyway on the print stdin-cheat: ,[.,]

@copy, No, it doesn't. As Peter Taylor's comments, a minimizer must reduce the size of something. And if you disagree, I can still beat it with Bash: cat

I'm sorry, but your python solution doesn't minify code at all.  Please, if you want to answer this question, make a good-faith effort at writing a legitimate code minifier.

@TehShirke, My solution is the lastest Bash solution. I left the rest, because I think the discussion in the comments in interesting, and it loses meaning without them. Note that other solution don't do much more minification than mine, and they also violate your first requirement (should be readable). Last, you said this isn't a duplicate of a previous question, because it has a metric for judging success. What value is the metric if you toss it away for "a good-faith effort"?

@ugoren: FWIW, my APL solution is only supposed to work on single lines of input, although it does pay heed to string/character literals. Making it work for multiple lines is trivial, though.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Busy Brain Beaver
Write a brainfuck program of no more than 256 characters that takes as many steps as possible, but does not loop infinitely.  The program may not take any input.
More specifically:

Assume an infinite number of cells to the right.
A < when at the leftmost cell does nothing.
A - when cell value is zero sets cell to 255.
The instructions +-<>. all count as one step when executed.
When a [ or ] is encountered, it counts as one step.  However, if the condition is true and control flow jumps, the corresponding ] or [ does not again count as a step.
The solution that takes the most steps wins.
If there is some kind of pattern in your solution, giving a function for how many steps a similar program of length n would take is appreciated but not mandatory.
To count instructions, you can use this modified interpreter:

Example:
++[-]

The encountered instructions are ++[-]-], and the program ran for 7 steps.

I would be surprised if the winner terminates without overflowing the interpreter's count. Bear in mind that the 6-state TM busy beaver takes at least 10**36534 steps.

I agree. Seems highly likely you could write a <50 char BF program that could run for years. I'll get started.

Signed. The Busy Beaver research page at http://www.drb.insel.de/~heiner/BB/ is very interesting, especially the fact that the record programs run extremely long and they still have exact results (see http://www.drb.insel.de/~heiner/BB/bb-xlist.txt) - simulations remember states, build "macros" to save simulation steps etc.

@PeterTaylor: Fortunately, in Python, integers convert to some bignum type when they overflow. :)

@AntonGolov: unfortunately, in this universe, RAMs and HDs don't convert to infinite storage devices when you try to store bignums larger than 256 ^ size in bytes on them...

@leftaroundabout: Joking aside, I am looking for a way to determine the number of steps taken by the solutions automatically.  I know about the halting problem and all, but I'm wondering if I could boil it down to a multiplication and then take the sum of the logarithms of the coefficients.

@AntonGolov: For some programs, yes, you can do that.  However... write a program that looks for zeros of the Riemann zeta function.  Find a zero, and halt.  Otherwise continue searching.  Figure out when that halts, and you'll get a million dollars (and piss off a bunch of mathematicians who believe RH).

Hmm... sorry, I'm a tard.  The above suggests computation with transcendentals, which is not doable with our piddly computers.

@boothby Its perfectly possible to do exact computations involving transcendentals on current computers.  The components of the values just have to be stored in a more abstract representation than the normal float or double primitives used for general everyday computing.  (At that point the computer is mostly just manipulating strings of that represent the equation)

Here's a 41-character program that eventually halts, leaving more than 10↑(10↑28) contiguous cells set equal to 1 (so the number of instructions executed is very much greater than that):
>+>+>+>+[->[>]+[->[>]+[->[>]+[<]+<]+<]+<]

If I'm not mistaken, that's a correct translation of the following program in the BF-variant language that uses a single bit for each memory cell (i.e., cell content 0..1 instead of 0..255, so '+' acts to simply flip the bit-value):
>+>+>+>+[+>[>]+[+>[>]+[+>[>]+[<]+<]+<]+<]

The exact value (the number of adjacent 1-bits) produced by the latter program is
3 * (2 ↑ 118842243771396506390315925503 - 1) + 1.

The above program initializes & computes a function that grows like 2↑↑x (in Knuth up-arrow notation).  Similar conversion of a variant-BF program that initializes & computes a function that grows like 2↑23x provides the following 256-character program:
>+>+>+>+>+>+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+

which eventually halts, leaving more than 2↑236 adjacent cells set equal to 1 (so the number of steps is enormously more than that).
NB-1: 2↑236 is an "inconceivably large" number; e.g., even 2↑46 = 2↑↑↑↑6 already surpasses the first term (3↑↑↑↑3) in the sequence used to compute Graham's number.
NB-2: I think it's likely that 256 characters is enough for a BF program to initialize & compute a function with output much larger than Graham's number — if I find time, maybe I'll try to write one.
NB-3: In case anyone is interested in the origin of the above programs, here are some programming resources for "Brainf*ck F", with various programs written in Python. ("Brainf*ck F", or just "F", is what I called a Turing-complete variant of the Smallf*ck esolanguage.) I just now uploaded these files, which have been offline for several years, and for now the linked webpage is just a "file cabinet" -- see the file Busy_Beavers.txt for a detailed discussion relevant to the above programs.

This is a clear winner at the moment (unless I'm just underestimating the others).  More suggestions are very welcome, but I'll mark it as accepted for now.  If anyone disagrees, please do comment.

When you get to this level, it becomes unrealistic to assume you have an interpreter with infinite memory. I am starting to think this would be a better challenge with finite wrapping memory, so we could actually run the answers.

Here is a nice 39 character one:
-[>-[>-[-[>+<-]<[>+<-]<[>+<-]>>>]<-]<-]

It basically makes a 3 space wide 'sled' that it moves right and decrements by one. Completed in 31,919,535,558 instructions, with the innermost loop executing 256^3 times. I still have plenty of room to extend this pretty far at a rate of 14 characters to another order of magnitude to the run time.
Works on any interpreter with unbounded memory, or with wrapping memory.
I leave it a an exercise to the reader to determine when the improved by 2 loops version will finish:
-[>-[>-[>-[>-[-[>+<-]<[>+<-]<[>+<-]<[>+<-]<[>+<-]>>>>>]<-]<-]<-]<-]

It has now run overnight, and it is over 3,000,000,000 steps. Still has not gotten through a single iteration of the outer loop. Has barely made it through 15% of the second loop.

This programs works in infinte number of cells.
Two values are initialized in the
begining with ascii values 255.
The first value at the first rotation of main loop is splited to 255 cell and they are initialized with 255 each, at the second rotation of main loop the each value in 255 cells again splits up to 255*255 cells, in the same way for 255 rotation of main loop the total cells initialized will be 255^255 .
The second value determines how much times the main loop is to be repeated.
>->>-[<<[<]>[[[>]>>>[>]-[<]<<<[<]>-]>]>[>>[>]>+<<[<]<-]>>[>]>-]

This program is almost same as my previous program , difference is that the value determining the outer loop remains fixed in a particular cell so both number of cells initialized and total steps at the end of the program can be increased
->>-<<[>>[>]<[[>>[>]-[<]<-]>>[[<+>-]>]<<[<]<]>>[[<+>-]>]<<[<]<-]

cells initialized at the end of program 255^255
-[>-[>->>[-]-<<[>>[>]<[[>>[>]-[<]<-]>>[[<+>-]>]<<[<]<]>>[[<+>-]>]<<[<]<-]<-]<-]

cells initialized at the end of program 255^255^3
I further modified it to run for even more number of steps.
->>>->>-<<<<<[>>>[>]<[[>>[>]<[[>>[>]-[<]<-]>>[[<+>-]>]<<[<]<]>>[[<+>-]>]<<[<]<-]<[>>>[[<+>-]>]<<[<]]<]>>>>[[<<+>>-]>]<-<<[<]<<-]

it initializes 255^255 cells during first rotation of main 255^(255^255*255) cells during second rotation of main loop 255^{255^(255^255*255)*255} cells during third rotation of main loop in this way loop repeats 255 times

Looks great!  Sorry for not yet accepting an answer -- I've got to take some time to look at these and figure out order of growth.  When you say "255^255255", do you mean "255^(255255)"?  (I'd expect "255^256" otherwise.)