# [Clingo](https://potassco.org/), 5.3 hours for 20×20

[This problem is NP-complete](http://www.cs.technion.ac.il/~itai/publications/Algorithms/Hamilton-paths.pdf), even if you were to guarantee that all `0`s 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 •───┘