• Subject: Re: n-queens problem
• From: Maxime Chupin <notezik@...>
• Date: Mon, 1 Aug 2011 10:53:01 +0100

------------------------------

Message: 5
Date: Mon, 01 Aug 2011 01:41:32 -0700
From: "Dimiter \"malkia\" Stanev" <malkia@gmail.com>
Subject: Re: n-queens -> save the solutions
To: lua-l@lists.lua.org
Message-ID: <4E3666BC.40309@gmail.com">4E3666BC.40309@gmail.com>
Content-Type: text/plain; charset=UTF-8; format=flowed

Hi Maxime,

You need to story a copy of your "q" array, because it gets modified later.

local N=6

local solutions={}

function NQueen(q,r)
if r==N+1 then
-- debug
char=""
local qcopy = {}
for e=1,N do
char=char..q[e].." "
qcopy[e] = q[e]
end
print(char.."\n") -- THIS PRINT THE RIGHT ARRAYS
-- end debug
solutions[#solutions+1]=qcopy
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)
print(#solutions.." solutions found") -- RIGHT NUMBER OF SOLUTIONS
local drawSol=solutions[2]
local char=""
for f=1,N do
char=char..drawSol[f].." "
end
print(char) -- THIS PRINT A WRONG ARRAY

Thanks,
Dimiter "malkia" Stanev.

On 8/1/11 1:09 AM, Maxime Chupin wrote:
> local N=6
>
> local solutions={}
>
> function NQueen(q,r)
>     if r==N+1 then
>        -- debug
>        char=""
>        for e=1,N do
>           char=char..q[e].." "
>        end
>        print(char.."\n") -- THIS PRINT THE RIGHT ARRAYS
>        -- end debug
>        solutions[#solutions+1]=q
>     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)
> print(#solutions.." solutions found") -- RIGHT NUMBER OF SOLUTIONS
> local drawSol=solutions[2]
> local char=""
> for f=1,N do
>     char=char..drawSol[f].." "
> end
> print(char) -- THIS PRINT A WRONG ARRAY
>
>

------------------------------

Message: 6
Date: Mon, 1 Aug 2011 10:41:58 +0200
From: Olivier Galibert <galibert@pobox.com>
Subject: Re: n-queens -> save the solutions
To: lua-l@lists.lua.org
Message-ID: <20110801084158.GA62823@dspnet.fr">20110801084158.GA62823@dspnet.fr>
Content-Type: text/plain; charset=us-ascii

On Mon, Aug 01, 2011 at 09:09:00AM +0100, Maxime Chupin wrote:
> I am playing with the n-queen problem to learn Lua. I want to save all the
> solution in a list (solutions) but it does not work and I do not understand
> why. Here my very simple code with which my problem is more understandable.

You're saving a reference to q (and hence to Dq), not a copy of q.  So
your solutions array will end up with a bunch of references to Dq,
which itself will be set at the final queen position.

Best,

OG.

Thank you ! This is understandable  now.

--
Maxime Chupin
http://mc.notezik.com