rc2maze.py

import numpy as np

def expected_time_to_solve(N):
    A = np.zeros((4*(N+2), 4*(N+2)))
    # (n, forward) => (4n + 0), (n, backward) => (4n + 1), (n, inside) => (4n + 2), (n, facewall) => (4n + 3)
    for i in range(4*(N+2)):
        if i < 4:
            A[i,4] = 1
        elif i >= 4*(N+1):
            A[i,i] = 1
        elif i % 4 == 0:
            A[i,i+2] = 3/4
            A[i,i+4] = 1/4
        elif i % 4 == 1:
            A[i,i+1] = 1/4
            A[i,i-4] = 3/4
        elif i % 4 == 2:
            A[i,i+1] = 1
        elif i % 4 == 3:
            A[i, i+1] = 1/2
            A[i, i+2-8] = 1/2
        else:
            raise RuntimeError("non-exhaustive Markov chain")

    Q = A[:4*(N+1),:4*(N+1)]
    x = np.linalg.inv(np.eye(4*(N+1)) - Q)
    return np.sum(x[0])

last = 1
for N in range(1,200):
    tts = expected_time_to_solve(N)
    ratio_with_last = tts/last
    print(N, tts, ratio_with_last)
    last = tts

results.txt

1 5.6 5.6
2 13.439999999999998 2.4
3 25.816000000000003 1.9208333333333338
4 44.542400000000015 1.725379609544469
5 72.15936000000002 1.6200150867488055
6 112.22310400000002 1.555212019618799
7 169.71234560000005 1.5122763455197248
8 251.59728384000005 1.4824925255172479
9 367.63619737600015 1.4612089278745692
10 531.4906763264004 1.445697350043086
11 762.2869468569604 1.4342433100158898
12 1086.8017255997447 1.4257121023530763
13 1542.5224158396427 1.4193227518003906
14 2181.9313821754995 1.4145216690337734
15 3078.503935045701 1.4109077674002157
16 4335.105509063981 1.408185794311686
17 6095.747712689574 1.406135952157193
18 8562.046797765406 1.404593365952747
19 12016.265516871565 1.4034337583867995
20 16853.571723620193 1.4025631923626152
21 23627.200413068273 1.4019105742407632
22 33111.68057829557 1.4014220897699503
23 46391.35280961381 1.401057028800373
24 64984.29393345935 1.400784628983539
25 91015.8115068431 1.4005816790136818
26 127461.33610958033 1.400430694396402
27 178486.4705534125 1.4003185279649442
28 249923.05877477748 1.4002353119531679
29 349935.6822846886 1.4001736534444356
30 489954.75519856386 1.4001280235262301
31 685982.8572779896 1.4000942944210868
32 960423.6001891854 1.400069389489103
33 1344642.0402648596 1.4000510191544548
34 1882549.2563708038 1.400037482094484
35 2635620.7589191245 1.400027515880301
36 3689922.2624867745 1.4000201849980958
37 5165945.767481486 1.4000147970596988
38 7232380.0744740805 1.4000108402222013
39 10125389.504263714 1.4000079365298022
40 14175604.1059692 1.4000058071840076
41 19845905.94835688 1.4000042467325944
42 27784329.92769964 1.4000031039147403
43 38898124.898779504 1.4000022674651564
44 54457439.25829131 1.4000016556067978
45 76240480.76160783 1.400001208283035
46 106736740.266251 1.4000008814215148
47 149431504.9727514 1.400000642702783
48 209204176.96185198 1.4000004684420466
49 292885919.1465928 1.4000003412933768
50 410040359.6052299 1.4000002485609422
51 574056577.6473218 1.4000001809577964
52 803679284.3062508 1.4000001316943367
53 1125151075.0287511 1.4000000958093626
54 1575211583.4402516 1.4000000696795316
55 2205296296.6163526 1.4000000506598613
56 3087414896.462894 1.4000000368204493
57 4322380937.648049 1.400000026753773
58 6051333396.707272 1.4000000194337343
59 8471866840.790177 1.4000000141125917
60 11860613663.906248 1.4000000102456756