标签: n-queens

所以我需要帮助解决经典的N-Queens问题.

运行程序的命令是: nqueens N k - 其中N是表的大小(N x N),k是解的数量

因此,例如,如果我通过键入nqueens 4 1来运行程序,则将打印出以下内容.

_ Q _ _

_ _ _ Q.

问_ _ _

_ _ Q _

但是,我无法弄清楚如何处理1个以上的解决方案？如何确定此问题不仅仅是一个解决方案？

我到目前为止的内容如下:

#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <vector>


using namespace std;

class Board
{
private:
    bool** spaces;
    int size;

public:
    Board(int size)
    {
        this->size = size;
        spaces = new bool*[size];
        for (int i = 0; i < size; ++i)
        {
            spaces[i] = new bool[size];
        }
    }

    bool …

我正在研究n-queen回溯.有人可以向我解释如何other_row_pos检查对角线？我不确定它为什么会起作用或者它是如何工作的.

取自wikibooks - http://en.wikibooks.org/wiki/Algorithm_Implementation/Miscellaneous/N-Queens:

bool isSafe(int queen_number, int row_position) {
    // Check each queen before this one
    for(int i=0; i<queen_number; i++) {
        // Get another queen's row_position
        int other_row_pos = position[i];
        // Now check if they're in the same row or diagonals
        if(other_row_pos == row_position || // Same row
           other_row_pos == row_position - (queen_number-i) || // Same diagonal
           other_row_pos == row_position + (queen_number-i))   // Same diagonal
            return false;
    }
    return true;
}

这篇文章的目的主要是针对相关研究的关键词.

无约束的N-Rook问题

在N×M(N <= M)的棋盘上计算N个车的所有可能的安排,以便没有车辆相互攻击.

解决方案很简单:C(M,N)N!

受约束的N-Rook问题

你不能在棋盘的某些地方放车.

例如,如果棋盘被显示为0-1矩阵,其中0是你不能放置的地方.所以矩阵的解决方案

1 1 1
1 1 1
0 1 1

是4:

R . . | R . . | . R . | . . R 
. R . | . . R | R . . | R . .
. . R | . R . | . . R | . R .

相关问题

可以从N-Queen问题轻松修改回溯算法.但是,现在我想解决N = 28左右的问题.甚至维基说,这个解决方案太大了,不能算是1比1

27×27板是完全枚举的最高级板.

加速的机会

到目前为止,我想到了一些加速算法的机会.

=====无约束子矩阵的因子=====

这是一种分而治之的方法.例如上面的矩阵

1 1 1 …

我刚刚解决了python中的nqueen问题.该解决方案输出用于在nXn棋盘上放置n个皇后的解决方案的总数,但是在n = 15时尝试它需要一个多小时才能得到答案.任何人都可以看看代码,并给我提示加快这个程序......一个新手python程序员.

#!/usr/bin/env python2.7

##############################################################################
# a script to solve the n queen problem in which n queens are to be placed on
# an nxn chess board in a way that none of the n queens is in check by any other
#queen using backtracking'''
##############################################################################
import sys
import time
import array

solution_count = 0

def queen(current_row, num_row, solution_list):
    if current_row == num_row:
        global solution_count 
        solution_count = solution_count + 1
    else:
        current_row += 1
        next_moves = gen_nextpos(current_row, solution_list, …

我正在开发一种启发式方法,将8个皇后放在8x8棋盘上.每个方格都有自己的消除编号(表示如果在该方格中放置一个女王,则"消除"空棋盘的平方数.)并且每个女王应放置在具有最低消除编号的方格中.

我的问题是我不知道如何继续减少其适当方格的特定消除数量,所以如果你帮助我,我将感激不尽.另一个问题,我觉得我的代码非常复杂,所以任何笔记都会让它变得更简单？

这是我的代码

public class Queen {
private final int SIZE = 8;
private int board[][] = new int[SIZE][SIZE]; // 8x8 board
private int hor[] = new int[SIZE]; // horizontal moves
private int ver[] = new int[SIZE]; // vertical moves
private int lowestValue = 22;
private int[][] queens = new int[SIZE][2]; // 8 queens 

public Queen () {
    // initialize each square with its own elimination number
    for (int row = 0; row < board.length; row++) {
        for (int col …

我很难理解递归和回溯,虽然我做了一些简单的练习(例如Fibonacci).所以请允许我在这里展示我的"脑力流":

1. 我阅读了教科书并知道如果当前位置消除了将下一个女王放入下一栏的可能性,你可以使用回溯来移除前一个女王.所以这似乎很容易,我需要做的就是删除它,让程序决定下一个可能的地方.

2. 过了一会儿,我发现程序在第6位女王停滞不前,所以我发现如果我简单地删除第5位女王,那么程序只需将其放回当前位置(即给出前4位女王,第5位女王总是落入同一位置地方,这并不奇怪).所以我认为我需要跟踪最后一位女王的位置.

3. 这是我困惑的时候.如果我要跟踪的最后一个皇后的位置(这样,当我原路返回程序是不允许把女王到同一个地方),有两个潜在的问题:

a)假设我删除了第五位女王,我必须编写代码来决定其下一个可能的位置.这可以通过忽略其当前位置(在被移除之前)来解决,并继续在以下行中查找可能的位置.

b)我应该追踪所有以前的皇后吗？似乎是这样.让我们说实际上我必须删除不是一个女王,而是两个女王(甚至更多),我当然需要跟踪他们当前的所有位置.但这比它看起来要复杂得多.

1. 所以我开始在教科书中寻找答案.遗憾的是,它没有回溯代码,只有递归代码.然后我在这里找到了代码:

http://www.geeksforgeeks.org/backtracking-set-3-n-queen-problem/

它让我感到非常惊讶,因为它非常简单而又有效!唯一的回溯部分是删除最后一个女王!所以问题是:以下代码如何确保当给出4个皇后的位置时,第5个皇后并不总是一次又一次地落入同一个地方？我认为我不明白的是你如何递归回溯(比如你需要删除更多的皇后).递归前进时我没有问题,但我怎样才能递归地向后移动？

/* A recursive utility function to solve N Queen problem */
bool solveNQUtil(int board[N][N], int col)
{
/* base case: If all queens are placed then return true */
if (col >= N)
    return true;

/* Consider this column and try placing this queen in all rows
   one by one */
for (int i = 0; i < N; i++)
{
    /* Check if queen can be placed on board[i][col] */ …

Algorithm NQueens ( k, n) //Prints all Solution to the n-queens problem
{
    for i := 1 to n do
    {
        if Place (k, i) then
        {
            x[k] := i;
            if ( k = n) then write ( x [1 : n]
            else NQueens ( k+1, n);
        }
    }
}

Algorithm Place (k, i)
{
    for j := 1 to k-1 do
        if (( x[ j ] = // in the same column
           or (Abs( x [ j ] - …

你们中的一些计算机科学、数学等专业的学生可能有解决这个问题的经验。它被称为“8皇后”。本质上，您可以用多少种不同的方式将 8 个皇后放置在 8x8 的棋盘上，以使它们都不发生冲突（又称对角线或水平线）。我在下面尝试了这个问题，但我的程序只打印出一个解决方案。

我想我需要一个柜台。我不知道如何继续，并且没有太多算法背景。非常感谢任何帮助，感谢您花时间提供帮助。

var n = 8;\n\nsolveNQ();\n\nfunction printSolution(board){\n  for(var i=0; i<n; i++){\n    for(var j=0; j<n; j++){\n      document.write(" "+board[i][j]+" ");\n    }\n    document.write("<br>");\n  }\n  document.write("<br>");\n}\n\nfunction isSafe(board, row, col){\n\n  // Checks the \xe2\x86\x90 direction\n  for(var i=0; i<col; i++){\n    if (board[row][i] === 1) {\n      return false;\n    }\n  }\n\n  // Checks the \xe2\x86\x96 direction \n  for(var i=row, j=col; i>=0 && j>=0; i--, j--){\n    if (board[i][j] === 1) {\n      return false;\n    }\n  }\n\n  // Checks the \xe2\x86\x99 direction …

我对 CVXPY 真的很陌生。我正在尝试解决8 个皇后问题，即将 8 个国际象棋皇后放在 8 x 8 棋盘上，这样两个皇后就不会互相威胁。据我了解，约束应该是：

1. 每行的总和等于 1。
2. 每列的总和等于 1。
3. 每条对角线的总和等于 1。
4. 所有变量都应大于 0。

此外，目标函数应该是：最大化矩阵的 2-范数（这样我们只能得到 1 和 0，因为我们也可以得到 s 的和为 1 float，但是 1 与 0 的范数大于浮点数的范数） 0 到 1 之间且总和为 1（例如：0.8^2+0.2^2 < 1^2+0^2）。

CVXPY 中可以解决此类问题吗？我对如何在 CVXPY 中形成约束和目标函数一无所知，但这是我最初的初步尝试（我立即收到“DCP 错误”，所以我没有理由继续，但仍然如此）：

from cvxpy import *
x=Variable(shape=(9,9), name='board')
obj = Maximize(norm(x))
const = [sum(x, axis=1)==1]
prob=Problem(objective=obj,constraints=const)
prob.solve()

任何帮助将不胜感激！！！

我想我理解 NQueens 算法的重点 - 您检查每一行是否存在可用空间，如果它们存在，则在那里放置一个皇后，然后递归地将算法调用到下一行。这是我的算法（N 大小为 3）

from typing import List
import pdb
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        self.solutions = 0 
        self.attack_zone = [[0]*n for i in range(n)]
        self.size = n
        self.backtrack_nqueens(0,0) #start on row 0 
        return self.solutions
    def backtrack_nqueens(self,row,iteration):
        #starting at row
        for col in range(self.size):
            if self.is_not_under_attack(row,col):
                print("on iteration",iteration,row,col,"was a safe place for some reason")
                #adds queen to this row
                self.place_or_remove_queen(row,col,True)
                if row + 1 == self.size:
                    ## THIS SHOULD NEVER HAPPEN 
                    self.solutions += 1 …