Mark Gritter (markgritter) wrote,
Mark Gritter

Legal Go Positions and Nonsingular Matrixes in F_3

A Go position is legal if there is no completely surrounded group of stones in it. It can be represented as an NxN array with each entry filled in as 0 (blank), 1 (white), or 2 (black.) I don't want to use the term "dead" because a dead group is a legal position, but an already-captured one still on the board is not. Note also that while players must alternate turns, 'pass' is a legal move so for example Black could fill the board all by herself without a single White stone. (But not fill in the last square as that would kill her group.)

A matrix over the finite field F_3 is also an NxN array with each entry either 0, 1, or 2. It is singular if its determinant is zero. The nonsingular matrices form a group under multiplication (because they are invertible.)

Owen Maresh asks how these two sets compare:

For the easily-tractable cases, here is the answer:

11,232 nonsingular 3x3 matrices over F_3
12,675 legal 3x3 Go positions
6,996 that are both

24,261,120 nonsingular 4x4 matrices over F_3
24,318,165 legal 4x4 Go positions
13,518,392 that are both
Tags: geek
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded