Skip to main content
Code Golf

Return to Answer

This is, like, a tiny bit faster
Source Link
Anders Kaseorg
Anders Kaseorg
  • 40.7k
  • 3
  • 76
  • 149

Clingo, 5.3 hours202 seconds for 20×20

#script (python) import clingo import itertools import sys def main(prg): matrix = [list(line.split()) for line in sys.stdin] def data(): for i, row in enumerate(matrix): for j, cell in enumerate(row): if cell == '0': yield f'cell(({i}, {j})).\n' def on_model(model): step = {} for atom in prg.symbolic_atoms: if atom.symbol.name == 'step' and model.contains(atom.symbol): a, d, b = atom.symbol.arguments step[a] = d, b moves = [] a = clingo.Tuple((0, 0)) while astep[a][1] in!= stepclingo.Tuple((0, 0)): d, a = step[a] moves.append(d) print(len(moves) + 1) print(','.join(f'{d} {len(list(g))}' for d, g in itertools.groupby(moves))) prg.add('data', [], ''.join(data())) prg.ground([('base', []), ('data', [])]) prg.solve(on_model=on_model) #end. #program base. dir(s, (1, 0); e, (0, 1); n, (-1, 0); w, (0, -1)). adj((X, Y), D, (X+DX, Y+DY)) :- cell((X, Y)), dir(D, (DX, DY)), cell((X+DX, Y+DY)). adj(A, end, (0, 0)) :- cell(A). {step(A, D, B) : adj(A, D, B)} <== 1 :- visit(A). :- cellvisit(B), {step(A, D, B) : adj(A, D, B)} >=!= 21. visit((0, 0)). visit(B) :- step(A, D, B). :~ visit(A). [-1, A] #show step/3. 
$ clingo -q longest.lp < 20x20.in  clingo version 5.2.2 Reading from longest.lp Solving... 1 2 s 1 3 es 2 4 es 3 5 e 3,s 1 6 e 3,s 2 7 e 3,s 3 9 e 3,s 85 … 263264 s 4,e 1,wn 4,e 2,s 1,nw 1,s 1,e 1,s 1,nw 1,s 1,e 1,s 1,nw 31,s 1,ew 1,sn 1,nw 1,s 13,e 21,sn 111,e 1,ws 12,ne 1,wn 113,e 32,s 1,e 2,sn 17,e 21,ws 2,e 2,wn 1,ew 1,wn 1,ne 24,s 15,nw 1,ws 1,ne 1,s 2,n 1,w 42,es 1,we 12,ns 1,w 1,s 1,e 41,s 1,nw 2,s 2,e 1,w 1,e 1,s 12,ew 1,wn 3,e 1,s 6,n 1,se 1,en 1,sw 1,n 23,we 1,n 1,sw 41,en 1,we 2,en 23,sw 1,ns 12,w 3,s 1,e 1,s 1,n 4,w 1,ns 1,we 1,es 14,w 1,n 2,w 1,s 3,e 1,s 1,nw 1,s 1,e 1,s 1,nw 1,s 1,e 13,s 1,ne 1,sn 23,e 1,wn 1,e 1,s 2,w 1,s 1,e 41,s 1,w 1,ns 32,w 1,n 1,w 2,en 1,w 2,s 1,e 1,s 1,e 1,w 2,n 1,ws 1,ne 2,wn 1,e 31,s 1,e 13,sn 32,e 2,wn 1,e 2,s 13,e 1,w 2,n 1,w 3,e 1,w 1,n 16,w 31,en 1,we 1,n 19,w 1,en 1,we 1,n 1,w 12,s 3,e 1,ws 1,nw 1,ws 1,e 1,ws 1,nw 1,ws 1,e 21,s 91,nw 1,s 1,e 1,s 31,nw 1,s 13,e 1,s 51,nw 1,ws 1,ne 1,s 12 265 e 3,s 24,we 1,n 4,e 2,s 1,w 21,s 1,e 1,s 1,w 1,s 1,e 1,s 1,w 1,s 31,ew 21,sn 111,ew 1,ns 123,we 21,n 1,e 1,ns 312,e 1,sn 313,e 2,s 1,e 2,sn 37,e 1,ns 2,e 12,n 21,w 21,n 1,e 24,ns 5,w 1,s 1,e 1,s 1,w 2,ns 41,e 62,s 1,w 1,s 1,e 1,s 111,w 12,ns 61,w 1,ns 12,ew 1,n 13,we 1,n 1,e 1,n 1,w 1,n 23,we 1,sn 1,w 1,n 1,e 2,n 3,w 1,s 2,ew 23,s 51,e 1,s 1,w 21,s 1,e 21,s 34,w 1,n 2,w 1,s 3,e 21,s 21,w 1,ns 1,we 21,ns 41,w 1,s 61,e 3,s 1,e 1,n 3,e 1,n 1,e 1,s 2,w 21,s 1,e 31,ns 21,ew 1,s 2,ew 1,n 1,w 2,n 1,w 2,s 1,e 1,s 1,w 1,s 1,e 2,n 41,e 1,s 1,e 3,n 2,e 2,n 1,e 2,s 21,e 1,ns 31,w 1,s 1,e 2,n 3,ew 1,n 1,w 1,n 31,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 21,sn 91,w 1,sn 1,e 1,sn 31,w 1,sn 1,e 1,sn 51,w 1,n 1,e 2,s 15 OPTIMUM FOUND Models : 25999 Optimum : yes Optimization : -265 Calls : 1 Time : 18918201.643s664s (Solving: 18918201.54s56s 1st Model: 0.00s Unsat: 0.00s) CPU Time : 18867201.092s602s 
•─────┐• ┌───┐ 1 0 1 ┌───────────┐┌─┐ ┌───────┐ 1 0 1 ┌───┐ ┌───┐│ │ ┌─┘ 1 0 1 │ ┌─┐│ └─┐ ┌─┐ ┌─┘│ 1 0 1 └─┐ │ └─┐│ └─┘│ └─┐ 1 0 1 │ │└───┘ └─┘│ │ └─┐│ 1 0 1 ┌─┘ │ ┌─┘│ ┌─┐│ ┌─┘ 1 0 1 │ └───┐┌─────┘ └─┐│ │ 1 0 1 └─┐ │ └─┐ │└─┘ │└─┐ 1 0 1 └───┐ │ ┌─┘└─┐ ┌───┘ │ 1 0 1 ┌─┘ │ ┌─┘ │┌─┐ │┌─┘ 1 0 1 ┌───┘ │ ┌─┘ └─┐ │┌─┘ 1 0 1 └─┐ │ │ ┌─┘└─┘ └───┐┌───┐ 1 └───┐ │ └─┐ ┌─┘ │└─┐ 1 0 1 ┌─┘ │ │ └───┐┌─┐ │ 1 └───┐└───┘ 1 │ │ └─┐ │┌───┘ 1 0 1 └─┐ │ └───┐└─┘ │ │ 1 0 1 │ ┌─┘ └─┐┌─┐ │ │ └───┐ 1 0 1 ┌─┘ │ 0 1 │ │ 1 1 1 │ │ ┌───┘ │ │└─┐ ┌─┘ 1 0 1 │└─┐ ┌─┘│ 0 1 │ │ 1 1 1 └─┘│ └───┐└─┘ │┌─┘ │└─┐ 1 0 1 │┌─┘ └─┐│ 0 1 │ │ 1 1 1 ┌─┐ ┌─┐ │└─┐ │┌─┘ │┌───┘ 1 0 1 └─┐ │ 0 1 │ │ 1 1 1 │ │ │ │┌─┘ │ │┌─┘ │┌─┐ 1 0 1 ┌─┘ │ 0 1 │ │ 1 1 1 │└─┐ │ │ └─┘┌─┘ └─┘│ 1 0 1 │└─┐ ┌─┘│ 0 1 │ │ 1 1 1 │┌─┘ │└─┘ └───┐│ ┌─┐┌─┘ 1 0 1 │┌─┘ └─┐│ 0 1 │ │ 1 1 1 │ └───┐ │└─────┐ │ │└─┐ 1 0 1 └─┐ │• 0 1 │ │ 1 1 1 │ ┌─┐┌───┐ └─┘ │ │┌─┘ 1 ┌───┐ │ │└─┐ 0 1 │ │ 1 1 1 └─┘ │└─┐ ┌─┐└───┐ │ └───┘┌───┘ 1 │ │└─┐ │ 0 1 │ │ 1 1 1 ┌───┘┌─┘ │┌─┐ │└─┘ └─┐│ 1 0 1 └─┘┌─┘ │ 0 1 └─┘ 1 1 1 └─────┘ └───┘ └─────┘ 1 0 1 •───┘└───┘

