著者

伊藤 大雄 藤井 愼二 上原 秀幸 横山 光雄

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.99, no.194, pp.17-24, 1999-07-21

参考文献数

17

被引用文献数

4

---

詰め将棋の盤面をn×nにし、王将以外の駒を0(n)個の用意した、一般化詰め将棋問題の計算複雑さについて論じる。詰め将棋には見た目や詰め方などに面白みを出すため、駒の初期配置に工夫をしたり、正解の詰め手順に美しい趣向が隠されている様な、趣向詰めというものがある。本稿では、飛車と角を使用しない「小駒図式」、初期配置に成り駒が無い「成り駒無し」、王将が初期配置で居た場所に戻って詰む「還元玉」、王将が中央のマスで詰む「都詰め」の4つの趣向を同時に満たすものに限定しても一般化詰め将棋問題がNP困難であることを証明する。

著者

横田 雅也 築地 立家 藤井 愼二 伊藤 大雄

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

電子情報通信学会論文誌 D (ISSN:09151915)

巻号頁・発行日

vol.J84-D1, no.1, pp.58-61, 2001-01-01

---

縦横 N ますに王将を除く各駒が O(N) 枚ずつ配置されている盤面が与えられたとき,詰み手順があるかどうかを判定する問題を一般化詰め将棋問題と呼ぶ.伊藤らはその計算複雑さがNP困難であることを証明した.本論文では盤面とともに手数の上限を単進数で与えたときの一般化詰め将棋問題がPSPACE完全であることを証明する.

著者

横田 雅也 築地 立家 藤井 愼二 伊藤 大雄

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-情報処理 (ISSN:09151915)

巻号頁・発行日

vol.84, no.1, pp.58-61, 2001-01-01

被引用文献数

1

---

縦横Nますに王将を除く各駒がO(N)枚ずつ配置されている盤面が与えられたとき, 詰み手順があるかどうかを判定する問題を一般化つめ将棋問題と呼ぶ.伊藤らはその計算複雑さがNP困難であることを証明した.本論文では盤面とともに手数の上限を単進数で与えたときの一般化詰め将棋問題がPSPACE完全であることを証明する.