用system verilog constrain random求解八皇后问题

vcs版本:L-2016.06_Full64

八皇后问题具体可以查看维基百科(或百度百科),简单说来就是在8*8的棋盘上需要摆放8个皇后,每一行,每一列都不能有两个皇后,并且两个皇后也不能处在与正(反)对角线平行的位置。思路主要来源于这篇文章。用Qi代表第i+1列,Qi的值代表皇后所处行(从下往上看),比如下图皇后的位置可以用Q0=5,Q1=3,Q2=1,Q3=7,Q4=2,Q5=8,Q6=6;Q7=4表示。

约束如下:

  • Qi的值在1-8之间。
  • i 不等于 j时,Qi不等于Qj,不能处于同一行。
  • |i-j|不等于|Qi-Qj|,即两个皇后不能处于斜对面。

程序去掉了重复的结果。N 为循环次数。

class Queens;
rand int Q[8];
constraint Qi{
foreach(Q[i])
Q[i] inside {[1:8]};
}
constraint Qi_n_Qj{
foreach(Q[i])
foreach(Q[j])
if(i!=j){
Q[i] != Q[j];
!((Q[i]-Q[j]) inside {(i-j), (j-i)});
}
}
endclass
program Eight_Queens;
parameter N=800; //loop times
int Array1[N][8]; 
int Result[N][8]; //default is zero
int m = 1;
int sum = 0;
int midvalue;
initial begin
Queens qc = new();
for(int i=0;i<N;i++) begin
qc.randomize();	//randomize Q
foreach(qc.Q[j]) Array1[i][j]=qc.Q[j];
if(i == 0) Result[0] = Array1[i];
//remove duplicate content,from the second 
if(i>0) begin
for(int k=0;k<i;k++) begin
for(int j=0;j<8;j++) begin 
//if sum not equal to zero,two line are different,the abs of Array1[k][j] minus Array1[i][j]
if(Array1[i][j]>Array1[k][j]) midvalue = Array1[i][j]-Array1[k][j];
else midvalue = Array1[k][j]-Array1[i][j];
sum = sum + midvalue;
end
if(k != (i-1)) begin
if(sum == 0) break;  //equal to some line,$break
else sum = 0;	      //rejudge next line
end
if(k == (i-1)) begin //judge equal to provious line or not
if(sum == 0) break;
end
end
if(!(sum == 0)) begin
Result[m] = Array1[i];
m = m+1;
sum = 0;
end
end 
end
foreach(Result[i]) begin
//remove usless line,the answer can't be start with 0
if(!(Result[i][0] == 0))	
$display("qc.Q is %p",Result[i]);
end
end
endprogram

使用如下命令(如果没有安装vcs,可以在这个网站注册账号,选择编译器为synopsys vcs,注册需要教育邮箱)。

vcs -full64 Eight_Queens.sv -sverilog

然后会生成simv可执行文件,执行

./simv

当N=8时,结果如下:

当N=80是,结果如下

如果在这个过程中遇到了其它问题,欢迎在评论区留言,或者Google一下,也欢迎把具体的解决方法留在评论区,以供后来者参考

欢迎转载,不需注明出处,就说是你写的

参考:http://yue-guo.com/2019/02/07/solving-the-n-queens-problem-using-constraints-in-systemverilog/

3 thoughts on “用system verilog constrain random求解八皇后问题

  1. 您好,我是sv小白,想先通过您的程序跑起来试试,但是现在出现的报错是:
    failed to create symbolic link ‘_4108_archive_1.so’: Operation not supported
    make[1]: *** [_4108_archive_1.so] Error 1
    make: *** [product_clean_order] Error 2
    Make exited with status 2
    生成了两个文件分别是csrc和simv.daidir,想请教一下如何解决,万分感谢!

      1. @PANG 解决了就好,平时没怎么看这个。像这种问题如果自己解决不定的话,可以直接在谷歌上输入关键字查询,大部分应该都是可以找到解决办法的。

发表评论

您的电子邮箱地址不会被公开。

*

code