Clingo, 5.3 hours for 20×20

#script (python) import clingo import itertools import sys def main(prg): matrix = [list(line.split()) for line in sys.stdin] def data(): for i, row in enumerate(matrix): for j, cell in enumerate(row): if cell == '0': yield f'cell(({i}, {j})).\n' def on_model(model): step = {} for atom in prg.symbolic_atoms: if atom.symbol.name == 'step' and model.contains(atom.symbol): a, d, b = atom.symbol.arguments step[a] = d, b moves = [] a = clingo.Tuple((0, 0)) while a in step: d, a = step[a] moves.append(d) print(len(moves) + 1) print(','.join(f'{d} {len(list(g))}' for d, g in itertools.groupby(moves))) prg.add('data', [], ''.join(data())) prg.ground([('base', []), ('data', [])]) prg.solve(on_model=on_model) #end. #program base. dir(s, (1, 0); e, (0, 1); n, (-1, 0); w, (0, -1)). adj((X, Y), D, (X+DX, Y+DY)) :- cell((X, Y)), dir(D, (DX, DY)), cell((X+DX, Y+DY)). {step(A, D, B) : adj(A, D, B)} <= 1 :- visit(A). :- cell(B), {step(A, D, B) : adj(A, D, B)} >= 2. visit((0, 0)). visit(B) :- step(A, D, B). :~ visit(A). [-1, A] #show step/3. 
$ clingo -q longest.lp < 20x20.in  clingo version 5.2.2 Reading from longest.lp Solving... 1 2 s 1 3 e 2 4 e 3 5 e 3,s 1 6 e 3,s 2 9 s 8 … 263 s 4,e 1,w 4,e 2,s 1,n 1,s 1,e 1,s 1,n 1,s 1,e 1,s 1,n 3,s 1,e 1,s 1,n 1,s 1,e 2,s 11,e 1,w 12,n 1,w 1,e 3,s 1,e 2,s 1,e 2,w 2,e 2,w 1,e 1,w 1,n 2,s 1,n 1,w 1,n 1,s 2,n 1,w 4,e 1,w 1,n 1,w 1,e 4,s 1,n 2,s 2,e 1,w 1,e 1,s 1,e 1,w 3,e 1,s 6,n 1,s 1,e 1,s 1,n 2,w 1,n 1,s 4,e 1,w 2,e 2,s 1,n 1,s 1,e 1,s 1,n 4,w 1,n 1,w 1,e 1,w 1,n 2,s 3,e 1,s 1,n 1,s 1,e 1,s 1,n 1,s 1,e 1,s 1,n 1,s 2,e 1,w 1,e 1,s 1,e 4,w 1,n 3,w 1,n 1,w 2,e 1,s 1,e 1,s 1,e 1,w 2,n 1,w 1,n 2,w 1,e 3,s 1,e 1,s 3,e 2,w 1,e 2,s 1,e 1,w 2,n 1,w 3,e 1,w 1,n 1,w 3,e 1,w 1,n 1,w 1,e 1,w 1,n 1,w 1,e 1,w 1,n 1,w 1,e 1,w 1,n 1,w 1,e 2,s 9,n 1,s 1,e 1,s 3,n 1,s 1,e 1,s 5,n 1,w 1,n 1,s 1 265 e 3,s 2,w 1,n 1,w 2,s 1,e 1,s 1,w 1,s 1,e 1,s 1,w 1,s 3,e 2,s 11,e 1,n 12,w 2,n 1,e 1,n 3,e 1,s 3,e 2,s 1,e 2,s 3,e 1,n 2,e 1,n 2,w 2,n 1,e 2,n 1,w 2,n 4,e 6,s 1,w 1,s 1,e 1,s 11,w 1,n 6,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 2,w 1,s 1,w 1,n 1,w 1,s 2,e 2,s 5,e 1,s 1,w 2,s 1,e 2,s 3,w 1,n 2,w 1,s 3,e 2,s 2,w 1,n 1,w 2,n 4,w 1,s 6,e 1,n 1,e 1,s 2,w 2,s 1,e 3,n 2,e 1,s 2,e 2,n 1,w 1,n 4,e 1,s 3,e 2,n 1,e 2,s 2,e 1,n 3,w 1,n 3,e 1,n 1,w 1,n 3,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 2,s 9,w 1,s 1,e 1,s 3,w 1,s 1,e 1,s 5,w 2 OPTIMUM FOUND Models : 259 Optimum : yes Optimization : -265 Calls : 1 Time : 18918.643s (Solving: 18918.54s 1st Model: 0.00s Unsat: 0.00s) CPU Time : 18867.092s 
•─────┐ 1 0 1 ┌───────────┐ 1 0 1 ┌───┐ ┌───┐ │ 1 0 1 │ ┌─┐ ┌─┐ ┌─┘ 1 0 1 └─┐ │ └─┐ └─┘ 1 0 1 │ │ └─┘ │ └─┐ 1 0 1 ┌─┘ │ ┌─┘ ┌─┐ 1 0 1 │ └───┐ └─┐ │ 1 0 1 └─┐ │ └─┐ │ │ 1 0 1 └───┐ │ ┌─┘ │ 1 0 1 ┌─┘ │ ┌─┘ │ │ 1 0 1 ┌───┘ │ └─┐ │ 1 0 1 └─┐ │ │ ┌─┘ └───┐ 1 └───┐ │ ┌─┘ │ 1 0 1 ┌─┘ │ │ └───┐ 1 └───┐ 1 │ │ └─┐ │ 1 0 1 └─┐ │ └───┐ │ 1 0 1 │ ┌─┘ └─┐ │ │ 1 0 1 ┌─┘ │ 0 1 │ │ 1 1 1 │ │ ┌───┘ │ │ 1 0 1 │ ┌─┘ 0 1 │ │ 1 1 1 └─┘ └───┐ │ │ 1 0 1 │ └─┐ 0 1 │ │ 1 1 1 ┌─┐ ┌─┐ │ │ │ 1 0 1 └─┐ │ 0 1 │ │ 1 1 1 │ │ │ │ │ │ │ 1 0 1 ┌─┘ │ 0 1 │ │ 1 1 1 │ │ │ └─┘ └─┘ 1 0 1 │ ┌─┘ 0 1 │ │ 1 1 1 │ │ └───┐ ┌─┐ 1 0 1 │ └─┐ 0 1 │ │ 1 1 1 │ └───┐ │ │ │ 1 0 1 └─┐ │ 0 1 │ │ 1 1 1 │ ┌─┐ └─┘ │ │ 1 ┌───┐ │ │ 0 1 │ │ 1 1 1 └─┘ │ ┌─┐ │ └───┘ 1 │ │ │ 0 1 │ │ 1 1 1 ┌───┘ │ │ └─┐ 1 0 1 └─┘ │ 0 1 └─┘ 1 1 1 └─────┘ └───┘ 1 0 1 •───┘

