ペンシルパズル「シャカシャカ」の計算複雑さと整数計画モデル
スポンサーリンク
概要
- 論文の詳細を見る
パズル「シャカシャカ」は,有名な数独をはじめとする多くのペンシルパズルと同様,日本の出版社ニコリが普及させたパズルである.これまで「シャカシャカ」の計算複雑さは未解決であった.本稿ではまず「シャカシャカ」がNP完全であることを示す.次に「シャカシャカ」を整数計画問題として記述する.これを実装し,市販されている本の問題をIPソルバで解いた実験結果を示す.その結果,どの問題も1秒以内に解けた.
- 一般社団法人電子情報通信学会の論文
- 2013-04-17
著者
-
上原 隆平
駒澤大学自然科学教室
-
上原 隆平
北陸先端科学技術大学情報科学研究科
-
岡本 吉央
豊橋技術科学大学情報工学系
-
岡本 吉央
東大総合文化
-
岡本 吉央
ETH Zurich
-
宇野 裕之
大阪府立大学
-
岡本 吉央
電気通信大学
-
ドメイン エリック・D
マサチューセッツ工科大学
関連論文
- 区間二部グラフの効率の良い認識に関する研究 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))
- Bipartite Permutation Graphのランダム生成と列挙
- 弦グラフおよび弦二部グラフのクラスにおけるマッチングの数え上げ
- 再構成問題の計算複雑さ
- フォン・ノイマン (特集 現代数学に影響を与えた数学者)
- あみだくじの高速列挙
- エレガントな解答をもとむ 解答--出題 2009年10月号
- 1-D-5 最小費用全域木ゲームにおけるシャープレイ値計算の困難性(離散アルゴリズム(2))
- 折紙の計算量的複雑さの研究(折紙工学の現状と課題)
- Complexity of pleat folding (理論計算機科学の深化と応用--RIMS研究集会報告集)
- Enumeration of Perfect Sequences of Chordal Graph (Acceleration and Visualization of Computation for Enumeration Problems)
- Polygons Folding to Plural Incongruent Orthogonal Boxes (Acceleration and Visualization of Computation for Enumeration Problems)
- Reconstruction of Connected Interval Graphs (Acceleration and Visualization of Computation for Enumeration Problems)
- 2-E-17 Enumeration of Perfect Sequences of Chordal Graph
- じゃばら折りの複雑さに関する研究
- 2-E-6 無限サーバ待ち行列がつくるスケールフリー区間グラフ : クラスタ係数の評価(待ち行列(2))
- 複数の箱を折ることのできる展開図に関する研究
- 折り紙とコンピュータサイエンス(学生/教養のページ)
- コーダルグラフの完全列の列挙
- 2-B-4 無限サーバ待ち行列がつくるスケールフリー区間グラフ(待ち行列(2))
- 区間表現からMPQ-treeを効率よく構成するアルゴリズム
- 区間表現からMPQ-tree を効率よく構成するアルゴリズム(計算機科学の理論とその応用)
- スケールフリーグラフ上における局所情報を用いたランダムウォークについて
- 2部パーミュテーショングラフのバンド幅
- 航空路線問題に対する効率の良いアルゴリズム
- プトレマイオスグラフのラミナー構造とその応用
- ある限られたグラフクラスに対する最長路問題
- 絵画的迷路の作り方 (理論計算機科学の深化と応用)
- 距離遺伝的グラフの木表現とその応用
- コーダルグラフの独立点集合の数えあげ問題
- Canonical Data Structure for Probe Interval Graphs (Evolutionary Advancement in Fundamental Theories of Computer Science)
- プロープ区間グラフの拡張MPQ木表現
- 2部グラフとProbe区間グラフにおける木スパナー
- 2部グラフの部分クラスに対するGI完全性について
- 重み最大マッチングを求める並列近似アルゴリズム
- グラフの連結成分の個数と応用
- 弦グラフの一般化と、そのグラフ上での問題の難しさ
- ある投票ゲームのシミュレーション
- Ptolemaic Graph 上の最長路問題に関する研究(計算機科学の理論とその応用)
- 飛び出す絵本の複雑さ
- 単純多角形の生成に関する発見的手法(セッション2)
- グラフ上のボロノイゲームとその困難性(セッション1)
- スーパーコンピューティング・コンテスト2010
- ネヴァンリンナ賞業績紹介 スピールマン (特集 国際数学者会議2010)
- 終わりなき旅 (特集 数学者の見た夢)
- 帯状の紙の折りたたみに関する最適化問題
- 正4面体と他の正多面体との共通の辺展開図に関する研究
- 一般化KaboozleのNP完全性
- 折紙における決定不能問題
- 最小費用全域木ゲーム(OR事典Wiki)
- 完全グラフ上の最大辺素パス問題に対する貪欲近似アルゴリズム (最適化の数理とアルゴリズム)
- パス上のボロノイゲーム
- 第4回 離散最適化と協力ゲーム(2)(離散最適化とその応用)
- 双二次最終多項式による有向マトロイドの実現不可能性判定
- Non-LP orientations, non-line shellings, and non-representable oriented matroids
- 「Cellチャレンジ2009」実施報告
- 第56回シンポジウムルポ(情報の窓)
- 固定パラメータ容易性(新・ORの図解,学会創立50周年記念号)
- グラフクラスにおける森の数え上げに対する高速指数時間アルゴリズム(セッション3)
- 離散最適化に対する高速な厳密アルゴリズム(OR研究の最前線)
- Submodularity of some classes of the combinatorial optimization games
- 組合せ最適化理論の三次元描像 (第21回 回路とシステム軽井沢ワークショップ論文集) -- (新世代の計算限界)
- k-木のスケールフリー性に関する研究
- 凸幾何上の協力ゲームにおけるコアの安定性(ゲーム)
- 2-F-5 多目的最適化への列挙アルゴリズム理論からのアプローチ(数理計画(1))
- UNO は一人でも難しい (計算機科学とアルゴリズムの数理的基礎とその応用)
- 正4面体と正6面体との共通の展開図の構成に関する研究
- 間違えても大丈夫な凸包構成アルゴリズム
- 等間隔の折り目を持つ紙の折り畳みの計算量について
- 複数の単位円による点集合の排他的被覆
- Hoffmanパズル解の列挙と一般化に関する研究
- 複数の直方体を折れる共通の展開図に関する研究
- グラフクラスとアルゴリズム
- レベル付き木の描画における頂点角解像度と交差角解像度
- 複数の直方体を折れる共通の展開図に関する研究
- Rational Secret Sharing for Non-Simultaneous Channels (情報理論)
- ゲーム・パズルの計算量を示すための新しい枠組みについて(パズルとゲームの計算理論)
- On the base-line location problem for the maximum weight region decomposable into base-monotone shapes (New Trends in Algorithms and Theory of Computation)
- 1.列挙の基本と基礎的なアルゴリズム(広がる列挙の技術-列挙による問題解決アプローチ-)
- 非協力ゲーム(基礎編)
- 『計算機科学者のためのゲーム理論入門』シリーズについて
- 施設配置ゲームにおける仁・シャープレイ値の計算について (Theoretical Foundations of Computing)
- 大学院における研究室教育の構造化へ向けて (II. 活動報告 . (2) 質保証枠組みの方策)
- 非協力ゲーム(発展編)
- JAIST創立20周年記念シンポジウム報告 (III. センター関連イベント報告 . (1) JAIST創立20周年記念シンポジウム)
- 4つの教育ポリシー&ガイドラインを基盤としたJAISTにおける国際的質保証に向けた提案 (II. 活動報告 . (2) 質保証枠組みの方策)
- メカニズムデザイン(基礎編)
- 費用2種類の施設配置ゲームの仁とシャープレイ値の計算について
- 基単調図形に分割可能な最大重み領域を得る基線の配置問題
- 非同時通信路における合理的秘密分散(情報セキュリティ)
- ある投票ゲームのシミュレーション
- 単位正方形上の一意被覆問題に対する近似アルゴリズム
- グラフを通したパズル・ゲームの一般化(娯楽のOR)
- 不完全データと矛盾しない有向二値完全系統樹を列挙する効率的手法
- トロミノ詰込問題の計算複雑さについて
- キャタピラグラフの独立点集合遷移問題に対する多項式時間アルゴリズム
- DS-1-11 Free Flood Filling Gameの計算複雑性について(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- ペンシルパズル「シャカシャカ」の計算複雑さと整数計画モデル
- 基単調図形に分割可能な最大重み領域を得る基線の配置問題