パズルで活躍する２進数

１．２進数とは何ぞや？

　数値を表現する時、我々は０〜９の10個の数字を使いますよね。
　いわゆる「10進数」というヤツです。
　そして、10進数による数値表現方法を「10進法」と呼びます。

　もちろん、10進数以外にも数値表記はあります。
　時計は60進数、コンピュータは２進数や16進数、etc...
　このページでは、２進数にスポットを当てて話をしていきます。

　まずは、「２進数とは何か？」を説明しましょう。
　既にご存じの方々は、次セクションに進んじゃってください😊

　２進法とは、\(0\) と \(1\) の２個の数字を使った数値表現方法です。
　そして、２進法で表現された数のことを２進数と言います。
　10進法だと \(9\) の次は繰り上がって \(10\) になりますが、２進法だと \(1\) の次は繰り上がって \(10\) になります。
　だから、２進数を \(0\) から順に書くと下記のようになるわけですね。

　２進数を \(0\) から書くと……
　\(0,\ 1,\ 10,\ 11,\ 100,\ 101,\ 110,\ 111,\ 1000,\ 1001,\ \cdots\) となる。

　10進数の「\(10\)」と２進数の「\(10\)」は異なることに注意しましょう。
　混同を避けるために、２進数の方は \(10_{(2)}\) といった表記をすることがあります。
　また、２進数の「\(10\)」をジュウとは読まない方が良いでしょう。
　イチゼロなどと読む方が誤解を減らせるかもしれませんね。

　10進数の構造について、皆さんは小学校で学んだことと思います。
　いわゆる「\(100\) を○個、\(10\) を○個、\(1\) を○個合わせた数」というヤツですね（○に入るのは０〜９のどれか）。
　10のべき乗の集まりという捉え方で数を理解していったことでしょう。

　実は、２進数も構造は同じです。
　２のべき乗の集まりと捉えるんです。
　「\(8\) を○個、\(4\) を○個、\(2\) を○個、\(1\) を○個合わせた数」といった感じで（○に入るのは０と１のどちらか）。
　例えば、２進数 \(11001\) はこう捉えます。

　２進数 \(11001\) は \(2^4\) を１個、\(2^3\) を１個、\(2^2\) を０個、\(2^1\) を０個、１を１個合わせた数である。
　\(11001_{(2)} = 2^4\cdot1 + 2^3\cdot1 + 2^2\cdot0 + 2^1\cdot0 + 1\cdot1\)

　さて。
　上記の足し算式は普通に計算できますよね。
　ちょいと計算してみましょうか。

\begin{align} 11001_{(2)} &= 2^4\cdot1 + 2^3\cdot1 + 2^2\cdot0 + 2^1\cdot0 + 1\cdot1 \\ &= 16+8+1 = 25 \end{align}

　これは、「２進数の \(11001\) と10進数の \(25\) は同じ数だ」ということを表します。
　この式を見ると、２進数から10進数への変換が可能だということがわかりますね。

　やっぱり、10進数に慣れきった我々にとって２進数をそのまま理解するのは結構大変です。
　２進数⇔10進数の相互変換ができるようになると、２進数を理解しやすくなりますね。
　その変換方法を紹介しましょう。

　【２進数→10進数】の変換は前述した通りです。
　\(1,\ 2,\ 2^2,\ 2^3,\ 2^4,\ 2^5, \cdots\) との積を作って足し算しましょう。
　例えば、２進数の \(1010011\) を10進数に変換するとこうなります。

\begin{align} 1010011_{(2)} &= 2^6\cdot1 + 2^5\cdot0 + 2^4\cdot1 + 2^3\cdot0 + 2^2\cdot0 + 2^1\cdot1 + 1\cdot1 \\ &= 64+16+2+1 = 83 \end{align}

　２進数の \(1010011\) を10進数に変換すると \(83\) になりました。

　次は【10進数→２進数】の変換。
　ここではテクニックを１つ紹介しましょう。

図 1-1

　「元の数を２で割りまくって余りを書き並べる」という方法があります。
　その方法で、10進数の \(83\) を２進数に変換してみましょう。

\(83\) を２で割り、余り１を書く。
\(41\) を２で割り、余り１を書く。
\(20\) を２で割り、余り０を書く。
\(10\) を２で割り、余り０を書く。
\(5\) を２で割り、余り１を書く。
\(2\) を２で割り、余り０を書く。
\(1\) を２で割り、余り１を書く。
元の数が \(0\) になったら、余りを下から順に書き並べて「\(1010011\)」のできあがり！

