Re^3: better algorithm: bitwise reordering

This sounds like a graph theory problem. (Though, given that I've been using Graph a bunch, and even submitted patches to it, recently, everything's been looking kinda like a nail right now.)

Here's what I mean

Create an undirected graph of X x Y vertices, presumably labeled a1, a2, b1, etc.
Create edges between all the squares that are connected to one another by means of how a rook can move. So, a1 has an edge to both a2 and b1, but a2 and b1 don't have an edge between them.
Put all the vertex names into a hash to mark if you've been there or not.
Pick a starting point. Mark it as being seen.
Find all the neighbors.
Iterate through them, recursively calling this function until you have touched every square.

The problem statement (as I read it) doesn't make mention of going back and forth between two squares (though it would be a valid variation upon a given walk), so you could probably prune a bunch of possibilities because you've already been there.

I would look at writing a better problem statement. Basically, are you only counting walks that minimize the number of squares touched? I would add the stipulation that you can only touch any square a maximum of two times. (One could add the once-per-square stipulation, but that may eliminate desired outcomes. I don't know enough about the problem domain to say with any certainty.)

The reason I suggest this option is because it sounds like you're not happy with your data structure which, in turn, is causing serious headaches with your algorithm.

------
We are the carpenters and bricklayers of the Information Age.

Then there are Damian modules.... *sigh* ... that's not about being less-lazy -- that's about being on some really good drugs -- you know, there is no spoon. - flyingmoose

I shouldn't have to say this, but any code, unless otherwise stated, is untested

Comment on Re^3: better algorithm: bitwise reordering

Replies are listed 'Best First'.
Re^4: better algorithm: bitwise reordering by hv (Prior) on Aug 25, 2004 at 17:39 UTC
The EIS reference is the best definition: "a rook must land on each square exactly once, but may start and end anywhere and may intersect it's own path". (For the non-chess players, the rook may move from a given square to any other square in the same row or the same column.) The data structure I'm using takes advantage of the fact that any given position is equivalent to one in which rows and/or columns are arbitrarily reordered, in an attempt to maximise the benefits of memoizing calculated values; the `rearrange()` function under discussion is trying to do precisely that reordering. I don't know enough graph theory to guess whether a graph-based approach would gain me anything; I think I'm happy with my data structure (though there may well be a better way), but I understand it rather better than I've been able to explain it so far. Hugo	[reply] [d/l]
Re^5: better algorithm: bitwise reordering by dragonchild (Archbishop) on Aug 25, 2004 at 18:03 UTC
Ok. This sounds interesting. And, yes, you could use graph theory to solve this, but you get a lot more edges. ponders Now I want to take a look at this problem. :-) Thanks! ------ We are the carpenters and bricklayers of the Information Age. Then there are Damian modules.... sigh* ... that's not about being less-lazy -- that's about being on some really good drugs -- you know, there is no spoon.* - flyingmoose I shouldn't have to say this, but any code, unless otherwise stated, is untested	[reply]