N-Queens问题:
这个问题表明,给定一个大小为N乘N的国际象棋棋盘,找到不同的排列,其中N个皇后可以放在棋盘上而没有任何一个相互威胁.
我的问题是:
程序可以在合理的时间内计算出答案的N的最大值是多少？或者到目前为止我们看到的最大N是多少？
这是我在CLPFD(Prolog)中的程序:
generate([],_).
generate([H|T],N) :-
H in 1..N ,
generate(T,N).
lenlist(L,N) :-
lenlist(L,0,N).
lenlist([],N,N).
lenlist([_|T],P,N) :-
P1 is P+1,
lenlist(T,P1,N).
queens(N,L) :-
generate(L,N),lenlist(L,N),
safe(L),
!,
labeling([ffc],L).
notattack(X,Xs) :-
notattack(X,Xs,1).
notattack(X,[],N).
notattack(X,[Y|Ys],N) :-
X #\= Y,
X #\= Y - N,
X #\= Y + N,
N1 is N + 1,
notattack(X,Ys,N1).
safe([]).
safe([F|T]) :-
notattack(F,T),
safe(T).
这个程序运行得很好,但是它花费的时间不断增加N.这是一个示例执行:
?- queens(4,L).
L = [2, 4, 1, 3] ;
L = [3, 1, 4, 2] ;
No
这意味着您将4个皇后放置在第1列的第2行,第2列的第4行,第3行的第1行和第4行的第3行(在4乘4的棋盘中)
现在让我们看看这个程序是如何执行的(计算第一个排列所花费的时间):
对于N …
#include<stdio.h>
#include<math.h>
void printboard(int n);
void fourQueen(int k,int n);
int place(int k,int i);
int x[100];
void NQueen(int k,int n)
{
int i;
for(i=1;i<=n;i++)
{
if(place(k,i)==1)
{ x[k]=i;
if(k==n)
{
printf("Solution\n");
printboard(n);
}
else
NQueen(k+1,n);
}
}
}
int place(int k,int i)
{
int j;
for(j=1;j<k;j++)
{
if((x[j]==i)||abs(x[j]-i)==abs(j-k))
return 0;
}
return 1;
}
void printboard(int n)
{
int i;
for(i=1;i<=n;i++)
printf("%d ",x[i]);
}
void main()
{
int n;
printf("Enter Value of N:");
scanf("%d",&n);
NQueen(1,n);
}
我认为它有时间复杂度:O(n ^ n),因为NQueen函数是递归调用的,但是这个程序可能有更严格的约束吗？那么最好的情况,最坏的情况时间复杂性.我也对place()函数感到困惑,它是O(k)并从NQueen()调用.
理论上,N-Queens难题可以在多项式时间内求解吗？如果是这样,它的最大复杂性是什么？我找到了很多算法,但我还没有找到时间复杂度究竟是什么.是否有任何文件或文件给出其复杂性的确切数量？
(PS显式解决方案非常有趣,但我忘了说,我希望找到所有的解决方案.)
我一直在研究8皇后问题,但我遇到了困难.我不想要代码.我会喜欢指导和指导,以便了解如何使用回溯递归来解决这个问题.
该程序应该通过在ASCII中绘制皇后的位置来枚举N皇后问题的所有解决方案,就像这里的两个解决方案一样.
到目前为止,我的伪代码是:
void queen(int n){
for( int i = 0; i < n; i++){
place queen[ i ] on row i;
for(int j = 0 ; j < n ; j++){
if( queen[ i ] is not in the same column as queen[0] through queen[ i - 1 ] &&
queen[ i ] is not on the same major diagonal with queen[0] through queen[ i -1 ] &&
queen[ i ] is not on the same minor …我对使用动态编程实现8-queen问题的想法很困惑.似乎DP的一端不可能"如果问题被分解为一系列子问题并且找到了每个子问题的最优解,那么所得到的解决方案将通过这些子问题的解决方案来实现.没有这种结构的动态编程无法解决"(参考).考虑到这一点,7x7电路板的最佳解决方案可能也不是8x8的最佳解决方案(甚至不正确).因此,问题的结果可能无法通过子问题的最优解来实现.
另一方面,DP是回溯问题的优化......如果是这样的话,那么8-queen问题可以通过回溯来解决...这是否意味着只存储死角可以将回溯解决方案转换为DP？如果是这样,则2,1对于父1,1可能不可行,但对于1,2可能是可行的.
更新
任何人都知道使用动态编程是否可以解决8-queen或n-queen问题？如果是,那么您对上述观察的评论是什么？
在Sterling＆Shapiro 的序言艺术中，练习14.1（v）节：
queens(N,Qs) :-
length(Qs,N),
place_queens(N,Qs,_,_).
place_queens(0,_Qs,_Ups,_Downs).
place_queens(I,Qs,Ups,[_|Downs]) :-
I > 0, I1 is I-1,
place_queens(I1,Qs,[_|Ups] ,Downs),
place_queen(I,Qs,Ups,Downs).
place_queen(Q,[Q|_],[Q|_],[Q|_]).
place_queen(Q,[_|Qs],[_|Ups],[_|Downs] ):-
place_queen(Q,Qs,Ups,Downs).
这是一个出色的程序，共有11行，可快速解决将皇后放在棋盘上的问题。这很神奇：只有计数器，递归和列表变得越来越长。我，即使在跟踪的帮助下，也不了解它。有人可以向我解释吗？您如何编写这样的程序？导致从（例如，另一个）（好的标准解决方案）派生该程序的逻辑/心理过程是什么？
queens(N,Qs) :-
numlist(1,N,Ns),
queens(Ns,[ ],Qs).
queens(UnplacedQs,SafeQs,Qs) :-
select(Q,UnplacedQs,UnplacedQs1),
\+ attack(Q,SafeQs),
queens(UnplacedQs1,[Q|SafeQs] ,Qs).
queens([ ],Qs,Qs).
attack(X,Xs) :-
attack(X,1,Xs).
attack(X,N,[Y|_]) :-
X is Y+N ; X is Y-N.
attack(X,N,[_|Ys]) :-
N1 is N+1,
attack(X,N1,Ys).
我试图了解Selectmonad是如何工作的.显然,它是表兄,Cont它可以用于回溯搜索.
我有这个基于列表的解决n-queens问题的方法:
-- All the ways of extracting an element from a list.
oneOf :: [Int] -> [(Int,[Int])]
oneOf [] = []
oneOf (x:xs) = (x,xs) : map (\(y,ys) -> (y,x:ys)) (oneOf xs)
-- Adding a new queen at col x, is it threathened diagonally by any of the
-- existing queens?
safeDiag :: Int -> [Int] -> Bool
safeDiag x xs = all (\(y,i) -> abs (x-y) /= i) (zip xs [1..])
nqueens :: Int …Google或-tools的一个示例是n-queens问题的解算器. 在底部,它表示可以通过向约束求解器添加对称破坏约束来改进实现.
环顾互联网,我发现n-queens问题的对称性破坏约束,但我不能为我的生活弄清楚如何将这些转换为约束到实现它们的python代码.
编辑:这是一个糟糕的问题,让我们更新......
我试过了什么？
以下是上面第一个链接的设置:
from ortools.constraint_solver import pywrapcp
N = 8
solver = pywrapcp.Solver("n-queens")
# Creates the variables.
# The array index is the column, and the value is the row.
queens = [solver.IntVar(0, N - 1, "x%i" % i) for i in range(N)]
# Creates the constraints.
# All rows must be different.
solver.Add(solver.AllDifferent(queens))
# All columns must be different because the indices of queens are all different.
# No two queens can be on …我使用以下简单代码来解决n-queens问题:
#lang racket
; following returns true if queens are on diagonals:
(define (check-diagonals bd)
(for/or ((r1 (length bd)))
(for/or ((r2 (range (add1 r1) (length bd))))
(= (abs (- r1 r2))
(abs(- (list-ref bd r1)
(list-ref bd r2)))))))
; set board size:
(define N 8)
; start searching:
(for ((brd (in-permutations (range N))))
(when (not (check-diagonals brd))
(displayln brd)))
它工作正常但需要很长时间in-permutations才能获得更大的N值.它使用函数来获得排列流.我还看到它仅使用25%的CPU功率(正在使用4个核中的1个).如何修改此代码,以便它使用来自in-permutations流的排列并行测试并使用所有4个cpu内核？谢谢你的帮助.
编辑:check-diagonals评论中建议的修改功能.旧代码是:
(define (check-diagonals bd)
(define res #f)
(for ((r1 (length bd))
#:break res)
(for …当为n-Queen问题的所有可能解决方案实现算法时,我发现许多分支都达到了相同的解决方案.有没有什么好方法可以为n-Queens问题生成每个独特的解决方案？如何避免不同分支生成的重复解决方案(存储和比较除外)？
以下是我尝试过的第一个解决方案:http: //www.ideone.com/hDpr3
码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* crude */
#define QUEEN 'Q'
#define BLANK '.'
int is_valid (char **board, int n, int a, int b)
{
int i, j;
for (i=0; i<n; i++)
{
if (board[a][i] == QUEEN)
return 0;
if (board[i][b] == QUEEN)
return 0;
}
for (i=a, j=b; (i>=0) && (j>=0); i--, j--)
{
if (board[i][j] == QUEEN)
return 0;
}
for (i=a, j=b; (i<n) && (j<n); i++, j++)
{
if (board[i][j] …