Code for table-and-glasses puzzles.

The form in which I've usually found this in puzzle books goes
something like this:

	You have a square table, with a well at each corner you can
	reach into but not look into.  In each well is a drinking
	glass, either right-side-up or upside-down.  The table is on a
	pivot, so it can spin, and there are sensors and a circuit that
	rings a bell as soon as all the glasses are the same way up.

	If you spin the table, it is unpredictable what orientation it
	stops in; effectively, this is a random circular permutation of
	the wells.

	The rules are that, at each step, you must psin the table, then
	choose two wells to reach into.  After feeling how the glasses
	are oriented, you may (but are not required to) invert either
	or both of them.  Your goal is to make the bell ring.

	It is easy, of course, to make it ring with probability 1 in
	unbounded time (just spin, reach, and turn both glasses, say,
	up, if they aren't already).  But the challenge is to make it
	ring with probability 1 in an a-priori-fixed number of steps.

	By symmetry, there are only two different ways to choose wells:
	either adjacent or diagonally opposite.  The typical solution
	goes like this (where each step has an implicit "if the bell
	doesn't ring..." attached) - actually, if you're not familiar
	with the puzzle, you may want to stop and work on it yourself
	for a bit, so I'm going to rot13 the solution.

	- Nqwnprag: ghea nal gung nera'g hc hc.
	- Bccbfvgr; ghea nal gung nera'g hc hc.
	- Bccbfvgr:
		Vs bar vf qbja, ghea vg hc; oryy jvyy evat.
		Bgurejvfr, ghea bar bs gurz (qbrfa'g znggre juvpu) hc.
	- Nqwnprag: vaireg obgu.
	- Bccbfvgr: vaireg obgu.  Oryy jvyy evat.

I started thinking about generalizations to W wells and H hands.  In
what follows I assume W>2, because W=2 is not interesting and W<2 is
even less interesting.

From this point on, possible spoilers abound.  If you want to work on
it yourself, I recommend stopping reading here.

H=1 is pretty obviously impossible, and H=W-1 is possible in two steps
(first: turn them all up; second: if one is down, turn it up;
otherwise, turn them all down).  I suspect W=5 H=2..3 are impossible,
though I haven't proved it to my satisfaction, except per below.  I
found a proof that W=6 H=3 is impossible (every hand pattern has two
unprobed wells with one well between them; if those two wells are set
differently, unlucky spins could keep placing them on the unprobed
spots for every probe), and I manually found a solution for W=6 H=4.
In the notation I've been using, which I hope is fairly obvious:

	- XXXX--: invert any which are u.
	- XXX-X-: invert any which are u.
	(At this point, the pattern is (some rotation of) uddddd.)
	- XXX-X-:
		if any u, invert it and bell will ring.
		Otherwise, invert -*----.
	(At this point, the pattern is ududdd.)
	- XXXX--:
		If two are up, invert them and bell will ring.
		If uddd--: invert --*---
		If dudd--: invert ---*--
		If ddud--: invert *-----
		If dddu--: invert -*----
	(At this point, the pattern is ududud.)
	- XXX-X-: invert *-*-*- and bell will ring.

I suspect all prime W are impossible for any H in 2..W-2, though I
don't have a proof.  My best guess at the idea of a proof is that I
suspect there is no possible second-last pattern, ie, the one that is
one move before the bell rings (taking the place of *-*- for 4/2 or
*-*-*- for 6/4).  I haven't found a way to construct such a pattern for
any prime W even for H=W-2.  (Clearly, if W=w H=h is possible, W=w H>h
is also possible; simply use the H=h algorithm, with enough additional
probes, whose observations are ignored, to reach the higher H.  Hence,
if W=w H=w-2 is impossible, so is W=w H<w-2.)

I set out to build a program to brute-force algorithms.  The idea is
that the only useful information at the time of a table spin is the set
of possible patterns.  Since any two patterns which are rotations of
one another are equivalent, there are far fewer such possisble patterns
tna seems initially apparent; for example, for W=6 there are only 14
such patterns, even including the all-U and all-D patterns:

------		******
*-----		*****-
*--*--		**-**-
*-*---		***-*-
*-*-*-		***---
**----		****--
**--*-		**-*--

Thus, any set of possible patterns can be represented as a 14-bit
number and the program needs to store at most 2^14 possible nodes in
the search tree.  There are also only three different probe patterns
(patterns of wells to probe and possibly invert), the three of the
above patterns which have four bits set: ****--, ***-*-, and **-**-.

It turns out that most of the potential sets of possible patterns are
actually unreachable, especially for large H.  My program iterates,
starting with one `root' node, which has all possible patterns except
the all-U and all-D patterns (which would ring the bell without doing
anything at all).  It then keeps a list of nodes-to-investigate, that
list initialized to just the root node.  For each node, it then tries
each probe pattern; for each of the glass patterns which is possible
for that node, it tries it in each position to get an observation
pattern.  Then, for each of the observation patterns that can be
obtained, for each of the glass patterns which can produce it, it tries
each of the 2^H possible invert patterns, computing what the resulting
glass pattern would be.  It then takes the resulting set of glass
patterns and, if no node has been set up for it yet, creates a node for
it and queues it for investigation.  It then goes on to the next probe
pattern.

When it finally runs out of nodes to investigate, every glass pattern
set that's reachable from the root node has a node created for it.  It
then builds the algorithm backwards: it looks for nodes that can be
forced to a bell-ring.  The program does not record bell-ringing
patterns, so a node with the empty set of patterns corresponds to a
forced bell-ring.  Conveniently, the algorithm below considers this
node, if there is one, can-be-forced without any reference to any other
nodes, so that's where we get started.  (If there is no such node,
there is no way to reach a forced-ring state at all, so there obviously
is no solution.)

It repeatedly scans all nodes that aren't already marked as
can-be-forced.  For each such node, it looks at each probe pattern.
For each probe pattern, it looks at each possible observation to see if
that observation has an invert pattern that results in a set (of
possible glass patterns) which corresponds to a can-be-forced node.  If
it finds any probe pattern for which every observation has such a
invert pattern, then it marks the node can-be-forced.  (This is why the
empty set of possible patterns works: the "every such observation" part
is always satisfied vacuously.)

Once it can't mark any more nodes, it checks.  If the root node is
can-be-forced, there is a solution algorithm; if not, there isn't.

For example, consider the W=4 H=2 problem.  There are six possible
qglass patterns, including the all-0 and all-1 patterns: ---- *--- *-*-
**-- ***- ****.  The root node then has the four of these which aren't
all the same: ***- **-- *-*- *---.  There are only two probe masks,
**-- and *-*-.  Naming nodes with capital letters, we have, in turn
(note that we have to consider all rotations of each possible glass
pattern):

node A (the root): possible ***- **-- *-*- *---
  Probe **--
    ***-: observe **..
    **-*: observe **..
    *-**: observe *-..
    -***: observe -*..
    **--: observe **..
    -**-: observe -*..
    --**: observe --..
    *--*: observe *-..
    *-*-: observe *-..
    -*-*: observe -*..
    *---: observe *-..
    -*--: observe -*..
    --*-: observe --..
    ---*: observe --..
    List of possible observations: **.. *-.. -*.. --..
    observation --.. could result from ---* --*- --**
      invert pattern **.. -> can result in ***-
		(**-* ***- ****, but the first two are equivalent and
		the third rings the bell immediately)
	New pattern set, call this node B
      invert pattern -*.. -> can result in ***- **-- *-*-
	New pattern set, call this node C
      invert pattern *-.. -> can result in ***- **-- *-*-
	(already seen, node C)
      invert pattern --.. -> can result in **-- *---
		(note the ---* and --*- are the same under rotation)
	New pattern set, call this node D
		(Those are the only possible inversion patterns; we
		can't invert an unprobed position.)
    observation -*.. could result from -*** -**- -*-* -*--
      invert pattern **.. -> ***- **-- *-*- *---
		(*-** *-*- *--* *---, but under rotation the set is
		equivalent.)
      invert pattern *-.. -> ***- **--
	New pattern set, call this node E
      invert nattern -*.. -> **-- *---
	(already seen, node D - I won't be mentioning further cases of
	"already seen")
      invert pattern --.. -> ***- **-- *-*- *---
    observation *-.. could result from -*** -**- -*-* -*--
      invert pattern **.. -> ***- **-- *-*- *---
      invert pattern *-.. -> **-- *---
      invert pattern -*.. -> ***- **--
      invert pattern --.. -> ***- **-- *-*- *---
    observation **.. could result from **-- **-* ***-
      invert pattern **.. -> *---
	New pattern, call this node F
      invert pattern *-.. -> **-- *-*- *---
	New pattern, call this node G
      invert pattern -*.. -> **-- *-*- *---
      invert pattern --.. -> ***- **--
  Probe *-*-
    Again, it turns out (unsurprisingly for the root node) that we can
    observe any of the four possible combinations of the probed bits.
    observation -.-.
      invert *.*. -> ***-
      invert *.-. -> ***- **--
      invert -.*. -> ***- **--
      invert -.-. -> *-*- *---
	New pattern set, call this node H
    observation -.*.
      invert *.*. -> ***- **-- *---
	New pattern set, call this node I
      invert *.-. -> ***- *-*-
	New pattern set, call this node J
      invert -.*. -> *-*- *---
      invert -.-. -> ***- **-- *---
    observation *.-.
      invert *.*. -> ***- **-- *---
      invert *.-. -> *-*- *---
      invert -.*. -> ***- *-*-
      invert -.-. -> ***- **-- *---
    observation *.*.
      invert *.*. -> *---
      invert *.-. -> **-- *---
      invert -.*. -> **-- *---
      invert -.-. -> ***- *-*-

Continuing in this way, we find a total of 16 nodes:

B ***-
C ***- **-- *-*-
D **-- *---
E ***- **--
F *---
G **-- *-*- *---
H *-*- *---
I ***- **-- *---
J ***- *-*-
K **-- *-*-
L
M *-*-
N ***- *-*- *---
O **--
P ***- *---

Node L has the empty set of possibilities, so it gets marked
can-be-forced.  Then node M is next, because (part of) its
investigation looks like

  Probe X-X-
...
    observation -.-. invert *-*- new:
...
    observation *.*. invert *-*- new:

so it has a probe pattern (X-X-) for which every possible observation
(-.-. and *.*.) has a invert pattern (both *-*- in this case) which
leads to a to-be-forced node.

Next is **--.  Part of its investigation looks like

  Probe XX--
...
    observation --.. invert **-- new:
...
    observation -*.. invert **-- new: *-*-
...
    observation *-.. invert **-- new: *-*-
...
    observation **.. invert **-- new:

(Incidentally, this matches perfectly with the manually-found
algorithm's step "Adjacent: invert both", though that is coincidence.)

Continuing in this way, we do eventually mark the root node.

In impossible cases, the can-be-forced marking doesn't end up reaching
the root node.  Typically, it stops much earlier; for 5/2 and 5/3, it
finds the empty-set node and marks it, then fails to find any other
node that can be forced to it.  For 6/3, it marks the empty set, then
marks the node for the set containing only *-*-*-, but fails to find
any node that can be forced to *-*-*, nor any other node that can be
forced to the empty set.

I remarked above that it turns out that most of the potential sets of
possible glass patterns are actually unreachable.  In the case of 4/2,
we actually end up investigating them all; there are only 6 distinct
glass patterns after accounting for rotation, or 4 after dropping ----
and ****.  2^4 is 16, and we investigate 16 different nodes, so we hit
them all.  But for larger puzzles, this is true; for the next larger
puzzle, 5-2, we investigate only 31 nodes, whereas there are 6 glass
patterns after dropping ----- and *****, for 64 conceivable sets.  For
5-3, we of course have the same set of possible glass patterns, but we
investigate 40 nodes.  This too is a small-number artifact; for 6
wells, we have 12 distinct patterns after dropping ------ and ******,
for 4096 conceivable sets, but we investigate only a small fraction of
them:
	H	#
	2	1740
	3	948
	4	175

This makes sense; as H goes up, we gather more information per probe
and thus it's reasonable for the possibility sets to shrink.  And,
indeed, they do: for the 6/4 puzzle, the count of nodes invstigated
versus set size is

	Set size	 #
	    0		 1
	    1		12
	    2		53
	    3		81
	    4		27
	    12		 1

Except for the root node, no nodes at all are investigated with sets of
size 5 or more.  But with H=2, we see a few sets that are just one
pattern short of all the possibilities:

	Set size	  #
	    0		  1
	    1		 12
	    2		 59
	    3		173
	    4		318
	    5		393
	    6		355
	    7		240
	    8		118
	    9		 49
	   10		 18
	   11		  3
	   12		  1

Out of pure curiosity, I looked at which patterns were missing for the
three 11-member sets.  They are *-----, *****-, and *-*-*-.