The Number of Ways to Place Non-Attacking Queens Does Not Always Grow with the Board ── Place n queens on an nx n board so that none attacks another along a row, column or diagonal ── 12x12 has 14200 ── [Paper 624]

Abstract

A chess queen moves any distance along rows, columns and diagonals. The ways to place n queens on an nx n board with no two attacking each other are counted (the n-queens problem). No new theorem or law is claimed. Scope of this paper (scope note): No new theorem or law is claimed──the 92 placements of eight queens and the counts for each n are known (the survey by Bell and Stevens of 2009, the paper by Rivin and coauthors of 1994, and others). Asymptotics for general n are not treated──n=1 to 12 are counted, with symmetries merged for n<=10. Fast construction is not treated──to construct a single placement, methods without counting them all are known. Relation to earlier papers: Paper 604 showed that no Latin square of order six has an orthogonal mate──Latin squares and queen placements are both arrangements with one per row and column; queens add the diagonal condition. Here too the count dips at 6. What is added is setting out the counts for n=1 to 12 and the merged counts for n<=10, matching two searches for n=4 to 8, and placing the separator on the board size and showing that the growth is not monotone. First, the 8x8 board has 92 placements, 12 when merged──merging placements that coincide under the 8 rotations and reflections of the board, the 92 become 12 (Section 2). Second, small boards have none──on 2x2 and 3x3 any placement attacks. The first placements appear on 4x4: 2 (1 when merged) (Section 2). Third, and this is the core. A larger board does not always have more placements──5x5 has 10, but 6x6 drops to 4 (1 when merged). 7x7 comes back to 40, and 12x12 rises to 14200 (Section 2). Fourth, two searches agree──a search placing one row at a time while recording used columns and both diagonals in bits, and a search trying all n! column orders, gave the same counts for n=4 to 8 (Section 3). Place n non-attacking queens on an nx n board. On 8x8 there are 92 placements, 12 when merged by rotation and reflection──two searches agreed for n=4 to 8. A larger board does not always have more placements──2x2 and 3x3 have none, and the 4 on 6x6 are fewer than the 10 on 5x5. From 7x7 on the counts grow, reaching 14200 on 12x12. Placed among the earlier papers──like the Latin squares of Paper 604 these are arrangements with one per row and column, and both dip at 6. To be honest──only boards up to 12 were counted; the behaviour for general n is not entered. On the making of this work: The ideas and content of this work stem from the author's own considerations. Assistance from an AI (a large language model) was used for structuring, English translation, and checking the algebra. Any remaining errors or misinterpretations are solely the author's. Feedback and corrections are sincerely appreciated. Keywords: eight queens puzzle, n-queens problem, backtracking, board symmetry, combinatorial search. ----- チェスのクイーンは、縦・横・斜めにいくらでも動ける。 nx n の盤に n 個のクイーンを、どの二つも取り合わないように置く置き方を数える(n クイーンの問題)。新しい定理も法則も主張しない。 本稿の射程(射程注記):新しい定理も法則も主張しない──8 クイーンの 92 通りと、各 n の置き方の数は、いずれも既知である(ベルとスティーヴンズの 2009 年の概説、リヴィンらの 1994 年の論文ほか)。一般の n の漸近式を扱わない──n=1 から 12 を数え、n<=10 で対称をまとめるだけである。置き方を作る速い方法を扱わない──一つ置き方を作るだけなら、全部を数えなくてもよい方法が知られている。既刊との関係:論文604 は、6 次のラテン方陣に直交する相手が一つも無いことを示した──ラテン方陣もクイーンの置き方も「行と列に一つずつ」を満たす並べ方で、クイーンにはさらに斜めの条件が足される。ここでも 6 で数が落ち込む。加えたのは、n=1 から 12 の数と、n<=10 で対称をまとめた数を並べたこと、二つの探し方を n=4 から 8 で突き合わせたこと、分離子を盤の大きさに置き、増え方が単調でないことを示したことである。 第一に、8x8 の置き方は 92 通り、まとめると 12 通りである──盤の回転と裏返し(8 通り)で重なる置き方を一つとまとめると、92 通りは 12 通りになる(第2節)。 第二に、小さい盤には置き方が無い──2x2 と 3x3 では、どう置いても取り合う。4x4 で初めて 2 通り(まとめると 1 通り)置ける(第2節)。 第三に、これが本稿の芯である。盤を大きくしても、置き方が増えるとは限らない──5x5 は 10 通りなのに、6x6 は 4 通り(まとめると 1 通り)に減る。7x7 で 40 通りに戻り、12x12 では 14200 通りまで増える(第2節)。 第四に、二つの探し方が一致した──縦・横・二方向の斜めの使用を桁で覚えて一行ずつ置く探し方と、列の並べ方 n! 通りを全部試す探し方で、n=4 から 8 の数が一致した(第3節)。 nx n の盤に、取り合わない n 個のクイーンを置く。8x8 では 92 通りで、盤の回転と裏返しでまとめると 12 通りである──二つの探し方が n=4 から 8 で一致した。盤を大きくしても、置き方が増えるとは限らない──2x2 と 3x3 には置けず、6x6 の 4 通りは 5x5 の 10 通りより少ない。7x7 から先は増え、12x12 で 14200 通りになる。既刊との位置──論文604 のラテン方陣と同じく「行と列に一つずつ」の並べ方で、どちらも 6 で数が落ち込む。正直に言えば──12 までを数えただけで、一般の n の振る舞いには入っていない。 作成にあたって:本稿の着想と内容は、著者自身の考察に基づくものです。文章の構成整理や英訳、数式の確認には AI(大規模言語モデル)の助力を得ました。最終的な内容の解釈や誤りがあれば、それらはすべて著者の責に帰します。お気づきの点があれば、ご教示いただければ幸いです。 キーワード:エイト・クイーン、n クイーン問題、バックトラック、盤の対称性、組合せ探索。