8-皇后算法示例？

Question

有人知道8-queens的好的/简洁的算法示例吗？ 我进行了网络搜索，但没有找到任何好的例子。

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 是什么时，stackoverflow 上已经有很多关于如何编写 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

8 皇后问题的要点通常只是为了说明搜索与剪枝相结合的威力。您几乎可以对搜索空间进行强力搜索，但当它违反解决方案的约束时（即一个皇后检查另一个皇后），请消除任何部分解决方案。

只需使用这种修剪，8皇后就可以轻松解决。

如果您想要更有效的解决方案，例如对 100 或 1000 个皇后有用，那就是另一回事了，您可以查看维基百科中的内容。但对于 8 皇后来说，暴力破解和修剪就足够了。 （即对搜索空间进行深度优先搜索，消除任何包含检查中的皇后的中间节点）。

Answer 3

将皇后放在 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]:

• (row,c) 未标记为
• c - (row - r) < 1或(row，c-(row-r))未标记
• c+(row-r)> 8 或 (row, c + (row - r)) 未标记

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

来自维基百科：

对于任何 nn ≥ 4 或 n = 1，此启发式解决了 n 个皇后：

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 6

这是一个简单的 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 7

在 EWD316 中，Dijkstra 导出了八皇后问题的解决方案相当正式。尝试一下，你可能会喜欢它！

Answer 8

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 9

这是 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;
}

Answer 10

在 TheWalnut.io 中，有 N 皇后的可视化：它被视为约束满意度问题并使用本地搜索算法（具有最小冲突启发式）来解决它。 代码（Javascript）也在那里。

可视化是针对 N == 8 的特殊情况，但它可以更改为任何 N。

Answer 11

    private const int Size = 8;
    private static readonly bool[,] chessboard = new bool[Size, Size];

    //The Rows are 8, numbered from 0 to 7.
    //The Columns are 8, numbered from 0 to 7.
    //The left diagonals are 15, numbered from -7 to 7. following formula : leftDiag = col - row.
    //The right diagonals are 15, numbered from 0 to 14 by the formula: rightDiag = col + row.
    private static readonly HashSet<int> AttackedRows = new HashSet<int>();

    private static readonly HashSet<int> AttackedCols = new HashSet<int>();

    private static readonly HashSet<int> AttackedLeftDiagonals = new HashSet<int>();

    private static readonly HashSet<int> AttackedRightDiagonals = new HashSet<int>();

    private static int solutionsFound;

    private static void Main(string[] args)
    {
        PutQueens(0);
        Console.WriteLine(solutionsFound);
    }

    private static void PutQueens(int row)
    {
        if (row == Size)
        {
            PrintBoard();
            solutionsFound++;
        }

        else
        {
            for (var col = 0; col < Size; col++)
            {
                if (CanPlaceQueen(row, col))
                {
                    MarkAllAttackedPositons(row, col);
                    PutQueens(row + 1);
                    UnMarkAllAttackedPositons(row, col);
                }
            }
        }
    }

    private static void UnMarkAllAttackedPositons(int row, int col)
    {
        AttackedRows.Remove(row);
        AttackedCols.Remove(col);
        AttackedLeftDiagonals.Remove(col - row);
        AttackedRightDiagonals.Remove(col + row);
        chessboard[row, col] = false;
    }

    private static void MarkAllAttackedPositons(int row, int col)
    {
        AttackedRows.Add(row);
        AttackedCols.Add(col);
        AttackedLeftDiagonals.Add(col - row);
        AttackedRightDiagonals.Add(col + row);
        chessboard[row, col] = true;
    }

    private static bool CanPlaceQueen(int row, int col)
    {
        var positionOccuppied = AttackedCols.Contains(col) || AttackedRows.Contains(row)
                                || AttackedLeftDiagonals.Contains(col - row)
                                || AttackedRightDiagonals.Contains(col + row);
        return !positionOccuppied;
    }

    private static void PrintBoard()
    {
        for (var row = 0; row < Size; row++)
        {
            for (var col = 0; col < Size; col++)
            {
                Console.Write(chessboard[row, col] ? "Q " : "- ");
            }
            Console.WriteLine();
        }
        Console.WriteLine();
    }

Answer 12

我用 Python 写了一个详细的、带注释的 N 皇后问题示例，并将其放在 GitHub 上。看看吧！

Answer 13

我通过部署 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;
}

Answer 14

SQL：

with tx1 as (select 1 as k union all select t2.k + 1 from tx1 as t2 where t2.k < 8)

select *
from tx1 as x1
join tx1 as x2 on 
    x2.k <> x1.k and 
    x2.k <> x1.k + 1 and x2.k <> x1.k - 1
join tx1 as x3 on 
    x3.k <> x1.k and x3.k <> x2.k and 
    x3.k <> x2.k + 1 and x3.k <> x2.k - 1 and
    x3.k <> x1.k + 2 and x3.k <> x1.k - 2
join tx1 as x4 on 
    x4.k <> x1.k and x4.k <> x2.k and x4.k <> x3.k and
    x4.k <> x3.k + 1 and x4.k <> x3.k - 1 and
    x4.k <> x2.k + 2 and x4.k <> x2.k - 2 and
    x4.k <> x1.k + 3 and x4.k <> x1.k - 3
join tx1 as x5 on 
    x5.k <> x1.k and x5.k <> x2.k and x5.k <> x3.k and x5.k <> x4.k and
    x5.k <> x4.k + 1 and x5.k <> x4.k - 1 and
    x5.k <> x3.k + 2 and x5.k <> x3.k - 2 and
    x5.k <> x2.k + 3 and x5.k <> x2.k - 3 and 
    x5.k <> x1.k + 4 and x5.k <> x1.k - 4