Clingo, 202 seconds for 20×20

#script (python) import clingo import itertools import sys def main(prg): matrix = [list(line.split()) for line in sys.stdin] def data(): for i, row in enumerate(matrix): for j, cell in enumerate(row): if cell == '0': yield f'cell(({i}, {j})).\n' def on_model(model): step = {} for atom in prg.symbolic_atoms: if atom.symbol.name == 'step' and model.contains(atom.symbol): a, d, b = atom.symbol.arguments step[a] = d, b moves = [] a = clingo.Tuple((0, 0)) while step[a][1] != clingo.Tuple((0, 0)): d, a = step[a] moves.append(d) print(len(moves) + 1) print(','.join(f'{d} {len(list(g))}' for d, g in itertools.groupby(moves))) prg.add('data', [], ''.join(data())) prg.ground([('base', []), ('data', [])]) prg.solve(on_model=on_model) #end. #program base. dir(s, (1, 0); e, (0, 1); n, (-1, 0); w, (0, -1)). adj((X, Y), D, (X+DX, Y+DY)) :- cell((X, Y)), dir(D, (DX, DY)), cell((X+DX, Y+DY)). adj(A, end, (0, 0)) :- cell(A). {step(A, D, B) : adj(A, D, B)} = 1 :- visit(A). :- visit(B), {step(A, D, B) : adj(A, D, B)} != 1. visit((0, 0)). visit(B) :- step(A, D, B). :~ visit(A). [-1, A] #show step/3. 
$ clingo -q longest.lp < 20x20.in clingo version 5.2.2 Reading from longest.lp Solving... 1 2 s 1 3 s 2 4 s 3 5 e 3,s 1 6 e 3,s 2 7 e 3,s 3 9 e 3,s 5 … 264 s 4,e 1,n 4,e 2,s 1,w 1,s 1,e 1,s 1,w 1,s 1,e 1,s 1,w 1,s 1,w 1,n 1,w 1,s 3,e 1,n 1,e 1,s 12,e 1,n 13,e 2,s 1,e 2,n 7,e 1,s 2,e 2,n 1,w 1,n 1,e 4,s 5,w 1,s 1,e 1,s 1,w 2,s 1,e 2,s 1,w 1,s 1,e 1,s 1,w 2,s 1,w 1,s 2,w 1,n 3,e 1,n 1,e 1,n 1,w 1,n 3,e 1,n 1,w 1,n 1,e 2,n 3,w 1,s 2,w 3,s 1,e 1,s 1,w 1,s 1,e 1,s 4,w 1,n 2,w 1,s 3,e 1,s 1,w 1,s 1,e 1,s 1,w 1,s 1,e 3,s 1,e 1,n 3,e 1,n 1,e 1,s 2,w 1,s 1,e 1,s 1,w 1,s 2,w 1,n 1,w 2,n 1,w 2,s 1,e 1,s 1,w 1,s 1,e 2,n 1,e 1,s 1,e 3,n 2,e 2,n 1,e 2,s 3,e 1,n 1,e 1,n 6,w 1,n 1,e 1,n 9,w 1,n 1,e 1,n 1,w 2,s 3,e 1,s 1,w 1,s 1,e 1,s 1,w 1,s 1,e 1,s 1,w 1,s 1,e 1,s 1,w 1,s 3,e 1,s 1,w 1,s 1,e 1,s 2 265 s 4,e 1,n 4,e 2,s 1,w 1,s 1,e 1,s 1,w 1,s 1,e 1,s 1,w 1,s 1,w 1,n 1,w 1,s 3,e 1,n 1,e 1,s 12,e 1,n 13,e 2,s 1,e 2,n 7,e 1,s 2,e 2,n 1,w 1,n 1,e 4,s 5,w 1,s 1,e 1,s 1,w 2,s 1,e 2,s 1,w 1,s 1,e 1,s 1,w 2,s 1,w 1,s 2,w 1,n 3,e 1,n 1,e 1,n 1,w 1,n 3,e 1,n 1,w 1,n 1,e 2,n 3,w 1,s 2,w 3,s 1,e 1,s 1,w 1,s 1,e 1,s 4,w 1,n 2,w 1,s 3,e 1,s 1,w 1,s 1,e 1,s 1,w 1,s 1,e 3,s 1,e 1,n 3,e 1,n 1,e 1,s 2,w 1,s 1,e 1,s 1,w 1,s 2,w 1,n 1,w 2,n 1,w 2,s 1,e 1,s 1,w 1,s 1,e 2,n 1,e 1,s 1,e 3,n 2,e 2,n 1,e 2,s 1,e 1,s 1,w 1,s 1,e 2,n 3,w 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 2,s 15 OPTIMUM FOUND Models : 99 Optimum : yes Optimization : -265 Calls : 1 Time : 201.664s (Solving: 201.56s 1st Model: 0.00s Unsat: 0.00s) CPU Time : 201.602s 
• ┌───┐ 1 0 1 ┌─┐ ┌───────┐ 1 0 1 ┌───┐ │ │ ┌─┘ 1 0 1 │ │ └─┐ ┌─┐ │ 1 0 1 └─┐ │ │ │ └─┐ 1 0 1 │ └───┘ │ │ │ 1 0 1 ┌─┘ │ │ │ ┌─┘ 1 0 1 │ ┌─────┘ │ │ 1 0 1 └─┐ │ └─┘ └─┐ 1 0 1 │ └─┐ ┌───┘ │ 1 0 1 ┌─┘ │ ┌─┐ ┌─┘ 1 0 1 │ ┌─┘ └─┐ ┌─┘ 1 0 1 └─┐ │ │ └─┘ ┌───┐ 1 │ └─┐ ┌─┘ └─┐ 1 0 1 ┌─┘ │ │ ┌─┐ │ 1 └───┘ 1 │ │ ┌───┘ 1 0 1 └─┐ │ └─┘ │ │ 1 0 1 ┌─┐ │ │ └───┐ 1 0 1 ┌─┘ │ 0 1 │ │ 1 1 1 │ │ │ └─┐ ┌─┘ 1 0 1 └─┐ │ 0 1 │ │ 1 1 1 │ └─┘ ┌─┘ └─┐ 1 0 1 ┌─┘ │ 0 1 │ │ 1 1 1 └─┐ ┌─┘ ┌───┘ 1 0 1 └─┐ │ 0 1 │ │ 1 1 1 ┌─┘ │ ┌─┘ ┌─┐ 1 0 1 ┌─┘ │ 0 1 │ │ 1 1 1 └─┐ │ │ ┌─┘ │ 1 0 1 └─┐ │ 0 1 │ │ 1 1 1 ┌─┘ └─┘ │ ┌─┘ 1 0 1 ┌─┘ │ 0 1 │ │ 1 1 1 └─────┐ │ └─┐ 1 0 1 └─┐ • 0 1 │ │ 1 1 1 ┌───┐ └─┘ ┌─┘ 1 ┌───┐ └─┐ 0 1 │ │ 1 1 1 └─┐ └───┐ │ ┌───┘ 1 └─┐ │ 0 1 │ │ 1 1 1 ┌─┘ ┌─┐ └─┘ │ 1 0 1 ┌─┘ │ 0 1 └─┘ 1 1 1 └───┘ └─────┘ 1 0 1 └───┘
Source Link
Anders Kaseorg
Anders Kaseorg
  • 40.7k
  • 3
  • 76
  • 149

