N-Queens не печатает все решения - PullRequest
Новая
       60

N-Queens не печатает все решения

0 голосов
/ 18 февраля 2019

Я новичок в рекурсии и возвращении.Я пытаюсь завершить задачу N-Queen, чтобы напечатать все решения вместо одного и понять эти концепции.

Я думаю, что алгоритм реализован частично правильно, так как я получаю некоторые решения, но не все напечатано,Мой код на Java.

  • Для значения N = 4 я получаю 2 решения - это правильно
  • Для значения N = 5 я получаю 5 решений -на самом деле их 10
  • При значениях N = 8 я ничего не печатаю

Я не могу понять, какую ошибку я делаю.У меня есть идея понять, что 1-я королева должна идти в первом ряду, 2-я во втором и т. Д. Мне нужно выяснить, какой столбец уместен, очевидно, заботясь о диагонали для размещения королевы.

Любая помощь в указании меня в правильном направлении приветствуется.Мой код приведен ниже, и я попытался добавить комментарии, чтобы он помог с пониманием. 

public class nQueens {

    static class Queen {
        public Queen( int row, int column) {
            this.row = row;
            this.column = column;
        }
        int row = -1;
        int column = -1;
    }

    static ArrayList<Queen> queens = new ArrayList<Queen>();

    public static void main(String argv[]) {
        int n = 5;
        int[][] chessBoard = new int[n][n];
        int placed = 0;
        solve(n, chessBoard, placed);
    }

    public static void solve(int n, int[][] chessBoard, int placed) {
        // this means that all the queens have been placed
        if (placed == n) {
            System.out.println("**** Solution *****");
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    System.out.print(chessBoard[i][j] + " ");
                }
                System.out.println();
            }
        } else {
            // we know that each queen can be placed on each row
            int i = placed;
            // iterate through the columns
            for (int j = 0; j < n; j++) {
                if (chessBoard[i][j] != 1) {
                    if (isSafe(i, j)) {
                        chessBoard[i][j] = 1;
                        Queen queen = new Queen( i, j);
                        queens.add(queen);
                        placed = placed + 1;
                        // solve for the remaining number of queens
                        solve(n, chessBoard, placed);
                        // un-mark the spot
                        chessBoard[i][j] = 0;
                        // remove the placed queen
                        queens.remove(queens.size() - 1);
                        placed = placed - 1;
                    }
                }
            }
        }
    }

    public static boolean isSafe(int row, int column) {
        // this means that there are no queens on the board
        if (queens.isEmpty()) {
            return true;
        } else {
            for (int i = 0; i < queens.size(); i++) {
                // same column
                if (queens.get(i).column == column) {
                    return false;
                }
                // check diagonal
                int slope = Math.abs((queens.get(i).row - row) / (queens.get(i).column - column));
                if (slope == 1) {
                    return false;
                }
            }
        }
        return true;
    }
}

Ответы [ 2 ]

0 голосов
/ 19 февраля 2019

Альтернативное решение для isSafe() и class Queen

  • сделать шахматную доску классом для отслеживания статуса
  • recurse
    • клонировать текущую доскуstatus
    • установить ферзь и заблокировать все поля, доступные ей
    • передать клон вниз для следующей строки
  • запомнить столбец на строкупозиции для каждой королевы

Ниже приводится универсальный решатель, который передается в закрытии placer.Используя этот подход, легко использовать один и тот же решатель для ладей (placeRook()), рыцарей (placeKnight()) или епископов (placeBishop()).

Обратите внимание, что мое решение написано на Groovy,который также работает на JVM и очень близок к Java.Так что не должно быть проблем с переводом сочных битов алгоритма в Java. 

class ChessBoard {
    int N
    int lastIndex
    private boolean[][] board
    int solutions

    ChessBoard(int n) {
        board     = new boolean[n][n]
        N         = n
        lastIndex = n - 1
        solutions = 0
        this.each { int row, int column -> board[row][column] = true }
    }

    ChessBoard(ChessBoard orig) {
        N         = orig.getN()
        board     = new boolean[N][N]
        lastIndex = N - 1
        solutions = 0
        this.each { int row, int column -> board[row][column] = orig.getField(row, column) }
    }

    void each(Closure c) {
        (0..lastIndex).each { row ->
            (0..lastIndex).each { column -> c(row, column) }
        }
    }

    void print() {
        println " ${'-' * N}"
        (0..lastIndex).each { row ->
            print "|"
            (0..lastIndex).each { column -> print "${board[row][column] ? ' ' : 'X'}" }
            println "|"
        }
        println " ${'-' * N}"
    }

