---
title: Nクイーン問題
tags: []
categories: ["Programming", "Algorithm", "Search", "NQueens"]
date: 2011-07-20T15:31:45Z
updated: 2011-07-20T15:31:45Z
---

探索問題復習シリーズその3。Nクイーン問題を解きます。

今度は最短経路とか関係ないので深さ優先探索で解きます。新規に生成される状態が被ることもないので訪問済みの状態を記憶する必要もないですね。

    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    import java.util.Stack;
    
    public class NQueens {
        static final int N = 8;
    
        static class State {
            char[][] board = new char[N][N];
            int currentRow = 0;
    
            {
                // 初期化
                for (int i = 0; i < N; i++)
                    Arrays.fill(board[i], '.');
            }
    
            List<State> movableState() {
                List<State> states = new ArrayList<State>();
                if (currentRow < N) {
                    for (int i = 0; i < N; i++) {
                        char[][] b = copyBoard();
                        b[currentRow][i] = 'Q';
                        if (isValidBoard(b, currentRow, i)) {
                            State s = new State();
                            s.board = b;
                            states.add(s);
                        }
                    }
                }
                for (State s : states) {
                    s.currentRow = currentRow + 1;
                }
                return states;
            }
    
            private char[][] copyBoard() {
                char[][] b = new char[N][N];
                for (int i = 0; i < N; i++) {
                    b[i] = board[i].clone();
                }
                return b;
            }
    
            private boolean isValidBoard(char[][] b, int r, int c) {
                // 行チェック
                for (int i = 0; i < r; i++) {
                    if (b[i][c] == 'Q')
                        return false;
                }
                // 列チェック
                for (int i = 0; i < c; i++) {
                    if (b[r][i] == 'Q')
                        return false;
                }
                // 左斜めチェック
                for (int i = r - 1, j = c - 1; i >= 0 && j >= 0; i--, j--) {
                    if (b[i][j] == 'Q')
                        return false;
                }
                // 右斜めチェック
                for (int i = r - 1, j = c + 1; i >= 0 && j < N; i--, j++) {
                    if (b[i][j] == 'Q')
                        return false;
                }
                return true;
            }
    
            boolean isGoal() {
                return currentRow == N;
            }
    
            void pringBoard() {
                for (char[] r : board) {
                    System.out.println(Arrays.toString(r));
                }
            }
        }
    
        public static void main(String[] args) {
            State init = new State();
            Stack<State> open = new Stack<State>();
            open.add(init);
    
            while (!open.isEmpty()) {
                State s = open.pop();
                for (State next : s.movableState()) {
                    if (next.isGoal()) {
                        next.pringBoard();
                        return; // returnしなければ全通り列挙できる
                    } else {
                        open.add(next);
                    }
                }
            }
        }
    }

実行結果


    [., ., ., ., ., ., ., Q]
    [., ., ., Q, ., ., ., .]
    [Q, ., ., ., ., ., ., .]
    [., ., Q, ., ., ., ., .]
    [., ., ., ., ., Q, ., .]
    [., Q, ., ., ., ., ., .]
    [., ., ., ., ., ., Q, .]
    [., ., ., ., Q, ., ., .]