Clingo, 5.3 hours for 20×20

This problem is NP-complete, even if you were to guarantee that all 0s are used, so your dreams of a program that runs efficiently for 500×500 may be a little bit unrealistic.

(The other answer using A* search doesn’t find the optimal solution, even on the 3×3 example case, because A* never revisits a node that was previously found on a different path.)

#script (python) import clingo import itertools import sys def main(prg): matrix = [list(line.split()) for line in sys.stdin] def data(): for i, row in enumerate(matrix): for j, cell in enumerate(row): if cell == '0': yield f'cell(({i}, {j})).\n' def on_model(model): step = {} for atom in prg.symbolic_atoms: if atom.symbol.name == 'step' and model.contains(atom.symbol): a, d, b = atom.symbol.arguments step[a] = d, b moves = [] a = clingo.Tuple((0, 0)) while a in step: d, a = step[a] moves.append(d) print(len(moves) + 1) print(','.join(f'{d} {len(list(g))}' for d, g in itertools.groupby(moves))) prg.add('data', [], ''.join(data())) prg.ground([('base', []), ('data', [])]) prg.solve(on_model=on_model) #end. #program base. dir(s, (1, 0); e, (0, 1); n, (-1, 0); w, (0, -1)). adj((X, Y), D, (X+DX, Y+DY)) :- cell((X, Y)), dir(D, (DX, DY)), cell((X+DX, Y+DY)). {step(A, D, B) : adj(A, D, B)} <= 1 :- visit(A). :- cell(B), {step(A, D, B) : adj(A, D, B)} >= 2. visit((0, 0)). visit(B) :- step(A, D, B). :~ visit(A). [-1, A] #show step/3.

