エイトクイーン

2003/6/15作成

エイトクイーン

エイトクイーン
画面サンプル

チェスのクイーンは縦横斜めの全ての方向に盤面の端まで進んでそこにある駒を取る事が出来ます。このクイーン8個をお互いに取られることの無いような位置にチェス盤に配置するパズルをエイトクイーンと言います。

エイトクイーンの解法にはバックトラック法というアルゴリズムを使っています。と言っても難しいものではなくて、1行ずつ試していって、駄目だったら大丈夫な所まで戻ってやり直すという方法です。1歩ごとにウェイトを入れていますので求める過程がよりよく分かるようになっていますし、エイトクイーンを解いていく様を見ていると一種の環境ソフトのようでもあります。

プログラム


/********************************************************/
/*  初期化                                              */
/********************************************************/

l = 0;

cls();
for( y = 0; y < 8; y++ ) {
    locate( 0, y );
    printstr( "........" );
}

/********************************************************/
/*  エイトクイーン作成                                  */
/********************************************************/

while( l < 8 ) {
    for( i = 0; i < 7; i++ ) {
        if( scan( i, l ) == 'Q' ) {
            locate( i, l );
            printstr( ".Q" );
            goto check;
        }
    }
    if( scan( 7, l ) == 'Q' ) {
        locate( 7, l );
        printstr( "." );
        l--;
        goto wait;
    }
    locate( 0, l );
    printstr( "Q" );

check:
    f = 1;
    /*  縦方向チェック  */
    for( x = 0; x < 8; x++ ) {
        c = 0;
        for( y = 0; y < 8; y++ ) {
            if( scan( x, y ) == 'Q' )
                c++;
        }
        if( c > 1 )
            f = 0;
    }
    /*  ななめ方向チェックその1 */
    for( w = 0; w < 8; w++ ) {
        for( x = 0; x < 8; x++ ) {
            c = 0;
            for( y = 0; y < 8; y++ ) {
                if( scan( x + y, y + w ) == 'Q' )
                    c++;
            }
            if( c > 1 )
                f = 0;
        }
    }
    /*  ななめ方向チェックその2 */
    for( w = 0; w < 8; w++ ) {
        for( x = 0; x < 8; x++ ) {
            c = 0;
            for( y = 0; y < 8; y++ ) {
                if( scan( x - y, y + w ) == 'Q' )
                    c++;
            }
            if( c > 1 )
                f = 0;
        }
    }
    /*  当たってる? */
    if( f == 1 )
        l++;

wait:
    /*  ウェイト    */
    wait( 500 );
}


/********************************************************/
/*  完成                                                */
/********************************************************/

/*  画面表示    */
locate( 2, 9 );
printstr( "PUSH ANY KEY" );

/*  キークリア待ち  */
while( ( pad() & 0xff ) );

/*  キー待ち    */
while( !( pad() & 0xff ) );

ダウンロード

8queen.zip

改良案

このプログラムでは一つのエイトクイーンの解答が見つかったらそれで終了していますが、実際には他にもエイトクイーンの解答はあるのです。そのまま続けていって、全てのエイトクイーンの解答を出すというように改造するのは、それほど難しくないと思います。

チェスから発したゲームですからエイトクイーンなのですが、エイトクイーンではなくてナインクイーンでもテンクイーンでも同じ事をやるのは可能でしょう。ただし、数が増えると解くのに掛かる時間が莫大になっていきますので、その点はご注意を。