　10進数の \(83\) を２進数に変換すると \(1010011\) になりました。

　これで２進数の説明は終わりです。
　次セクションからは、２進数を使った小話やパズルを３つ紹介しましょう。

２．魔法のカードで数字を当ててみせましょう！

　このセクションからは、２進数を使ったお話をしましょう。
　まずは「相手の思い浮かべた数字をズバリ当てる」というマジックです。

図 2-1

　さぁ、ここに５枚のカードがあります！
　このカード達を使って、アナタの思い浮かべた数字を当ててご覧に入れましょう！

　\(1\) から \(31\) までのうち好きな数字を思い浮かべてください！
　思い浮かびましたか？
　では、その数字の書かれているカードをすべて教えてください！
　ほぅほぅ、ＡとＤとＥ、この３枚ですね？

　え〜と、え〜っと（考えてるフリ）。
　……。
　はい、わかりました！
　アナタの選んだ数字は……「\(25\)」ですね？
　どうです？　当たったでしょう！！
　（万雷の拍手に包まれながら渾身のドヤ顔）

　……とまぁ、こんな感じで、相手の指したカードから数字をズバリ当ててしまう！
　\(1\)〜\(31\) ならどんな数字でも当たります。
　まぁ、相手がウソを言ってたら成功しませんが😅
　それは相手が無粋なだけなので、それはないと信じましょう。

　もちろん、このマジックにはタネがあります。
　５枚のカードに書かれた数字、これに秘密があるんです。
　その秘密を明かしましょう。

　図2-1 では、相手は「\(25\)」を思い浮かべていました。
　\(25\) を２進数で表してみます。

\(25\) の２進表現は \(11001\)。

図 2-2

　２進数 \(11001\) の１桁目は１ですね。
　１桁目が \(1\) である２進数、どんな物があるでしょうか？
　10進表記とともに挙げてみましょう。

1：00001	3：00011	5：00101	7：00111
9：01001	11：01011	13：01101	15：01111

　他には \(17,\ 19,\ 21, \cdots\) があるけれど、要は奇数です。
　そして、それらはすべてカードＡに書かれているんです。

　また、２進数 \(11001\) の４桁目も１ですね。
　４桁目が１である２進数、どんな物があるでしょうか？

8：01000	9：01001	10：01010	11：01011
12：01100	13：01101	14：01110	15：01111
24：11000	25：11001	26：11010	27：11011
28：11100	29：11101	30：11110	31：11111

　全部で16個。
　そして、それらはすべてカードＤに書かれているんです。

　２桁目・３桁目・５桁目の場合もまったく同様です。
　つまり、こういうことなんです。

２進数にすると１桁目が \(1\) になる数字のみ、カードＡに書いてある。
２進数にすると２桁目が \(1\) になる数字のみ、カードＢに書いてある。
２進数にすると３桁目が \(1\) になる数字のみ、カードＣに書いてある。
２進数にすると４桁目が \(1\) になる数字のみ、カードＤに書いてある。
２進数にすると５桁目が \(1\) になる数字のみ、カードＥに書いてある。

　２進数の各桁にカードが対応しているんですね。
　これがわかると、５枚のカード達の秘密が見えてくる。
　その秘密とは……これなんです。

カードの選び方に応じて、ただ１つの数字が決まる。

　それはなぜか？
　選んだカードに応じて２進数がただ１つに決まるからです。
　例えば、選んだカードがＡ, Ｂ, Ｃなら、対応する２進数は \(00111\)。
　\(00111\) に等しい10進数は \(7\) だけど、５枚のカードをよく見ると数字 \(\boldsymbol{7}\) はＡ, Ｂ, Ｃにしか書かれていないんです。
　もし選んだカードがＢ, Ｅなら、２進数 \(10010\) が対応する。
　\(10010_{(2)}=18\) であり、数字 \(\boldsymbol{18}\) はカードＢ, Ｅにしか書かれていません。
　カードにはこういう秘密があるんです。

　となれば、やるべき作業はもぅ簡単！
　相手の選んだカードに応じて２進数を作り、それを10進数に変換すれば良い。
　そうすれば、相手の思い浮かべた数字がわかる。
　そういう仕組みなんですね。
　もしＡ, Ｄ, Ｅが選ばれたなら２進数 \(11001\) を作り、それを10進数に変換して \(25\) とするんです。

