文献

J-GLOBAL ID：201202261482556499   整理番号：12A0937479

立方体上のn-クイーン問題とn-ルーク問題

n-Queens and n-Rooks Problem on Cubes

著者 (2件)： 藤原美早紀 (秋田大) ,  山村明弘 (秋田大)
資料名： 情報処理学会論文誌ジャーナル(CD-ROM)  (情報処理学会論文誌 論文誌ジャーナル(CD-ROM))
巻： 53  号： 6  ページ： 1592-1601  発行年： 2012年06月15日 
JST資料番号： Z0778B  ISSN： 1882-7837  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 2次元チェス盤上のエイトクイーンパズルを立方体表面上に拡張して構成されるn-クイーン問題およびn-ルーク問題について考察する。2次元チェス盤上のn-ルーク問題の解は自明であるが,立方体表面の6つの面にn×nのチェス盤を置いて構成した立体的なゲーム盤上のn-クイーン問題およびn-ルーク問題の解の個数や特徴は明らかではない。本論文では,1辺がnの立方体表面上で互いに攻撃しないルークの最大個数は[3n/2]であることを証明し,互いに攻撃しない最大個数のルークが立方体表面上に配置されるときに満たさなければならない必要条件を示す。さらに立方体を自分自身に重ね合わせる変換で移り合うn-クイーン問題およびn-ルーク問題の解を同一視するため,正8面体群の立方体への作用からn-クイーン問題およびn-ルーク問題の解の集合への作用を導入し,その作用に関する同値類の個数を求めることで本質的に異なる解の個数を計算する。n-クイーン問題(n≦8)およびn-ルーク問題(n≦6)の本質的に異なる解の個数を報告する。(著者抄録)

シソーラス用語： *ゲーム ,  多面体 ,  *定理証明 ,  必要条件 ,  重合せ ,  同値関係 ,  ゲーム理論 ,  配置問題 ,  数学的性質 ,  問題
準シソーラス用語： *n-クイーン問題 ,  *n-ルーク問題 ,  *チェス ,  同値類 ,  立方体

分類 (2件)： ゲーム理論  (KA03060T) ,  計算理論  (JB02000A)

引用文献 (9件)：

• [1] Rivin, I., Vardi, I. and Zimmerman, P.: The n-Queens Problem, The American Mathematical Monthly, Vol.101, No.7, pp.629-639 (1994).
• [2] Hsiang, J., Hsu, D. and Shieh, Y.-P.: On the Hardness of Counting Problems of Complete Mappings, Discrete Mathematics, Vol.277, pp.87-100 (2004).
• [3] Sloane, N.: The On-Line Encyclopedia of Integer Sequences, available from (http://oeis.org) (accessed 2011-08-30).
• [4] Pólya, G.: Uber die "doppelt-periodischen" Losungen des n-Damen-Problems, MIT Press, Cambridge, London, Rota, G.-C. edition (1984).
• [5] Barr, J. and Rao, S.: The n-Queens Problem in Higher Dimensions, Elemente der Mathematik, Vol.61, No.4, pp.133-137 (2007).

タイトルに関連する用語 (1件)： 立方体