数独パズルの難易度判定 ~解法ロジックを用いた数値化の提案~

Slides:



Advertisements
Similar presentations
SQL による数独の解法 青山学院大学理工学部 矢吹太朗・佐久田博司. 数独とは何か ナンプレとも呼ばれ る制約充足問題 各行・列・ブロック に 1 から 9 の数字を一 つずつ当てはめる 新聞等に載っている ものはとても簡単 人間には難しいもの → もある.
Advertisements

シーケンス図の生成のための実行履歴圧縮手法
3次元nクイーン問題の 解に関する研究 論理工学研究室 伊藤精一
CPUとGPUの 性能比較 -行列計算およびN体問題を用いて-
数当てゲーム (「誤り訂正符号」に関連した話題)
XHTML構文検証手法における スクリプト要素の静的解析アルゴリズム
インターネットを利用して パズルを楽しむ シニアSOHO横浜・神奈川主催 第39回 シニア情報生活アドバイザー養成講座 平成23年5月27日 田中 稔 受講生 田中 稔です。 「インターネットを利用してパズルを楽しむ」ことについて、私自身が楽しんでいることについて、紹介します。 1.
国内線で新千歳空港を利用している航空会社はどこですか?
JavaによるCAI学習ソフトウェアの開発
研究集会 「超大規模行列の数理的諸問題とその高速解法」 2007 年 3 月 7 日 完全パイプライン化シフト QR 法による 実対称三重対角行列の 固有値並列計算 宮田 考史  山本 有作  張 紹良   名古屋大学 大学院工学研究科 計算理工学専攻.
Finger patternのブロック化による 陰的wavelet近似逆行列前処理の 高速化
ファーストイヤー・セミナーⅡ 第8回 データの入力.
経営情報 #1 デジタル表現 / 2003 (春) 安田豊 1.
整数計画法を用いた スリザーリンクの解法 杉村 由花 (東京大学)
リバーシの並列化 並列化するときに起こる問題を定義しろ おぷてぃまいざー SSAIとMSAIは比較しろ  前田昂寛.
プログラミング論 I 関数の再帰呼び出し
LCAを用いたパレット運用における総合的な環境影響に関する研究
15パズルの解法について 北海道情報大学 情報メディア学部 情報メディア学科 新井山ゼミ  大石 貴弘.
4.2 連立非線形方程式 (1)繰返し法による方法
2進数・16進数.
アルゴリズムとデータ構造 補足資料10-2 「nクイーン」
モンテカルロ碁 電気通信大学 村松研究室 下川和也.
JAVAでつくるオセロ 伊東飛鳥、宮島雄一 長畑弘樹、ソギ原直人.
アスペクト指向プログラミングを用いたIDSオフロード
川口真司 松下誠 井上克郎 大阪大学大学院情報科学研究科
~オセロゲーム~ アルゴリズムとそのプログラム
プログラム実行履歴を用いたトランザクションファンクション抽出手法
プログラム実行時情報を用いたトランザクションファンクション抽出手法
MPIを用いた並列処理 ~GAによるTSPの解法~
思考支援ツールを用いた 情報処理技術知識の学習方式
定兼邦彦 今井浩 東京大学理学系研究科 情報科学専攻
動的依存グラフの3-gramを用いた 実行トレースの比較手法
東京医科歯科大学 歯科器材・薬品開発センター シンポジウム
プログラミング2 関数の再帰呼び出し
BLACK JACKの作成 ブラックジャックのルール 概要 勝敗の判定 開発中の問題点 Aの扱いについて 配り直し(DEAL) 工夫した点
実践プログラミング入門2 配列を使ってゲームを作ろう 徳山 豪 東北大学情報科学研究科 システム情報科学専攻 情報システム評価学分野.
出発点となる2つの問い 概念化 1つめの問い 「(自立生活)能力の有無」を軸にして、なぜ位相の異なるQOL観が並列的に位置できているか(例えば「寝たきり老人」「認知症高齢者」における違い) 2つめの問い 昨今、「QOL」が数値化されているが、そもそも主観を尺度化できるのか 尺度化.
変換されても変換されない頑固ベクトル どうしたら頑固になれるか 頑固なベクトルは何に使える?
数独の解生成と 解に対する番号付け 理学部 情報科学科 渡辺研究室 戸神星也.
プログラミングコンテストシステムへの 提出履歴データとその分析
バイトコードを単位とするJavaスライスシステムの試作
モンテカルロ法を用いた 立体四目並べの対戦プログラム
院内の回復期リハ病棟間の成果比較  -予後因子(入院時年齢・FIM・発症後日数)の階層化による測定法を用いて-
2011年度 情報科学&情報科学演習 ~ 定番プログラム(2) ~.
アルゴリズムとデータ構造1 2006年7月11日
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
表計算 Excel 演習 1.Excel を使ってみる.
Problem L: シャノワール 問題作成: 高橋 解法作成: 安達・高橋・前原 解説: 安達.
文法と言語 ー文脈自由文法とLR構文解析ー
構造的類似性を持つ半構造化文書における頻度分析
Flashを用いたゲーム制作 05A1304 鈴木 浩高.
「マイグレーションを支援する分散集合オブジェクト」
アスペクト指向言語のための視点に応じた編集を可能にするツール
データマイニングアルゴリズム「アプリオリ」と「ID3」の比較
大阪工業大学 情報科学部 情報科学科 学生番号 A 苧谷 真行
Jh NAHI 横田 理央 (東京工業大学) Hierarchical low-rank approximation methods on distributed memory and GPUs 背景  H行列、H2行列、HSS行列などの階層的低ランク近似法はO(N2)の要素を持つ密行列をO(N)の要素を持つ行列に圧縮することができる。圧縮された行列を用いることで、行列積、LU分解、固有値計算をO(Nlog2N)で行うことができるため、従来密行列の解法が用いられてきた分野では階層的低ランク近似
第2章 統計データの記述 データについての理解 度数分布表の作成.
分枝カット法に基づいた線形符号の復号法に関する一考察
Othello G班         山崎 木下 山本 上手      .
原口和也 高橋隆一 丸岡章 石巻専修大学 理工学部 情報電子工学科
プログラミング2 関数の再帰呼び出し
周辺環境スカウター 防災 減災 少子 高齢 産業 創出 周辺環境スカウター 誕生の キッカケ 周辺環境スカウター でこう 変わった!
一問一答式クイズAQuAsにおける学習支援の方法
ピクロスのプログラミング 発表者 07A1075 八尋貴文.
インセンティブにより自律ユーザに 高品質なオーバーレイマルチキャスト木を 構築させるプロトコルの提案
各種荷重を受ける 中空押出形成材の構造最適化
1 ひとりにしてくれ数 東北大学 大学院情報科学研究科 ◎鈴木 顕 内澤 啓 国立情報学研究所 情報学プリンシプル研究系 宇野 毅明.
プログラミング論 バイナリーサーチ 1.
ペンシルパズルの大道芸ステージショーへの応用
ペンシルパズル「一本線」のヒント数の扱いに関する解析
Presentation transcript:

数独パズルの難易度判定 ~解法ロジックを用いた数値化の提案~ 大阪工業大学 情報科学部コンピュータ科学科 土出 智也

目的 近年日本では脳トレやパズルが人気 中でも数独はその手軽さから注目されている 難易度は「★」、「Hard」など大雑把なものが多い そこで解法によって難易度を数値化する →実際に解くことによって、より詳しく数値化できる

数独とは? ルール 1.ヨコ列のどの列にも1~9の数字が1つずつ入る 2.タテ列のどの列にも1~9の数字が1つずつ入る 3.太線で囲まれた3×3のどのブロックにも1~9の数字が1つずつ入る

難易度判定の現状 解法ではなく既存の情報から難易度を判定 →空きマスが多いほど難しい? →候補数が多いほど難しい? 公称難易度と空きマス数の関係 →空きマスが多いほど難しい? 公称難易度と候補数の関係 →候補数が多いほど難しい? 空きマス数:数字を埋める場所(白マス)の合計値のこと 候補数:各マスに入る可能性のある数字(候補)の数のこと

公称難易度と空きマス数の関係 難易度が高いほど、空きマス数のピークが右側にある

公称難易度と候補数の関係 Zhe Chenの数独エントロピー 難易度の高いものほど、数独エントロピーは高くなっている 表2 世界基準ナンプレでの数独エントロピー(600問) 難易度の高いものほど、数独エントロピーは高くなっている

問題点 以上の2つは、どちらも解く以前の盤面の状態から難易度を示している 計算は簡単であるが、解いてみないとわからない部分の数値化には至っていない 本研究では実際に数独を解くことで、数字の埋まりやすさや思考の難しさを難易度の指標に取り込む

使用する解法 雑誌・書籍に記載されているものをベースに、独自に7つに分類した 解法は使用順にCRBE法(column,row,block,elimination)、単一候補法、単一マス法、双子法、共有候補法、三つ子法、対角線法とした

CRBE法とは? 右上ブロックで8がどこに入るかを考える 1行目と2行目には既に8がある →一箇所に決定する

数値化の方法 数値化は、問題を解く際の時間を用いる “時間”はそれぞれの解法の中でのループや探索の回数を用いる (例えば「1が埋まる場所を探す→6が埋まる場所を探す→ 4が埋まる場所を探す」なら、時間は3) このようにすることで、一度に埋まる数字が少ないような難解な問題ほど数値が大きくなる 算出した数値を“スコア”と呼ぶ

結果:スコアと空きマス数 同じような空きマス数でも、スコアを用いると難易度に違いがでる

結果:スコアと数独エントロピー 数独エントロピーが同じような値でも、スコアを用いると難易度に違いがでる

まとめ 解法を元に難易度を数値化した 解法の実行時間を元に数値化したので、空きマス数や候補数より詳細に難易度を知ることができた 同じ解法の中でもばらつきがあるため、比較ができるようになった このスコア計算法を元に、ソフトウエアを制作:『SudokuAnalyzer』