パズルで活躍する2進数

 2進数とは、「0」「1」の2つだけで表した数のことです。
 この2進数がパズルでも活躍することがあるんです。
 そういう話をいくつか集めてみました。

1.2進数とは何ぞや?

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

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

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

 2進法 とは、0と1の2個の数字を使った数値表現方法です。
 そして、2進法で表現された数のことを 2進数 と言います。
 10進法だと9の次は繰り上がって 10 になりますが、2進法だと1の次は繰り上がって 10 になります。
 だから、2進数を0から順に書くと 0, 1, 10, 11, 100, 101, 110, 111, 1000, ……となるわけですね。

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

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

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

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

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

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

 【2進数→10進数】の変換は前述した通りです。
 1, 2, 22, 23, 24, 25, ……との積を作って足し算しましょう。
 例えば、2進数の 1010011 を10進数に変換するとこうなります。

 2進数の 1010011 を10進数に変換すると 83 になりました。

 次は【10進数→2進数】の変換。
 これはちょっと手間がかかります。

図 1-1

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

  1. 83 を2で割り、余り1を書く。
  2. 41 を2で割り、余り1を書く。
  3. 20 を2で割り、余り0を書く。
  4. 10 を2で割り、余り0を書く。
  5. 5を2で割り、余り1を書く。
  6. 2を2で割り、余り0を書く。
  7. 1を2で割り、余り1を書く。
  8. 元の数が0になったら、余りを下から順に書き並べて「1010011」のできあがり!

 10進数の 83 を2進数に変換すると 1010011 になりました。

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

2.魔法のカードで数字を当ててみせましょう!

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

図 2-1

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

 1から31までのうち好きな数字を思い浮かべてください!
 思い浮かびましたか?
 では、その数字の書かれているカードをすべて教えてください!
 ほぅほぅ、AとDとE、この3枚ですね?

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

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

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

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

図 2-2

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

1:000013:000115:001017:00111
9:0100111:0101113:0110115:01111

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

 また、2進数 11001 の4桁目も1ですね。
 4桁目が1である2進数、どんな物があるでしょうか?

8:010009:0100110:0101011:01011
12:0110013:0110114:0111015:01111
24:1100025:1100126:1101027:11011
28:1110029:1110130:1111031:11111

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

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

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

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

 それはなぜか?
 選んだカードに応じて2進数がただ1つに決まるからです。
 例えば、選んだカードがA, B, Cなら、対応する2進数は 00111。
 00111 に等しい10進数は7だけど、5枚のカードをよく見ると数字7はA, B, Cにしか書かれていないんです。
 もし選んだカードがB, Eなら、2進数 10010 が対応する。
 10010(2)=18 であり、数字18はカードB, Eにしか書かれていません。
 カードにはこういう秘密があるんです。

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

図 2-3

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

 なぜかと言うと、2進数の各桁に相当する10進数がカードの左上に書いてあるからです。
 例えば、2進数の3桁目の「1」は10進数で言うと4ですよね。
 その「4」はカードCの左上に書かれてあるんです。
 5桁目の「1」は10進数で言うと16ですね。
 その「16」はカードEに書かれてある。
 他も同様なんです。

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

1+8+16= 25

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

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

3.ニセ金貨はど〜れだ?

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

図 3-1

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

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

 この問題は「何グラム軽いか?」という視点で考えるとうまくいきます。
 5つの袋をA〜Eとしましょう。
 そして、Aからは金貨1枚、Bからは2枚、Cからは3枚、Dからは4枚、Eからは5枚取り出します。
 この全15枚をまとめて台秤に載せるんです。

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

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

図 3-2

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

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

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

図 3-3

 今回はこうしましょう。
 Aからは金貨1枚、Bからは2枚、Cからは4枚、Dからは8枚、Eからは16枚取り出します。
 この全31枚をまとめて台秤に載せるんです。

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

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

 ニセ金貨の内訳は1枚+4枚+8枚。
 というわけで、ニセ金貨の袋はA, C, Dの3つでした。
 これで無事解決😊

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

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

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

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

4.ナンプレソフトにも2進数が大活躍してる!

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

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

図 4-1

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

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

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

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

図 4-2

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

  • 000000000
  • 101100001  ※候補数字 1, 6, 7, 9
  • 001100101  ※候補数字 1, 3, 6, 7(マスA)
  • 100010000  ※候補数字 5, 9
  • 000000000
  • 000110001  ※候補数字 1, 5, 6
  • 101010000  ※候補数字 5, 7, 9
  • 000000000
  • 001110001  ※候補数字 1, 5, 6, 7

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

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

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

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

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

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

図 4-3

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

  • 000001000

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

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

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

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

図 4-4

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

  • 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

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

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

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

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

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

更新履歴