著者

藤原 美早紀 山村 明弘

出版者

情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.53, no.6, pp.1592-1601, 2012-06-15

---

2次元チェス盤上のエイトクイーンパズルを立方体表面上に拡張して構成されるn-クイーン問題およびn-ルーク問題について考察する.2次元チェス盤上のn-ルーク問題の解は自明であるが,立方体表面の6つの面にn × nのチェス盤を置いて構成した立体的なゲーム盤上のn-クイーン問題およびn-ルーク問題の解の個数や特徴は明らかではない.本論文では,1辺がnの立方体表面上で互いに攻撃しないルークの最大個数は$\lfloor 3n/2 \rfloor$であることを証明し,互いに攻撃しない最大個数のルークが立方体表面上に配置されるときに満たさなければならない必要条件を示す.さらに立方体を自分自身に重ね合わせる変換で移り合うn-クイーン問題およびn-ルーク問題の解を同一視するため,正8面体群の立方体への作用からn-クイーン問題およびn-ルーク問題の解の集合への作用を導入し,その作用に関する同値類の個数を求めることで本質的に異なる解の個数を計算する.n-クイーン問題(n ≤ 8)およびn-ルーク問題(n ≤ 6)の本質的に異なる解の個数を報告する.We discuss n-queen and n-rook problems on cubes, which are generalization of the eight queen puzzle over two-dimensional chessboard. We can easily get a solution of the n-rook problem on a two-dimensional chessboard, while it has not been known the number or any theoretical properties of solutions for the n-rook problem on three-dimensional game board constructed by six chessboards placed on six faces of a cube. We show the maximal number of mutually non-attacking rooks placed on the surface of a cube of side length n is $\lfloor 3n/2 \rfloor$ and give some necessary conditions for maximal numbers of rooks to satisfy when placed on a cube. Furthermore, we apply the octahedral group action on a cube to the set of solutions to identify them if they can transfer to one another. We count the number of essentially different solutions by counting equivalence classes induced from the action. We report the numbers of solutions of the n-queen problem for n ≤ 8 and the n-rook problem for n ≤ 6.