N-queens problem: Difference between revisions
Content added Content deleted
m (→Python: backtracking on permutations: Adjusted a few final details) |
m (→Python: Backtracking on permutations: Minor editing) |
||
Line 12,887: | Line 12,887: | ||
92</syntaxhighlight> |
92</syntaxhighlight> |
||
The preceding function does not enumerate solutions in lexicographic order, see [[Permutations#Recursive implementation]] for an explanation. The following does, but is almost 50% slower, because the exchange is always made (otherwise, |
The preceding function does not enumerate solutions in lexicographic order, see [[Permutations#Recursive implementation]] for an explanation. The following does, but is almost 50% slower, because the exchange is always made (otherwise, restoring the state of the array after the loop wouldn't work). On a regular 8x8 board only 5,508 possible queen positions are examined. |
||
However, it may be interesting to look at the first solution in lexicographic order: for growing n, and apart from a +1 offset, it gets closer and closer to the sequence [http://oeis.org/A065188 A065188] at OEIS. The first n for which the first solutions differ is n=26. |
However, it may be interesting to look at the first solution in lexicographic order: for growing n, and apart from a +1 offset, it gets closer and closer to the sequence [http://oeis.org/A065188 A065188] at OEIS. The first n for which the first solutions differ is n=26. |
||
Line 12,902: | Line 12,902: | ||
yield from queen(i + 1) |
yield from queen(i + 1) |
||
b[i + j] = c[i - j] = True |
b[i + j] = c[i - j] = True |
||
a[i:(n - 1)] = a[(i + 1):n] |
a[i:(n - 1)], a[n - 1] = a[(i + 1):n], a[i] |
||
a[n - 1] = j |
|||
else: |
else: |
||
yield a |
yield a |