LinuxQuestions.org
View the Most Wanted LQ Wiki articles.
Go Back   LinuxQuestions.org > Blogs > Bits and Pixels
User Name
Password

Notices



Concerning free software, programming, and whatever else I find interesting. Also the blog for my Web site, frigidcode.com.
Rate this Entry

First prolog program: eight queens problem

Posted 11-09-2012 at 04:36 AM by hydraMax
Updated 11-09-2012 at 04:38 AM by hydraMax
Tags prolog, puzzles

Sniff, sniff... my first prolog "program" is complete. I decided to do a solution to the eight queens problem, figuring that no one has tried that one before.

Code:
%% Prolog Eight Queens Solution
%% Copyright 2012 by Christopher Howard
%%
%% CC0 Public Domain Dedication:
%% To the extent possible under law, Christopher Howard has waived all copyright
%% and related or neighboring rights to Prolog Eight Queens Solution. This work
%% is published from: United States.
%%
%% creativecommons.org/publicdomain/zero/1.0/
%%
%% Written for GNU Prolog 1.4.1
%%
%% To use, load in interpreter and call
%%
%% ?- queensSolution(A).
%%
%% To get all solutions at once, call
%%
%% ?- setof(A,queensSolution(A),B).
%%
%% Board representation is a list with each element representing a queen on a
%% separate file (left to right) with the integer representing the rank the
%% queen is located on.
%%
%% This program uses the traditional brute force method, first solving the
%% Eight rooks problem and then eliminating solutions in which there is
%% diagonal contact.


queensSolution(A) :-
    queens(A)
    , \+ diagonalContact(A).

rank(1).
rank(2).
rank(3).
rank(4).
rank(5).
rank(6).
rank(7).
rank(8).

queens([A,B,C,D,E,F,G,H]) :-
    queens__([A,B,C,D,E,F,G,H])
    , queens_([A,B,C,D,E,F,G,H])
    .

queens__([A]) :- rank(A).

queens__([A|B]) :-
    rank(A)
    , queens__(B)
    .

queens_([_]).

queens_([A|B]) :-
    \+ member(A,B)
    , queens_(B)
    .

diagonalContact([A|B]) :-
    diagonalContact_(A,1,B)
    ; diagonalContact(B)
    .

diagonalContact_(A,B,[C|D]) :-
    A+B =:= C
    ; A-B =:= C
    ; ( E is B+1
      , diagonalContact_(A,E,D)
      )
    .
Sorry, I didn't feel like writing the GUI, so you just have to read the arrays:

Code:
| ?- setof(A,queensSolution(A),B), length(B,C).

B = [[1,5,8,6,3,7,2,4],[1,6,8,3,7,4,2,5],[1,7,4,6,8,2,5,3],[1,7,5,8,2,4,6,3],[2,4,6,8,3,1,7,5],[2,5,7,1,3,8,6,4],[2,5,7,4,1,8,6,3],[2,6,1,7,4,8,3,5],[2,6,8,3,1,4,7,5],[2,7,3,6,8,5,1,4],[2,7,5,8,1,4,6,3],[2,8,6,1,3,5,7,4],[3,1,7,5,8,2,4,6],[3,5,2,8,1,7,4,6],[3,5,2,8,6,4,7,1],[3,5,7,1,4,2,8,6],[3,5,8,4,1,7,2,6],[3,6,2,5,8,1,7,4],[3,6,2,7,1,4,8,5],[3,6,2,7,5,1,8,4],[3,6,4,1,8,5,7,2],[3,6,4,2,8,5,7,1],[3,6,8,1,4,7,5,2],[3,6,8,1,5,7,2,4],[3,6,8,2,4,1,7,5],[3,7,2,8,5,1,4,6],[3,7,2,8,6,4,1,5],[3,8,4,7,1,6,2,5],[4,1,5,8,2,7,3,6],[4,1,5,8,6,3,7,2],[4,2,5,8,6,1,3,7],[4,2,7,3,6,8,1,5],[4,2,7,3,6,8,5,1],[4,2,7,5,1,8,6,3],[4,2,8,5,7,1,3,6],[4,2,8,6,1,3,5,7],[4,6,1,5,2,8,3,7],[4,6,8,2,7,1,3,5],[4,6,8,3,1,7,5,2],[4,7,1,8,5,2,6,3],[4,7,3,8,2,5,1,6],[4,7,5,2,6,1,3,8],[4,7,5,3,1,6,8,2],[4,8,1,3,6,2,7,5],[4,8,1,5,7,2,6,3],[4,8,5,3,1,7,2,6],[5,1,4,6,8,2,7,3],[5,1,8,4,2,7,3,6],[5,1,8,6,3,7,2,4],[5,2,4,6,8,3,1,7],[5,2,4,7,3,8,6,1],[5,2,6,1,7,4,8,3],[5,2,8,1,4,7,3,6],[5,3,1,6,8,2,4,7],[5,3,1,7,2,8,6,4],[5,3,8,4,7,1,6,2],[5,7,1,3,8,6,4,2],[5,7,1,4,2,8,6,3],[5,7,2,4,8,1,3,6],[5,7,2,6,3,1,4,8],[5,7,2,6,3,1,8,4],[5,7,4,1,3,8,6,2],[5,8,4,1,3,6,2,7],[5,8,4,1,7,2,6,3],[6,1,5,2,8,3,7,4],[6,2,7,1,3,5,8,4],[6,2,7,1,4,8,5,3],[6,3,1,7,5,8,2,4],[6,3,1,8,4,2,7,5],[6,3,1,8,5,2,4,7],[6,3,5,7,1,4,2,8],[6,3,5,8,1,4,2,7],[6,3,7,2,4,8,1,5],[6,3,7,2,8,5,1,4],[6,3,7,4,1,8,2,5],[6,4,1,5,8,2,7,3],[6,4,2,8,5,7,1,3],[6,4,7,1,3,5,2,8],[6,4,7,1,8,2,5,3],[6,8,2,4,1,7,5,3],[7,1,3,8,6,4,2,5],[7,2,4,1,8,5,3,6],[7,2,6,3,1,4,8,5],[7,3,1,6,8,5,2,4],[7,3,8,2,5,1,6,4],[7,4,2,5,8,1,3,6],[7,4,2,8,6,1,3,5],[7,5,3,1,6,8,2,4],[8,2,4,1,7,5,3,6],[8,2,5,3,1,7,4,6],[8,3,1,6,2,5,7,4],[8,4,1,3,6,2,7,5]]
C = 92

(23066 ms) yes
I haven't hand checked all of those, but since there are exactly 92 results I feel fairly confident.
Posted in Uncategorized
Views 836 Comments 0
« Prev     Main     Next »
Total Comments 0

Comments

 

  



All times are GMT -5. The time now is 03:33 AM.

Main Menu
Advertisement

Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration