1) What is the maximum number of 9×9 Sudoku puzzles equivalent to a given one? (Defining “equivalent” properly is part of the problem).

2) You are playing a computer game where you have to get out of a finite maze by a sequence of arrow keystrokes (up, down, left, right). You are guaranteed that there are no dead ends: from any point in the maze there is a way out. Reversing your previous move does not always get you back to the same place because the passages are twisty. The monitor breaks and you can no longer see where you are, but you can keep pressing arrow keys and the computer will beep if you have escaped. Is there a strategy to guarantee you eventually get out?

### Like this:

Like Loading...

*Related*

for number two

i assume the meaning here is supposed to be, “the program doesn’t alert you to collisions, so, if you push against a wall and then retreat, you may wind up elsewhere even though you’ve pressed two opposite buttons in a row”. is that correct?

when i first read “twisty” i had a mental image of passages that were not time-invariant, but i doubt that’s what you meant. or perhaps you left it deliberately ambiguous.

in any case, i’m going to give the retarded solution here and postulate that you could just use a completely random algorithm — say, use the decimal version of pi (with 0/1 = left, 2/3 = right, 4/5 = down, 6/7 = up, 8/9 = take a breather), or roll two dice (odd/odd = left, odd/even = right, even/odd = down, even/even = up). i have no idea how to do the relevant math, and i’m sure that this “algorithm” would take days if not years to get out of any maze of non-negligible size, but it seems the sort of thing that would have some time (however obnoxiously long) after which it would have more than N percent chance of getting you out.

… and this would have the same chance of working even with the non-time-invariant walls, right?

hm.

for number one:

let’s number the squares of the grid like a chessboard, a1 a2 a3 … i7 i8 i9. i can’t remember which is which, so i’ll guess that the numbers are columns.

here are some things you could do to get boards that are different-but-not-different (in one interpretation of the word):

* switch around columns 1, 2, 3 (or 4, 5, 6 or 7, 8, 9) in whatever order. should be 6 ways to do this for each block of three.

* switch around rows a, b, c (or d, e, f or g, h, i) in whatever order. should be 6 ways to do this for each block of three.

* switch around the 3 whole “towers” that consist of columns 1/2/3; 4/5/6; and 7/8/9 respectively. should be 6 ways to do this.

* switch around the 3 whole “bands” that consist of rows a/b/c; d/e/f; and g/h/i respectively. should be 6 ways to do this.

* re-label the numbers — you should be able to just rip the labels off and re-stick them so that the top left square becomes 123/456/789. there should be 9! ways to do this.

* change rows into columns (and vice versa). 2 ways.

you can also rotate and reflect, but i think those are covered. for instance, a 90 degree rotation is, i think, the same as turning rows into columns (+ vice versa) except in that all the columns wind up in reverse order. so you could just do that, and then switch the 3 towers, and then switch the 3 columns in each tower.

i think you can get the other rotations (and reflections) this way, too.

so that’s what, 9! times 6 x 6 x 6 x 6 x 6 x 6 x 6 x 6 x 2, which is a really big number of some kind.

You get an A+ for your solution to the Sudoku problem.

For the maze problem, what I meant is that if you go “up” from room A into room B, then going “down” from room B might not get you back into room A but rather have you remain in room B or go to room C. Imagine that the passage up from A made a right turn so that you entered B at its left wall, then going “left” from B would get you back to A. Also, some passages might be one-way and not traversable in the other direction. None of this matters — all you need to know is that there is a finite set of locations, and for each location there is a mapping from arrow keys to new locations (which might be the same as the old one), such that you can never get irreversibly stuck.

Obviously random moves will probably get you out eventually since the maze is finite — no exit sequence can be longer than the number of rooms, and eventually you will be in a room where you guess the right exit sequence. But the question is, can you find a deterministic way to do it which will infallibly work (random moves only probably work)?

hey, you said “guarantee … eventually”, so i win. heh

but ok, three other things

1) do the paths cross over or under each other, or is it something that works as an overall picture in 2d?

2) can you tell when you’ve hit a wall? (or “followed a passage that loops back into the same room”, which is the same as hitting a wall, it seems)

3) is this something that can be done using only high school math?

in any case, this problem seems … hard, so i’m going to go with the psychological-deconstruction solution:

this is the first problem that you’ve phrased as a yes/no question (“Can you find X”) rather than as a command (“Find X”). from this observation i will infer that the answer is “No, you can’t”.

am i right?

As I said, all you need to know is that there is a finite set of places you can be, and for each place there is a mapping of arrow keys to new places (which might be the same as the old one, corresponding to hitting a wall). The 2d or 3d geometry is irrelevant.

And your psychological deconstruction is backwards. If I am saying that certain assumptions which ought to make solving the maze easier aren’t necessary, shouldn’t that imply there is a more general solution? And it requires no math, just logic.

narciso, it’s been a couple days, so I’ll give the answer.

LEMMA: For any maze there is some sequence which will work no matter what room you start in: try the escape sequence from room 1, then if that doesn’t work try the escape sequence from the room that the first escape sequence would have gotten you to if you had started from room 2, then try the escape sequence from the room that the first 2 escape sequences would have gotten you to if you had started from room 3, and so on. If the maze has N rooms, then the concatenation of those N sequences escapes from anywhere in the maze.

