Mise en ligne du code des N-queens

[luatex.git] / nqueens / nqueen.lua

diff --git a/nqueens/nqueen.lua b/nqueens/nqueen.lua
new file mode 100644 (file)
index 0000000..9b8719a
--- /dev/null
+++ b/nqueens/nqueen.lua
@@ -0,0 +1,48 @@
+local solutions={}
+
+function NQueen(q,r)
+   if r==N+1 then
+      local qsave={}
+      for e=1,N do
+         qsave[e]=q[e]
+      end
+      solutions[#solutions+1]=qsave
+   else
+      for j=1,N do
+         valid=true
+         for i=1,(r-1) do
+            if ((q[i]==j or math.abs(q[i]-j)==math.abs(r-i)) and r>1) then
+               valid=false
+            end
+         end
+         if valid then
+            q[r]=j
+            NQueen(q,r+1)
+         end
+      end
+   end
+end
+
+Dq={}
+for i=1,N do
+  Dq[i]=0
+end
+
+NQueen(Dq,1)
+q=solutions[1]
+
+-- on envoie tout à TeX
+tex.print("Il y a "..#solutions.." solutions pour N="..N.."\\dots\\par")
+tex.print("\\begin{tikzpicture}\\draw (0,0) grid ("..N..","..N..");")
+for i=1,N do
+   for j=1,N do
+      if ((i%2 == 0) and (j%2==1)) or ((i%2 == 1) and (j%2==0))  then
+         tex.print("\\fill[black!20] ("..(i-1)..","..(j-1)..") rectangle ("..i..","..j..");")
+      end
+      if q[j]==i then
+         tex.print("\\node[scale=2] at("..(i-0.5)..","..(j-0.5)..") {\\wD};")
+      end
+   end
+end
+
+tex.print("\\end{tikzpicture}")