Mise en ligne du code des N-queens

diff --git a/nqueens/LISTE.txt b/nqueens/LISTE.txt
new file mode 100644 (file)
index 0000000..fb8902d
--- /dev/null
+++ b/nqueens/LISTE.txt
@@ -0,0 +1,4 @@
+== Sources et pdf produit
+nqueen.lua
+nqueen.tex
+nqueen.pdf

diff --git a/nqueens/index.xml b/nqueens/index.xml
new file mode 100644 (file)
index 0000000..c8a4fc8
--- /dev/null
+++ b/nqueens/index.xml
@@ -0,0 +1,11 @@
+<?xml version="1.0" encoding="ISO-8859-1"?>
+<simple>
+  <titre>Le problème des n-queens</titre>
+  <auteur>Maxime Chupin</auteur>
+  <header>mathjax</header>
+  <echo/>
+  <h2>Le problème</h2>
+    <div class="plaque">
+    <segment f="nqueens.html"/>
+  </div>
+</simple>

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}")

diff --git a/nqueens/nqueen.pdf b/nqueens/nqueen.pdf
new file mode 100644 (file)
index 0000000..e684126
Binary files /dev/null and b/nqueens/nqueen.pdf differ

diff --git a/nqueens/nqueen.sol b/nqueens/nqueen.sol
new file mode 100644 (file)
index 0000000..e69de29

diff --git a/nqueens/nqueen.tex b/nqueens/nqueen.tex
new file mode 100644 (file)
index 0000000..02acfdc
--- /dev/null
+++ b/nqueens/nqueen.tex
@@ -0,0 +1,18 @@
+\documentclass{article}
+\usepackage{diagram}
+\usepackage{tikz}
+\newcommand\nqueen[1]{
+\directlua{
+N=#1
+dofile("nqueen.lua")
+}
+}
+
+
+\begin{document}
+
+\nqueen{10}
+
+\nqueen{12}
+
+\end{document}

diff --git a/nqueens/nqueens.html b/nqueens/nqueens.html
new file mode 100644 (file)
index 0000000..54919bf
--- /dev/null
+++ b/nqueens/nqueens.html
@@ -0,0 +1,6 @@
+<h2 id="principe-du-probl&#232;me">Principe du problème</h2>
+<p>Le but du problème des <span class="math">\(n\)</span>-dames est de placer <span class="math">\(n\)</span> dames d'un jeu d'échecs sur un échiquier de <span class="math">\(n\times n\)</span> cases sans que les dames ne puissent se menacer mutuellement, conformément aux règles du jeu d'échecs (la couleur des pièces étant ignorée). Par conséquent, deux dames ne devraient jamais partager la même rangée, colonne, ou diagonale.</p>
+<h2 id="un-exercice-de-programmation">Un exercice de programmation</h2>
+<p>Ce problème bien que simple à formuler n'est pas évident et constitue un bon exercice de programmation. Ici, il est résolu avec un algorithme récursif. Ceux qui veulent en faire la résolution par un autre mais toujours en lua sont les bienvenus !</p>
+<h2 id="laffichage-pour-latex">L'affichage pour LaTeX</h2>
+<p>L'affichage des solutions est toujours plaisant, c'est pour cela que l'utilisation de LuaTeX convient tout à fait avec les fontes d'échiquiers. Vous pouvons donc parcourir le code pour voir l'interaction (simple) entre TeX et Lua, Lua résoud et TeX affiche...</p>

diff --git a/nqueens/nqueens.text b/nqueens/nqueens.text
new file mode 100644 (file)
index 0000000..1595d3e
--- /dev/null
+++ b/nqueens/nqueens.text
@@ -0,0 +1,23 @@
+## Principe du problème
+
+Le but du problème des \(n\)-dames est de placer $n$ dames d'un jeu
+d'échecs sur un échiquier de \(n\times n\) cases sans que les dames ne
+puissent se menacer mutuellement, conformément aux règles du jeu
+d'échecs (la couleur des pièces étant ignorée). Par conséquent, deux
+dames ne devraient jamais partager la même rangée, colonne, ou
+diagonale.
+
+## Un exercice de programmation
+
+Ce problème bien que simple à formuler n'est pas évident et constitue
+un bon exercice de programmation. Ici, il est résolu avec un
+algorithme récursif. Ceux qui veulent en faire la résolution par un
+autre mais toujours en lua sont les bienvenus !
+
+## L'affichage pour LaTeX
+
+L'affichage des solutions est toujours plaisant, c'est pour cela que
+l'utilisation de LuaTeX convient tout à fait avec les fontes
+d'échiquiers. Vous pouvons donc parcourir le code pour voir
+l'interaction (simple) entre TeX et Lua, Lua résoud et TeX affiche...
+

diff --git a/nqueens/nqueens.tmp b/nqueens/nqueens.tmp
new file mode 100644 (file)
index 0000000..7e3a196
--- /dev/null
+++ b/nqueens/nqueens.tmp
@@ -0,0 +1,23 @@
+## Principe du problème
+
+Le but du problème des $n$-dames est de placer $n$ dames d'un jeu
+d'échecs sur un échiquier de $n\times n$ cases sans que les dames ne
+puissent se menacer mutuellement, conformément aux règles du jeu
+d'échecs (la couleur des pièces étant ignorée). Par conséquent, deux
+dames ne devraient jamais partager la même rangée, colonne, ou
+diagonale.
+
+## Un exercice de programmation
+
+Ce problème bien que simple à formuler n'est pas évident et constitue
+un bon exercice de programmation. Ici, il est résolu avec un
+algorithme récursif. Ceux qui veulent en faire la résolution par un
+autre mais toujours en lua sont les bienvenus !
+
+## L'affichage pour LaTeX
+
+L'affichage des solutions est toujours plaisant, c'est pour cela que
+l'utilisation de LuaTeX convient tout à fait avec les fontes
+d'échiquiers. Vous pouvons donc parcourir le code pour voir
+l'interaction (simple) entre TeX et Lua, Lua résoud et TeX affiche...
+