Re: Random rook's tour of a rectangle
- To: mathgroup at smc.vnet.net
- Subject: [mg50337] Re: Random rook's tour of a rectangle
- From: robertzierer at yahoo.com (Robert Zierer)
- Date: Sat, 28 Aug 2004 04:37:48 -0400 (EDT)
- References: <cggs1h$gb3$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
"DIAMOND Mark R." <dot at dot.dot> wrote in message news:<cggs1h$gb3$1 at smc.vnet.net>... > I wondered if anyone might know of an algorithm for generating a random > "rooks's tour" of a (not necessarily square) chessboard. I have looked in > the literature on self-avoiding walks tours of chessboards but not found > what I seek. (Knight's tour obviously gets a lot of attention). > > I have found some exhaustive enumeration algorithms which cope with > relatively small chessboards, but none that find a random paths, and none > that would manage with, say, a 1000*1000 chessboard. > > Any hints, algorithm, reference, suggestions for modifying an existing > algorithm (etc.) would be most appreciated. Hi, I am no mathematician and my mother tongue is not english, so my words are not always accurate. There is enough literature and algorithms on the moving knigths problem, even a book. Problematic is the high runtime. One standard way to cope with such large boards is to partitionate it into smaller boards, e.g. 5*5 and to search either closed or open ways with specificly choosen end- and startingpoints on it. The boards were then put side by side. With the open tours their end-/statpoints were already choosen to fit. With the closed walks, one must find four points where two are on the other board and each two of them in one jump distance; the paths were then changed from pattern '=' to '||' or 'X'. This should be fast enough to find one random walk. I know of a way to describe the whole problem to a underdetermined partially sparse linear equation system with quite restrictive bounds on the variables: variables can only be 0 or 1 and eight certain choosen variables add up to an integer. This gives in your case some million equations and variables. Imho this all will not be a better solution, as I don't know how to make such a thing into a easily calculable formula. If someone knows how to transform such a thing into a few for-loops I'd appreciate any comments. -- Robert Zierer