    int getN()                            { return N }
    int getSolutions()                    { return solutions }
    boolean getField(int row, int column) { return board[row][column] }

    void blockField(int row, int column)  {
        if ((row < 0) || (row > lastIndex))
            return
        if ((column < 0) || (column > lastIndex))
            return
        board[row][column] = false
    }

    List<Integer> getFree(int row)            {
        (0..lastIndex).findResults { int column -> board[row][column] ? column : null }
    }

    void placeQueen(int row, int column, boolean all = true) {
        if (all) {
            (0..lastIndex).each { offset ->
                blockField(row,    offset)                // row
                blockField(offset, column)                // column
                blockField(row + offset, column + offset) // diagonals
                blockField(row + offset, column - offset)
                blockField(row - offset, column + offset)
                blockField(row - offset, column - offset)
            }
        } else {
            blockField(row, column)
        }
    }

    // recursive solver
    void solve(ChessBoard previous, List<Integer> columns, int row, Closure placer) {
        List<Integer> free = previous.getFree(row)
        if (row < lastIndex) {
            // recurse
            free.each { column ->
                ChessBoard work = new ChessBoard(previous)
                columns[row] = column
                placer(work, row, column, true)
                solve(work, columns, row + 1, placer)
            }
        } else {
            // solutions
            free.each { column ->
                ChessBoard solution = new ChessBoard(N)
                columns[row] = column
                (0..lastIndex).each { placer(solution, it, columns[it], false) }
                println "Solution #${++solutions}:"
                solution.print()
            }
        }
    }

    // start recursion
    void solve(Closure placer) {
        List<Integer> columns = []
        solve(this, columns, 0, placer)
    }
}

board = new ChessBoard(8)
board.solve { ChessBoard work, int row, int column, boolean all -> work.placeQueen(row, column, all) }
println "Solutions: ${board.getSolutions()}"

Тестовый прогон: 

Solution #1:
 --------
|X       |
|    X   |
|       X|
|     X  |
|  X     |
|      X |
| X      |
|   X    |
 --------
...
Solution #92:
 --------
|       X|
|   X    |
|X       |
|  X     |
|     X  |
| X      |
|      X |
|    X   |
 --------
Solutions: 92

Если моя память мне не изменяет, 92 звучит правильнопроблема 8-королевы.Но прошло более 35 лет с тех пор, как я решил эту проблему в школе, используя итеративный подход в Паскале: -)

ОБНОВЛЕНИЕ улучшенное решение

  • splitисходный класс в ChessBoard для отслеживания состояния и Solver для алгоритма
  • россыпей для королев, грачей, слонов и рыцарей
  • вычисление решений для размеров от 1 до 8
  • создать таблицу уценок для результатов 
class ChessBoard {
    private int         N
    private int         lastIndex
    private boolean[][] state

    ChessBoard(int n) {
        N         = n
        lastIndex = N - 1
        state     = new boolean[N][N]
        (0..lastIndex).each { row ->
            (0..lastIndex).each { column ->
                setField(row, column, true)
            }
        }
    }

    ChessBoard(ChessBoard orig) {
        N         = orig.getN()
        lastIndex = N - 1
        state     = new boolean[N][N]
        (0..lastIndex).each { row ->
            (0..lastIndex).each { column ->
                setField(row, column, orig.getField(row, column))
            }
        }
    }

    int getN() {
        return N
    }

    boolean getField(int row, int column) {
        return state[row][column]
    }

    void setField(int row, int column, boolean free = false)  {
        if ((row < 0) || (row > lastIndex))
            return
        if ((column < 0) || (column > lastIndex))
            return
        state[row][column] = free
    }

    List<Integer> getFree(int row) {
        (0..lastIndex)
            .findResults { int column ->
            getField(row, column) ? column : null
        }
    }

    // for debugging only
    void print() {
        println " ${'-' * N}"
        (0..lastIndex).each { row ->
            print "|"
            (0..lastIndex).each { column -> print "${getField(row, column) ? ' ' : 'X'}" }
            println "|"
        }
        println " ${'-' * N}"
    }
}

class Solver {
    private int   N
    private int   lastIndex
    private int   solutions
    private int[] columns

    Solver(int n) {
        N         = n
        lastIndex = N - 1
        solutions = 0
        columns   = new int[N]
    }

    void printSolution(String label) {
        solutions++
        if (!label)
            return
        println "${N}-${label} solution #${solutions}"
        println " ${'-' * N}"
        (0..lastIndex).each { row ->
            int column = columns[row]
            println "|${' ' * column}X${' ' * (lastIndex - column)}|"
        }
        println " ${'-' * N}"
    }

