X-Git-Url: https://melusine.eu.org/syracuse/G/git/?p=luatex.git;a=blobdiff_plain;f=nqueens%2Fnqueen.lua;fp=nqueens%2Fnqueen.lua;h=9b8719a37c4df8fa9f64ab6319203b858d1a8650;hp=0000000000000000000000000000000000000000;hb=eb175bb39dea197a47b469da49ee1e83c3b43b3a;hpb=056042f08bda9111ae23ebdc00218ac95cd1b018;ds=sidebyside

diff --git a/nqueens/nqueen.lua b/nqueens/nqueen.lua
new file mode 100644
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}")