バックトラック法
バックトラック法とは
バックトラック法とは、問題への解のすべてを系統的かつ効率的に探索する方法です。 一般的に、ある問題の答えの組み合わせのすべてを網羅的に試行すると、解に至るまでの組み合わせが膨大になり、解が得られない。ということが起こりえます。バックトラック法の例として有名なのが、8クイーン問題です。8クイーン問題を一般化した問題がNクイーン問題です。
8クイーン問題
8クイーン問題とは、「タテ・ヨコ・ナナメに効きがあるクイーンを、8×8マスの盤上に、互いに効きがないように8つのクイーンを配置する」という問題です。タテ・ヨコ・ナナメに効きがないようにクイーンを配置できれば成功、そうでなければ失敗とします。問題としては非常にシンプルながら、クイーンを配置できるすべての組み合わせを網羅したのち、題意を満たすクイーンの配置を調べるという方法だと組み合わせが膨大になります。つまり、盤のマスは8*8=64つあり、1つ目のクイーンを置くマスの選び方は64通り、2つ目は63通り、、、とすると8つのマスの選び方は
つ存在することになります。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; } }
