Hex Slide: Initial Thoughts

gistfile1.txt

hexslide initial thoughts
-------------------------

(If something doesn't seem right, keep reading; I may have corrected
myself later on.)

Counting Configurations for:

 * *
* * *
 * *

solvable:
 O O    - -    O O    - -
- - O  - - O  - - O  - - O    4
 O O    O O    - -    - -

unsolvable:
 O \    O \    O O    - -
- - \  - - \  - - /  - - /    4
 O O    - -    O /    O /

1/2 of the configurations are solvable

--------

Counting configurations for:

  * * *
 * * * *
  * * *

solvable:
 O O O
- - O O
 O O O

 O O O    - - O    O - -
- - O O  - - O O  - - O O
 - - -    - - -    - - -
                             8
 - - -    - - -    - - -
- - O O  - - O O  - - O O
 O O O    - - O    O - -

 - - -
- - O O
 - - -

unsolvable:

 O \ O    O \ O    O \ \    O \ \
- - \ O  - - \ O  - - \ \  - - \ \
 O O \    - - \    O O \    - - \

 O O /    - - /    O O /    - - /
- - / O  - - / O  - - / /  - - / /
 O / O    O / O    O / /    O / /

[ [  O \ O    O \ O    O \ O  ]         O \ \  ]         O \ *
[ [ - - \ O  - - \ O  - - \ O ] *2 for - - \ \ ] +2 for - - \ *
[ [  O O O    - - O    O - -  ]         * * *  ]         - - -

                  * * *
above row *2 for * * / *
                  * / *

###################
#BREAK IN COUNTING# (sure takes a lot for that one)
###################

I surmise that counting can be simplified by doing solutions for rows
1 thru (R+1)/2, where R is the number of rows, assuming an odd number
of rows. [AFTERNOTE: This actually wouldn't be more efficient. You'd
easily run into a situation where you'd have to keep track of 2- and
3-pieces that start on the other side and poke into (or through) the
center row.

Other notes:

- Once you place a piece that causes an unsolvable puzzle, just figure
  out the number of possible configurations of 2-pieces, 3-pieces, and
  gaps in the space left.

- How to account for boards where more than one piece is required to
  make a game unwinnable is unknown. Without any formal working-out of
  it, this would appear to be an issue when R>5 (l[12] is always the
  starting piece, and l is always the center row when R is odd)

- This (so far) is only counting the number of obviously unsolvable
  configurations (that is, any piece occupying an l groove spot is
  clearly unable to be moved out of the way). It's not known right now
  if all unsolvable configure are obviously so.

- Obviously unsolvable configurations can be said as failing the
  condition

    O ≤ T - R_c

  Where O is the number of occupied spaces (not counting l[12]), T is
  the total number of spaces on the board, and R_c is how many spaces
  are in the center row (where l[12] is).

  In graphical terms, the pieces must be rearrangeable to so that no
  pieces occupy the spaces with X's:

                    O O O
   O O    O O O    O O O O
  X X X  X X X X  X X X X X ... etc. ...
   O O    O O O    O O O O
                    O O O

- For all configurations that are not obviously unsolvable, play the
  game until you play l[12 -> 23]. Then the subset of configurations
  not obviously unsolvable for l[23] are able to avoid occupying all
  of the spaces with X's, such as these examples below:

                    O O O
   O O    O O O    O O O O
  O X X  O X X X  O X X X X ... etc. ...
   O O    O O O    O O O O
                    O O O

- Note that there are no unsolvable solutions for l[56] in the
  standard game board.

- Conjecture: Is the number of unobviously unsolvable configurations
  of l[12] equal to the summation of the obviously unsolvable
  configurations of l[23], l[34], l[45], l[56]?

- Perhaps working things out for a square tile version (a more
  familiar shape in our culture, surely) would be easier and help hone
  in on a good technique for the original hex board?

Hand counting configurations of:

* * *                               * * *
* * *  3x3 square, starting piece:  - - *
* * *                               * * *

Solvable:

O O O  - - O  O - -  - - -
- - O  - - O  - - O  - - O
O O O  O O O  O O O  O O O

O O O  - - O  O - -  - - -
- - O  - - O  - - O  - - O
- - O  - - O  - - O  - - O
                              16 configurations
O O O  - - O  O - -  - - -
- - O  - - O  - - O  - - O
O - -  O - -  O - -  O - -

O O O  - - O  O - -  - - -
- - O  - - O  - - O  - - O
- - -  - - -  - - -  - - -

Unsolvable:

O O |  O O |  O O |  O O |
- - |  - - |  - - |  - - |
O O O  - - O  O - -  - - -

- - |  - - |  - - |  - - |
- - |  - - |  - - |  - - |
O O O  - - O  O - -  - - -

O O O  - - O  O - -  - - -
- - |  - - |  - - |  - - |    20 configurations
O O |  O O |  O O |  O O |

O O O  - - O  O - -  - - -
- - |  - - |  - - |  - - |
- - |  - - |  - - |  - - |

O O |  - - |  O O |  - - |
- - |  - - |  - - |  - - |
O O |  O O |  - - |  - - |

Couple more notes on hex slide in general:

- For every configuration with one 3-piece, there are 2 more with one
  2-piece instead of the 3-piece, as well as one where all three
  spaces occupied by the 3-piece are empty (note that there may be
  more than four ways to fill/not fill the space occupied by the
  3-piece. This is just to say that for every 3-piece, there are 4
  guaranteed near-identical configurations differing only in whether
  this location holds a 3-piece, a 2-piece, or a 3-space gap (3-gap))

- The equation above does not work (O ≤ ...). Oh well. There has got
  to be some way of verifying that a configuration is unwinnable...

- For one n-piece taking up a spot in an l groove, the number of
  spaces in that piece's groove must be at least 2n+1 (assuming an odd
  number of rows where the l groove is the center row)

- If a piece occupying an l-groove needs to be moved, then moving that
  piece can be looked at as another mini-hexslide game, perhaps? (only
  this time you need to just make sure the piece isn't in any l-groove
  spots)