ホームページへ戻る　開発ノートメニューへ戻る

ライツアウトを解く

アルゴリズム考察

　アルゴリズムはアルゴリズム講座/多重ループ検索で説明した通り、32通りだけの探索です。
for文を5重にネストしても良いのですが、私はバックトラックを用いることにしました。(この方が一般的と思います。)

0 1 2 3 4 5
6 7 8 91011
121314151617
181920212223
242526272829
303132333435
3637383940
　さて先ず、ライトボタンを押下することで自分と上下左右のライトが反転する動作ですが、角や辺にあたる位置を押下された場合にはゲーム枠からはみ出た位置にも作用し、ヘタな記述をするとエラーになってしまいます。これを回避する方法として、JAVA言語なら、2次元配列のアクセスをtry{}で囲んでエラーは無視するという方法が簡単ですが、私は2次元配列ではなく1次元の連続座標を使いたかったのでこういう例外処理の使えないC言語等でよく使われるゲーム枠をダミーの壁で囲うという方法を使いました。
　右図の青色の部分がダミー壁です。ここの中身はどうでもよく、角や辺の位置でも単純に５ヶ所のライトを反転出来ます。また、走査位置(pos)は０から２４として、この値からダミー壁付きの作業エリアへの座標変換テーブルを作っておくことにします。

　次にバックトラック処理の中身ですが、走査位置により３通りに分かれます。

//--------------------------------------------------
// 電子頭脳  (pos=走査位置 0から24)
//--------------------------------------------------
void computer(int pos) {

    if (pos == 25) {         // 走査の終端
        最下段５つの消灯チェック;
        解の記録更新;
    } else {
２５ヶ所総てが終わった場合
　→最下段５ヶ所のライトが総て消えているか 
        if (pos < 5) {       // 最上段５つの試行錯誤
            computer(pos+1);     // 押さずに次へ

            押す;
            computer(pos+1);     // 押して次へ
            押す;                // 元に戻す
最上段の５ヶ所の場合
　→通常のバックトラック処理をする 
        } else {             // ２段目以降の確定対応
            if (上部が消えている) {
                computer(pos+1); // 押さずに次へ
            } else {
                押す;
                computer(pos+1); // 押して次へ
                押す;            // 元に戻す
            }
        }
    }
２段目以降の場合
　→上部のライトの状態で決定する
}

ＪＡＶＡ言語

　ＪＡＶＡ言語には幾つかの特殊メソッド(関数)が用意されています。アニメーション処理の必要ない今回の様な簡単なアプレットでは、initメソッド、paintメソッド、mouseDownメソッド等で充分です。また、これらのメソッドは大変重要な必須メソッドと言えるものです。

//--------------------------------------------------
// 初期処理
//--------------------------------------------------
public void init() {
    ボタン配置処理
}
init()はアプレット実行開始時に自動で1度だけ実行されるメソッドで、アプレットの実行に必要な各種の初期処理や定義を書き込んでおきます。
　今回は、[CLEAR]と[START]の2つのボタンを下部中央に配置しています。 
//--------------------------------------------------
// 画面の表示
//--------------------------------------------------
public void paint(Graphics g) {
    画面全体を表示
}
paint(Graphics g)はアプレット実行開始時に自動で実行されるだけでなく、アプレットが他のWindowに隠されたりスクロールで見えなくなった部分を修復する時にも自動で実行されます。
　従って、その時その時の状態を画面全体に渡って完全に再現表示できるように記述しておかなければなりません。 
//--------------------------------------------------
// マウスイベント
//--------------------------------------------------
/* 入力エリアの編集受付 */
public boolean mouseDown(Event e, int x, int y) {
    if (クリック位置(x,y)が入力域なら) {
        その位置のライトを反転する;
        その位置を再表示する;
    }
    return true;
}

/* ボタンによる命令受付 */
public boolean action(Event e, Object arg) {
    if ([CLEAR]ボタンなら) {
        入出力データをクリア;
    } else if ([START]ボタンなら) {
        computer(0); // 探索処理を実行
    }
    repaint();       // 画面全体を再表示
    return true;
}
マウスクリックによる割り込み処理です。

アプレット上の任意の場所をクリックされたことに反応するのは、mouseDown(Event e, int x, int y)です。クリック位置は引数のxとyに格納されています。

ボタンをクリックされたことに反応するのは、action(Event e, Object arg)です。どのボタンが押されたかはargにボタン上の文字が格納されています。

　尚、どちらもboolean型なので最後に論理値(true,false)を返す必要があります。

　

repaint()は画面の再表示を強制的に実行させます。 

//--------------------------------------------------
// 電子頭脳
//--------------------------------------------------
void computer(int pos) {
    省略
}
computer(int pos)は特殊メソッドではありません。
ユーザーが定義した関数です。
ダウンロード

　私のヘタクソなプログラムのソースコードをダウンロード出来ます。

・ソースコード　light.java
・その他の必要なファイル　ありません
・アプレットサイズ　width=374　height=204

追記（驚異のライツアウト解法ロジック）

　ここで使用したアルゴリズムよりも、もっと面白い方法でライツアウトを解く方法があります。→ここ

ホームページへ戻る　開発ノートメニューへ戻る