[原创]八皇后问题的递归写法

gm_jwl

<!--emo&:d--><img src='https://www.kaiyuan.info/modules/ipboard/html/emoticons/teeth_smile.gif' border='0' style='vertical-align:middle' alt='teeth_smile.gif' /><!--endemo-->  <!--emo&:d--><img src='https://www.kaiyuan.info/modules/ipboard/html/emoticons/teeth_smile.gif' border='0' style='vertical-align:middle' alt='teeth_smile.gif' /><!--endemo--> <br>--------------<br>public class Queen{<br>   private int[][] checkerboard=new int[8][8]; <br>   private int[] local=new int[8];  <span style='color:blue'>//save the queens&#39; locations everytimes</span><br>int nummer=0;<br>   public void queenSearch(){<br>       rekQueen(0);<br>   }<br>   void prt(){<br>        System.out.println(&quot;\nStart&quot;);<br>        for(int i=0;i&lt;8;i++){<br>          for(int j=0;j&lt;8;j++){<br>              if(local&#33;=j) System.out.print(&quot;- &quot;);<br>              else System.out.print(&quot;Q &quot;);<br>          }<br>          System.out.println();<br>         }<br>         System.out.println(&quot;End\n&quot;);<br>   }<br><span style='color:blue'>//Rekursion</span><br>   <span style='font-size:12pt;line-height:100%'><span style='color:red'>void rekQueen(int horizontal){<br>        int k=horizontal;<br>        int[][] backup=new int[8][8];<br>        for(int i=0;i&lt;checkerboard.length;i++){<br>           if(checkerboard[k]==0){<br>local[k]=i;<br>              if(k==7){<br>                checkerboard[7]=2;<br>                prt();<br>                  nummer++;<br>                continue;<br>             }<br>             arrayCopy(checkerboard,backup);  <span style='color:blue'>//make a backup</span><br>             remark(checkerboard,k,i);<br>             rekQueen(k+1);<br>             arrayCopy(backup,checkerboard);<br>           }<br>        }<br>        local[k]=-1;<br>        return;        <br>   }        </span></span>   <br>void arrayCopy(int[][] a1,int[][] a2){<br>        for(int i=0;i&lt;a1.length;i++){<br>                  for(int j=0;j&lt;a1.length;j++) a2[j]=a1[j];<br>         }<br>   }<br>   void remark(int[][] array,int i,int j){<br>        array[j]=2;<br>        if(i&lt;array.length-1){ <span style='color:blue'>// asure that the horizon between 0-6</span>       <br>               int m=i,l=j,n=l;<br>               while(++m&lt;array.length){<br>                array[m][j]=1;<br> <span style='color:blue'>//make vertical as unavailable</span><br>                if(--l&gt;=0) array[m][l]=1; <br><span style='color:blue'>//left tilted</span><br>                if(++n&lt;array.length) array[m][n]=1; <span style='color:blue'>//right tilted</span><br>                }<br>        }<br>    }        <br>    public static void main(String[] args){<br>        Queen q=new Queen();<br>        long time1=System.currentTimeMillis();<br>        q.queenSearch();<br>        long time2=System.currentTimeMillis();<br>System.out.println(&quot;nnInsgesamt gibt&#39;s &quot;+nummer+&quot; Loesungen.&quot;);<br>        System.out.println(&quot;nDie Durchlaufzeit betraegt &quot;+(time2-time1)+&quot; ms.&quot;);<br>    }<br>}<br>-------------