図 2-3

　ただ、実際はわざわざ２進数を作る必要はありません。
　各カードの左上には数字 \(1,\ 2,\ 4,\ 8,\ 16\) がありますよね。
　それらを足すだけでいいんです。

　なぜかと言うと、２進数の各桁に相当する10進数がカードの左上に書いてあるからです。
　例えば、２進数の３桁目の「\(1\)」は10進数で言うと \(4\) ですよね。
　その「\(4\)」はカードＣの左上に書かれてあるんです。
　５桁目の「\(1\)」は10進数で言うと \(16\) ですね。
　その「\(16\)」はカードＥに書かれてある。
　他も同様なんです。

　「\(25\)」を思い浮かべた人はカードＡ, Ｄ, Ｅを選びます。
　そのカード達の左上数字 \(1,\ 8,\ 16\) を見てチャチャッと暗算すれば……

\(\boldsymbol{1+8+16 = 25}\)

　となって、見事に数字を当てられるのです。
　これがこのマジックのタネ明かし😊

　当然ですが、このマジックは数字 \(31\) までに限った話ではありません。
　カードをもう１枚増やして「\(1\) から \(63\) までの数字を当ててご覧に入れましょう！」というマジックもできます。
　何だったら、カードを32枚にして「\(1\) から \(4294967295\) までの（以下略）」だってできる！
　絶対やらんけど😅

３．ニセ金貨はど〜れだ？

　次は、ニセ金貨のパズルを紹介しましょう。
　まずは、２進数を使わない軽いジャブ的問題から。

図 3-1

　さて、ここに金貨がたんまり入った袋が５つあります。
　どの袋も中の金貨は見た目が同じ。
　しかし、この５つのうち、本物の金貨だけを詰めたのは４つだけ。
　１つはニセモノの金貨だけを詰めた袋なのです。

　幸いなことに、本物は１枚10グラム、ニセモノは１枚９グラムだということはわかっています。
　さぁ、台秤を１回だけ使って、どれがニセ金貨の袋か当てられますか？

　この問題は「何グラム軽いか？」という視点で考えるとうまくいきます。
　５つの袋をＡ〜Ｅとしましょう。
　そして、Ａからは金貨１枚、Ｂからは２枚、Ｃからは３枚、Ｄからは４枚、Ｅからは５枚取り出します。
　この全15枚をまとめて台秤に載せるんです。

　もし15枚全部が本物なら、台秤は150グラムを指すはず。
　しかし、実際はニセ金貨があるからその個数分軽くなりますね。
　どれだけ軽くなったかでニセ金貨の袋がわかります。
　もし 149グラムならニセ金貨はＡ、148グラムならＢ、……、145グラムならＥというわけです。
　これで無事解決ですね😊

　さ、ジャブはここまで。
　ここからが本番です。
　次は、さらに難しくしたニセ金貨問題を紹介しましょう。

図 3-2

　さて、ここに金貨がたんまり入った袋が５つあります。
　どの袋も中の金貨は見た目が同じ。
　しかし、今度はニセ金貨の袋が何個あるのかはわからない！

　今回も幸いなことに、本物は１枚10グラム、ニセモノは１枚９グラムだとわかっています。
　さぁ、台秤を１回だけ使って、ニセ金貨の袋をすべて当てられますか？

　今回は前回とは同じようにはいきません。
　台秤が146グラムを指しても「ニセ金貨はＤの袋だ！」とは断定できないですもんね。
　「ＡとＣの袋」かもしれないし。
　でも、ここはちょいと工夫して、２進数を利用するとうまくいくんです。

図 3-3

　今回はこうしましょう。
　Ａからは金貨１枚、Ｂからは２枚、Ｃからは４枚、Ｄからは８枚、Ｅからは16枚取り出します。
　この全31枚をまとめて台秤に載せるんです。

　もし金貨がすべて本物なら、台秤は310グラムを指します。
　当然、ニセ金貨の分だけ軽くなるから、ニセ金貨の枚数がわかりますね。
　例えば、台秤が297グラムを指したとすると、ニセ金貨は13枚。
　あとは、この「13枚」から袋を突き止めるだけ。
　ここで２進数を活用するんです。

