Mark Gritter (markgritter) wrote,
Mark Gritter
markgritter

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: https://twitter.com/graveolens/status/691732255333548032

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
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 5 comments