用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