|
%I #38 Apr 07 2020 10:38:37
%S 1,2,10,124,4620,536360,189313340,201653395768,651683788574786
%N Number of self-avoiding walks from NW to SE corners on an n X n grid which pass through all points on the diagonal connecting NW and SE corners.
%C a(11) = 191874208353355680763886. - _Seiichi Manyama_, Apr 07 2020
%e a(2) = 2;
%e S--* S
%e | |
%e E *--E
%e a(3) = 10;
%e S--*--* S--*--* S--*
%e | | |
%e +--* *--+--* +--*
%e | | |
%e *--E *--*--E E
%e S--* S--* S *--*
%e | | | | |
%e + *--+ * + *
%e | | | | |
%e *--E *--*--E *--* E
%e S *--* S S
%e | | | | |
%e *--+ * * +--* *--+--*
%e | | | | |
%e E *--* E E
%e S
%e |
%e *--+
%e |
%e *--E
%e a(4) = 124;
%e S--*--*--* S--*--*--* S--*--*--*
%e | | |
%e *--+--* * *--+--* * *--+ *--*
%e | | | | | | | | |
%e *--* +--* * +--* * *--+
%e | | |
%e *--*--E *--*--*--E *--*--*--E
%e ... and so on.
%o (Python)
%o # Using graphillion
%o from graphillion import GraphSet
%o import graphillion.tutorial as tl
%o def A333455(n):
%o if n == 1: return 1
%o universe = tl.grid(n - 1, n - 1)
%o GraphSet.set_universe(universe)
%o start, goal = 1, n * n
%o paths = GraphSet.paths(start, goal)
%o for i in range(n - 1):
%o paths = paths.including((n + 1) * i + 1)
%o return paths.len()
%o print([A333455(n) for n in range(1, 10)])
%o (Ruby)
%o def search(x, y, n, used)
%o return 0 if x < 0 || n <= x || y < 0 || n <= y || used[x + y * n]
%o return 1 if x == n - 1 && y == n - 1 && (0..n - 2).all?{|i| used[(n + 1) * i] == true}
%o cnt = 0
%o used[x + y * n] = true
%o @move.each{|mo|
%o cnt += search(x + mo[0], y + mo[1], n, used)
%o }
%o used[x + y * n] = false
%o cnt
%o end
%o def A(n)
%o @move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
%o used = Array.new(n * n, false)
%o search(0, 0, n, used)
%o end
%o def A333455(n)
%o (1..n).map{|i| A(i)}
%o end
%o p A333455(6)
%Y Cf. A000108, A007764.
%K nonn,more
%O 1,2
%A _Seiichi Manyama_, Mar 22 2020
| 