---------- Forwarded message ----------
From: Neil Munro <[EMAIL PROTECTED]>
Date: 2008/8/26
Subject: Re: N queens problem again.
To: York Linux Users Group <[EMAIL PROTECTED]>
Hi,
Neil Munro wrote:
Hi again,
>
> I have a couple of pointers for you that may help.
>
> Firstly (ignore this if you already know it)
>
> The program is basically trying to complete a list showing the
>
> positions of queens on a given board size.
> The way this list is set up is this:
>
>
> Yes, I understand what it's trying to do :)
>
> Sorry if I sounded patronising, but without your comments about the subtle
changes to the assignment, it looked like you were using the list
incorrectly.
Hence the smile, I know you weren't being patronising, just explaining
something on the off chance I didn't understand.
>
>
> Imagine you have a board of size 4, with a queen at row 1 in
> column 3, row 4 in column 2, and row 2 in column 1.
> Ie we are looking for the row for the 4th column.
> Reading in columns from right to left, the queens are
> currently at rows 1,4 and 2 respectively.
> The list that represents this is [1 4 2] - note, just row
> numbers from right to left!
> So, the members of this list are all integers.
>
>
> Ok, now this would be allowed in the previous assignment, however
> the assignment explicitly states that the Queens function, which
> passes it's list to revise takes tuples in the form Column#Row
> where row numbers are numerically sequential. [1#1 3#2 5#3...].
>
>
> Here I still have a problem. The {Revise} function accepts a list which it
> decomposes into a 'H' and a 'T'. Later on it uses 'H+1#N'. Now if the list
> 'L' is a list of tuples of the form [a#b c#d e#f g#h etc] as you've said,
> then 'H' would be a single tuple, say x#y. Now it is not possible to do
> x#y + 1. The only thing you can add 1 to is a number (ie an integer or
> float). So, if the {Revise} function is listed correctly in the code i've
> seen, it can't possibly take a list of tuples and work.It must take a list
> of integers. Using the assumption that the {Revise} function has been
> supplied in full working order, there is something wrong with the type of
> list {Queens} is sending it. Similarly, the statement 'if H == BoardSize'
> makes no sense if H is a tuple and BoardSize is an integer!
>
Ok if we look at my Queens function
fun {Queens L N}
if {GetLengthOfList L} == N then
{Browse L}
L
else
{Queens {Revise 0|L}}
end
end
As we can see here, the head of the list in revise becomes 0, which IS an
integer, but the rest of the list is comprised of tuples, and H+1 can be
performed on the head of the list if it is an integer, but we need to turn
the integer into a tuple and then move it to the end of the list once the
correct queens placement has been found, if possible.
>
>
> Now, your {BuildList} function expects a list of integers as
> above, so the line which starts H.1#..... makes
> no sense because H is an integer and doesn't have a '.1' to
> access.
>
>
> It is because it is my understanding that revise is passed a tuple
> in the form column#row and because {Revise} uses {BuildList}
> {BuildList} will also inevitably be passed the same tuples, now
> with {BuildList} we recurse quite a bit, getting a smaller and
> smaller list until we get a list of size 1, now, since the
> assignment wants everything in tuples it seems, I had to make a
> way of working around this, so lets assume we have three elements
> on a 7x7 grid [1#1 3#2 5#3] now once {Buildlist} gets to these
> elements H is going to represent the whole tuple. So if we get the
> first part of the tuple H.1, which will in the first element in
> the list be 1, now because {BuildList} has recursed to there only
> being one element in the list, and it's the first element, then it
> MUST be in the first row (part of the assignment constraints) so
> if we just measure the size of the list we can assume it's
> accuratly going to be the correct row number so that's how the
> H.1#{GetLengthOfList L}|{BuildList T} came from.
> H.1#{GetLengthOfList L} will become 1#1. It's a bit roundabout in
> it's execution, but that's how and why it does what it does.
>
> If it's wrong, fine, ok, but within the assignment limits and this
> overuse of tuples it's the only solution I understand.
>
> Ditto. Because in the {Revise} function, 'H' must be an integer, it follows
> that 'T' must be a list of integers, therefore {BuildList} must also be
> working with integers.
>
We ARE working with a list where the head is an integer, the tail being
tuples, as far as I understand the workings of the function at least.
Secondly, as I said before, stick with the version of {Revise}
> that the lecturer gave you (exactly as it is) it works 100%
> guaranteed!
> I suspect the line
> else {AddToList H+1#N T}
> should be different in the original version.
>
>
> I have amended {Revise} to be as the tutor wrote, however new grid
> co-ordiantes which are 'discovered' are added to the beginning of
> the list not the end, this is why I wrote and used the {AddToList}
> function. If there is an easier way to add elements to the end of
> the list I am unaware of it.
>
> No, there isn't an easier way to add elements to the tail of a list. List's
> are intended to be accessed from the head usually.
>
But I still need to add the newly found element to the end of the list, not
the beginning.
This is why - Revise is taking this list of integers we
> mentioned and is looking for another integer, representing a
>
non-conflicting row for the next column, to stick on the head of the list.
> Now, in this function, the value being tested
>
> is always H+1 , so if H+1 is not {Threatened} then H+1 is the
> value that must be added to the head of the list.
>
>
> {Threatened} is given a list and a co-ordinate, the co-ordinate is
>
> then passed to {Attack} along with the next element in the list.
> It then checks if the co-ordiante and the next element in the
> list, conflict, if so return true (which implies a new co-ordinate
> has to be generated) if not, accept this as a usable position for
>
> a new queen.
> As we add elements to the list the list grows, now lets assume a
> 7x7 grid with three 'known' queens, we add 0 to the head of the
> list and then go to revise.
> The co-ordinate is then H+1 (so 0+1 = 1) #{lengthoflist}(the list
>
> WAS 3, but had 0 added to the beginning, so it's actually now size
> 4), which creates 1#4. This generates the co-ordinates that get
> passed into {Attack}
>
> Also lets assume 1#1 has been taken, 1#4 can't be used, so we
>
> recurse and H+1, which generates 2#4 and so on until we find a new
>
> non-conflicting queens position.
Again, this all seems to revolve around the question of whether the list is
> integer or tuple. I know {Threatened} uses tuples but surely the list it
> receives is generated by {BuildList} but the question is, generated from
> what? Sorry if I'm adding confusion, but something just doesn't sound
> right. I would normally have 100% faith in any functions provided with the
> assignment, but the one i've seen seems to contradict what you are telling
> me about the assignment specification.
>
Ok, if we are both confused about what it's asking, lets look at the
function requirements.
2. (a) Write an oz function {Attack U V} whose input parameters
U
and V are both squares in the form col#row. The function should
return true if U and V are on the same row, column or diagonal;
otherwise it should return false.
(b) Write an oz function {Threaten L U} whose L is a
(possibly
empty) list of squares in the form col#row and whose input pa-
rameter U is a square in the same form. The function should
return true if U is attacked, in the sense of the Attack function
above, by any of the squares in L ; otherwise it should return false.
(c) Write an oz function {Queens L N} whose input parameter N is
the board size, and whose input parameter L is a non-empty list of
squares in the form col#row, whose rows run consecutively from 1,
L being a partial solution of the N queens problem. The function
has to extend L if this is possible to a full solution of the N
queens
problem, returning this as a list of squares in the same col#row
form. Otherwise, if no such extension is possible, the function
must return an empty list.
To me that reads pretty explicit that the list contains tuples, but then I *
DID* have to email the tutor about what C really asks, so I may just be
confused over the wording of the assignment. If so, please do correct me cos
if my understanding of what it's asking me is wrong then my implementation
will also be wrong.
Regards
Mark
Thanks
Neil Munro
--
Mark Richardson
Final year undergraduate
University of Teesside
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
