From eb175bb39dea197a47b469da49ee1e83c3b43b3a Mon Sep 17 00:00:00 2001 From: Maxime Chupin Date: Sun, 29 Jan 2012 22:52:24 +0100 Subject: [PATCH] Mise en ligne du code des N-queens --- nqueens/LISTE.txt | 4 ++++ nqueens/index.xml | 11 ++++++++++ nqueens/nqueen.lua | 48 +++++++++++++++++++++++++++++++++++++++++++ nqueens/nqueen.pdf | Bin 0 -> 18438 bytes nqueens/nqueen.sol | 0 nqueens/nqueen.tex | 18 ++++++++++++++++ nqueens/nqueens.html | 6 ++++++ nqueens/nqueens.text | 23 +++++++++++++++++++++ nqueens/nqueens.tmp | 23 +++++++++++++++++++++ 9 files changed, 133 insertions(+) create mode 100644 nqueens/LISTE.txt create mode 100644 nqueens/index.xml create mode 100644 nqueens/nqueen.lua create mode 100644 nqueens/nqueen.pdf create mode 100644 nqueens/nqueen.sol create mode 100644 nqueens/nqueen.tex create mode 100644 nqueens/nqueens.html create mode 100644 nqueens/nqueens.text create mode 100644 nqueens/nqueens.tmp 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 0000000000000000000000000000000000000000..e68412646f5b13d7eac0d50c931125a4333b91c1 GIT binary patch literal 18438 zcma%iQy-p7-q{q*@67QHv6A!ml zK=7KnKS3#gf|HYebBz4v9`A6PU}J(u$9yS-z`-f0zj-G9w3qc??D)0-CEw1_1aBOI zvsBQqg~<{YFkGE{ZJSC$zrB7K=Hj@AV!$VDd!h3(5+NK_ZtG7bxY60lb*32+16ROX z$jVC&N@;pcFJ>z2;qN22b3<&CqlTQ`ueNC6O&8c-K3bCiP7y)hZ;^xX_SAonZe9$= zfF`j5U4lDF4IQTX0@b}yV>gXp69{qpJd?-_1gQ0)#cmoPCNZGlrzhePjvD-%p z2_v}s%(0>jFm%vsjAez`PNe-#t zxomUl0uJQ0)jeASn0xgC*5W3kxg&*~49>Fx$Z^;!1=GMPlOp3eZzdu3<`?NhEfhB< z&i6)OlhiiWqm1hoW4#Wf>#%qTE7y(tB>PyxgIYkK;tWwV)jN)Gw8?c1+4UXc>+ogt z%xd<~6e=}@C_|;M27GJ*sQ{8h#kV*s)+ciu{@iVpV_f)`*dZJCFu2BTztp48dV*K7 zuHqvEPwmZ9nlN42-r_qF<*Or36me^kIE3!l5vgJWk|Zc`r-)oO&CGok{sAuucGQBy ztwQ`xr@>g;+Q@3<#@B0y#-ymy!F@se;qsYvlg?V#)e3x6sWPEd>_aGi`ZS zFHjGhOD}-9EtRf4P|ea)Y^3=uSpNdP%O4IahDw0`U2Oqf4MAYa+cgSTpP;7*oEU;> ztBFYi{7yk6NH9HVU$1;#bY)xExxLidlrahD%3CA*s#xQG`CfRDUp1;JT za1UHU$G|FGJx)pc*7Epo_$xEz7G7)~=_Ij$^A^n?W=vB5q0TsB=Q9ywt{l?!qU6aN zBRCIlm2saUe^x|+SDhhYKKsgK7Plq}{2!e=7-+4&vjKXc&=xn`tPTJ;*p`ICxEoid zd6pMIUQ3kk;eHE(6D*@u_GrAQ=RmVLNrB+{wB%-+eiguen6p=OO^R@OR3>Hz;2J0h zTmIhSCPjDyYBTa8OnVi6d*GoYN?Kdc_^iy+boVAsIljhE7~*dZAj!DJ$A1LlH8cCi zfrS-31k%x~{}ds&mkF3yCMcSTj4Q1ud3#55o4|5>pev82pA3bJE^31pzpsY0#Gb%1 zJ zGvIuzGV={Jbj1$#Tm)WTk<6aP*V<`sAmJ0H2nLc+`hjedW2_a2mRd(Kh@Pr-#xfg9 ztF2oXrfYse?vk%D;EcHd6C2oD(lUo`1CX(PE3K^G_B(v)blHDZ0)vzUXw!Y%&4!k` zd)Lf7GY}%_!~gp1Xj1?!#g`GumlxJ~x4!iuwk)-^aC;53wuwdUdSpbanhPtIX4T$% zEt@IQb%MPWm!!ST3|A;^&;A#9@3mPA%EZ?A|484z(SKxRwY@l9A+-A^1s(PZJpX4Ms$mM zi;O-VS~I^kKRwc}4gHvx+efN)1=&AuA1}9mCG<+j9&H$GmYbERyYqAT0A8x?e{&bTD*IY z5wzX4esWTfv2goCTFDMqX@o2oB)$Q@~`@9kBlylvd zR=;kMyY-V*N$166e|-}vd97Wn-Ti8z{@L8!_4EAP|Gu6m^z}16&IWgeU*|!GDwx9&ByoFX1$e;_pz*2jE7GUGsT|InD;QuIYeZgDPw0 zU{0&CEMJa)<%|xV7XvmRbq{;kEc8k+X0peBG(RV-vlG-6Yu*Ptk-YE!v=88s{ts7O zgrgrzI`Ds(`xjW=3h0`#q|;A?9Qr#W<7@G3TMDj~EQ>UbqOHzS18g#fnakWr=y2y= z!6!ntTAhN&d>lcaVmxXGg-VejmT^T>NxB3;96h+>H>9A56WKE8jw^S=|DF6wt~?Ub zp6W54Oe`G@S$!ZV)xl*x@rb1D?FVHckpxD=i=}%>DnKkZ%0V-`a)QA<0sY(WB~OmR zK)<1m)rUI+n;(QZ(Odx=IX`j*@Zlb<4TYjSrZTM_-tq!IH(D88nIGD)VJZ^RHv+G- zJ_zWzFVFv`x*xNqqS_h4BCY}iyU<a)5aiE*6*IywZrlkjToyLm~91;1szuDZ&&C;g)zlS02XivW^~y2#SiXL@;EP1 zpt%t%fR4t(qU}n2Ob*LuPj6e%=jdp)heZtU>R7|2)WTFNBY2 z{U8bsWdzWJVQq4d!g)D>Ryv^7BhiE`i)d1!j{}t9MB&Z5!PUy!_Jxu?t3AbL{;@4A zRK4reX&wmQ>RGbHo@05w;LJtRbze-Ypm((zSw9)!abo#^;G#OB zQQNb|zg&t0SzOX2uxeSuS#6>3MhA};$_w6-K5?me&<-jMUVb_40o#TPh63>)bsucs^$1Sbk#7XUn`Ja!|2@1*lCS25YqO5+yUx5_8Ke<9Y zw};d|ZY3M`zCxT50dLbvt@FMic!Jtk%F=7ai4^4JKq6&@%SuN+U-CtI@sxaJ4R50x z!0OkSh>*aEO11u9CDJ0vYbhh&VcH1FgwgV^J(2d)y8zv5sg!0NNJFx+INT4n(S)L; zR>MFHtcK}~9|ivF)vTd`zR z34Hr#*B#~?qeAFHZFv>#Yr21kIp|n3IAAlsIBag!U-NXImC(8PZ#EiAlIWJ7OUYm1 zG;gZZK&V2I%w>eNj9O@o-8VOtB&}#Qt{5Nzi_V&@{kh=o4p5Qg#c*_+KWO@J;N(8Z zfe%}?LI0M$rav!kp}q2JnfMoHF1(ElYM#|V1}jo){O(9n#EXi73k6)}GYxyHUKn`r zvo(CfyZUx^9pb-I40!&B%v_(`37+QUm3FG?5Z2O1$vjz<1ESkOcK|Zr$sbQb z&Kp)G+;?|d$3xoz;e-3(PVTMvtJvPCaJh$E_&)6X9&K_0?I+H#Z!R<7xNQL~&6}c) zRe0bOug}9aWW2T>+PQvf1(344u8Np%G@Ar|jn_s0cE|eh&;Jx>@L_bLI$v9xtCWZ< zj0$c`pWW;zKnnDDW0AvooukoX5A4w3!71xsL_F^lq+DPg{BK14pO4e`ZXSH@RHOkX z9>TAL41gw4dYMj%fFTBjfw2A+VV`2WEj)j?><$oXe z@&Df^ew9SNC}alYzFl~Ge0MGz)Ub7LAhN-MZEPsuQ%G9^a}xqV;cH|wk@*AtM(nB> zbFUD*1IfuhsIF#K4kE@;RyFFKD8`3g<2hcW#P2dYyIpM0cb+N|Bw>zPE0Q107@9^8)2ZcV6?2K*bF)?Pa z)kdM_K$>Q;=C(~US_QBYW#ZMHc_X43nE?dd*fzENp}wT@`q4|qwzi(a@vYk#!5z{V zf9xSyM!Vyv?8x9LoIoc&&bU}8cIK|~XM5J0eU#ueOxzOEP{fnlJ<_x6tFbbH^)=0_ z@iI^QHpEZ+dcsvNa~GAwV}lnuGI0eSG?r|)a0q?i2UHh@0LMr9Zxc)jTL;hooNINP z*b$Sl^sOG!IKjx)Lu@;kg53p~Cm2df5qFB4fl`P2X0wpp0(C$4eoqi&zX#axR@Yh6 zrK%4OS@{ReL4^+68L7o96I(0c;MXgk<%L~efJzQpcC|iDlj4qYB#0fKz-ff6ME+7V z_2_!(i8Z9ZCiEnw^7|s7_4V2qP5#l47o`>nT2`4LQLj1^i?SQ64o}ZO=Q^ox-#jDf zcf|lXqT|gq+}mpv`{MnDmNOgf{=blh4Gm4y2un;< z3mh5{)6*Xs!Vpp(kP`?eE5Ou$HxLkNgtd<^nSoFNV2N5F)^9__W}1L@1eU)qsvpxB z3WTet${r{a5C?#69I#@+5kQ0s|4pu8D;LDGPtOck-@y2tYfG=v4;(1qSKZp$($dPv z?2jvO01dziz7;;df?zDd0aQLXdeF2lQcN|Djou0t7gkVJjEpXX-_;g6K0(zVdS8UM zRBkaP@OYe|gn0zxZ!N;bTY9=uYFJjJ=H`09K!RBD-d8d(M}UkT>`tu3+~jYF78gLT zFVHCgeWu4!)^fWK+frUo^hakU!RY!Nk39v>Fa^j+duig3VNiFG#Zc$kR5y| zzt>0z^)8_9^xpbl^mPqP!0Nti7^jm#tA1hcp8!8ZKX8?a3}>~|-&6(6Yg?#&-=(3c zgP(D*r@b42AGHbjfM0H4pqr_>U_fQR7Ct}ahrXl}`Ze;<$in(z zsi&<2O6U3Yr`rF{Y3O<;Lw?b{ATV3LTR%k~ z-8r&+GZ4`ozr+0;;(`F_1eAzBGPRU+1*ob7Ot+#8-0GmWh`y0gv@rM1)4NY`HL-8^ zhWtt@~=yTK%y@NxA5Ry^RRsJ3bOHk$LEjLxgB^`{ta=sTp&6B=VCc}iD5fyPN(-8XB|hRbGI8SAuo zJw{|v9cATqEZj~*}C630KVt?HC;d}0;j>Qo65 z2znE7JL_N0wvhtf^L&llTXCKG3GRt*8;FEy_jw7%y3x)22>Q=kQfsT557W2|rl5Kx zLL%u$;SbhsG6yWA-JYRk^*ZwOVS?X#yyZr09X3{-(lcG!_qz(hAYeC|x#x&@Ca+{s zHr2@FPiuDOU4nCi+mmx=eu=a5O!qe$Be6+Bmdr?_+Wr1*M-(ZZ(gLkYhaxxR)S((S zMW%8lN{P}i%jLQxnf=D6S#M|2TEQzhy)|_i&7O9zQmEKLp3bS3Zty^#q3_Z>yW`Vfp!t*>C9rNBbbOV1TOF@_4sh=jnl;_4wwf-;(Wu(j&N%Q*-I5QlW`# zU8gPF2+;ty=r~TlBMLS4&N9d@ z1FEr>lJZ9yR477*JBc_xpcF9%%I4Za`mOqpB?r-!w_0-9)EE_p_&n8wESzkcd8{Nc zBVSDYOnpnxIY#;UYdzY&bO^8=i7Ab?ILX>!f%c5D&^XUz?zeUFyQr%uVtm4AOqbQW zVuX4cG!Ft|?t8|IwQR-Z&55Gw2aTK>BaoWZt2ctBB_(Ad=;wVj2p#(&TwMZ87^A*R zZ;P&dJLSEPemZH_URd;wWVa^2&){Ujn*8lC{^d}^=nIvE&JzkXIb^3Ml%ggJ@43r$ zs1)<#k&UEqeygS5LFMXN+qb}d5L1M0!+wmjk?QdH>jQXIj?JRI_le5Dfs;o%*SoXL zNn$>^8C8nDgfku_7z?57t?maxaB3>>y9tbP$e#Vi->Jo(ph??Iiza284L~it{e=M ziDhFKlAYrQvIM3~@=bR;uf6W^f_~(AvH?0}4-Y@#0qn(^Y>P`@F<)mk*TqYzd6f^N zF1*R((+N3MpUr|975?=7!n~$q{E9`}lJMzz5NudEm`SbRc6X-W0baIPtlyRp6oCAp z%s_r^4*JfEc4!lV!G2>AkBp*E8^BjyT0cCMDbnXTqsFJ8;sKxM=+P2F&b@0kRC5lq zMGGuyb$JG-%v*Q+1fs-SI@9=6VSF$wm8!@_NK zoYkZ^2#Dmtg3}k_BNmVe?l$K0B0@D3ueCt-=go57s*iHZ@{CrEPFt8Iyl+BiEfpk9 zwrmoDFkW4{L&gVLmT=}5AVdbwyW5m!$o&dSp1hB-;~m04u=C>Ty)^sa?Cs{%n94b>R9xgXiRbhI?tt_pg8eWz_lOh&oCyAdsMHcTDgFN~0Zln3g z8~2p|cmPMXuU@k_UOt970y4yc;l(vzPZK8f+imwY5%r~--X7ge!H*TUAD)X9WTSH6 zhaH=ufU;ACH-}D2IXWguO$OwU8-<)w@BD&jIkgFdjNyw)kgsGtjuYDAki(pki$Xyk z!m@*pepE@Tn3HcNj_arEbXmJwu%SX{<8RxS6X-UaoSdHL z(6J=YN4nsQyfH-0Bc>u9h9GUJ+g`UHKp@% zJIkO#uFfBpZwIUR4<}8h&a%{C+N!ZYn;(`JeHh>Dv_ZbR&YWJ`DMAMI66?;opwV-N z+xroY0mNMv|k?JoA2C{ z4;|yaaLDRDk1QiV_osvB6`{jh(t;~A_}UB5HMxrIkmedLbN81yYQSD_C?BzU%-c`TU7elxYrGAF^4P)^?C7F^Ll+wqQ-vsk3b+rKKX_8F_g1}rU5KDf3} zlA*zLTdHu$QLx~6lddLZ41np^%QrbR#cXZl9nx*^CVK6+uS4+Vb^VH5 zpLcSAUC{_Bk+D9Y>%y?_;%t@~VMcg(J75ip<|m|-#J&kIitH;pFI4h!7i^l21{T$2 zs)uf{SN<>+ouRLB)8S=ImZlgrdj$sT#$Cn)9&YUCYR|BG&8hFD>PeaLE?V8L?&I)( zD>X&apR9Zx4LPVB>B#>%X_c(O z^DYi#tmA&&XThuRKqHATrQfwMif@R}ZkW~Mw%+~uyFippy%N%C5`ibd&1j<5c1+uV zq<{R^0@0(Z%)vO27q+rFuZP-sSh2(p8ext`>l8CK+4-vG^^ic7;B@7*ujo&As{>Ub z;PPGw$LpBqK6;aR0EW_GcIYRgG8mc5Oo&WtUmlG(1i z3U_64Fc>xNOnCHkNveDw>D7Z81<-$ms%oduS4Dn1(vLm?n9Zws1`rC zoK5G4AoaATLyQ4C`wYb(4;Q7Q8@%+!mZ@r>fC|MF&!=&X}Z=eC$4| zuOIW<&5Iry0Ab~@=wuktt3RG?zZbE_P?DGil3tbij5u;BhO5kKU0px%XKIYSV_)%2 zKVEt&>?v3P>%+!G8ONIhI>-7PlY};*G=6p}VPtGZuKrz#Eynv#=yV8dQ)WOuX#)<} z*J^9~0)kgP43m|IOK;+>6nY@>N?gDfAHzjef(<)1?1mir@13;6L^e#W5Y*Are^bq3 zeWl5@>TV8-qv^;FH#Nj7*ug~?)8gzT+sLq%pI0DFZNxKs5EYXPqEEd-ZDKh>0Xc*8 z91PxyCEt+FY|NEW>s|EFQ=yXD+F9)GvSbzvO41XJJ97p`J~N{y_@=!-#*J@=TQGCI z>C;v_1t>Mp<5W9@OlWV}VfjR=ipzh_p6zv%)M~d?9@hcZ-7HfEEZb6rE1rq96)rIH z{n!)N?rK=G+}MgNkG4)HJEXgvPBtm|zDXE~A3WX&mqaKPqy+e0gnRf^w!{WX3i~5p znDW;Yx0Hv74-+l*z@~%^@D}U#c&xN!$}BxD9?99m)Lh<;qeL5x^ljiOMTl7CE>~xQ zO+;gq7gjLhc&(C&wU*)1)siG}fWvSdH0%$KcV*wiuA<#w;=fO*;gI3O>dGQKi4-xe9!xjmA4Xs_hTcKi8ly1uDq_aIlGBnmXb93*hg znydV|&@7^50-^l4Mvydb;$4sHH-P@jeqH0jApQ{i!+q%pCk`!{vM^s5uE^(@W923C zWIE+D2;gQTf7FN-QX9D8=|h9XXPds#pP}CfQzAV@!#YT;wFg6BZlo${PO&lT&AfMS z)D3kg@UUFSlx$ZEL&UjUcOe?4zBt#_ya~)eYewyg8u_vuefGLwo7s&SwBaa0<|;I9 z{I;3lk2*xi0(tW*u-X;@G!(J;9X$Q?&=o~tG zY!_o1Lz-E9Lie!&ZSc75375IwT9Rum7Xqy=9s0A@vM?Y^(wi%VjcZnGL=Kj0t{G?N z8X;0g=TX>4m!2q4Z9GI5YzRtdP97FLvf!M-Vg)NE%JBn>W>u`+rSu^?2SM4*zTL#= z4rsn($rw7Od5lem`oqWy1=x92uQRl_^%iE#H7KDZ*3Y)ZbCfn!k9gZu^YGY0VoCI8 zSjQSi$ft>DqgdjTNoUe10(N$6Tz1u5)(vVh?h(@}*F%5vQ10&b8;Pkm0a*+lP(#wo_o|8ByWqUtx7uL&M`U#h0(FehKuvJ60qxW+q662h0;L*W9Si6gL^% z7nM9M4Sb%4wY3JMWId74H)mE&%-R*Nw{EQ!opmQV+O;BO3|;Q%a%ir@O{<2E62r?! zZu6^S_Tb|^C=a#LSL`VasJv*u>S+CuIOv7JizClQWrFRw5Zdl<=2lu7gKU6MMow0g zFonJI#^p$$qJiuJ4_v)I3NNYZSfRJu?Q!;@YR+wK+}46-D#OWo2*u&t&rJH#g4Vl3T#TPy~YH)@=MwMMqCM?;HexRG7Rn zQiU?_C-MQO>s3Eyx4C`IL@*5L7PG-4qBP32_udL&b-Y=)&Aj_PI>t_0qpQ0OMhAbp z+zkfB$udo9$;L%{%1oBJliS)?H~am%7}6p`NQc5iPh^CxAGg#1!_QsbdlMWp4%}65 ze6c@8lPjiH%mywcRq-UITm`B)hm?#>0$rQL72p!yfo6&6JL@}PAl~0 z0amH`8+{XZbPI2-vOU57S&bz*n4ZAQM0ourhk-T1A0&oeynG%Qwg9HW~St zQ*m?I0}wN@eGCj;l}exV_QcxYl5s~FC$O2?;~x9mj;&*4bGZYedOxb7b;fBd>{(9&iOOOj1r26C$A ziJsF21=$Uh^z3grF5Nc%iZg`aX3Ro%C~DH6=OM(w9t%GE${(AtFPzAQ<|T@$7$HEjv#ij=_`;*op6;G9{vV z*bJeb9|aBTfcPESE@3ot3t@Rei^qKXN^xG2O!_i)R;E<86`}BGk!TZ(pw0$vG&@G$ zd082VeFr$%NQ;NoW0ho`i@M9#XXQ!e<7jDrO;q{H<&G9TIXOP4zL`{^c#lJ`U2bj6 zrGj#WvAl%BPbD6}<@(v)6-l41m8Fvv4$y8c60jb)m)< z=A`A3kgi%Nb-GRCB4~fy65{d|j9D|Hq&X#beNqxxq zGyWL3^%OHd_i@AR<$!{zP`APst|DaFTNa=sGo#Be$Dj&*yjCL*l92QZ?#A-tE!m~R z7Z&9fXQkI@Dd40prHV^&-v22GxlrA3y$s34750&W#l3zAO)kwq)GsLpH|i!!1p%R@ zN9}{VNIJf?B-tl==zC81MEJVn1YwgT8H812xO?;ob|Rfg8187P@m|Ps;G0WEH^5ci zLzW)ZpUpQ3ufo6AMYRo=vDLlMerorQQO>{>@we$m(7=2i*r~O<7Bm2*Bp{`z3#7+QEZ_Eehg>>Ujng3W9Nj)za1r8T8q9f9ww#*vsI@8sFu$ zFi;Es3-;=}ws#)rI9PCVXX&DYU_D2o<~w9#l|Cr;4m|k#%qo;eC*2C9y}jKhLrK6( z{fYDf#dZLMNfj@I)c9;*&%M1jKf6o30Y``8FfU?uutGl=#Ksn!p>dM*VNrFO5G)U% zd_A0=w)#M)dS>O~iXz(4O!$F1qT3OBe3QtN9lvLXB+d>gjw<_omR=QH9?NhmXD)6xEZRuCR|mVJB8QW*)KD+KA#Odpb7i&1wuQ~lge0dB z8y&itf7J|Gxkfb^ZCbKW%((C?zuFz&BWwV8IQNAQbi|#~4}+ zlBbWbaEw5fj`l?}?EB}YXl}6%;M64(S&fGl2AamVQvpZQC97mWBeK5C{r%@znxP|s z!=&XDe%~B73miB4D!O*5IC$MX0<-u9|AaG{naqVh1(Gx}5cFjEYE)8~GzxnB)^)@I zAXpiYY&wt5Gh~iuPD~Re^u56$4#JT|ff_sxY}!Cx z7~ffgEPzPQ?QSQaxl`O!1*K@iUM|pd029g$UeLZvLu|OVjM@sJDg-Viqrz&T`ygli zMdQ1JO}WCXbAyJrpE>1KDTtnrt>so~82+jnPKzb-#c#h!eP;emqqc;_z2nQLKi6GR zU(6E&LHX5qn@`dokqsVp6j*hJv#pLyO{s{j^!r7I=vv3JUZGouqEHP|2nsWCf>SCC zG`d+ZC1{Qmb?T_bF|-~k#{9{%cPn1q73AA90??w~RLwjtqzG6b=Pm;3Y1ql@HTpF+ z?}qF}h;#lFm|=5U&WhXgYJ3~rDLcSWLiXx~oTK4U^QL+|Dq>>PK`N9p*~2{5>yW&} z9=|{PwOBbm4rRYcK4Io>yll1TcJQD=nPZxTO#~(Jg=SmCaN7NpKGo+BB6lu512#s<)VjFbds6u<`1&IsC|Th|xC)>t^=eJr z)+w-xF!N8~jR8g}<{fx=I34qO`cX%urntU`OfF$y^4q?vViLAq>D&dH&W6cV996alH1ob$2PGQGG z$wE+dSDFDY(oT_)7)g+rF{7-TH9`YzpQnfZG! z;JD5ll-YhyB3ZNxftSjRb9qulyr9wri(lWBO66yrh>~gD_cP5ldX$#|+WT4=gvetm z8FA`_!|^DAi1Aiv0&7a&yfLYzs|Bzw5Uh8+m-8jiAtMITQ8u6KErmZC47W!CEqL{4 z759V=xmLFvWmIqr&P@)Krirc<^1^0VoSMPnL?nbu?tq7L2$7+ztWOs1{0^HP6t&n;`~1u%0kkjW~xt&h8!7}q_o^B&TXd;8qdy*j!$Mxz%6yI~zH zcu1jE!A9k3@m6LG%(-xsjlnO(F=!9m#+qS;7&Z=6OZ}E1Dps-Q6Hwa{ z2XOksG;vPeBCl0CH63=-O1R=E@ex%a5FWYV5wbOyPVF{3UBy~H7JImQ?XCE1q}f6O zjmPLr)G1QX_@u%B6dtx9)~^}kN@2hHgxjh5h)4|zhQ>NPYW#*Fm6mvTBM~MX zhyFU^I|1TsMUz%HG=e2pi5P5**I z(zO&&k}D8PY5@KZu*k&&rNh=Q>?6o4y62|0pQgmE`a8smC{x?gL&9F z85f+sH4h4RdIEj{6>}vJqzWv1v*7nKEKc?M`*vy9y5cPScdMPjJ@~01oh}u!sOKaq zOI6wH^Qni|O?-641zv9$ui>c=N=-;99~mK~W?S5*i4#%;@A?l7rfYlvj zlqprJ&!%ZtSa;w!3|7qr`*{)&pYKh?G?;* zD;&m_0Y2F6KAGAy!+8!>@!N&BcGh?%hMs}C(6f6JNfEz9v7G61`!VNWyjwBn`qG+f z8#BnN=f{;*zp0}Tv32AChQWBvEmLxjIKi;~Sz*=d0%Fc965LS)H-L7UqakWoCVU^c z3r6gPG#kxx>O+CY(QPTiRzcrL6mZl+G24EAWAZKCqQtZHIz{3L>k25NfF3y~%4<#b z=5VCAZ~jwT-ZlZfiYtTbik!oQ7oS0(3f;f|T7dk#SF2o^Oa!3VjTF*-koKcB?`7|p zn^%ZV7F)9~&%ZeITivy#i})P9zYl!OaEvX%O)oU){nTx05)T0Ax#c^`i496l`eVwOOnTD+rK)N1(TvGQ(DUx4&5t)x~ zOprG!-tq45@PRj@BTT_%YRHWQ+)1grPG1{B<`Y{y|hEHTWF6u51zN8VdoT)#980M(fnAiANAy)88tiH17Sm+TxpC3p__TQu`4C)g zbu0rvSg1`L6bS)@(oC0vq8a`C4g*LWD0uW~CqozZLoYgj$k&9%oidrI;Hj;%O#9FM zXBQbZ<(SZ=353#f%y6zh$EdaZH-01&oD|97-d91w_|r6F^%9_OPXu=T)242Ywzj-i z1OY9lo$z4l7d>V!GI`#K-f5fz8xLN;(HCt`hJd6+EN|Do+%(l2iQN_6QM->06hA2zpX5mQ8MB|oMVEWZEg|CZU)?x4jV?YcCnTtipI_VnkBSwD4s+Ta zLz(7pJ|4-I6XlcMs+?bEV=VI8;M%gp1-hn1!ObTpvO?e0Ed;+zHqKMyK$E}$9*JPC$W%RDb}#cDsYy2>w5R+cBr%toNW#Ds=O9k_sS35dvL8bU zw={F%n4jR752rsOI7?d|cs>W3rg?6XQj2Na?~l9bf)#LyOg5VWhBS6 z+k+DQ>AiE#2Pc$uIkxz+-Aa1zJ$lh=Pa5$@IVyhOP$TPlVJ|8avu^eX#T?=*Y7>fH z&nz@np>2BNj||bpKLex(N)6*zqE$nlT<%nsROUGk5Nrkl%d>BwgfrWXY)CjLKeQAS zDYha(h1riXw8B|3*2SZ*I3o++WB5QRic?3*5Fah;m#~luiYMzkAH*E3Q*6u)u)|6f zxM0^71jx)^%tVaO4b+1OLlC1QsxF|ofL&>kof#V0OxG+Pv!-jF(?(m?Y3Lcj?00$; z5U?u{KIktn%w&6K*ej6&N(ZROPKSJ?aSiFNlmP`pLt`0?q?=z^+S;~~t5Ee&ToEh@ z>VSle(@g~Q1il(vizays-~M@>>5`EQQo);7QB+4qxpS?&191?DB~?jC%gS(~m`ov@ zA0#08xDkv>dfnK2W3&nFm1LH2k&A7hg6Y>u1NS$V^mvTXCId>evb=1%Q#hr&Hy`DT zA>`AFF!1$1j$WVC(T->dUMHOJ%xI#o!<(_niJj8h-vVo{B37avLNTg6K$($I}0Byqj{jBDuZX95#9vRBVVg8 zdXmxhVY5q;YS|)R{7`y0Z*h-YQS<8`)q9h?zqe{u2}#NaYe#OqPi4yg_{w=0gDO%w zf)3MA_K8pkkH!{zkO$ciC$zM~XX9olj|9zc&UlQ%@}f+GlGsIY69#6cNU5-5k_EV5 zd3bCFBtZs@Rde|2;Ie@z|7^U=KcU~9v+UEnG&sj}ZP!p}W5RTnNb@!RUvnz-ddGkM z`TYq2Vsk6zte^4tB+EUfTH&SV;+L9pMjkcJH|w>Mv9g_MbSOr-tl;BZ)oITfx4+bh zRq*NZopQ{lkwe*PkzUx#Nm(-Gl`j_^g`Dy{vy{+}{yK8S?<$w~KfbeD&-vw7l{4D8MM5vk zy6=jms-85ki?WeErFFmnxUDVy-rkR=--`G2O_kZKwC?aW+vB=BthJXtnBy9+S7{(- z=iPigM_uQHry=*ggQ;)Xr4yK+|4>%BeAOb&@Zq|XuI0cv$6kH@pCy>P3XF`9b`=B^<)@S;1J9b!@F`6UNsZ7o&@(sCGt}hLcLts{ zQIZdo0E)u6nfZAxz!NDHG+eBV3=9noEDQ{dj7<#<47Cjm)eQ{Pf$DtoQwS*uDM~CT zNKFAAZ;_Z&oXVvi5aJr4=T@4Nla!d32XabCMrN@B5J8-zqY#!_R1CCQAt|*a5$Zr) zu>EF+CWdAT8bzsP3MNM8=9*x~D)?lUr7D2rH5IZ85=%0QQxg@+phlSKfqe%&Oar!+ z*Z?UsLMjVV74-d+vVu!;x%B;jdo4gabBc;f6budEn=Ta0EG>xMx3f1SH~Y4Mz`u9# zh4SWZwbSnNF1(;p8oq1Vq$z6!J~@_(xKFq>Z*9rjy1(z2YiIhgI^x#m}KWTXHda79{TiTP{IZSpd!kItkp80-|iT#~ znw?j@Kj%x~>)-9}Xl&Xk(0I9i_s;+2%C}zaGv5<%W6^aUnIF>&-^_2{-M{g?4#%4f zr`N^?u5r2X<$>`1ZwI@Rt#8iXVi&t<_WUXJYi6yvHdXWWy1v_w?C&jk{N?hCG9{Tw z>r?L)82)ma|C4XdP8K%-ehJa3zZaeSp<9rCaN-&}?YZkSq=lDSaLu2~X}8C$Xzk{1 zrFdnC;1%!JFiB5t9>rMY)9vJEX4-$ zo_k0}i3mzff46Wjl#G;alB4GF!S{NFd MaH*=g`nz!f0KE15Hvj+t literal 0 HcmV?d00001 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... + -- 2.20.1