    int getSolutions() {
        return solutions
    }

    void placeQueen(ChessBoard board, int row, int column) {
            // only modify fields from (row+1) downwards
            (1..(lastIndex - row)).each { offset ->
                board.setField(row + offset, column)          // column
                board.setField(row + offset, column + offset) // diagonals
                board.setField(row + offset, column - offset)
            }
    }

    void placeRook(ChessBoard board, int row, int column) {
        // only modify fields from (row+1) downwards
        (1..(lastIndex - row)).each { offset ->
            board.setField(row + offset, column) // column
        }
    }

    void placeBishop(ChessBoard board, int row, int column) {
        // only modify fields from (row+1) downwards
        (1..(lastIndex - row)).each { offset ->
            board.setField(row + offset, column + offset) // diagonals
            board.setField(row + offset, column - offset)
        }
    }

    static void placeKnight(ChessBoard board, int row, int column) {
        // only modify fields from (row+1) downwards
        board.setField(row + 1, column - 2)
        board.setField(row + 1, column + 2)
        board.setField(row + 2, column - 1)
        board.setField(row + 2, column + 1)
    }

    // recursive solver
    void solve(ChessBoard previous, int row, Closure placer, String label) {
        List<Integer> free = previous.getFree(row)
        if (row < lastIndex) {
            // recurse
            free.each { column ->
                ChessBoard work = new ChessBoard(previous)
                columns[row] = column
                placer(this, work, row, column)
                solve(work, row + 1, placer, label)
            }
        } else {
            // solutions
            free.each { column ->
                columns[row] = column
                printSolution(label)
            }
        }
    }

    // start recursion
    int solve(Closure placer, String label = null) {
        solve(new ChessBoard(N), 0, placer, label)
        return solutions
    }
}

Map<String, Closure> placers = [
    'Queens':  { Solver solver, ChessBoard board, int row, int column -> solver.placeQueen(board,  row, column) },
    'Rooks':   { Solver solver, ChessBoard board, int row, int column -> solver.placeRook(board,   row, column) },
    'Bishops': { Solver solver, ChessBoard board, int row, int column -> solver.placeBishop(board, row, column) },
    'Knights': { Solver solver, ChessBoard board, int row, int column -> solver.placeKnight(board, row, column) },
]
Map<String, List<Integer>> solutions = [:]

// generate solutions up to maxN
int     maxN  = 8
boolean print = false
placers
    .keySet()
    .each { String key ->
        Closure placer = placers[key]
        List<Integer> results = []
        (1..maxN).each { N ->
            results.push(new Solver(N).solve(placer, print ? key : null))
        }
        solutions[key] = results
    }

// generate markdown table from solutions
List lines = []
    (0..maxN).each { lines[it] = [it ?: 'Size'] }
[
    'Queens',
    'Rooks',
    'Bishops',
    'Knights',
].each { key ->
    List<Integer> results = solutions[key]
    lines[0].push(key)
    (1..maxN).each { lines[it].push(results[it - 1]) }
}

lines.each { line -> println line.join('|') }
return

Таблица результатов: 

| Size | Queens | Rooks | Bishops | Knights |
|------|--------|-------|---------|---------|
|   1  |      1 |     1 |       1 |       1 |
|   2  |      0 |     2 |       2 |       4 |
|   3  |      0 |     6 |       5 |       9 |
|   4  |      2 |    24 |      24 |      52 |
|   5  |     10 |   120 |     125 |     451 |
|   6  |      4 |   720 |     796 |    4898 |
|   7  |     40 |  5040 |    5635 |   67381 |
|   8  |     92 | 40320 |   48042 | 1131382 |
|------|--------|-------|---------|---------|
0 голосов
/ 19 февраля 2019

Проблема в следующем: 

int slope = Math.abs((queens.get(i).row - row) / (queens.get(i).column - column));
if (slope == 1) {
    return false;
}

Вы приводите slope к целому числу.Это означает, что наклон 1.5 или 1.3 становится 1 и в результате вы возвращаете false, даже если королева не находится на этой диагонали.(обратите внимание, что деление java является целочисленным делением, поэтому вам нужно сначала привести либо делитель, либо дивиденд к плавающей запятой, чтобы получить вывод с плавающей запятой), чтобы учесть наклоны с плавающей запятой: 

float tmp = (queens.get(i).row - row);
float slope = Math.abs(tmp/ (queens.get(i).column - column));
if (slope == 1) {
    return false;
}
...