JESS: N-Queens

[Senlin Liang]

Dear all,

I am trying to solve the N-Queens problem using Jess. Is there a way to use rules to make a efficient program, or I have to use functions to do the brute force search?

I am trying to compare several systems to see which one is good at this N-Queens problem.

Thanks,
Senlin

[Ernest Friedman-Hill]

The most efficient known algorithm for solving n-queens is the fairly  
obvious backtracking one, where you place one queen at a time, giving  
up and backtracking when you fail. This is *not* a brute-force search  
-- brute force would be explicitly checking each possible board  
position with all eight queens on the board at once, which is a much  
bigger search.

Here's a good paper about the backtracking solution: http://penguin.ewu.edu/~trolfe/SCCS-95/SCCS-95.html

Now, as far as an implementation in Jess: Michel Futtersack's CCP page  
has a couple of different solutions in the CLIPS (Jess) language. See http://www.droit.univ-paris5.fr/futtersack/english/research/CCP/index.html 
. There's one simple solution for 5-queens in a single rule. But his  
general constraint-satisfaction paradigm leads to an excellent  
solution, linked from that page. The code needs only small changes to  
work with Jess.

On May 11, 2008, at 5:15 PM, Senlin Liang wrote:

> Dear all,
>
> I am trying to solve the N-Queens problem using Jess. Is there a way  
> to use rules to make a efficient program, or I have to use functions  
> to do the brute force search?
>
> I am trying to compare several systems to see which one is good at  
> this N-Queens problem.
>
> Thanks,
> Senlin

---------------------------------------------------------
Ernest Friedman-Hill
Informatics & Decision Sciences          Phone: [phone]
Sandia National Labs                FAX:   [phone]
PO Box 969, MS 9012                 ejfried@...
Livermore, CA 94550                 http://www.jessrules.com




--------------------------------------------------------------------
To unsubscribe, send the words 'unsubscribe jess-users you@...'
in the BODY of a message to majordomo@..., NOT to the list
(use your own address!) List problems? Notify owner-jess-users@....
--------------------------------------------------------------------