バックトラック法

バックトラック法とは

バックトラック法とは、問題への解のすべてを系統的かつ効率的に探索する方法です。 一般的に、ある問題の答えの組み合わせのすべてを網羅的に試行すると、解に至るまでの組み合わせが膨大になり、解が得られない。ということが起こりえます。バックトラック法の例として有名なのが、8クイーン問題です。8クイーン問題を一般化した問題がNクイーン問題です。

8クイーン問題

8クイーン問題とは、「タテ・ヨコ・ナナメに効きがあるクイーンを、8×8マスの盤上に、互いに効きがないように8つのクイーンを配置する」という問題です。タテ・ヨコ・ナナメに効きがないようにクイーンを配置できれば成功、そうでなければ失敗とします。問題としては非常にシンプルながら、クイーンを配置できるすべての組み合わせを網羅したのち、題意を満たすクイーンの配置を調べるという方法だと組み合わせが膨大になります。つまり、盤のマスは8*8=64つあり、1つ目のクイーンを置くマスの選び方は64通り、2つ目は63通り、、、とすると8つのマスの選び方は

 64*63*62*61*60*59*58*57 = 178,4629,8763,7760

つ存在することになります。178兆...膨大ですね。
この組み合わせ爆発を解決するために、バックトラック法ではクイーンを1つ目、2つ目、、、と順番に配置していきますが、Nつ目のクイーンの配置で失敗となった場合は、N+1つ以降のクイーンの配置方法については探索せず、別の配置方法を探索します。

実装例

以下の実装例は若干冗長です。盤を2次元配列で表しているため、クイーンの利きを調べる方法が煩雑になっているためです。効率的な実装は「Javaプログラマのためのアルゴリズムとデータ構造」*1に記載がありますので、そちらを参照してください。

public class NQueenComp {

    int N;                         // クイーンの数
    int[][] board;                 // 盤:[行][列]

    /**
    * @param n 盤の長さ(=クイーン数)
    * */
    public NQueenComp(int n) {
        board = new int[n][n];
        N = n;
    }

    // テスト用
    public static void main(String[] args) {
        NQueenComp q = new NQueenComp(8);
        q.tryQueenCompAll(0);
    }

    public boolean tryQueenComp(int row) {

        for (int col = 0; col < N; col++) {
            if (lengthCheck(board, col) && sideCheck(board, row) && upLeftCheck(board, row, col) && upRightCheck(board, row, col)) {
                board[row][col] = 1;
                // N個のクイーンを置ければ成功である
                if (row + 1 >= N) {
                    return true;
                } else {
                    // 行[row+1]以降の行に置ければ成功である
                    if (tryQueenComp(row + 1)) {
                        return true;
                    } else {
                        board[row][col] = 0;
                    }
                }
            }
        }
        // この行には置くことができなかった
        return false;
    }

    public boolean tryQueenCompAll(int row) {

        for (int col = 0; col < N; col++) {
            if (lengthCheck(board, col) && sideCheck(board, row) && upLeftCheck(board, row, col) && upRightCheck(board, row, col)) {
                board[row][col] = 1;
                // N個のクイーンを置ければ成功である
                if (row + 1 >= N) {
                    print();
                } else {
                    // 行[row+1]以降の行に置ければ成功である
                    tryQueenCompAll(row + 1);
                }
                board[row][col] = 0;
            }
        }
        // この行には置くことができなかった
        return false;
    }

    // クイーンの配置を表示
    // 1:クイーンがあるマス、0:何もないマス
    private void print() {

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println("");
        }
        System.out.println("");
    }

    // 縦にすでにクイーンが存在しないかチェックする
    private boolean lengthCheck(int[][] board, int col) {
        for (int i = 0; i < N; i++) {
            if (board[i][col] == 0) continue; return false;
        }
        return true;
    }

    // 横にすでにクイーンが存在しないかチェックする
    private boolean sideCheck(int[][] board, int row) {
        for (int j = 0; j < N; j++) {
            if (board[row][j] == 0) continue; return false;
        }
        return true;
    }

    // 斜めにすでにクイーンが存在しないかチェックする
    private boolean upRightCheck(int[][] board, int row, int col) {

        // 上方向へのチェック
        for (int r = row, c = col; r >= 0 && c < N; r--, c++) {
            if (board[r][c] == 0) continue; return false;
        }

        // 下方向へのチェック
        for (int r = row, c = col; c >= 0 && r < N; r++, c--) {
            if (board[r][c] == 0) continue; return false;
        }
        return true;
    }

    // 斜めにすでにクイーンが存在しないかチェックする
    private boolean upLeftCheck(int[][] board, int row, int col) {

        // 上方向へのチェック
        for (int r = row, c = col; r >= 0 && c >= 0; r--, c--) {
            if (board[r][c] == 0) continue; return false;
        }
        // 下方向へのチェック
        for (int r = row, c = col; r < N && c < N; r++, c++) {
            if (board[r][c] == 0) continue; return false;
        }
        return true;
    }
}

*1:近藤嘉雪著,「定本Javaプログラマのためのアルゴリズムとデータ構造」,SBクリエイティブ,2011