Пример алгоритма 8-Queens?

Question

Кто-нибудь знает хорошие / сжатые примеры алгоритмов для 8-куин ? Я сделал поиск в Интернете и не нашел ни одного хорошего примера.

Answer 1

Вот простая реализация Java наивного рекурсивного алгоритма;это должно быть поучительно.

public class NQueens {
    final static int N = 4;
    static int[] position = new int[N];

    public static void main(String[] args) {
        solve(0);
    }

    static boolean isSafe(int k, int p) {
//      for (int i = 1; i <= k; i++) {
//          int other = position[k - i];
//          if (other == p || other == p - i || other == p + i) {
//              return false;
//          }
//      }
        return true;
    }
    static void solve(int k) {
        if (k == N) {
            System.out.println(java.util.Arrays.toString(position));
        } else {
            for (char p = 0; p < N; p++) {
                if (isSafe(k, p)) {
                    position[k] = p;
                    solve(k+1);
                }
            }
        }
    }
}

Обратите внимание, что isSafe содержит закомментированные строки прямо сейчас;это сделано специально.С этими комментариями программа становится рекурсивным генератором кортежей N, где каждое значение находится между 0 (включительно) и N (эксклюзивом).Таким образом, программа как есть генерирует следующий вывод:

[0, 0, 0, 0]
[0, 0, 0, 1]
[0, 0, 0, 2]
[0, 0, 0, 3]
[0, 0, 1, 0]
[0, 0, 1, 1]
[0, 0, 1, 2]
[0, 0, 1, 3]
:
:
[3, 3, 3, 0]
[3, 3, 3, 1]
[3, 3, 3, 2]
[3, 3, 3, 3]

Эта генерация кортежа N является конкретной подзадачей проблемы NQueens.Уже есть много вопросов о стековом потоке о том, как написать N -несложенные циклы, когда вы не знаете, что такое N.Я чувствую, что необходимо временно остановиться на этой проблеме и сначала понять ее решение, а isSafe закомментировано просто return true;, чтобы сначала почувствовать, что делает рекурсия.

Как только выВам удобно, что этот генератор рекурсивных кортежей работает, просто раскомментируйте эти строки, и вы получите простой, наивный, но работающий решатель NQueens.Если строки N=5 и isSafe не закомментированы, программа генерирует следующий вывод:

[0, 2, 4, 1, 3]
[0, 3, 1, 4, 2]
[1, 3, 0, 2, 4]
[1, 4, 2, 0, 3]
[2, 0, 3, 1, 4]
[2, 4, 1, 3, 0]
[3, 0, 2, 4, 1]
[3, 1, 4, 2, 0]
[4, 1, 3, 0, 2]
[4, 2, 0, 3, 1]

Каждая строка является решением проблемы 5 ферзей.i -й элемент массива обозначает позицию строки i -й королевы, помещенной в i -й столбец (все индексы основаны на 0).Итак, первое решение на доске выглядит следующим образом:

[0,2,4,1,3]

 Q · · · ·
 · · · Q ·
 · Q · · ·
 · · · · Q
 · · Q · ·

Я оставлю это в качестве упражнения, чтобы понять, почему isSafe работает, и как печатать макет платы, и как реализовать быстрее, ноболее сложные рекурсивные алгоритмы.

Счастливого обучения.

Answer 2

для размещения ферзя в строке r:

if r = 0 then you're done -- return ok
for each c [1 .. 8]:
  if (r,c) is safe:
    mark (r,c)
    if you can place queen on row r-1 then return ok
    unmark (r,c)  (if you're here, this c won't work)