　\(13\) を２進数で表しましょう。\(13\) は \(1101_{(2)}\) ですね。
　この \(1101\) を足し算式で表すと、\(13\) の内訳がわかります。

\[ 1101_{(2)} = 2^3\cdot1 + 2^2\cdot1 + 2^1\cdot0 + 1\cdot1 = 8+4+1 \]

　ニセ金貨の内訳は１枚＋４枚＋８枚。
　というわけで、ニセ金貨の袋はＡ, Ｃ, Ｄの３つでした。
　これで無事解決😊

　さて。
　上記では足し算で袋を突き止めましたが、実は２進数そのものでも可能です。
　なぜなら、取り出した金貨の枚数のおかげで、２進数の各桁に袋が対応できるからです。
　例えば、２進数の４桁目は10進数で言うと \(8\) に相当します。
　金貨８枚は袋Ｄから取り出しているんですね。
　だから、４桁目に袋Ｄが対応する。
　他も同様で、要はこういうことなんです。

２進数の１桁目に金貨１枚が対応、つまり袋Ａが対応している。
２進数の２桁目に金貨２枚が対応、つまり袋Ｂが対応している。
２進数の３桁目に金貨４枚が対応、つまり袋Ｃが対応している。
２進数の４桁目に金貨８枚が対応、つまり袋Ｄが対応している。
２進数の５桁目に金貨16枚が対応、つまり袋Ｅが対応している。

　だから、ニセ金貨の枚数を２進数にした時点でもぅ正解は出るんです。
　13枚の場合は \(13=01101_{(2)}\) だから……

\(01101\) の１, ３, ４桁目が \(1\) だから、袋Ａ, Ｃ, Ｄはニセ金貨。
\(01101\) の２, ５桁目が \(0\) だから、袋Ｂ, Ｅは本物の金貨。

　こういうわけなんですね。
　これで無事解決😊

　当然ですが、このパズル問題は袋の個数を増やせます。
　袋を６つにして同じ話を展開できたりする。
　その時は、６つめの袋Ｆは金貨を32枚取り出すことになりますね。
　もちろん、袋はもっともっと増やせます。
　何だったら50個にもできる！
　ただ、最後の袋からは 562,949,953,421,312枚（＝2⁴⁹枚）取り出さなきゃいけないけれど😅

４．ナンプレソフトにも２進数が大活躍してる！

　コンピュータでは、２進数をフラグとして扱ったりしますよね。
　オン/オフを切り替える機能です。
　例えば、ロールプレイングゲームやアドベンチャーゲームなどでは、キーとなる行為をすると次の展開に進めます。
　それは、ゲーム内部でフラグが管理されていて、キー行為によって該当フラグがオンになるからなんです。
　これらのゲームは「フラグ立てゲーム」とも言えますね。

　ナンプレ界はソフトであふれかえっている。
　そういうソフトにもフラグとして２進数が利用されているんです。
　このセクションでは、ソフトがナンプレを解く時に２進数をどう活用しているのかを話してみようと思います。

図 4-1

　ソフトがナンプレを解く時に最初に行うこと。
　それは、「各マスに入り得る数字を洗い出す」ということです。

　図4-1 を見てみましょう。
　盤面の空きマスに入り得る数字をそれぞれ洗い出し、列挙してみました。
　この薄くて小さい数字、ナンプレ界ではこれらを候補数字と呼びます。

　ソフトは各マスの候補数字たちを記憶しているわけだけど、その方法として２進数が使われています。
　「候補数字がある/ない」にオン/オフを対応させ、各マスの候補数字を９桁の２進数で管理しているんです。
　この９桁をここでは候補フラグと呼ぶことにしましょう。
　どのマスも候補フラグを１個ずつ持っています。

　例えば、ど真ん中の青色マス。
　候補数字は 2, 4, 6, 9 ですね。
　このマスの候補フラグは 100101010 です。
　候補数字２があるから（右から）２桁目は１、候補数字４があるから４桁目も１、……ということですね。
　この候補フラグ１つだけで候補数字の内訳がわかるんです。

図 4-2

　今、左上の黄色ブロックに注目しましょう。
　この９マスの候補フラグを順に書くとこうなります。

000000000
101100001※候補数字 1, 6, 7, 9
001100101※候補数字 1, 3, 6, 7（マスＡ）
100010000※候補数字 5, 9
000000000
000110001※候補数字 1, 5, 6
101010000※候補数字 5, 7, 9
000000000
001110001※候補数字 1, 5, 6, 7

