Number of legal Go positions

This is sequence A094777 in the fabulous On-Line Encyclopedia of Integer Sequences.

Click on the left links to find tables for L(m,n).

n number of legal n*n positions
1 1
2 57
3 12675
4 24318165
5 414295148741
6 62567386502084877
7 83677847847984287628595
8 990966953618170260281935463385
9 103919148791293834318983090438798793469
10 96498428501909654589630887978835098088148177857
11 793474866816582266820936671790189132321673383112185151899
12 57774258489513238998237970307483999327287210756991189655942651331169
13 37249792307686396442294904767024517674249157948208717533254799550970595875237705
14 212667732900366224249789357650440598098805861083269127196623872213228196352455447575029701325
15 10751464308361383118768413754866123809733788820327844402764601662870883601711298309339239868998337801509491
16 4813066963822755416429056022484299646486874100967249263944719599975607459850502222039591149331431805524655467453067042377
17 19079388919628199204605726181850465220151058338147922243967269231944059187214767997105992341735209230667288462179090073659712583262087437
18 ~0.017322427762 * 3^324 ~ 6.697231143 * 10^152
19 ~0.011957528698 * 3^361 ~ 2.081681994 * 10^170

The results for n=14,15,16 and 17 were obtained in a joint effort between Michal Koucký and John Tromp.

A preliminary version of our paper ``Combinatorics of Go'' that contains these and many other results.

This gzipped tar contains various programs used to compute the exact numbers. Many thanks to Gunnar Farnebäck and Michal Koucký for their contributions. Gunnar wrote a legal counting program in pike, while Michal suggested the use of Chinese Remaindering and implemented a file based program.

This small program approximates the probability of a random n*n position being legal.

Additions and corrections are welcome. tromp@cwi.nl