return not ok     (if you're here, no c generated a solution)

(r, c) безопасно, если для каждой строки [r + 1 .. 8]:

• (строка c) не помечена
• c - (строка - r) <1 или (строка c - (строка - r)) не отмечена </li>
• c + (строка - r)> 8 или (строка, c + (строка - r)) не помечена

Answer 3

Суть проблемы 8 ферзей часто состоит в том, чтобы просто показать силу поиска в сочетании с сокращением.Вы можете в значительной степени выполнить поиск методом грубой силы в пространстве поиска, но исключите любое частичное решение, если оно нарушает ограничения решения (т. Е. Одна королева проверяет другую).легко решаемо.

Если вам нужны более эффективные решения, которые были бы полезны, например, для 100 или 1000 королев, это другая история, и вы можете посмотреть на материал в википедии.Но для 8 королев достаточно грубой силы и обрезки.(т. е. сначала выполнить поиск в глубине пространства поиска, исключив любой промежуточный узел, включающий проверяемую королеву).

Answer 4

// Demonstration of the 8-Queens problem

// This handout shows interactively how the 8-Queens problem can be solved
// using recursion and backtracking (with exhaustive search with pruning).

// As far as this code goes, some improvements can definitely be made,
// especially with regard to the interface and the flexibility for the
// user.  However, it does an adequate job of showing the steps involved in
// solving the 8-Queens problem.

import javax.swing.*;
import java.awt.*;
import java.awt.geom.*;
import java.awt.event.*;

public class JRQueens extends JFrame implements Runnable
{
    public ChessSquare [][] squares;
    public boolean [] saferow;   // is the row empty?  true or false
    public boolean [] safeleftdiag; // is the left (from upper right to lower left)
    // diagonal unthreatened?  true or false
    public boolean [] saferightdiag; // is the right (from upper left to lower right)
    // diagonal unthreatened?  true or false

    private ShapePanel drawPanel; // panel for the board to be drawn -- see details
    // in class definition below
    private JLabel info;  // informative label
    private JButton runDemo; // button to allow interaction
    private Thread runThread; // thread to allow "motion"
    private int delay;   // delay between moves
    private PauseClass pauser; // class to allow execution to pause in between
    // solutions -- see details in definition below
    private boolean paused;  // is execution paused?  true or false
    private int sol, calls;

    public JRQueens(int delta)
    {
        super("Interactive 8 Queens Problem");
        delay = delta;
        drawPanel = new ShapePanel(450, 450);

        runDemo = new JButton("See Solutions");  // Set up button
        ButtonHandler bhandler = new ButtonHandler();
        runDemo.addActionListener(bhandler);

        info = new JLabel("The 8 Queens Problem", (int) CENTER_ALIGNMENT);

        Container c = getContentPane();   // Set up layout
        c.add(drawPanel, BorderLayout.CENTER);
        c.add(info, BorderLayout.NORTH);
        c.add(runDemo, BorderLayout.SOUTH);

        squares = new ChessSquare[8][8]; // initialize variables
        saferow = new boolean[8];
        safeleftdiag = new boolean[15];
        saferightdiag = new boolean[15];
        int size = 50;
        int offset = 25;
        for (int row = 0; row < 8; row++)
        {
            saferow[row] = true;  // all rows are safe
            for (int col = 0; col < 8; col++)
            {
                squares[row][col] = new ChessSquare(offset + col*size, 
                offset + row*size, 
                size, size);
            }
        }

        for (int i = 0; i < 15; i++)
        {                               // initialize all diagonals to safe
            safeleftdiag[i] = true;
            saferightdiag[i] = true;
        }
        sol = 0;
        calls = 0;

        runThread = null;

        setSize(475, 525);
        setVisible(true);
    }

    // Is the current location safe?  We check the row and both diagonals.
    // The column does not have to be checked since our algorithm proceeds in
    // a column by column manner.
    public boolean safe(int row, int col)
    {
        return (saferow[row] && safeleftdiag[row+col] &&
        saferightdiag[row-col+7]);
    }

    // This recursive method does most of the work to solve the problem.  Note
    // that it is called for each column tried in the board, but, due to
    // backtracking, will overall be called many many times.  Each call is from
    // the point of view of the current column, col.
    public void trycol(int col)
    {
        calls++; // increment number of calls made
        for (int row = 0; row < 8; row++)    // try all rows if necessary
        {
            // This test is what does the "pruning" of the execution tree --
            // if the location is not safe we do not bother to make a recursive
            // call from that position, saving overall many thousands of calls.
            // See notes from class for details.
            if (safe(row, col))
            {
                // if the current position is free from a threat, put a queen
                // there and mark the row and diags as unsafe
                saferow[row] = false;
                safeleftdiag[row+col] = false;
                saferightdiag[row-col+7] = false;
                (squares[row][col]).occupy();
                repaint();

                if (col == 7)      // queen safely on every column, announce
                {                  // solution and pause execution
                    sol++;
                    info.setText("Solution " + sol + " Found After " + calls + " Calls");
                    runDemo.setText("Click to Continue");
                    runDemo.setEnabled(true);
                    pauser.pause();
                }
                else
                {
                    // Still more columns left to fill, so delay a bit and then
                    // try the next column recursively
                    try
                    {
                        Thread.sleep(delay);
                    }
                    catch (InterruptedException e)
                    {
                        System.out.println("Thread error B");
                    }

                    trycol(col+1);  // try to put a queen onto the next column
                }

                saferow[row] = true;               // remove the queen from
                safeleftdiag[row+col] = true;      // the current row and
                saferightdiag[row-col+7] = true;   // unset the threats. The
                (squares[row][col]).remove();      // loop will then try the
                // next row down
            } 
        }
    // Once all rows have been tried, the method finishes, and execution
    // backtracks to the previous call.
    }

    // This method executes implicitly when the Thread is started.  Note that
    // its main activity is the call trycol(0), which starts the recursive
    // algorithm on its way.
    public void run()
    {
        paused = false;
        pauser = new PauseClass();
        trycol(0);
        repaint();
        info.setText("Program Completed: " + sol + " Solutions, "
        + calls + " Calls, "
        + (8*calls) + " iterations ");
    }

    public static void main(String [] args)
    {
        // Use the delay value entered by the user, or use 100 if no
        // value is entered.
        int delay;
        if (args != null && args.length >= 1)
        delay = Integer.parseInt(args[0]);
        else
        delay = 100;
        JRQueens win = new JRQueens(delay);

        win.addWindowListener(
            new WindowAdapter()
            {
                public void windowClosing(WindowEvent e)
                { System.exit(0); }
            }
        );
    }

    // This class is used to enable the execution to pause between
    // solutions.  The Java details of this class have to do with monitors
    // and synchronized Threads and are beyond the scope of the CS 1501
    // course.  However, if you are interested in learning more about these
    // Java features, feel free to look them up in the Java API.
    private class PauseClass
    {
        public synchronized void pause()
        {
            paused = true;
            try
            {
                wait();
            }
            catch (InterruptedException e)
            {
                System.out.println("Pause Problem");
            }
        }

        public synchronized void unpause()
        {
            paused = false;
            notify();
        }
    }

    // Class to handle button.  For more on the Java details, see
    // the API online.
    private class ButtonHandler implements ActionListener
    {
        public void actionPerformed(ActionEvent e)
        {
            if (e.getSource() == runDemo)
            {
                if (!paused)
                {
                    runDemo.setEnabled(false);
                    info.setText("Searching for Solutions");
                    runThread = new Thread(JRQueens.this);
                    runThread.start();
                }
                else
                {
                    runDemo.setEnabled(false);
                    info.setText("Searching for Solutions");
                    pauser.unpause();
                }
                repaint();
            }
        }
    }

    // Inner class to represent a square on the board.  This class extends
    // Rectangle2D.Double, which can be drawn graphically by the draw() method
    // of the Graphics2D class.  The main additions I have made in the subclass
    // are the occupied variable and the drawing of the Q if the space is
    // occupied.
    private class ChessSquare extends Rectangle2D.Double
    {
        private boolean occupied;

        public ChessSquare(double x1, double y1, double wid, double hei)
        {
            super(x1, y1, wid, hei);
            occupied = false;
        }

        public void draw(Graphics2D g2d)
        {
            g2d.draw(this);
            int x = (int) this.getX();
            int y = (int) this.getY();
            int sz = (int) this.getWidth();

            if (occupied)
            {
                g2d.setFont(new Font("Serif", Font.BOLD, 36));
                g2d.drawString("Q", x+10, y+sz-10);
            }
        }

        public void occupy()
        {
            occupied = true;
        }

        public void remove()
        {
            occupied = false;
        }

        public boolean isOccupied()
        {
            return occupied;
        }
    }

    // Class that allows the board to be rendered in a nice way.
    // See that Java API or a good book on Java graphics for more
    // details about this class.
    private class ShapePanel extends JPanel
    {
        private int prefwid, prefht;

        public ShapePanel (int pwid, int pht)
        {
            prefwid = pwid;
            prefht = pht;
        }

        public Dimension getPreferredSize()
        {
            return new Dimension(prefwid, prefht);
        }

        public void paintComponent (Graphics g)
        {
            super.paintComponent(g);
            Graphics2D g2d = (Graphics2D) g;
            for (int i = 0; i < 8; i++)
            {
                for (int j = 0; j < 8; j++)
                {
                    (squares[i][j]).draw(g2d);
                }
            }    
        }
    }
}

Answer 5

Это простое решение в C #.

//----N Queens ----
public static bool NQueens(bool[,] board, int x)
{
      for (int y = 0; y < board.GetLength(1); y++)
      {
          if (IsAllowed(board, x, y))
          {
               board[x, y] = true;
               if (x == board.GetLength(0) - 1 || NQueens(board, x + 1))
               {
                   return true;
               }
               board[x, y] = false;
          }
     }
     return false;
}
//verify diagonals, column and row from i=0 to x because from x to down it dont put anything
private static bool IsAllowed(bool[,] board, int x, int y)
{
    for (int i = 0; i <= x; i++)
    {
        if (board[i, y] || (i <= y && board[x - i, y - i]) || (y + i < board.GetLength(0) && board[x - i, y + i]))
        {
            return false;
        }
    }
    return true;
}

С http://yadiragarnicabonome.com/n-queens-problem/

Answer 6

public class NQueensSolver
{
    private readonly List<int[]> _solutions = new List<int[]>();
    private readonly int[] _current;
    public int N { get; private set; }

    public NQueensSolver(int n)
    {
        N = n;
        _current = new int[N];
    }

    public IList<int[]> FindAllFormations()
    {
        PopulateFormations(0);
        return _solutions;
    }

    private void PopulateFormations(int row)
    {
        if (row == N)
        {
            _solutions.Add(_current.ToArray());
            return;
        }

        for (int col = 0; col <= N-1; col++)
        {
            if (Threatened(row, col))
                continue;

            _current[row] = col;
            PopulateFormations(row + 1);
        }
    }

    private bool Threatened(int row, int col)
    {
        for (int i = 0; i <= row - 1; i++)
            if (_current[i] == col || row - i == Math.Abs(col - _current[i]))
                return true;

        return false;
    }
}

Некоторые тесты:

[TestMethod]
public void TestNQueens()
{
  Assert.AreEqual(1, new NQueensSolver(1).FindAllFormations().Count);
  Assert.AreEqual(0, new NQueensSolver(2).FindAllFormations().Count);
  Assert.AreEqual(0, new NQueensSolver(3).FindAllFormations().Count);
  Assert.AreEqual(2, new NQueensSolver(4).FindAllFormations().Count);
  Assert.AreEqual(10, new NQueensSolver(5).FindAllFormations().Count);
  Assert.AreEqual(4, new NQueensSolver(6).FindAllFormations().Count);
  Assert.AreEqual(40, new NQueensSolver(7).FindAllFormations().Count);
  Assert.AreEqual(92, new NQueensSolver(8).FindAllFormations().Count);
  Assert.AreEqual(352, new NQueensSolver(9).FindAllFormations().Count);
  Assert.AreEqual(724, new NQueensSolver(10).FindAllFormations().Count);
}

Answer 7

В EWD316 Дейкстра довольно формально находит решение проблемы восьми королев. Попробуйте, вам может понравиться!

Answer 8

Вот простое решение на C # Я думаю, что это работает

public static class EightQueens
    {
        static   int[] board = new int[8];
        static int MaxRows = 8, MaxCols = 8;
        public static int[] GetPosition()
        {
            if (GetPosition(0)) return board;
            else return null;
        }
        public static bool IsCollision(int row, int col)
        {
            for (int i = 0; i < col; i++)
            {
                if (board[i] == row) return true; // Same Row
                if ((board[i] + col - i == row) || (board[i] - col + i == row))
                    return true;
            }
            return false;

        }
        public static bool GetPosition(int col)
        {
            if (col == MaxCols) return true;
            for (int row = 0; row < MaxRows; row++)
                if (!IsCollision(row, col))
                {
                    board[col] = row;
                    if (GetPosition(col + 1)) return true;
                }
            return false;

        }
    }

Answer 9

С Википедия :

Эта эвристика решает n королев для любого nn ≥ 4 или n = 1:

1. Разделите n на 12.Запомните остаток (n = 8 для загадки о восьми королевах).
2. Напишите список четных чисел от 2 до n по порядку.
3. Если остаток равен 3 или 9, переместите 2в конец списка.
4. Добавляйте нечетные числа от 1 до n по порядку, но, если остаток равен 8, переключайте пары (т. е. 3, 1, 7, 5, 11, 9,…).
5. Если остаток равен 2, поменяйте местами 1 и 3, затем переместите 5 в конец списка.
6. Если остаток 3 или 9, переместите 1 и 3 вконец списка.
7. Поместите королеву первого столбца в строку с первым номером в списке, поместите королеву второго столбца в строку со вторым номером в списке и т. д.

Answer 10

Я решил развернуть C ++, посмотрите правильные шаги на терминале.

Вы можете увидеть более подробную информацию о my queen.cpp

функция размещения шахмат

void amo::Queen::place(int probing, int n) {
    if (n != row || n != col ) {
        if (chess != nullptr) {
            for (int i=0;i<row;i++) delete *(chess+i);
            delete chess;
        }   
        row = n;
        col = n;
        chess = new int*[n];
        for (int i=0;i<n;i++) {
            *(chess+i) = new int[col];
            for (int j=0; j<col; j++) 
                *(*(chess+i)+j) = 100*(i+1)+j;
        }
    }
    if (probing >= n) {
        ans += 1;
        std::cout << GREEN <<"[Queen::place()]: returns when met the pass-the-end of probing which means deduced one of answer:" << ans << WHITE << std::endl;
        for (std::vector<int>::iterator it=queens.begin(); it!=std::next(queens.begin(), n); it++)
            collect(moves, 1, std::distance(queens.begin(), it), *it);
        traverse(moves);
        moves.clear();
        return;
    }
    for (int pruning=0; pruning<col; pruning++) {
        track++;
        //traverse(probing, pruning);
        //if (probing==n-1 && pruning==col-1) std::cout << RED <<"[Queen::place()]: track:" << track << WHITE << std::endl; //final track=4^4+4^3+4^2+4^1=340 if n=4 or track=3^3+3^2+3^1=39 if n=3
        if (!check(probing, pruning)) {
        //if (false) { //watching all moves
            //std::cout << "[Queen::place()]: going to prune" << WHITE << std::endl;
            /**
             * 'prunes' when met one of dead ends of this probing at this pruning
             */
            continue;
        }
        else { //found one of rights of this probing at this pruning and digs into the one more deeper 
            //std::cout << "[Queen::place()]: going to probe" << WHITE << std::endl;
            if (queens.size() < n) queens.resize(n);
            queens.at(probing) = pruning;
            /**
             * 'probes' one more deeper by making one more call stack returning back here as backtracking and proceeding to another pruning
             */ 
            place(probing+1, n);
        }
    }
    /**
     * 'backtracks'
     */ 
    return;
}

и функция для проверки, являются ли ходы решениями

bool amo::Queen::check(int row, int column) {
    if (row == 0) {
        //std::cout << CYAN << "okay chess[" << row <<"][" << column << "]" << WHITE << std::endl;
        return true;
    }
    for (std::vector<int>::iterator it=queens.begin(); it!=std::next(queens.begin(), row); it++) {
        int placed_row = std::distance(queens.begin(), it);
        int placed_column = queens.at(placed_row);
        if (placed_column == column) {
            //std::cout << MAGENTA << "not across,   queen[" << placed_row << "][" << placed_column << "] and chess[" << row <<"][" << column << "]" << WHITE << std::endl;
            return false;
        }
        if (std::abs(placed_column-column) == std::abs(placed_row-row)) {
            //std::cout << MAGENTA << "not diagonal, queen[" << placed_row << "][" << placed_column << "] and chess[" << row <<"][" << column << "]" << WHITE << std::endl;
            return false;
        }
    }
    //std::cout << CYAN << "okay chess[" << row <<"][" << column << "]" << WHITE << std::endl;
    return true;
}