1 ひとりにしてくれ数 東北大学　大学院情報科学研究科 ◎鈴木 顕　内澤 啓 国立情報学研究所　情報学プリンシプル研究系 宇野 毅明.

Presentation on theme: "1 ひとりにしてくれ数 東北大学　大学院情報科学研究科 ◎鈴木 顕　内澤 啓 国立情報学研究所　情報学プリンシプル研究系 宇野 毅明."— Presentation transcript:

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号 ひとりにしてくれ１

4 ひとりにしてくれのルール 問題 解答 1 3 2 4 1 3 2 4 1 3 2 4 次の３つのルールを満たすように
盤面に並んでいる数字のうち，いくつかを黒く塗る． (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 次の３つのルールを満たすように
5 次の３つのルールを満たすように 盤面に並んでいる数字のうち，いくつかを黒く塗る． (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 次の３つのルールを満たすように
6 次の３つのルールを満たすように 盤面に並んでいる数字のうち，いくつかを黒く塗る． (1) 同じ行，列に同じ数字が重複しない． (2) 黒マスはタテヨコに連続しない． (3) 白マスは黒マスに分断されない． 問題 解答 1 3 2 4 1 3 2 4 1 3 2 4

7 ひとりにしてくれのルール 問題 解答 1 3 2 4 1 3 2 4 次の３つのルールを満たすように
7 次の３つのルールを満たすように 盤面に並んでいる数字のうち，いくつかを黒く塗る． (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が大きくても差は２以下 n×nのひとりにしてくれの，ひとりにしてくれ数 下界 上界 n=100 67 69
31 n×nのひとりにしてくれの，ひとりにしてくれ数 下界 上界 どんなにnが大きくても差は２以下 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が大きくても差は２以下 n×nのひとりにしてくれの，ひとりにしてくれ数 下界 上界 n=100 67 69
33 n×nのひとりにしてくれの，ひとりにしてくれ数 下界 上界 どんなにnが大きくても差は２以下 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 逆ひとりにしてくれ数の上界 唯一の解である塗りわけの２つの性質を利用 (1) 問題で使用される数字の種類は 高々白マスの個数である．
各数字が1つずつ白マスのときに一致 (2) 3×3の白マスの塊は存在しない．

39 いまのところの結果 n×nのひとりにしてくれの，逆ひとりにしてくれ数 下界 上界 n=100 7500 8976 n=3000
39 n×nのひとりにしてくれの，逆ひとりにしてくれ数 下界 上界 n=100 7500 8976 n=3000