4 ms·

> couple of extra bits Two?

• yjftsjthsd-h 3y ago
  There are four ways to rotate, so yes exactly two bits, right?
  • Nevermark 3y ago
    Plus a third bit for rotationally flipped. I.e., [O X -] [- - -] [- - -] can be rotated 90 degrees 4 times (2 bits) to return to the same arrangement. It can also be rotationally flipped 2 times (1 bit), clockwise <--> counter-clockwise, to return again. With the dual state for the above non-rotated original: [O - -] [X - -] [- - -] So three bits to extract symmetry (or recreated the broken symmetry) But ... some arrangements have instance symmetry where only 1 bit of rotation symmetry is needed, and no rotation-flips: [O - X] [- - -] [X - O] So sometimes 3 bits of symmetry will contain redundant information. (i.e. rotations 0 and 2, and rotations 1 and 3, look the same. Rotation flip changes nothing. And this field requires 0 symmetry bits, as all rotations and flips are identities (1 step to return = 0 bits) [- - -] [- X -] [- - -] A representation that always uses the minimum number of bits but has a straightforward relationship to the actual playing field is illusive
    • pavon 3y ago
      And that double-counts board layouts that are symmetric. Digging through the references led me to this page[1] which has a nice discussion on different ways to compute the number of states. Without symmetry you have 5478 possible board states, which is less than the 6120 you would get by adding rotation/flip bits to the 765 states. Both require 13 bits though. Too bad, I was hoping it would fit into a 12-bit PDP-8 word :) [1]https://web.archive.org/web/20020513063952/http://www.mathrec.org/old/2002jan/solutions.html https://web.archive.org/web/20020513063952/http://www.mathre...