| Bytes | Lang | Time | Link |
|---|---|---|---|
| 992 | Python3 | 240829T193401Z | Ajax1234 |
| 1074 | Haskell | 120202T131105Z | ceased t |
| 2225 | C# | 120201T220911Z | captncra |
| 1079 | Python | 120202T000856Z | Keith Ra |
Python3, 992 bytes
from itertools import*
M=[(1,0),(-1,0),(0,-1),(0,1)]
E=enumerate
def f(b):
Z=eval(str(b))
q=[(d:={(x,y):v for x,r in E(b)for y,v in E(r)},{i:0 for i in d if d[i].isdigit()})]
for a,b in q:
if[]==(k:=[j for j in b if b[j]!=int(a[j])]):
for(x,y),v in a.items():Z[x][y]=v
return'\n'.join(map(''.join,Z))
t=min(k,key=lambda x:int(a[x]))
x,y=t
Q,S=[(int(a[t])-b[t],4,[])],[]
for X,e,O in Q:
if 0==X:S+=[O];continue
for i in[1,2]:
if X-i>=0 and e:Q+=[(X-i,e-1,O+[i])]
W=[]
for O in S:
for D in combinations(M,len(O)):
A,B,F=[],[],1
for o,(X,Y)in zip(O,D):
j,k=x,y
while 1:
if(T:=(j+X,k+Y))not in a:F=0;break
if a[T].isdigit():
if b[T]+o<=int(a[T]):B+=[(T,o)]
else:F=0
break
if' '!=a[T]:F=0;break
A+=[(T,['|','║'][o==2]if X else['-','═'][o==2])]
j,k=T
if F==0:break
if F:W+=[({**a,**{T:R for T,R in A}},{**b,**{T:b[T]+R for T,R in B},(x,y):int(a[(x,y)])})]
if W:
for i in W:q+=[i]
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
結合(事:覧)(物:一覧)=(事,物):結合 覧 一覧
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;
}
}
}
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.