Re: Random rook's tour of a rectangle
- To: mathgroup at smc.vnet.net
- Subject: [mg50297] Re: Random rook's tour of a rectangle
- From: Paul Abbott <paul at physics.uwa.edu.au>
- Date: Wed, 25 Aug 2004 03:36:09 -0400 (EDT)
- Organization: The University of Western Australia
- References: <cggs1h$gb3$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
In article <cggs1h$gb3$1 at smc.vnet.net>, "DIAMOND Mark R." <dot at dot.dot> wrote: > 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. Not sure if this will help but Chapter 6 of Computational Recreations in Mathematica by Ilan Vardi (Addison-Wesley, 1991) has a chapter on "The n-Queens Problem" that mentions non-attacking rooks on an n x n chess board. Perhaps Ilan Vardi or Igor Rivin would be able to help. Cheers, Paul -- Paul Abbott Phone: +61 8 9380 2734 School of Physics, M013 Fax: +61 8 9380 1014 The University of Western Australia (CRICOS Provider No 00126G) 35 Stirling Highway Crawley WA 6009 mailto:paul at physics.uwa.edu.au AUSTRALIA http://physics.uwa.edu.au/~paul