A "change" is a bellringing term. Technically speaking, the
"change" is the move from one row (or permutation, or ordering of
the bells) to the next, but we typically use it to mean the row
itself. For historical reasons, in bellringing, we always ring
each of the bells in the tower once in some order, making a row,
and then change to the next row, in which the bells are once again
all rung once in some order.
So the game is really just to guess an ordering of the numbers 1
to n, for whatever n you pick.
If you ask to "Watch computer play", the computer will follow the
strategy of generating a random guess compatible with all the
information it has so far. It does this by working through all n!
possibilities until it finds something that works -- note that this
can take it quite a while for 10
bells).
If you watch the fast solver instead, the computer will not be
trying to minimise the guesses it makes. Each guess will be the
initial guess with one pair of bells swapped, until it has collected
sufficient information. This is a much faster solver and you can
run it for many more bells without upsetting your browser, but it
uses a lot more guesses!
I want to play with bells (if you pick 10, use 0)
OR: Watch the computer play with bells: (minimum-guess strategy: slow – choose
4–10 bells)
OR ... Watch fast solver (but many guesses) with bells (4–100 bells):
Working (put what you like in this space):
Some questions about this game:
Guessing strategy: How many guesses do we need?
Is it always optimal to guess an ordering that is consistent with
the information you currently have? (While this is not the case with
some other guessing games like Wordle or Mastermind, I think that in
this case it is)
Are there "better" or "worse" choices that are consistent with
the current information? (i.e. is there a "more optimal" strategy
than "pick any consistent guess"?)
Given the "any consistent guess" strategy / an optimal strategy,
what's the worst case number of guesses I need? What's the average?
(Try watching the computer play to get a feel for this!)
Running time: How tractable is the problem?
The any-consistent-guess strategy implemented by
the computer solver above searches through O(n!) guesses
(although it doesn't make most of them), so the running time doesn't
scale well (hence the drop-down stopping at 10) -- (how) can we do
better than that?
A solver that (without checking for consistency) swaps (and
scores) all n-choose-2 pairs from an initial guess can solve in
O(n^3) time, but also makes O(n^2) guesses, which is certainly more
than a fewest-guess strategy needs.
Is there a way to combine a fewest-guesses strategy with a
best-runtime strategy?