　当然ですが、既に数字が確定していれば、そのマスの候補フラグは 000000000 です。

　実は、このブロックではマスＡに数字３が確定します。
　それをナンプレソフトはどうやって見つけるんでしょう？
　そのメカニズムに迫ってみましょう。

　「マスＡに数字３が確定する」とはどういうことか？
　それは、「マスＡに候補数字３があり、他の８マスには候補数字３が一切ない」ということです。
　そう考えると、候補フラグの３桁目になにやら秘密がありそうですね。
　マスＡと他８マスの３桁目を比較してみると……

マスＡ
001100101
他８マス
000000000
101100001
100010000
000000000
000110001
101010000
000000000
001110001

　なんと、一目瞭然じゃぁないですか！
　マスＡだけ「１」になっている！
　これで候補数字３はマスＡにしかないことがわかり、マスＡに数字３が確定するんですね。

　列やブロックに属する９マスの候補フラグを取得して、そのフラグ達に対して次のことを調べまくる。
　そうすれば、いろんなマスに数字が確定していく。
　これを繰り返して、ソフトはナンプレを解き進めているわけですね。

９個の候補フラグの各桁を見て、１個だけが「１」/他はすべて「０」になっているかどうかを調べる。
その後、「１」を持つただ１つのマスに数字を確定させる。

　この他にも、ソフトはもう１つの解き方をしています。
　それも紹介しましょう。

図 4-3

　図4-3 の緑色マスを見てみましょう。
　候補数字は４だけ。当然、数字４で確定しますね。
　このマスの候補フラグはこうなっています。

000001000

　これもわかりやすい！
　４桁目にしか「１」がない！
　「１」が１個しかないのを見つけて、数字４が確定する。
　こういう仕組みです。

　ソフトは次のことも調べてマスに数字を確定させています。

候補フラグの「１」の個数を調べる。
１個しかなかった場合、そのマスに数字を確定させる。

　これまで説明した２つの手法は初歩的な手法です。
　が、ナンプレには「２国同盟」などの高度な解き方もたくさんありますよね。
　それらもフラグがはたらいてくれるんです。
　２国同盟を例に挙げて説明しましょう。

図 4-4

　図4-4 の盤面。
　右下ブロックには数字６, ７の２国同盟がありますね。
　それを踏まえて、この９マスの候補フラグを見てみましょう。
　６, ７桁目に秘密があるんです。

010000101※候補数字 1, 3, 8
000000000
011100001※候補数字 1, 6, 7, 8（同盟マス）
000000011※候補数字 1, 2
000000000
001100001※候補数字 1, 6, 7（同盟マス）
010000111※候補数字 1, 2, 3, 8
010000011※候補数字 1, 2, 8
000000000

　いや〜もぅ、非常にわかりやすい！
　こんなにもハッキリと分かれるもんなんですなぁ。
　こういうところから２国同盟を発見できるんですね。

　そういや、なぜフラグの用途で２進数を使うんでしょう？
　それは、たくさんのフラグを一括して扱えるからです。
　例えば、プログラミングでは64桁の２進数を扱えるけれど、これは「64個のフラグをまとめて扱える」ということ。
　だから、64×64という巨大ナンプレでも候補フラグ１つで賄える。
　すごく効率的なんですね。

　また、プログラミング言語には２進数を直接操作できる「ビット演算」「シフト演算」がありますが、それらの小技は重宝します。
　「この２進数に１は何個あるか」「一番右にある１は何桁目か」といったことは簡単に計算できる。
　だから、候補フラグを基にさまざまな操作や値取得が容易くできます。

　あとは、メモリの節約や処理速度という点でも有利でしょうか。
　パズル誌『ナンプレファン』の57合体くらいの巨大ナンプレともなると、その有利さはバカになりません。
　仕事に活用するために私は簡易ナンプレソフトを自作しましたが、候補フラグに２進数を採用してみたらソースコードの量が格段に減りました。
　本当にソースコードが半分くらいに短くなって驚いたことを覚えています。
　コードもスッキリ。私の心もスッキリ🥰

　数値ではなくフラグとして２進数を見る。
　コンピュータ界では日常茶飯事な視点だけど、パズル界では風変わりな視点です。
　こういう見方もまた面白いものですね。

更新履歴

2022. 5.15.
- 新規公開。