cp's OEIS Frontend

A333455 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.

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