From: Maxime Chupin Date: Sun, 29 Jan 2012 21:52:24 +0000 (+0100) Subject: Mise en ligne du code des N-queens X-Git-Url: https://melusine.eu.org/syracuse/G/git/?p=luatex.git;a=commitdiff_plain;h=eb175bb39dea197a47b469da49ee1e83c3b43b3a Mise en ligne du code des N-queens --- diff --git a/nqueens/LISTE.txt b/nqueens/LISTE.txt new file mode 100644 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 index 0000000..c8a4fc8 --- /dev/null +++ b/nqueens/index.xml @@ -0,0 +1,11 @@ + + + Le problème des n-queens + Maxime Chupin +
mathjax
+ +

Le problème

+
+ +
+ 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}") diff --git a/nqueens/nqueen.pdf b/nqueens/nqueen.pdf new file mode 100644 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 index 0000000..e69de29 diff --git a/nqueens/nqueen.tex b/nqueens/nqueen.tex new file mode 100644 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 index 0000000..54919bf --- /dev/null +++ b/nqueens/nqueens.html @@ -0,0 +1,6 @@ +

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.text b/nqueens/nqueens.text new file mode 100644 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 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... +