join tx1 as x6 on 
    x6.k <> x1.k and x6.k <> x2.k and x6.k <> x3.k and x6.k <> x4.k and x6.k <> x5.k     and
    x6.k <> x5.k + 1 and x6.k <> x5.k - 1 and
    x6.k <> x4.k + 2 and x6.k <> x4.k - 2 and
    x6.k <> x3.k + 3 and x6.k <> x3.k - 3 and 
    x6.k <> x2.k + 4 and x6.k <> x2.k - 4 and 
    x6.k <> x1.k + 5 and x6.k <> x1.k - 5
join tx1 as x7 on 
    x7.k <> x1.k and x7.k <> x2.k and x7.k <> x3.k and x7.k <> x4.k and x7.k <> x5.k and x7.k <> x6.k and
    x7.k <> x6.k + 1 and x7.k <> x6.k - 1 and
    x7.k <> x5.k + 2 and x7.k <> x5.k - 2 and
    x7.k <> x4.k + 3 and x7.k <> x4.k - 3 and 
    x7.k <> x3.k + 4 and x7.k <> x3.k - 4 and 
    x7.k <> x2.k + 5 and x7.k <> x2.k - 5 and
    x7.k <> x1.k + 6 and x7.k <> x1.k - 6
join tx1 as x8 on 
    x8.k <> x1.k and x8.k <> x2.k and x8.k <> x3.k and x8.k <> x4.k and x8.k <> x5.k and x8.k <> x6.k and x8.k <> x7.k and
    x8.k <> x7.k + 1 and x8.k <> x7.k - 1 and
    x8.k <> x6.k + 2 and x8.k <> x6.k - 2 and
    x8.k <> x5.k + 3 and x8.k <> x5.k - 3 and 
    x8.k <> x4.k + 4 and x8.k <> x4.k - 4 and 
    x8.k <> x3.k + 5 and x8.k <> x3.k - 5 and
    x8.k <> x2.k + 6 and x8.k <> x2.k - 6 and
    x8.k <> x1.k + 7 and x8.k <> x1.k - 7
order by 1,2,3,4,5,6,7,8

Answer 15

我的解决方案
https://jsfiddle.net/coder039/2Ljxtus3/3/

const log = (...args) => {
  // console.log(...args)
  document.write(...args)
  document.write('<br />')
}

// get the print function (for printing the board)
const getPrint = (n) => (arr) => {
  const print = () => {
    let str = ''
    for (let i = 1; i <= n; i++) {
      for (let j = 1; j <= n; j++) {
        str += !!arr.find((o) => o.row === i && o.col === j) ? ' x' : ' o'
      }
      str += `<br />`
    }
    log(str)
  }

  print()
}

const head = (arr) => {
  return arr[0]
}

const tail = (arr) => {
  const [, ...a] = arr
  return a
}

const makePoint = ({
  row,
  col
}) => {
  return {
    row,
    col
  }
}

// check if 2 points attacking each other
const checkTwoPoint = (p1, p2) => {
  const {
    row: row1,
    col: col1
  } = p1
  const {
    row: row2,
    col: col2
  } = p2

  // check not attacking by same row or same col
  if (row1 === row2 || col1 === col2) {
    return false
  }

  // check not attacking by same diagonal line
  if (Math.abs(row1 - row2) === Math.abs(col1 - col2)) {
    return false
  }

  return true
}

// check if one point attacking any point in a list of points (assume list of points includes all points that not attacking each others)
const checkOnePointAndListPoint = (point, ls) => {
  if (ls.length === 0) {
    return true
  }

  return (
    checkTwoPoint(point, head(ls)) && checkOnePointAndListPoint(point, tail(ls))
  )
}
// check if a list of point is valid (no point attacking each others)
// const checkListPoint = (ls) => {
//   if (ls.length <= 1) {
//     return true
//   }
//   if (ls.length === 2) {
//     return checkTwoPoint(ls[0], ls[1])
//   }

//   return checkOnePointAndListPoint(car(ls), cdr(ls)) && checkListPoint(cdr(ls))
// }

const stackMaker = (printFn) => {
  const data = []
  return {
    push: (item) => {
      data.unshift(item)
      printFn(data)
    },
    remove: () => {
      const itemToRemove = data.shift()
      return itemToRemove
    },
    top: () => {
      return data[0]
    },
    listExceptTop: () => {
      return tail(data)
    },
    size: () => {
      return data.length
    },
  }
}

const queen = (n) => {
  const stack = stackMaker(getPrint(n))

  const back = () => {
    const isLastPointAtTheLastRow = () => {
      const lastPoint = stack.top()
      return lastPoint.row === n
    }

    if (!isLastPointAtTheLastRow()) {
      const lastPoint = stack.remove()
      place({
        row: lastPoint.row + 1,
        col: lastPoint.col
      })
    } else {
      stack.remove()
      back()
    }
  }

  const checkValidBoard = () => {
    const lastPoint = stack.top()
    const remainder = stack.listExceptTop()
    const isValid = checkOnePointAndListPoint(lastPoint, remainder)

    if (isValid) {
      place({
        row: 1,
        col: lastPoint.col + 1
      })
    } else {
      back()
    }
  }

  const place = ({
    row,
    col
  }) => {
    if (stack.size() === n) {
      log('done ')
      return 'done'
    }
    const point = makePoint({
      col,
      row
    })
    stack.push(point)
    checkValidBoard()
  }

  place({
    row: 1,
    col: 1
  })
}

queen(4)