Hi,<br><br>I&#39;m trying to solve the N-queens problem, but with a catch: I want to generate solutions in a random order.<br><br>I know how to solve the N-queens problem; my solver (below) generates all possible solutions.  What I am trying to do is generate solutions in a random order by somehow randomizing the order in which &quot;nextRow&quot; considers the unused columns.  I tried adding a random number generator to the solution state; the problem with this approach is that whenever the solver backtracks, the state of the random number generator backtracks along with it.  In effect, I am selecting a random, but fixed, permutation for each row, and then I am applying that same set of permutations along all computational paths.  Whenever I consider row R, regardless of which path I have taken, I am applying row R&#39;s permutation to the unused columns.<br>
<br>This is not the behavior I want.  I want each computational path to use a new, different permutation for each row.  On the other hand I also want to be able to take the first few solutions without waiting for all possible solutions to be generated.  How might I go about doing this?<br>
<br>-- Ron<br><br>------------------------------------------------------------<br>module Main<br>where<br><br>import Control.Monad.State<br>import Data.List<br>import System.Environment<br>import System.Random<br>import System.Random.Shuffle -- from package random-shuffle<br>
<br>newtype Location = Location {unLocation :: (Int, Int)}<br>  deriving (Show)<br><br>isAttacked :: Location -&gt; Location -&gt; Bool<br>isAttacked (Location (row1, column1)) (Location (row2, column2)) =<br>    or [ (row1 == row2)<br>
       , (column1 == column2)<br>       , ((row1 - row2) == (column1 - column2))<br>       , ((row1 - row2) == (column2 - column1))<br>       ]<br><br>newtype Board = Board {unBoard :: [Location]}<br>  deriving (Show)<br>
<br>data (RandomGen g) =&gt; SolutionState g = SolutionState<br>    { solnBoard :: Board<br>    , solnUnusedColumns :: [Int]<br>    , solnRandomGen :: g<br>    }<br><br>nextRow :: (RandomGen g) =&gt; Int -&gt; Int -&gt; StateT (SolutionState g) [] ()<br>
nextRow n row  = do<br>  (SolutionState (Board locs) unusedColumns gen) &lt;- get<br>  let (ps, gen&#39;) = randShuffleSeq (length unusedColumns) gen<br>  column &lt;- lift $ shuffle unusedColumns ps<br>  let loc = Location (row, column)<br>
  guard $ all (not . isAttacked loc) locs<br>  let remainingCols = unusedColumns \\ [column]<br>  put $ (SolutionState (Board (loc : locs)) remainingCols gen&#39;)<br><br>randShuffleSeq :: (RandomGen g) =&gt; Int -&gt; g -&gt; ([Int], g)<br>
randShuffleSeq 0 g = ([], g)<br>randShuffleSeq 1 g = ([], g)<br>randShuffleSeq n g = (x:xs, g2)<br>    where<br>      (x, g1) = randomR (0, n-1) g<br>      (xs, g2) = randShuffleSeq (n-1) g1<br><br>allRows :: (RandomGen g) =&gt; Int -&gt; StateT (SolutionState g) [] ()<br>
allRows n = mapM_ (nextRow n) [1..n]<br><br>solve :: (RandomGen g) =&gt; Int -&gt; g -&gt; [Board]<br>solve n gen = map solnBoard $<br>              execStateT (allRows n) (SolutionState (Board []) [1..n] gen)<br><br>formatSolution :: Board -&gt; String<br>
formatSolution = show . map unLocation . unBoard<br><br>main :: IO ()<br>main = do<br>  args &lt;- getArgs<br>  let boardSize = read $ args !! 0<br>      maxSolns = if length args &gt; 1 then read (args !! 1) else 10<br>      allSolns = solve boardSize (mkStdGen 42)<br>
  putStrLn $ unlines $ map formatSolution $ take maxSolns allSolns<br><br>