For a part of my project I must solve the n-queens problem using
backtracking.You can represent a board configuration with a simple n
element list
(c1 c2 c3 c4 ... cn), ci corresponds to the column position of i-th
queen in
the i-th row. For example, (1 3 2 4) would correspond to the 4 queens
in positions (1,1) (row 1, column 1), (2,3) (row 2, column 3), (3,2)
(row 3, column 2), and (4,4) (row 4, column 4). Note that in our
representation we do not use double indexes: the i-th queen is placed
in the i-th row and its column index is ci. Note: If you want to write
a
faster program you can use a vector (or array) to represent your
board
position. You should worry about faster implementation only after you
are absolutely sure that you can solve the problem using a (easier to
write and debug) list implementation.
Posted at: http://www.groupsrv.com
Posted Via Usenet.com Premium Usenet Newsgroup Services
----------------------------------------------------------
** SPEED ** RETENTION ** COMPLETION ** ANONYMITY **
----------------------------------------------------------
http://www.usenet.com
Shame, shame, shame. The full text of this homework assignment can be
found at:
http://cs.gmu.edu/~zduric/cs480/Homeworks/Hwk3-s05.txt
Somebody should write a dishonest student detector which feeds USENET
posts from Google Groups into Google's WWW search. URLs for homework
assignments are pretty regular; that should help identifying suspect
posts. It would be interesting to see if this could be made into a
completely unsupervised process with a low degree of error.
On 25 Mar 2005 01:26:24 -0500, Carl Shapiro <·············@panix.com>
wrote:
>Shame, shame, shame. The full text of this homework assignment can be
>found at:
>
>http://cs.gmu.edu/~zduric/cs480/Homeworks/Hwk3-s05.txt
>
>Somebody should write a dishonest student detector which feeds USENET
>posts from Google Groups into Google's WWW search. URLs for homework
>assignments are pretty regular; that should help identifying suspect
>posts. It would be interesting to see if this could be made into a
>completely unsupervised process with a low degree of error.
Carl you screwed up bad. There are many ways of punishing morons who
try to cheat in this way.
For example here is a good site for those posting to Tolkien
newsgroups asking for help with homework:
http://www.flyingmoose.org/tolksarc/homework.htm
Better to write a solution which is in some way unique.
For example as you loop through the rows, on each sucessive
loop you can use a technique which reverses the orders of
the positions. Then you could send an email to the gmu instructor.
When he sees a student whose homework matches your solution,
he will have foiund the cheater. Also use some unusual naming
convention or names that are not right ( a Y mixer might
be a cool thing for the loops, but use Z instead of Y ), odds are
the guy is not going to even bother to change the names.
BTW you may have missed my earlier post. Do you have a rough
( it's OK if it's very rough ) date on when you will be releasing your
CMUCL win32 port?
The reply-to email address is ··········@yahoo.com.
This is an address I ignore.
To reply via email, remove 2002 and change yahoo to
interaccess,
**
Thaddeus L. Olczyk, PhD
There is a difference between
*thinking* you know something,
and *knowing* you know something.
TLOlczyk <··········@yahoo.com> writes:
> Carl you screwed up bad. There are many ways of punishing morons who
> try to cheat in this way.
And what about punishing instructors who continue assigning the
n-queens problem as homework? :)
Paolo
--
Why Lisp? http://lisp.tech.coop/RtL%20Highlight%20Film
Recommended Common Lisp libraries/tools (see also http://clrfi.alu.org):
- ASDF/ASDF-INSTALL: system building/installation
- CL-PPCRE: regular expressions
- UFFI: Foreign Function Interface
In article <············@127.0.0.1>, aref wrote:
[ solve the n-queen problem for me]
Let me guess... It can't be the evil scientist, Joe Marshall found him
out: <············@ccs.neu.edu>
It's got to be... aliens! They must have abducted you with n-1 other
hapless victims and placed you on a giant chess board. They gave you a few
minutes to find your spots on the board, after which they'll disintegrate
whoever is in an attacking position. Then they will take the survivors and
put them on a smaller board, and so on until no one is left. Your only
chance is to solve the n-queen problem. You will take advantage of their
momentary confusion to activate their ship's auto-desctuct mechanism and
flee in an escape pod. This is brillant!
--
Eric Daniel
Eric Daniel <···········@barberic.org> writes:
> In article <············@127.0.0.1>, aref wrote:
> [ solve the n-queen problem for me]
>
>
> Let me guess... It can't be the evil scientist, Joe Marshall found him
> out: <············@ccs.neu.edu>
Bwahahahaaaa!
In article <············@127.0.0.1>,
·······@yahoo-dot-com.no-spam.invalid (aref) wrote:
> For a part of my project I must solve the n-queens problem using
> backtracking.You can represent a board configuration with a simple n
> element list
> (c1 c2 c3 c4 ... cn), ci corresponds to the column position of i-th
> queen in
> the i-th row. For example, (1 3 2 4) would correspond to the 4 queens
> in positions (1,1) (row 1, column 1), (2,3) (row 2, column 3), (3,2)
> (row 3, column 2), and (4,4) (row 4, column 4). Note that in our
> representation we do not use double indexes: the i-th queen is placed
> in the i-th row and its column index is ci. Note: If you want to write
> a
> faster program you can use a vector (or array) to represent your
> board
> position. You should worry about faster implementation only after you
> are absolutely sure that you can solve the problem using a (easier to
> write and debug) list implementation.
So what part of it do you need help with? If you have a question, ask
it. If you've written something that doesn't work, post it and we can
comment on where you've gone wrong.
You don't expect us to just do your (home?)work for you?
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
Barry Margolin wrote:
> In article <············@127.0.0.1>,
> ·······@yahoo-dot-com.no-spam.invalid (aref) wrote:
>
>> For a part of my project I must solve the n-queens problem using
>> backtracking.You can represent a board configuration with a simple n
>> element list
>> (c1 c2 c3 c4 ... cn), ci corresponds to the column position of i-th
>> queen in
>> the i-th row. For example, (1 3 2 4) would correspond to the 4 queens
>> in positions (1,1) (row 1, column 1), (2,3) (row 2, column 3), (3,2)
>> (row 3, column 2), and (4,4) (row 4, column 4). Note that in our
>> representation we do not use double indexes: the i-th queen is placed
>> in the i-th row and its column index is ci. Note: If you want to write
>> a
>> faster program you can use a vector (or array) to represent your
>> board
>> position. You should worry about faster implementation only after you
>> are absolutely sure that you can solve the problem using a (easier to
>> write and debug) list implementation.
>
> So what part of it do you need help with?
The part where you write the program for him.
·······@yahoo-dot-com.no-spam.invalid (aref) wrote:
> For a part of my project I must solve the n-queens problem using
> backtracking.
don't know, if it uses backtracking, but here is a solution:
http://groups.google.de/groups?selm=cvs9s3%24cdn%241%40newsreader2.netcologne.de
--
Frank Bu�, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
On Fri, 25 Mar 2005 18:25:44 +0000, Frank Buss wrote:
> ·······@yahoo-dot-com.no-spam.invalid (aref) wrote:
>
>> For a part of my project I must solve the n-queens problem using
>> backtracking.
>
> don't know, if it uses backtracking, but here is a solution:
>
> http://groups.google.de/groups?selm=cvs9s3%24cdn%241%40newsreader2.netcologne.de
http://www.inf.tu-dresden.de/~s1054849/snippets/nqueens.lisp
Solves the 2000-queens problem in about 3 minutes on my laptop. So there
is room for improvement. Homework shouldn't be so easy anyway.
:-P
Regards,
--
Julian Stecklina
-- Common Lisp can do what C, C++, Java, PASCAL, PHP, Perl, (you --
-- name it) can do. Here's how: --
-- --
-- http://www.amazon.com/exec/obidos/ASIN/1590592395 --
>>>>> "Julian" == Julian Stecklina <··········@web.de> writes:
Julian> On Fri, 25 Mar 2005 18:25:44 +0000, Frank Buss wrote:
>> http://groups.google.de/groups?selm=cvs9s3%24cdn%241%40newsreader2.netcologne.de
Julian> http://www.inf.tu-dresden.de/~s1054849/snippets/nqueens.lisp
Oh for crying out loud! Why are you all giving him needlessly
complicated solutions?
(defvar mapping '((1 . 4) (2 . 2) (3 . 7) (4 . 3)
(5 . 6) (6 . 8) (7 . 5) (8 . 1)))
(defun eight-queens () (eight-queens-helper 1))
(defun eight-queens-helper (n)
(cond ((= n 9) '()) ; Termination condition
(t (cons (cdr (assoc n mapping))
(eight-queens-helper (+ n 1)))))) ; recursive call
Andru
--
Andru Luvisi
Quote Of The Moment:
Knuth's Tex for the Math-kings of sigma, and pi,
Unix vim for the Server-lords with their O'Reilly tomes,
Word for Mortal Men doomed to die,
Emacs from the Bearded One on his Gnu throne,
In the land of Stallman where free software lies.
One Emacs to rule them all. One Emacs to find them,
One Emacs to take commands and to the keystrokes bind them,
In the land of Stallman, where free software lies.
--- Raffael Cavallaro
Andru Luvisi <······@andru.sonoma.edu> wrote:
+---------------
| Oh for crying out loud! Why are you all giving him needlessly
| complicated solutions?
+---------------
Uh... Because it was obviously homework?
You think *this* crowd was rough, you should see what
the response to such things is over on "comp.arch"... ;-}
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
····@rpw3.org (Rob Warnock) writes:
> Andru Luvisi <······@andru.sonoma.edu> wrote:
> +---------------
> | Oh for crying out loud! Why are you all giving him needlessly
> | complicated solutions?
> +---------------
>
> Uh... Because it was obviously homework?
I think Andru's solution is especially suitable, then.
Zach
Zach Beane <····@xach.com> wrote:
>····@rpw3.org (Rob Warnock) writes:
+---------------
| > Andru Luvisi <······@andru.sonoma.edu> wrote:
| > | Oh for crying out loud! Why are you all giving him needlessly
| > | complicated solutions?
| > +---------------
| >
| > Uh... Because it was obviously homework?
|
| I think Andru's solution is especially suitable, then.
+---------------
Oops! Right you are. I didn't notice before replying
that his EIGHT-QUEENS was just (MAPCAR #'CDR MAPPING).
That *is* more the comp.arch style... ;-}
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607