数の並び順はじめに皆さんは「スライドパズル」というゲームをご存知でしょうか？これは、枠の中に何枚かのコマが収められていて、1 カ所だけ空いた場所があるというものです。ここでは、この空いた場所を「ブランク」と呼ぶことにします。スライドパズルは、このブランクを利用して、コマをスライドさせ、ばらばらになった絵を完成させたり、数字を並べ替えたりするゲームです。中でも 4×4 の枠の中に、「1」から「 15」までのコマをランダムに並べて、元の並び頓に戻すパズルは大変有名です。このパズルは、もともとの起源はかなり古いようですが、現在広く知られているものと言えば、19 世紀にアメリカの SamuelLoyd 氏によって考案された「15 パズル」です。ゲームは、「単純なものほどおもしろい」とよく言われますが、このパズルも単純でありながら、なかなか奥深いテーマが隠されています。今回はこの 15 パズルを基にした問題に挑戦しましよう。今回の問題その１図 A のように「14」と「15」のコマの順番がひっくり返った 15 パズルが参る。これを並び替えて「1」から「15」までの並び順に戻すことができるかどうか考え、できる場合にはその手順を、できない場合にはその理由を説明しなさい。 15 パズルのルールを確認する 15 パズルは、プログラミングにはうってつけの題材です。とくに、四角いマスをベースに数字を扱うパズルとなると、ExcelVBA のためにあるようなものと言えます。今回は、問題の解法は後回しにして、まず、ひとり遊び用の 15 パズルを作ってみたいと思います。ルールは単純ですが、ゲーム作りのための細かい仕様をここで確認しておきましょう。仕様１［スタート］ボタンをクリックすると、新しい問題として盤面に「1」から「15」までの数字がセットされる。このとき、盤の右下隅はブランクとして「0」をセットし、選択状態にする（図 1）。仕様２コマを移動するには、移動したいコマを選択し、続いてブランクセルを選択する。ここでブランク以外のセルを選択した場合には、何も起こらない（図 2）。仕様３「1」から「15」までの数字が所定の位置に正しく並んだ場合には正解のメッセージを出す（図 3）。 1 図 1：［スタート］ボタンをクリックして盤に数字をセットする図 3：正しく数字を並べ替えるとメッセージが出る図 2：コマを移動する 15 パズル作りにチャレンジ！ 15 パズルのサンプルアプリケーションは、大きく分けて次の 2 段階の手順で進めてゆくことにします。・数字をセットする処理・コマを動かす処理サンプルアプリケーションでは、移動前のコマの位置、移動後のコマの位置、現在のブランクの位置などを肥握しておく必要があります。この位置は、図 4 の左側の図のように、連番で表わすことにしますが、これは実際にセットされているコマの数字とは別のものです。たとえば、図 4 の右側の図で「 15」のコマは 7 番目の位置にあると考えることにします。図 4：コマの位置とセットされた数字の関係ワークシートを準備する新規にワークシートを 1 枚用意し、セル「C3」から「F6 」の範囲に 4×4 の大きさの盤を作り、幅や高さ、セルの書式などを整えておきます。 2 次に、このセル範囲を選択した後、名前ボックスに「board」と入力し、［Enter］キーを押して、盤を表わすセル範囲に「 board」という名前をつけておきます（図 5）。図 5：ワークシートの準備 ②名前ボックスに「 board 」と入力し [Enter] キーを押す ①セル C3 から F6 までを範囲選択壁に数字をセットするコードを記述それでは、実際にプログラムコードを記述してゆくことにしましょう。VBEditor を起動して標準モジュールを追加し、リスト 1 のコードを記述します。リスト 1 には 3 つのプロシージャがあります。「main 」は、盤にコマの位置を表わす数字をセットするためのメインプロシージャです。「S_Place」は「1」から「15」までの数値をランダムに、盤の「1」から「15」の位置に配置するためのプロシージャです。「S_Draw」は盤面の色を塗り替えるプロシージャです。それでは順番にコード内容を見てゆきましょう。リスト 1：盤に数字をセットするコード Option Base 1 Public ZeroNo As Integer コ ' マのない位置 Public PreNo As Integer コ ' マの移動前の位置 '*** 盤面セット *** Sub main() Dim i As Integer With Range("board").Cells(16) .Value = 0 .Select End With PreNo = 16 ZeroNo = 16 s_Draw End Sub ③ ② ① '*** 数字を盤に並べる *** Sub s_Place() Dim i As Integer, myNum As Integer Dim num(15) As Boolean For i = 1 To 15 Do Randomize myNum = Int(Rnd * 15 + 1) Loop While num(myNum) = True Range("board").Cells(i).Value = myNum num(myNum) = True Next End Sub '*** 盤面を塗り分ける *** Sub s_Draw() Dim myR ange As Range Dim i As Integer With Range("board") .Interior.ColorIndex = 35 .Font.ColorIndex = 55 End With With Range("board").Cells(ZeroNo) .Interior.ColorIndex = 16 .Font.ColorIndex = 16 End With End Sub 3 宣言セクションリスト 1 −①の宣言セクションでは、サンプルアプリケーションの中で利用する変数を宣言しています。 ExcelVBA では、複数のプロシージャ間で情報の受け渡しをする場合は、次の方法があります。・ワークシートのセルを利用する・プロシージャの引数として億を渡す・グローバル変数を利用する・今回はグローバル変数を利用することにしましょう。グローバル変数は、宣言セクションに Public ステートメントで宣言します。これにより、この変数をすべてのプロシージャから利用することができるようになります。また、ここで宣言している「 ZeroNo」はブランクセルが何番目に位置しているかを、け「 PreNo 」は移動前のコマの位置をそれぞれ格納するための変数です。なお、冒頭の「 OptionBase」ステートメントは、配列変数のインデックス番号を変更するためのものですが、これは、また後ほど説明することにします。「main 」プロシージャリストト１-②では、盤の右下隅にブランクセルを設定し、残りの「1」から「 15」までの 15 個のコマをランダムに配置する処理を行なっています。ここで注意したいのは、「Range（"board"）.Cells （n ）」というコードです。通常、「Cells」プロパティは「Cells （行，列）」といった記述の仕方をしますが、もうひとつの方法として、セル「A1」を基点としてセル全体に連続番号をふり、「Cells （連続番号）」という形式で、セルを参照することも可能です。たとえば、「Cells（260）」は、セル「D2」を表わしています（図 6）。このテクニックを用いて、「 Range （"board"）.Cells（n ）」といつた記述をすることで、「board」と名前をつけたセル範囲内の中で、n 番目のセルを指定することができるのです（図 7）。図 6：連続番号でセルを特定する図 7：指定した範囲内で連続番号によリセルを特定するリストト③では、変数に初期値を設定し、盤面を塗り分けるプロシージャを呼び出しています。この時点では、移動前のコマもブランクのコマも同じ 16 番目の位置となります。「s_Place 」プロシージャでは、盤の 1 番目の位置から、ランダムに数字をセットしてゆく処理を行なっています。「S_Place」プロシージャの冒頭では「 num」という配列変数を宣言しています。このモジュールの宣言セクションで「OptionBase1」と記述することにより、配列のインデックス番号は「1」から始まるようになっています。「num（15）」であれば、「num（1）」から「num（15）」までの 15 個の変数を取り扱うことが可能です。今回の「 num」配列変数は、ランダムに数字をセットしてゆく過程で、その数字がすでに使われたかどうかをチェックするのに使用しています。これはどういうことでしょうか？まず、Boolean 型で宣言した「 num」配列変数には、初期値として「False」という値が設定されています。たとえば、盤にすでに「 3」「8」「2」と数字がセットされていたとします。その場合、「num」配列変数には図 8 のように該当個所に「True」という値がセットされています。そして、次に 4 番目の位置の数字を決めるとしましょう。仮にランダムに選ばれた数字が「8」だった場合、まず「num（8）」の値をチェックします。このと 4 き、値が「True」であれば、すでに使われている数字と判断し別の数字をループして探す仕組みになっているのです。最後の盤面を塗りわける「s_Draw」プロシージャでは、いったんすべてのセル色と文字色を指定の色で塗りつぶした後、ブランクセルのみ、別の色で塗りつぶす処理を行ないます。コマを動かすコードを入力続いて、実際にコマを動かす処理を行なうプロシージャを作成しましょう。図 8：数字の重複チェックに配列変数を利用するサンプルアプリケーションでは、セルのクリックに反応して処理を行なわせるため、「Worksheet_SelectionChange」イベントを利用することにします。VBEditor のプロジェクトウィンドウで、「Sheet1 」をダブルクリックしてコードウィンドウを開き（図 9）、リスト 2 のコードを記述してください。リスト 2 の処理コードを解説する前に、コマの移動に関してもう一度ルールを確認しておきましょう。ルールは簡単です。直前に選択されていたコマは、次に選択されたセルに移動する図 9：「Sheet1 」のコードウィンドウを開くただし、このルールには 3 つの条件があります。・移動先のセルが盤内にある・移動先のセルがブランクである・直前に選択されているセルとの位置関係が上下左右いずれかで隣り合っている「Worksheet_SelectionChange」プロシージャでは、この最初の 2 つの条件のチェックを行ないます（リスト 2−②）。この条件をクリアした場合にのみ、3 つ目の条件をチェックする「s_Move」プロシージャを呼び出します。それ以外のケースでは、コマの移動は実行されません。ただし、アクティブなセルは動きますので、そリスト 2：セルがクリックされた時の処理コードのセルの位置を変数「PreNo」に格納します。このとき、盤内のセルが選択された場 Private Sub Worksheet_SelectionChange(ByVal Target As Range) 合には、セル位置を表わす「1」から「16」 Dim myRange As Range のいずれかの数値が格納されますが、それ ① On Error Resume Next 以外のセルが選択された場合の「PreNo」 Set myRange = Application.Intersect(Target, Range("board")) の値は、意味をなさない値となります。 If Not myRange Is Nothing And Target.Value = 0 Then s_Move Target Else PreNo = (Target.Row - 3) * 4 + (Target.Column - 2) End If End Sub なお、サンプルアプリケーションでは、単一のセルを選択してコマを動かしてゆきますが、複数のセルを選択するとエラーが発生し、グローバル変数の値などがリセットされてしまいます。このため、リスト 2 −①のコードを記述し、エラーをスキップさせています。 ② 5 次に標準モジュールに戻り、リスト 3 のコードを記述します。リスト 3 には、前述した「s_Move」プロシージャと、「s_Move」プロシージャから呼び出される「s_Correct 」プロシージャの 2 つのプロシージャがあります。「s_Move」プロシージャは、現在選択されたセルと直前に選択されていたセルとの位置関係をチェックしますが、コマを動かすには直前に選択されているセルが盤内にある必要があります。この条件を変数け「PreNo」の値でチェックしています（リスト 3−①）。リスト 3−②では、直前に選択されていたセルの行位置 (PreR) と列位置（PreC）を求め、同様に現在選択されているセルの行位置（CurR）と列位置（CurC）、さらに盤内の順番（ CurNo）を変数に格納しています。これらの変数を使って、リスト 3−③のブロックで位置関係のチェックを行ない、コマ移動できる位置関係の場合のみ、コマの移動、すなわち 2 つのセル内容の交換を行なっています。リスト 3：コマの移動を行なう処理コード '*** コマ移動のチェック *** Sub s_Move(Target As Range) Dim CurNo As Integer Dim CurR As Integer, CurC As Integer Dim PreR As Integer, PreC As Integer Dim tempNo As Integer Dim myTmp As Integer If PreNo < 1 Or PreNo > 16 Then Exit Sub PreR = (PreNo - 1) ¥ 4 + 3 PreC = (PreNo - 1) Mod 4 + 3 CurR = Target.Row CurC = Target.Column CurNo = (Target.Row - 3) * 4 + (Target.Column - 2) If ((CurR = PreR) And Abs(PreC - CurC) = 1) _ Or ((CurC = PreC) And Abs(PreR - CurR) = 1) Then With Range("board") .Cells(CurNo).Value = .Cells(PreNo).Value . C e l l s ( P reNo).Value = 0 ZeroNo = PreNo PreNo = CurNo End With s_Draw s_Correct End If End Sub ① ② ③ '*** 並び順をチェックする *** Sub s_Correct() Dim i As Integer For i = 1 To 15 If Range("board").Cells(i).Value <> i Then Exit Sub End If Next MsgBox " おめでとう" End Sub 6 「s_Correct」プロシージャでは、盤内の数字が順番に並んでいるかどうかをチェックします。ここまでの手順で 15 パズルはひとまず完成です。ワークシートにコマンドボタンを貼り付け、「マクロの登録」ダイアログボックスで、「main 」プロシージャを割り当てた後、コマンドボタンをクリックしてみましょう。まず、正しく数字がセットされたかを確認します。そして、実際に盤内のセルをクリックしてコマを動かし、正しい順番に並び替えてみてください。問題について考えるいかがでしょう。うまく並べ替えることができたでしょうか？実は何回か試していただくと、どうしてもうまく並び替えることができないケースが発生するはずなのです。そう、今回の問題で示したように、どこか 1 カ所が必ずひっくり返っているケースです。結論から言ってしまうと、このような場合には正しい順番に並び替えることはできません。なぜできないのでしょうか？この連載で定番の“問題を簡略化する”方式で考えてみましよう。たとえば、「1」から「5」までのカードが並んでいるとします。このカードから任意の隣り合う 2 枚を選んで位置を交換します。図 10：横並びのカードを並べ替えるこれで交換回数は 1 回です。では、もう 1 回、別のカードの位置を交換してみましょう。これで交換回数は 2 回となります（図 10）。次に、このカードを元の状態に戻すことにしましょう。図 10 のケースでは 2 回の操作で元に戻すことができるはずです。ここで、交換回数についてもう少し考えてみましょう。1 回カードを交換したら、元に戻すのに必ず 1 回の交換が必要となります。合計の交換回数は 2 回です。2 回カードを交換したら通常は元に戻すのに、やはり 2 回、合計 4 回です。つまり、どれだけカードを入れ替えても、元に戻すには遇数回の交換が必要になるわけです。このように偶数回で元の状態に戻せる数の並びを「偶順列」と呼びます。では、最初から、という順番でカードが並べられている場合を考えてください。このカードを正しい順番に直すには、単純に考えれば交換回数は 1 回です。わざと複雑に交換したとしても、その交換回数は必ず奇数回になります。このような順番の並びを「奇順列」と呼びます。「奇順列」の場合には、偶数回の交換操作では決して正しい並び順にはならないのです。さて、話を 15 パズルに戻しましょう。 15 パズルではコマの移動が先の交換回数に相当します。そして、ばらばらに並んでいる数字を元の順番に並べ替える過程をブランクに注目してイメージしてみましょう。数字が配置された直後、最初にブランクは盤の右下隅にあります。コマをどのように動かすかは、人それぞれですが、どのように動かしたとしても、最後は必ず右下隅に戻ってきます。そして、これが大事なポイントなのですが、このとき、ブランクの移動の回数は必ず偶数回になるのです。 7 ここで、もう一度、「今回の問題その 1」で掲げた図 A を見てみましょう（図 11）。誰が見てもわかるように、この並びを元に戻すには 1 回の操作が必要です。つまり、この数の並びは「奇順列」です。ところが、ブランクを元の位置に戻すには必ず偶数回の操作が必要となります。以上の点から、このパズルを元に戻すことができないということがおわかりいただけたでしょうか。図 11：図 A 「奇順列」か「偶順列」かを判定する 15 パズルは、最初に設定された並び傾が「偶順列」か「奇順列」かで、正しく並べられるかどうかが決定されてしまいます。せっかくゲームを楽しんでいたのに最後になって、「実はできませんでした」ではなんとも悔しいものです。かといって、最初の状態で一見して判断できるものではありません。図 12：数字の交換回数を考えるでは、どうしたらいいでしょう？実は、次に紹介する方法で、並べ替えを行なわなくても、「寄順列」か「偶順列」かを判断できるのです。図 12 では、1 番最初の数は「 4」です。この「 4」の後ろに「 4」よりも小さい数がある場合には、必ずコマを入れ替えなければいけません。この場合、「1」「2」「3」がそれに該当しますので、最低でも 3 回の交換が必要です。次に、2 番目の「11」ではどうでしょうか。「11」の場合には、自分より小さい数は、「9」「8」「1」「5」「10」「2」「7」「3」「6」の 9 つとなります。以下、同様にそれぞれの数字について最低の交換数を求め、すべての交換数を合計してみましょう。この例では「44」という値になるはずです。そして、こうして求めた交換の回数が、偶数の場合には「偶順列」、奇数ならば「奇順列」ということになります。この計算は、手作業では手間がかかりますが、プログラミングには適した処理です。この交換回数を求めるプロシージャがリスト 4 の「f_Even」です。このプロシージャは盤内に設定された数字の最小交換回数を求め、その値が偶数ならば「True」を、奇数ならば「False」を返します。リスト 4：偶順列か奇順列かを判定する処理コード '*** 並び順の交換回数をチェックする *** Function f_Even() As Boolean Dim myRange As Range Dim myNum(15) As Integer Dim i As Integer, j As Integer Dim mySum As Integer For i = 1 To 15 myNum(i) = Range("board").Cells(i).Value Next For i = 1 To 14 For j = i + 1 To 15 If myNum(i) > myNum(j) Then mySum = mySum + 1 End If Next Next If (mySum Mod 2) = 0 Then f_Even = True Else f_Even = False End If End Function 8 また、「f_Even」プロシージャは、「main 」プロシージャの盤内に数字をセットする処理と縮めて呼び出すため、「main 」プロシージャの一部をリスト 5−①のように変更します。これで盤面に最終的にセットされる数字は、必ず「偶順列」となります。これで安心してパズルを解くことができますね。リスト 5：修正した「main 」プロシージャ Sub main() Dim i As Integer With Range("board").Cells(16) . V alue = 0 .Select End With Do s_Place Loop Until f_Even PreNo = 16 ZeroNo = 16 s_Draw End Sub おわりに「今回の問題その 1」は、「今回の問題その 2」にあるような条件を付け加えることで、正しい順番に並べ替えることができます。どうしてそうなるのかと言うと………。それは、少し考えてみてください。ヒントはやはり交換回数にありそうですね。コマを並べ替えるパズルは、実にいろいろなバリエーションをもって多くの人に親しまれてきました。一列に並んだ状態でコマを入れ替える「カエル飛び」の問題など、興味深いものがたくさんあります。定番問題を集めたパズルの本などに載っていますので、興味のある方は、ぜひ挑戦してみてください。今回の問題その２図 A のように「14」と「15」のコマの順番がひっくり返った 15 パズルがある。これを図 B のように「1」から「15」まで順番に並べ替えなさい。 9 10