%I #32 Apr 07 2020 10:38:43
%S 1,0,2,20,752,84008,29145982,30795358024,99417240957788
%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 NE and SW corners.
%C a(11) = 29262010991555584566654. - _Seiichi Manyama_, Apr 07 2020
%e a(3) = 2;
%e S--*--+ S *--+
%e | | | |
%e *--+--* * + *
%e | | | |
%e +--*--E +--* E
%e a(4) = 20;
%e S--*--*--+ S--*--*--+ S--*--*--+
%e | | |
%e *--*--+--* *--*--+--* *--* +--*
%e | | | | |
%e * +--* * +--*--* * +--*
%e | | | | | | |
%e +--* *--E +--* E +--*--*--E
%e S--*--*--+ S--*--*--+ S--*--*--+
%e | | |
%e *--+--* *--+--* *--+ *
%e | | | | |
%e *--+ *--* *--+ *--+ *--*
%e | | | | |
%e +--*--* E +--*--*--E +--*--*--E
%e S--*--*--+ S--* *--+ S--* *--+
%e | | | | | | |
%e +--* *--* + * *--+ *
%e | | | | |
%e *--+--* * +--* * *--+--*--*
%e | | | | |
%e +--*--*--E +--* E +--*--*--E
%e S--* *--+ S *--*--+ S *--*--+
%e | | | | | | | | |
%e * + * *--* +--* * *--+ *
%e | | | | | | |
%e *--+ * * *--+--* * +--* *
%e | | | | | | |
%e +--*--* E +--*--*--E +--* E
%e S *--*--+ S *--*--+ S *--+
%e | | | | | | | | |
%e * * +--* * * +--* *--*--+ *
%e | | | | | | |
%e * + * * + *--* *--+--*--*
%e | | | | | | |
%e +--* *--E +--* E +--*--*--E
%e S *--+ S *--+ S *--+
%e | | | | | | | | |
%e *--* + * * *--+ * * *--+ *
%e | | | | | | | | |
%e *--+ * * * +--* * * + *--*
%e | | | | | | | | |
%e +--*--* E +--*--* E +--* *--E
%e S *--+ S *--+
%e | | | | | |
%e * *--+ * * + *
%e | | | | | |
%e * + * * +--* *
%e | | | | | |
%e +--* E +--* E
%o (Python)
%o # Using graphillion
%o from graphillion import GraphSet
%o import graphillion.tutorial as tl
%o def A333464(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):
%o paths = paths.including((n - 1) * (i + 1) + 1)
%o return paths.len()
%o print([A333464(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 - 1).all?{|i| used[(n - 1) * (i + 1)] == 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 return 1 if n == 1
%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 A333464(n)
%o (1..n).map{|i| A(i)}
%o end
%o p A333464(6)
%Y Cf. A007764, A333455.
%K nonn,more
%O 1,3
%A _Seiichi Manyama_, Mar 22 2020