User guide

11.5. THE N-QUEENS DEMONSTRATION 203
mcRR(mc_add, col, p) // col := col+p
mcRR(mc_add, rd, p)
mcRK(mc_rsh, rd, 1) // rd := (rd+p)>>1
cmpltry(i+1, n, all) // Compile code for row i+1
mcR (mc_pop, poss) // Restore the state
mcR (mc_pop, rd)
mcR (mc_pop, col)
mcR (mc_pop, ld)
mcRK(mc_cmp, poss, 0)
mcJL(mc_jne, M) // } REPEATWHILE poss
}
mcL(mc_lab, L)
mcComment("// End of code from try(%n, %n, %n)*n*n",
i, n, all)
}
In this implementation all the working variables are held in registers and all re-
cursive calls are unwound knowing that the depth of recursion will be li m i te d, in this
case to no more t han 16. The stack is used to save the state at the moment when a
recursive call would have been made in the original program. An optimisation is done
based on the knowledge that if a queen can be placed on the nth row of n × n board
then the solution count can be incremented.
When running on a Pentium IV this implementation executes approximately 24
times faster than the normal interpretive Cintcode version and 25% faster than the
corresponding optimi se d C version of the algorithm.