Please do. I just wrote a computer program to solve this. I found at least one solution where the number of red paths is even, but not a single one for odd.
It was interesting practice writing this variant.
Brute-Force Man here!
My program counts 152 solutions with 2 red edges in the path, 612 solutions with 4 red edges in the path, and 224 solutions with 6 red edges in the path, for a total of 988 solutions, not including rotations (my code starts and ends at node A only).
The code I wrote dumped all the solutions to a nice HTML table, but I’m having tremendous FTP difficulties right now. I’ll try to remember to upload it to my web site after I get home tonight, and post a link here.
I realize now I was certainly out of my pay grade posting to this thread.
Anyway, I believe I enumerated every possible path where red=1 and it doesn’t exist. The thing seems to have left-right symmetry and from the above if red=1 it must connect to B or F, so I started with ABC and ABG and couldn’t get a solution.
I don’t see this is exactly like the knight problem, but if you guys say it is, I’ll take it as fact.
As you probably know, a re-entrant knight’s tour is a Hamiltonian (closed loop) over the 64 squares of a chessboard, where legal moves are the moves of a knight in chess. I thought of a way to reduce it to 16 squares, and it’s a snap to see a Hamiltonian on a 16-node diagram, if one exists.
Okay, so label your chessboard like this (notice that if you rotate the board 90 degrees, the letters are the same but the colors swap):
D O M F B P N D
N A C L J E A O
P E K G I K C M
B J I H H G L F
F L G H H I J B
M C K I G K E P
O A E J L C A N
D N P B F M O D
Now, you will probably easily see where I got the node diagram from - from a blue F, for instance, you can go to a blue A, a blue K, a red I, or a red E.
So say you took a Hamiltonian on the 16-node diagram - like ABCDEFIPOLHKJNMGA - and followed the 16 moves. Starting from, say, the A in the upper-left quadrant, you move to B, then C, D, E, F, I, and so on. After 16 moves, you’d wind up back on an A, having hit each of the 15 other letters once. If you were on the A in the lower-left, you could repeat the 16 moves, this time hitting 16 new letters, and wind up on the A in the lower-right. You could then repeat it two more times and complete the entire circuit.
The only problem is that if you wound up on a blue A, it wouldn’t work. The circuit would be over in either 16 or 32 moves. So you’d have to change colors an odd number of times. No problem - every move that corresponds to a change in colors you identify on your graph, and make sure you hit an odd number of them.
That brings us to the OP. Simple, huh? Now, I should point out before you look at me disdainfully that this method is not as hopeless as it might seem. I once solved a very similar problem using the same method. In that case, the “chessboard” was 10 by 10, and your “chess piece” could move either three spaces horizontally or vertically, or two spaces diagonally. This method reduced the problem to 25 nodes, and it was easy after drawing the diagram. In that case, there were two nodes that were linked with both a blue edge and a red edge, so that was no big issue.
I was kicking myself about the even numbers I reported, until I took off the restriction that my program only report even numbers. With it counting both even and odd numbers of red edges in the path, the results are the same as the numbers above. In other words, if a path which starts at A also has to end at A, there are no solutions with an odd number of red edges.
For those who might be curious, if the path can start at A, and end at any node, then any number of red edges between 1 and 8 are possible. 40 paths exist with 1 red edge, 202 with 2, 856 with 3, 1206 with 4, 1262 with 5, 612 with 6, 140 with 7, and 20 with 8.
Okay, I got a few questions.
First, in completing a cycle over the entire chessboard, you’d have to change colours (according to your diagram, anyway) an even number of times (if you include the jump from the final square back to the start). I don’t see how you’re getting an odd number of colour changes.
Second, I can’t quite see (though I haven’t dug enough yet) why you had us looking for a cycle with an odd number of red edges taken.
Finally, I’m curious whether you’re suggesting there’s no way to form a 64-step cycle from some four 16-step cycles in a 4x4 grid, or whether it’s just that this particular 16-step solution can’t be so connected.
Its funny, I had a somewhat discussion about 5 years ago with a co-worker about solving massive knights tour problems in time linear with the number of squares on a rectangular board. We vaguely speculated on solving it by using smaller solutions and connecting them… Didn’t really pursue it though – we had work to do. =) Now you got me curious about this again.
Or was it longer ago? Geez… time is fleeting…
I’ve gotta tone down the obsessive-compulsive setting. I’ve got chess boards running through my head now.
You’d change colors an even number of times over all 64 moves combined, yes, but in the first 16 you’d change color an odd number of times. At least, that was the idea. Does that make sense?
16 moves exceeds the number of squares in a single colour, so you must by definition have moved to a new colour at least once. This means you’ve actually visited (including the initial square) 17 squares.
On top of this, I can sort of see that if you want to repeat the same operation 3 more times, exploiting some sort of rotational symmetry, then you couldn’t change colours an even number of times or you’d end up in either the same quadrant or the one in the opposite corner. In the second case, another iteration would end up in the original corner. You’d never end up in either of the other two quadrants by repeating the original operation any number of times.
But I can’t convince myself that there is no way to cover the entire board if the number of colour changes is even.
I’ll have to poke at this. 
I may be out of my league here.
Okay, this is all I’m saying. If the number of color changes in the first 16 moves is even, then you cannot cover the entire board simply by repeating the first 16 moves three times (but rotated 90 degrees each time). I was looking for a way to do that.
Also, it’s clear that you can’t stay in one quadrant for 15 moves. This is clear because as aahala pointed out, there’s no loop which uses only blue paths.
Yup, I’ve poked at this, and I think I finally agree.
If the 16 step solution uses node X for some X in any quadrant, it can’t use it in any other quadrant, because when you repeat the solution, you’d end up using more copies of X than exist and so no cycle can exist. That means you can use A through P alone, just 16 nodes. Even if the B you use is in a different quadrant from where you started, you can’t use it twice.
Further, the ‘red’ edges are basically those connections that cross a boundary. It doesn’t represent edges between red nodes. Moving between two red nodes would be consistent with a blue edge. (The colouring of edges and nodes probably should have been kept unique). This wasn’t previously clear to me.
I’m just reiterating stuff you’ve already said, but I had to walk through it.
Hey, that’s a neat technique. I’ll have to add that to my mental collection.
Have you tried solutions that don’t involve just rotations of the 16 move sequence, but flips as well?
Given what you want to do, Achernar, the solution lies in the I-to-I and G-to-G red paths missing from the original graph. I believe you’ll need to work out a path with 16 letters (or 15 ‘steps’), going from G to I, using all the letters and an even number of red paths.
You’ll start one path on the G in the upper-left corner (for example). Run the path to come to an I. Whether it’ll be the upper-left or lower-right I will depend on the jumps you’ve chosen, but it’ll be one of those two. Make a jump from I to an I of the opposite color as your 16th step. Now, run the path backwards, and you’ll wind up on a G of the opposite color from where you started. As your 32nd step, you’ll a jump from the G you’re on now, to the G of the opposite color which was not the one you started on. Run the path from G to I again, and then make, as your 48th step, a jump from whatever I you’re on to the last I left to visit. Run the path from I back to G one more time, and as the 64th step, you could make a G-to-G jump back to your original starting square in the upper-left corner.
Those G-to-G and I-to-I jumps are what get you from the blue quadrants to the red, and back again. The complete loop has four of them, so the total number of red jumps you’ll make will indeed be even, but the number of red jumps you make every 16 steps will be odd.
I’ll try to get some time to find the G-to-I paths with my program, and verify what I’m talking about. Can’t do it now. And the list of A-to-A paths I promised to put up and link to earlier is now moot.
A quick search of the web turned up this page, which contains more than you ever wanted to know about knight’s tours. (Well, maybe not more than you ever wanted to know, but more than I ever wanted to know.)
As to the specific topic given here, here’s what this page says about the kind of tours you’re looking for:
A closed tour of an 8x8 chessboard with what’s called “oblique quaternary symmetry” by the author of this page is impossible. See the section called “Symmetry in Knight’s Tours” and look for Theorem 5.
[QUOTE=ftg]
“Pure Math Problem”, Travelling Salesperson???
You do understand that Travelling Salesperson is an important problem in Computer Science and that Computer Science is most definitely not Math, Pure or otherwise? Hardly any Mathematicians care in the least about NP complete problems.
[QUOTE]
Graph Theory looks very mathematical to me.
MikeS wrote:
Actually, the tour I just constructed by hand using the guidelines I listed above (and one of the 86 paths between G and I as displayed by my code: GABCDEFKNMJHLOPI) displays a binary oblique symmetry, not quarternary. Oddly, all 86 paths contain either 3 or 5 red edges (58 and 28 of them, respectively), and none contain an even number of red edges. I expected the opposite situation. My method still appears to work, however. Gotta verify all patterns automatically. Maybe I’ll post some designs later.
I suspect that half of the 86 paths are mirror flips of the others, along a diagonal. Will work to verify this, also.
I believe it goes a little something like this. Aside from the gray segments, the entire thing has quaternary oblique symmetry, and with the gray segments added it still has binary oblique, as you said. Good job - you rescued what I thought was a dead end.
Achernar wrote:
Good job, yourself. You built the exact same tour I did. When you come to that first I, you’ve got a choice of two. I believe that had you chosen the other I, you would wind up with the same pattern, but rotated 90 degress (in other words, not exactly the same as the one you built and displayed 
). I’m still working (albeit slowly) on verifying that and the other 85 tours, but I’m very happy to see that my instructions were clear enough to follow.
Eager to put my original method to good use, I decided to apply it to a 9 by 9 board, with the center square removed. A Hamiltonian on the remaining 80 squares is the longest Hamiltonian you can make on a 9 by 9. I used this lettering:
S D Q B M C K J S
J A P G T O R A D
K R E L I F E P Q
C O F N H N L G B
M T I H X H I T M
B G L N H N F O C
Q P E F I L E R K
D A R O T G P A J
S J K C M B Q D S
Here’s the node diagram that results. A bit less symmetric than the last one, to be sure, but you should have seen it before I reorganized the nodes. >_<
As you can see, some of the nodes are connected by both a red and a blue edge. This makes it easy to come up with a path with an odd number of reds. I used ACEDGHIBOJQLMRSPKTNFA, taking the blue path between N and T. Here’s the solution that resulted.
Well, on this web page, you can find all of the solutions to the “quartered 8x8 knight tour” that my code found. If for nothing else, spending the time I did was well worth it, 'cause the images look pretty cool.
The tour plotted earlier, GABCDEFKNMJHLOPI, is tour #105 on the linked-to list. And yes, switching where the first I-to-I jump goes on that one does simply rotate the tour. Surprisingly (to me, at least), there were some paths for which the different I-to-I jumps made non-reflected, non-rotated tours from the originals.
Out of 172 possible tours using the method I described, there were 51 unique tours. Would anyone like to explain the math behind that? An easier question might be: does anyone know how those numbers compare to a 6x6 board, or a 10x10 or higher? Is there a pattern there?
Back to the 8x8: I’d like to nominate tour #27 as the closest (as possible) to having each quarter-path all bunched up in the same quadrant.
I’d also like to note that tour #123 has each quarter path (mostly) stay in the same half of the board as it started. Only the last jumps of the 1st and 3rd quarters breach the halfway boundaries.
My code is generalized now (although decidedly hackish and ugly), and will support any even-sided square board (but I haven’t tried anything but 8x8). Though I’ve got a question for you, Achernar: what scheme are you using to determine the lettering? If I could figure out that scheme, or abandon it, my code wouldn’t need any more input than the length of a side of the board.
As it is, all I put in is the side length, plus a “map” of one quadrant to maintain the same lettering. The code reads that map, and goes ahead and creates its own graph of the nodes and possible paths (which is why the list doesn’t start with GABCDEF… like it used to - but you didn’t see the previous listings of quarter-paths).
At this point, modifying the code to run non-square quadrants, or odd-sided boards, would be a real pain. Without getting paid, I won’t be motivated enough to make these mods anytime soon.
Wow, that’s impressive. I like it!
Oh that’s easy. When I first did it, I just labelled them alphabetically, A through P. Then, when I had made the node diagram pretty, I relabeled them so that the node diagram was in order, and mapped it back to the chessboard.