|
| |
|
|
A094777
|
|
Number of legal position in Go played on an n X n grid (each group must have at least one liberty).
|
|
1
| |
|
|
1, 57, 12675, 24318165, 414295148741, 62567386502084877, 83677847847984287628595, 990966953618170260281935463385, 103919148791293834318983090438798793469, 96498428501909654589630887978835098088148177857, 793474866816582266820936671790189132321673383112185151899, 57774258489513238998237970307483999327287210756991189655942651331169, 37249792307686396442294904767024517674249157948208717533254799550970595875237705, 212667732900366224249789357650440598098805861083269127196623872213228196352455447575029701325, 10751464308361383118768413754866123809733788820327844402764601662870883601711298309339239868998337801509491
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
COMMENTS
| John Tromp wrote a small C program to compute the number for boards up to size 4 X 5, given in above rec.games.go posting. Gunnar Farnebaeck (gunnar(AT)lysator.liu.se) wrote a pike script to compute the number by dynamic programming, which handles sizes up to 12 X 12 (available upon request).
|
|
|
LINKS
| British Go Association, Go
Sandy Harris, Number of Possible Outcomes of a Game.
John Tromp, Number of legal Go positions
John Tromp, Complexity of Chess and Go
|
|
|
FORMULA
| 3^(n*n) is a trivial upper bound.
|
|
|
EXAMPLE
| The illegal 2 X 2 positions are the 2^4 with no empty points and the 4 X 2 having a stone adjacent to 2 opponent stones that share a liberty. That leaves 3^4-16-8 = 57 legal positions.
|
|
|
CROSSREFS
| Sequence in context: A132783 A127455 A091749 * A093257 A069255 A065869
Adjacent sequences: A094774 A094775 A094776 * A094778 A094779 A094780
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Jan Kristian Haugland (jankrihau(AT)hotmail.com), Jun 09 2004
|
|
|
EXTENSIONS
| More terms from John Tromp (tromp(AT)cwi.nl), Jan 27 2005
a(10) - a(13) from John Tromp (tromp(AT)cwi.nl), Jun 23 2005
a(14), a(15) from John Tromp (tromp(AT)cwi.nl), Sep 01 2005.
a(16) = 4813066963822755416429056022484299646486874100967249263944719599975607459850502222039591149331431805524655467453067042377. - John Tromp (tromp(AT)cwi.nl), Oct 06 2005
Michal Koucky should be credited for carrying most of the computational load for computing the n=14, 15 and 16 results with his file-based implementation.
|
| |
|
|
