nqueens/nqueen.lua

   1 local solutions={}
   2
   3 function NQueen(q,r)
   4    if r==N+1 then
   5       local qsave={}
   6       for e=1,N do
   7          qsave[e]=q[e]
   8       end
   9       solutions[#solutions+1]=qsave
  10    else
  11       for j=1,N do
  12          valid=true
  13          for i=1,(r-1) do
  14             if ((q[i]==j or math.abs(q[i]-j)==math.abs(r-i)) and r>1) then
  15                valid=false
  16             end
  17          end
  18          if valid then
  19             q[r]=j
  20             NQueen(q,r+1)
  21          end
  22       end
  23    end
  24 end
  25
  26 Dq={}
  27 for i=1,N do
  28   Dq[i]=0
  29 end
  30
  31 NQueen(Dq,1)
  32 q=solutions[1]
  33
  34 -- on envoie tout à TeX
  35 tex.print("Il y a "..#solutions.." solutions pour N="..N.."\\dots\\par")
  36 tex.print("\\begin{tikzpicture}\\draw (0,0) grid ("..N..","..N..");")
  37 for i=1,N do
  38    for j=1,N do
  39       if ((i%2 == 0) and (j%2==1)) or ((i%2 == 1) and (j%2==0))  then
  40          tex.print("\\fill[black!20] ("..(i-1)..","..(j-1)..") rectangle ("..i..","..j..");")
  41       end
  42       if q[j]==i then
  43          tex.print("\\node[scale=2] at("..(i-0.5)..","..(j-0.5)..") {\\wD};")
  44       end
  45    end
  46 end
  47
  48 tex.print("\\end{tikzpicture}")