Demo

$ clingo -q longest.lp < 20x20.in clingo version 5.2.2 Reading from longest.lp Solving... 1 2 s 1 3 e 2 4 e 3 5 e 3,s 1 6 e 3,s 2 9 s 8 … 263 s 4,e 1,w 4,e 2,s 1,n 1,s 1,e 1,s 1,n 1,s 1,e 1,s 1,n 3,s 1,e 1,s 1,n 1,s 1,e 2,s 11,e 1,w 12,n 1,w 1,e 3,s 1,e 2,s 1,e 2,w 2,e 2,w 1,e 1,w 1,n 2,s 1,n 1,w 1,n 1,s 2,n 1,w 4,e 1,w 1,n 1,w 1,e 4,s 1,n 2,s 2,e 1,w 1,e 1,s 1,e 1,w 3,e 1,s 6,n 1,s 1,e 1,s 1,n 2,w 1,n 1,s 4,e 1,w 2,e 2,s 1,n 1,s 1,e 1,s 1,n 4,w 1,n 1,w 1,e 1,w 1,n 2,s 3,e 1,s 1,n 1,s 1,e 1,s 1,n 1,s 1,e 1,s 1,n 1,s 2,e 1,w 1,e 1,s 1,e 4,w 1,n 3,w 1,n 1,w 2,e 1,s 1,e 1,s 1,e 1,w 2,n 1,w 1,n 2,w 1,e 3,s 1,e 1,s 3,e 2,w 1,e 2,s 1,e 1,w 2,n 1,w 3,e 1,w 1,n 1,w 3,e 1,w 1,n 1,w 1,e 1,w 1,n 1,w 1,e 1,w 1,n 1,w 1,e 1,w 1,n 1,w 1,e 2,s 9,n 1,s 1,e 1,s 3,n 1,s 1,e 1,s 5,n 1,w 1,n 1,s 1 265 e 3,s 2,w 1,n 1,w 2,s 1,e 1,s 1,w 1,s 1,e 1,s 1,w 1,s 3,e 2,s 11,e 1,n 12,w 2,n 1,e 1,n 3,e 1,s 3,e 2,s 1,e 2,s 3,e 1,n 2,e 1,n 2,w 2,n 1,e 2,n 1,w 2,n 4,e 6,s 1,w 1,s 1,e 1,s 11,w 1,n 6,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 2,w 1,s 1,w 1,n 1,w 1,s 2,e 2,s 5,e 1,s 1,w 2,s 1,e 2,s 3,w 1,n 2,w 1,s 3,e 2,s 2,w 1,n 1,w 2,n 4,w 1,s 6,e 1,n 1,e 1,s 2,w 2,s 1,e 3,n 2,e 1,s 2,e 2,n 1,w 1,n 4,e 1,s 3,e 2,n 1,e 2,s 2,e 1,n 3,w 1,n 3,e 1,n 1,w 1,n 3,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 2,s 9,w 1,s 1,e 1,s 3,w 1,s 1,e 1,s 5,w 2 OPTIMUM FOUND Models : 259 Optimum : yes Optimization : -265 Calls : 1 Time : 18918.643s (Solving: 18918.54s 1st Model: 0.00s Unsat: 0.00s) CPU Time : 18867.092s

