Download presentation
Presentation is loading. Please wait.
Published byNuray Çağlar Modified 約 5 年前
1
1 ひとりにしてくれ数 東北大学 大学院情報科学研究科 ◎鈴木 顕 内澤 啓 国立情報学研究所 情報学プリンシプル研究系 宇野 毅明
2
ひとりにしてくれ 1990年,パズル通信ニコリ29号で発表される. 不人気(難しすぎる,解いていて面白くない.) 1998年頃,人気上昇.
4 6 7 1 8 9 5 3 4 7 8 5 3 1 2 9 6 数独(ニコリ・ 1984年) ニコリ10号 ニコリ133号
3
ひとりにしてくれ 1990年,パズル通信ニコリ29号で発表される. 不人気(難しすぎる,解いていて面白くない.) 1998年頃,人気上昇.
3 1990年,パズル通信ニコリ29号で発表される. 不人気(難しすぎる,解いていて面白くない.) 1998年頃,人気上昇. 1999年,1冊全部ひとりにしてくれの本が発行される. ニコリ10号 ニコリ133号 ひとりにしてくれ1
4
ひとりにしてくれのルール 問題 解答 1 3 2 4 1 3 2 4 1 3 2 4 次の3つのルールを満たすように
盤面に並んでいる数字のうち,いくつかを黒く塗る. (1) 同じ行,列に同じ数字が重複しない. (2) 黒マスはタテヨコに連続しない. (3) 白マスは黒マスに分断されない. 問題 解答 1 3 2 4 1 3 2 4 1 3 2 4
5
ひとりにしてくれのルール 問題 解答 1 3 2 4 1 3 2 4 1 3 2 4 次の3つのルールを満たすように
5 次の3つのルールを満たすように 盤面に並んでいる数字のうち,いくつかを黒く塗る. (1) 同じ行,列に同じ数字が重複しない. (2) 黒マスはタテヨコに連続しない. (3) 白マスは黒マスに分断されない. 問題 解答 1 3 2 4 1 3 2 4 1 3 2 4
6
ひとりにしてくれのルール 問題 解答 1 3 2 4 1 3 2 4 1 3 2 4 次の3つのルールを満たすように
6 次の3つのルールを満たすように 盤面に並んでいる数字のうち,いくつかを黒く塗る. (1) 同じ行,列に同じ数字が重複しない. (2) 黒マスはタテヨコに連続しない. (3) 白マスは黒マスに分断されない. 問題 解答 1 3 2 4 1 3 2 4 1 3 2 4
7
ひとりにしてくれのルール 問題 解答 1 3 2 4 1 3 2 4 次の3つのルールを満たすように
7 次の3つのルールを満たすように 盤面に並んでいる数字のうち,いくつかを黒く塗る. (1) 同じ行,列に同じ数字が重複しない. (2) 黒マスはタテヨコに連続しない. (3) 白マスは黒マスに分断されない. 問題 解答 1 3 2 4 1 3 2 4
8
ひとりにしてくれの例題 8 問題 1 3 2 4
9
ひとりにしてくれの例題 9 1 3 2 4 問題 1 3 2 4 1 3 2 4 1 3 2 4
10
ひとりにしてくれの例題 10 問題 1 3 2 4 1 3 2 4 1 3 2 4
11
ひとりにしてくれの例題 11 問題 1 3 2 4 1 3 2 4 1 3 2 4
12
ひとりにしてくれの例題 問題 解答 1 3 2 4 2 4 3 1 (1) 同じ行,列に同じ数字が重複しない. (2)
12 問題 解答 1 3 2 4 2 4 3 1 (1) 同じ行,列に同じ数字が重複しない. (2) 黒マスはタテヨコに連続しない. (3) 白マスは黒マスに分断されない.
13
ひとりにしてくれの難しさ 13 n×nのひとりにしてくれの問題が与えられたときに, 解があるかどうか判定するのはNP完全[HD09]. n
14
ひとりにしてくれ数 1 3 2 4 今回私たちはひとりにしてくれ数を提案した ひとりにしてくれの問題で使われる 数字の種類数に深く関係する数
4種類
15
問題に使う数字の種類 4種類 5種類 8種類 3種類 1種類 2種類 12種類 16種類 1 3 2 4 1 3 2 5 4 1 2 3 4
15 1 3 2 4 1 3 2 5 4 1 2 3 4 5 6 8 7 3 1 2 4種類 5種類 8種類 3種類 1 1 2 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1種類 2種類 12種類 16種類
16
問題に使う数字の種類 唯一の解 唯一の解 唯一の解 唯一の解 4種類 5種類 8種類 3種類 解がない 解がない 唯一の解 複数の解 1種類
16 唯一の解 唯一の解 唯一の解 唯一の解 1 3 2 4 1 3 2 5 4 1 2 3 4 5 6 8 7 3 1 2 4種類 5種類 8種類 3種類 解がない 解がない 唯一の解 複数の解 1 1 2 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1種類 2種類 12種類 16種類
17
問題に使う数字の種類 17 4×4のひとりにしてくれ
18
問題に使う数字の種類 4×4のひとりにしてくれ 1種類 2種類 3種類 4種類 5種類 6種類 7種類 8種類 9種類 10種類 11種類
18 4×4のひとりにしてくれ 1 1 2 3 1 2 1 3 2 4 1 3 2 5 4 3 4 2 5 1 6 1種類 2種類 3種類 4種類 1種類 2種類 3種類 4種類 5種類 6種類 5種類 6種類 7種類 4 1 2 7 3 5 6 1 2 3 4 5 6 8 7 6 5 9 3 1 7 4 2 8 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 12 8種類 9種類 10種類 11種類 7種類 8種類 9種類 10種類 11種類 12種類 12種類 13種類 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 14種類 15種類 16種類 13種類 14種類 15種類 16種類
19
問題に使う数字の種類 4×4のひとりにしてくれ 解がない 1種類 1種類 ・・・ 2種類 3種類 4種類 1 5種類 6種類 7種類 8種類
19 4×4のひとりにしてくれ 1種類 ・・・ 2種類 解がない 3種類 4種類 1 5種類 6種類 7種類 8種類 9種類 10種類 11種類 1種類 12種類 13種類 14種類 15種類 16種類
20
問題に使う数字の種類 4×4のひとりにしてくれ 解がない 2種類 1種類 ・・・ 2種類 ・・・ 3種類 4種類 1 2 1 2 1 2 1
20 4×4のひとりにしてくれ 1種類 ・・・ 2種類 ・・・ 解がない 3種類 4種類 1 2 1 2 1 2 1 2 5種類 6種類 7種類 8種類 9種類 10種類 11種類 2種類 12種類 13種類 14種類 15種類 16種類
21
問題に使う数字の種類 解がない 複数の解 4×4のひとりにしてくれ 唯一の解 唯一の解 3種類 唯一の解 3種類 3種類 4種類 5種類 1
21 解がない 複数の解 4×4のひとりにしてくれ 1 2 3 2 1 3 1種類 ・・・ 2種類 ・・・ 3種類 ・・・ 4種類 ・・・ 5種類 ・・・ 6種類 唯一の解 唯一の解 3種類 唯一の解 3種類 7種類 8種類 9種類 3 1 2 1 3 2 4 1 3 2 5 4 10種類 11種類 12種類 13種類 14種類 15種類 16種類 3種類 4種類 5種類
22
問題に使う数字の種類 唯一の解 唯一の解 4×4のひとりにしてくれ 唯一の解 6種類 唯一の解 7種類 8種類 9種類 3 4 2 5 1
22 唯一の解 唯一の解 4×4のひとりにしてくれ 3 4 2 5 1 6 4 1 2 7 3 5 6 1種類 ・・・ 2種類 ・・・ 3種類 ・・・ 4種類 ・・・ 5種類 ・・・ 6種類 ・・・ 唯一の解 6種類 唯一の解 7種類 7種類 ・・・ 8種類 ・・・ 9種類 ・・・ 1 2 3 4 5 6 8 7 6 5 9 3 1 7 4 2 8 10種類 11種類 12種類 13種類 14種類 15種類 16種類 8種類 9種類
23
問題に使う数字の種類 唯一の解 唯一の解 4×4のひとりにしてくれ 唯一の解 10種類 11種類 12種類 1 2 3 4 5 6 7 8
23 唯一の解 唯一の解 4×4のひとりにしてくれ 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 11 1種類 ・・・ 2種類 ・・・ 3種類 ・・・ 4種類 ・・・ 5種類 ・・・ 6種類 ・・・ 唯一の解 10種類 11種類 7種類 ・・・ 8種類 ・・・ 9種類 ・・・ 1 2 3 4 5 6 7 8 9 10 11 12 10種類 ・・・ 11種類 ・・・ 12種類 ・・・ 13種類 14種類 15種類 16種類 12種類
24
問題に使う数字の種類 複数の解 4×4のひとりにしてくれ 13種類 13種類 13種類 13 12 11 10 9 8 7 5 6 4 3
24 複数の解 4×4のひとりにしてくれ 13 12 11 10 9 8 7 5 6 4 3 2 1 13種類 13 12 11 10 9 8 7 5 6 4 3 2 1 13種類 13 12 11 10 9 8 7 5 6 4 3 2 1 13種類 1種類 ・・・ 2種類 ・・・ 3種類 ・・・ 4種類 ・・・ 5種類 ・・・ 6種類 ・・・ 7種類 ・・・ 8種類 ・・・ 9種類 ・・・ 10種類 ・・・ 11種類 ・・・ 12種類 ・・・ 13種類 ・・・ 14種類 15種類 16種類
25
問題に使う数字の種類 複数の解 複数の解 4×4のひとりにしてくれ 13種類 複数の解 複数の解 14種類 15種類 16種類 13 12
25 複数の解 複数の解 4×4のひとりにしてくれ 13 12 11 10 9 8 7 5 6 4 3 2 1 13種類 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1種類 ・・・ 2種類 ・・・ 3種類 ・・・ 4種類 ・・・ 5種類 ・・・ 6種類 ・・・ 複数の解 複数の解 14種類 7種類 ・・・ 8種類 ・・・ 9種類 ・・・ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 10種類 ・・・ 11種類 ・・・ 12種類 ・・・ 13種類 ・・・ 14種類 ・・・ 15種類 ・・・ 16種類 ・・・ 15種類 16種類
26
問題に使う数字の種類 4×4のひとりにしてくれ 唯一の解が存在する問題を作れる. 1種類 ・・・ 2種類 ・・・ 3種類 4種類 5種類
26 4×4のひとりにしてくれ 1種類 ・・・ 2種類 ・・・ 3種類 4種類 5種類 6種類 7種類 8種類 9種類 10種類 11種類 12種類 ・・・ 3種類 ・・・ 4種類 5種類 6種類 7種類 8種類 9種類 10種類 11種類 12種類 ・・・ 唯一の解が存在する問題を作れる. 13種類 ・・・ 14種類 ・・・ 15種類 ・・・ 16種類 ・・・
27
問題に使う数字の種類 12×12のひとりにしてくれ 9種類 108種類 1 2 3 4 5 6 7 8 9 4 5 23 6 7 8 9
24 25 22 10 26 27 15 28 29 1 30 31 32 33 34 35 36 37 2 38 39 40 41 42 43 44 45 46 47 3 48 49 13 50 51 18 52 53 54 55 11 56 57 16 58 59 20 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 14 80 81 19 82 83 84 85 12 86 87 17 88 89 21 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 9種類 108種類
28
問題に使う数字の種類 唯一の解 唯一の解 12×12のひとりにしてくれ 9種類 108種類 どちらもユニークな解を持つ! 1 2 3 4 5
6 7 8 9 4 5 23 6 7 8 9 24 25 22 10 26 27 15 28 29 1 30 31 32 33 34 35 36 37 2 38 39 40 41 42 43 44 45 46 47 3 48 49 13 50 51 18 52 53 54 55 11 56 57 16 58 59 20 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 14 80 81 19 82 83 84 85 12 86 87 17 88 89 21 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 9種類 108種類 どちらもユニークな解を持つ!
29
ひとりにしてくれ数 定義: 唯一の解が存在するn×nのひとりにしてくれの 問題を作るのに,必要な数字の種類の数. 4×4のひとりにしてくれ
29 定義: 唯一の解が存在するn×nのひとりにしてくれの 問題を作るのに,必要な数字の種類の数. 1種類 2種類 3種類 4種類 5種類 6種類 7種類 8種類 9種類 10種類 11種類 12種類 13種類 14種類 15種類 16種類 4×4のひとりにしてくれ ・・・ ←4×4のとき最小値は 3 唯一の解が存在する問題を作れる. 4×4のひとりにしてくれの, ひとりにしてくれ数は 3. n×nのひとりにしてくれの, ひとりにしてくれ数は?
30
本研究の結果 n×nのひとりにしてくれの,ひとりにしてくれ数 下界 上界 これより少ない種類で 唯一の解をもつ問題を作れない
30 n×nのひとりにしてくれの,ひとりにしてくれ数 下界 上界 これより少ない種類で 唯一の解をもつ問題を作れない これだけの種類使えば 唯一の解をもつ問題を作れる
31
本研究の結果 どんなにnが大きくても差は2以下 n×nのひとりにしてくれの,ひとりにしてくれ数 下界 上界 n=100 67 69
31 n×nのひとりにしてくれの,ひとりにしてくれ数 下界 上界 どんなにnが大きくても差は2以下 n=100 67 69 n=30000 20000 20001
32
ひとりにしてくれ数の上界 実際に問題を構成することで証明 使う数字の種類のなるべく少ない問題 唯一の解 1 2 3 4 5 6 7 1 2
32 実際に問題を構成することで証明 使う数字の種類のなるべく少ない問題 唯一の解 1 2 3 4 5 6 7 1 2 3 4 5 6 7
33
本研究の結果 どんなにnが大きくても差は2以下 n×nのひとりにしてくれの,ひとりにしてくれ数 下界 上界 n=100 67 69
33 n×nのひとりにしてくれの,ひとりにしてくれ数 下界 上界 どんなにnが大きくても差は2以下 n=100 67 69 n=30000 20000 20001
34
ひとりにしてくれ数 定義: 唯一の解が存在するn×nのひとりにしてくれの 問題を作るのに,必要な数字の種類の数. 4×4のひとりにしてくれ
34 定義: 唯一の解が存在するn×nのひとりにしてくれの 問題を作るのに,必要な数字の種類の数. 1種類 2種類 3種類 4種類 5種類 6種類 7種類 8種類 9種類 10種類 11種類 12種類 13種類 14種類 15種類 16種類 4×4のひとりにしてくれ ・・・ ←最小値 唯一の解が存在する問題を作れる. ←最大値
35
逆ひとりにしてくれ数 定義: 唯一の解が存在するn×nのひとりにしてくれの 問題を作れる,最も多い数字の種類の数. 4×4のひとりにしてくれ
35 定義: 唯一の解が存在するn×nのひとりにしてくれの 問題を作れる,最も多い数字の種類の数. 1種類 2種類 3種類 4種類 5種類 6種類 7種類 8種類 9種類 10種類 11種類 12種類 13種類 14種類 15種類 16種類 4×4のひとりにしてくれ ・・・ ←最小値 唯一の解が存在する問題を作れる. 4×4のひとりにしてくれの, 逆ひとりにしてくれ数は 12. ←最大値 n×nのひとりにしてくれの, 逆ひとりにしてくれ数は?
36
いまのところの結果 n×nのひとりにしてくれの,逆ひとりにしてくれ数 下界 上界 n=100 7500 8976 n=3000
36 n×nのひとりにしてくれの,逆ひとりにしてくれ数 下界 上界 n=100 7500 8976 n=3000
37
逆ひとりにしてくれ数の下界 実際に問題を構成することで証明 唯一の解 使う数字の種類の なるべく少ない問題 108種類 4 5 23 6 7
9 24 25 22 10 26 27 15 28 29 1 30 31 32 33 34 35 36 37 2 38 39 40 41 42 43 44 45 46 47 3 48 49 13 50 51 18 52 53 54 55 11 56 57 16 58 59 20 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 14 80 81 19 82 83 84 85 12 86 87 17 88 89 21 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 使う数字の種類の なるべく少ない問題 108種類
38
逆ひとりにしてくれ数の上界 唯一の解である塗りわけの2つの性質を利用 (1) 問題で使用される数字の種類は 高々白マスの個数である.
各数字が1つずつ白マスのときに一致 (2) 3×3の白マスの塊は存在しない.
39
いまのところの結果 n×nのひとりにしてくれの,逆ひとりにしてくれ数 下界 上界 n=100 7500 8976 n=3000
39 n×nのひとりにしてくれの,逆ひとりにしてくれ数 下界 上界 n=100 7500 8976 n=3000
Similar presentations
© 2024 slidesplayer.net Inc.
All rights reserved.