PROOF: Since every maze has an escape sequence that works for all rooms in the maze, a universal escape sequence that works for any maze is one that has all possible subsequences. Eventually you will hit the subsequence that works for your maze, and at that point it won’t matter how lost within your own maze you had gotten. Here is a universal sequence (assuming only 4 directions Up Down Left Right): U,D,L,R,UU,UD,UL,UR,DU,DD,DL,DR,LU,LD,LL,LR,RU,RD,RL,RR,UUU,UUD,…

Extra credit: how much more efficient a universal sequence can you come up with? Obviously I didn’t need to list all 2-element sequences since “UD”, “DL”, “LR, “RU”, etc. had already occurred as subsequences by the time they got listed as single units between commas, so my sequence was dopier than it needed to be.

heh

i thought about the sub-sequence approach — specifically i remember seeing my 7th grade teacher write “0.1234567891011121314…” on the board as an irrational number, and so i was thinking “12341112131421222324…”

but isn’t there a problem with that approach, i.e., isn’t it not guaranteed to get you out of the maze unless you can keep “resetting” to the same initial room?

meaning, yeah the sequence contains all the different possible sub-sequences, but, since the subsequences are constantly being started from different rooms, isn’t there a chance that you might never get them to “line up” properly?

maybe i’m thinking too simplistically about this.

i like the “lemma”. that sounds like some kind of small high-desert animal. like a llama, only smaller.

Read the proof of the lemma more carefully.

ok, i got you. you can find the whole sequence of sequences in there.

neat.

under what type of math would these sorts of things be classified? or where would one find a discussion of them that wouldn’t be buried miles deep in formal notation? i’ve never seen anything like them. they’re cool.

i might actually post something in the next week.

This is classified under “combinatorics” which is a sort of catch-all term for math that doesn’t require a lot of math courses to understand but can still be very hard. Some mathematicians look down on this subfield because it has fewer “barriers to entry” but with the rise of the theory of algorithms and computation combinatorics has become fashionable again.

The efficiency question is interesting. There’s probably some literature on this. I’m pretty sure that you can have a sequence with all possible N-element consecutive subsequences for a k-letter alphabet whose length is not much more than the obvious minimum of k^N+N-1; but because of the “resetting” problem that might not get you out of all N-room mazes. I know the right person to ask about this though.

Here is another math puzzle. I’m interested in your response:

A very fast object, say a pebble shot at 300 mph, hits an object that for our purposes is immovable: a solid rock wall. The wall does not move or chip at impact.

How would you graph the deceleration of the pebble at impact? observably, it goes from 300 to zero in an instant. But a deceleration like that woudl plot a vertical line drop on the graph, an illegal function as far as I know. Thus, you’d need to plot its deleceration as an

almostvertical line… but that implies intermediate speeds of 299 mph, 200 mph, 173 mph, 5 mph, and 0.5 mph… for which there is no physical room between the pebble and the wall.So how do you plot the deceleration of this nature, where there is no give on impact?

The energy has to go somewhere, so the pebble deforms and either bounces away or breaks. Its shape is changing. And even if you just look at an atom on the leading surface that hits the wall, it doesn’t decelerate to 0 instantly, it penetrates the wall slightly and the atoms in the wall get pushed around and squeezed together some: although the forces in the wall that straighten them out and bounce the pebble away will operate very quickly their speed is not infinite. If you want to idealize the problem by forgetting that things are made of atoms and just modeling the wall as a perfectly rigid and immovable solid surface, then this unreality means that the non-continuous function that goes from 300 to 0 in an instant is no longer illegal.

PA:

1000 words:

(this is also a good way to impress upon people the importance of things like motorcycle safety)

also, note that you answered your own question (“The wall does not move or chip at impact”).

and, as long as it’s nitpicking time — if “the energy doesn’t go anywhere”, wouldn’t it go from 300 to -300, not 300 to 0? go pop science!

Thanks for the clear responses guys. Thus, in the real universe there will always be compression at impact, and with it, deceleration. And an idealized no-compression model allows for instant deceleration.

Narciso,

I spoke to my friend John H. Conway, a mathematician who discussed problems related to this one in Chapter 1 of his book “Regular Algebra and Finite Machines” in 1971. As I remembered, there is a perfectly efficient sequence from a k-letter alphabet which contains all possible length-n subsequences in the with the minimum length of (k^n)+n-1. Conway proves there is also a master sequence which will escape all mazes which has length at most (k^(2n-1))*8(n^2)*log(n) where the log is base 2. So if you have 4 directions and 8 rooms, then you can escape for sure in at most (4^15)*256*3 = 3*2^36 = 206,158,430,208 moves, though more efficient sequences are certainly possible. We know that you will need at least (4^8)+8-1 = 65,543 moves in any event, since for any sequence of length 8 I can construct a maze which requires those 8 moves to get out of where any deviation dumps you back to the initial state, so any sequence of length 65,542, which has only 65,535 = 4^8 -1 subsequences of length 8, will fail on a maze constructed this way using a “missing subsequence”.