nouveau document microsoft word.doc

For the incomplete methods, we kept the representation of the queens by a table and the method of ca

                             Complete methods:

    The complete methods requiring much calculations, for these first heuristic, we represented the chess-board by a matrix where one represents by 2 the fact that a queen is placed in a box, 1 the fact that a box is seizable by a queen and 0 that the box is free.  Thus, when one places (resp. withdraws) a queen, one updates the boxes that this queen can (resp. could) take.  As the operation generally returning is the test to seek a free place, it is then enough to find a place containing one 0 without having to seek the other queens.
heuristics:  backtracking with random shift:
    Tests:  50 queens in less than 1 second and 1350 iterations.  100 queens in 3 seconds and 11348 iterations.  150 queens in 28 seconds and 30160 iterations.
heuristics:  backtracking with order according to the number of possible places:
    Tests:  100 queens in less than 1 second and 411 iterations.  400 queens in 1 second and 516 iterations.  1000 queens in 6 seconds and 1016 iterations.
heuristics:  backtracking recursive to determine the whole of the possible solutions.
    Tests:  724 solutions found for 10 queens.  2680 solutions for 11 queens.  14200 solutions for 12 queens.


                             Incomplete methods:
For the incomplete methods, we kept the representation of the queens by a table and the method of calculation to determine if two queens are in conflict, which is much faster for this kind of problems than the representation by a matrix.
heuristics:  descent.
    Tests:  100 queens in less than 1 second and 67 iterations.  500 queens in 1 second and 257 iterations.  1000 queens in 11 seconds and 492 iterations.
heuristics:  Simulated annealing.
    Tests:  100 queens in less than 1 second and 47 iterations.  500 queens in 5 seconds and 243 iterations.  1000 queens in 13 seconds and 497 iterations.
heuristics:  based on Simulated Annealing.
    Tests:  100 queens in less than 1 second and 60 iterations.  500 queens in 1 second and 224 iterations.  1000 queens in 5 seconds and 459 iterations.  10 000 queens in 20 minutes 30 seconds and 4885 iterations.