MathGroup Archive 2004

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Random rook's tour of a rectangle

  • To: mathgroup at
  • Subject: [mg50337] Re: Random rook's tour of a rectangle
  • From: robertzierer at (Robert Zierer)
  • Date: Sat, 28 Aug 2004 04:37:48 -0400 (EDT)
  • References: <cggs1h$gb3$>
  • Sender: owner-wri-mathgroup at

"DIAMOND Mark R." <dot at> wrote in message news:<cggs1h$gb3$1 at>...
> 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.


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

  • Prev by Date: Re: Beware of NSolve - nastier example
  • Next by Date: Re: Integrate UnitStep, Bug?
  • Previous by thread: Re: Random rook's tour of a rectangle
  • Next by thread: subscripted function variables