login
Number of ways of placing n nonattacking queens on n X n board (symmetric solutions count only once).
(Formerly M0180 N0068)
21

%I M0180 N0068 #72 Dec 23 2019 18:58:43

%S 1,0,0,1,2,1,6,12,46,92,341,1787,9233,45752,285053,1846955,11977939,

%T 83263591,621012754,4878666808,39333324973,336376244042,3029242658210,

%U 28439272956934,275986683743434,2789712466510289,29363495934315694

%N Number of ways of placing n nonattacking queens on n X n board (symmetric solutions count only once).

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D M. B. Wells, Elements of Combinatorial Computing. Pergamon, Oxford, 1971, p. 238.

%H J. R. Bitner and E. M. Reingold, <a href="/A002562/a002562.pdf">Backtrack programming techniques</a>, Commun. ACM, 18 (1975), 651-656. [Annotated scanned copy]

%H J. R. Bitner and E. M. Reingold, <a href="http://dx.doi.org/10.1145/361219.361224">Backtrack programming techniques</a>, Commun. ACM, 18 (1975), 651-656.

%H P. Capstick and K. McCann, <a href="/A000170/a000170_1.pdf">The problem of the n queens</a>, apparently unpublished, no date (circa 1990?) [Scanned copy]

%H V. Chvatal, <a href="http://users.encs.concordia.ca/~chvatal/8queens.html">All solutions to the problem of eight queens</a>

%H V. Chvatal, <a href="/A002562/a002562_1.pdf">All solutions to the problem of eight queens</a> [Cached copy, pdf format, with permission]

%H Popular Computing (Calabasas, CA), <a href="/A002562/a002562.png">8 Queens</a>, Vol. 2, No. 13, Apr 1974, page PC13-1. Illustrates a(8)=12.

%H Popular Computing (Calabasas, CA), <a href="/A002562/a002562_1.png">8 Queens</a>, Vol. 2, No. 13, Apr 1974, page PC13-2.

%H Popular Computing (Calabasas, CA), <a href="/A002562/a002562_2.png">8 Queens</a>, Vol. 2, No. 13, Apr 1974, page PC13-3.

%H Popular Computing (Calabasas, CA), <a href="/A002562/a002562_3.png">8 Queens</a>, Vol. 2, No. 13, Apr 1974, page PC13-4.

%H Thomas Preusser, <a href="http://queens.inf.tu-dresden.de">Queens%40TUD</a>-Project

%H E. M. Reingold, <a href="/A000170/a000170_2.pdf">Letter to N. J. A. Sloane</a>, Dec 27 1973

%H M. A. Sainte-Laguë, <a href="https://eudml.org/doc/192551">Les Réseaux (ou Graphes)</a>, Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1923, 64 pages. See p. 47.

%H M. A. Sainte-Laguë, <a href="/A002560/a002560.pdf">Les Réseaux (ou Graphes)</a>, Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1923, 64 pages. See p. 47. [Incomplete annotated scan of title page and pages 18-51]

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/QueensProblem.html">Queens Problem.</a>

%H M. B. Wells, <a href="/A000170/a000170.pdf">Elements of Combinatorial Computing</a>, Pergamon, Oxford, 1971. [Annotated scanned copy of pages 237-240]

%H WikiMili, <a href="https://wikimili.com/en/Eight_queens_puzzle">Eight queens puzzle</a>, (2019).

%F a(n) = (1/8) * (Q(n) + P(n) + 2 * R(n)), where Q(n) = A000170(n) [all solutions], P(n) = A032522(n) [point symmetric solutions] and R(n) = A033148(n) [rotationally symmetric solutions].

%e a(4) = 1:

%e +---------+

%e | . . Q . |

%e | Q . . . |

%e | . . . Q |

%e | . Q . . |

%e +---------+

%e a(5) = 2:

%e +-----------+ +-----------+

%e | . . . Q . | | . . . Q . |

%e | . Q . . . | | Q . . . . |

%e | . . . . Q | | . . Q . . |

%e | . . Q . . | | . . . . Q |

%e | Q . . . . | | . Q . . . |

%e +-----------+ +-----------+

%e a(6) = 1:

%e +-------------+

%e | . . . . Q . |

%e | . . Q . . . |

%e | Q . . . . . |

%e | . . . . . Q |

%e | . . . Q . . |

%e | . Q . . . . | - _Hugo Pfoertner_, Mar 17 2019

%e +-------------+

%e a(7) = 6:

%e +---------------+ +---------------+ +---------------+

%e | Q . . . . . . | | Q . . . . . . | | . Q . . . . . |

%e | . . Q . . . . | | . . . Q . . . | | . . . Q . . . |

%e | . . . . Q . . | | . . . . . . Q | | Q . . . . . . |

%e | . . . . . . Q | | . . Q . . . . | | . . . . . . Q |

%e | . Q . . . . . | | . . . . . Q . | | . . . . Q . . |

%e | . . . Q . . . | | . Q . . . . . | | . . Q . . . . |

%e | . . . . . Q . | | . . . . Q . . | | . . . . . Q . |

%e +---------------+ +---------------+ +---------------+

%e .

%e +---------------+ +---------------+ +---------------+

%e | . Q . . . . . | | . Q . . . . . | | . Q . . . . . |

%e | . . . . Q . . | | . . . . Q . . | | . . . . . Q . |

%e | Q . . . . . . | | . . . . . . Q | | . . Q . . . . |

%e | . . . Q . . . | | . . . Q . . . | | . . . . . . Q |

%e | . . . . . . Q | | Q . . . . . . | | . . . Q . . . |

%e | . . Q . . . . | | . . Q . . . . | | Q . . . . . . |

%e | . . . . . Q . | | . . . . . Q . | | . . . . Q . . |

%e +---------------+ +---------------+ +---------------+

%e - _Hugo Pfoertner_, Mar 18 2019

%Y Cf. A000170, A032522, A033148.

%K nonn,nice

%O 1,5

%A _N. J. A. Sloane_

%E a(17) and a(18) found by Ulrich Schimke in Goettingen, Germany (UlrSchimke(AT)aol.com)

%E Formula and a(19) to a(23) added by _Matthias Engelhardt_ in Nuremberg, Germany, Jan 23 2000

%E Terms (calculated from formula) added by _Thomas B. Preußer_, Dec 15 2008

%E a(26) (derived from formula after recent extension of A000170) added by _Thomas B. Preußer_, Jul 12 2009

%E a(27) (derived from formula after recent extension of A000170) added by _Thomas B. Preußer_, Sep 23 2016