The final output line (above OPTIMUM FOUND) corresponds to the following path through 265 nodes:

•─────┐ 1 0 1 ┌───────────┐ 1 0 1 ┌───┐ ┌───┐ │ 1 0 1 │ ┌─┐ ┌─┐ ┌─┘ 1 0 1 └─┐ │ └─┐ └─┘ 1 0 1 │ │ └─┘ │ └─┐ 1 0 1 ┌─┘ │ ┌─┘ ┌─┐ 1 0 1 │ └───┐ └─┐ │ 1 0 1 └─┐ │ └─┐ │ │ 1 0 1 └───┐ │ ┌─┘ │ 1 0 1 ┌─┘ │ ┌─┘ │ │ 1 0 1 ┌───┘ │ └─┐ │ 1 0 1 └─┐ │ │ ┌─┘ └───┐ 1 └───┐ │ ┌─┘ │ 1 0 1 ┌─┘ │ │ └───┐ 1 └───┐ 1 │ │ └─┐ │ 1 0 1 └─┐ │ └───┐ │ 1 0 1 │ ┌─┘ └─┐ │ │ 1 0 1 ┌─┘ │ 0 1 │ │ 1 1 1 │ │ ┌───┘ │ │ 1 0 1 │ ┌─┘ 0 1 │ │ 1 1 1 └─┘ └───┐ │ │ 1 0 1 │ └─┐ 0 1 │ │ 1 1 1 ┌─┐ ┌─┐ │ │ │ 1 0 1 └─┐ │ 0 1 │ │ 1 1 1 │ │ │ │ │ │ │ 1 0 1 ┌─┘ │ 0 1 │ │ 1 1 1 │ │ │ └─┘ └─┘ 1 0 1 │ ┌─┘ 0 1 │ │ 1 1 1 │ │ └───┐ ┌─┐ 1 0 1 │ └─┐ 0 1 │ │ 1 1 1 │ └───┐ │ │ │ 1 0 1 └─┐ │ 0 1 │ │ 1 1 1 │ ┌─┐ └─┘ │ │ 1 ┌───┐ │ │ 0 1 │ │ 1 1 1 └─┘ │ ┌─┐ │ └───┘ 1 │ │ │ 0 1 │ │ 1 1 1 ┌───┘ │ │ └─┐ 1 0 1 └─┘ │ 0 1 └─┘ 1 1 1 └─────┘ └───┘ 1 0 1 •───┘