Implementation of the Eight (Non-attacking) Knights using Prolog

Question

I am currently working on an algorithm that seeks to find all the solutions to the question, "How many ways is there to place 8 Knights on an 8x8 board in such a way that none of them can attack each other?"

Now I have been able to apply the 8 Queens 8x8 board solution for similar problems regarding 8 Bishops and 8 Rooks from the 8 Queens algorithm I found online. (Since Bishops and Rooks move either Diagonally, or Horizontally/Vertically across the board, it was very similar to the Queens algorithm)

Here is what I have so far.

solution([]).
solution([X/Y|Others]) :-
   solution(Others),
   member(Y, [1, 2, 3, 4, 5, 6, 7, 8]),
   noattack(X/Y, Others).


noattack(_,[]).
noattack(X/Y, [X1/Y1|Others]):-
      Y1 - Y =\= 2, X1 - X =\= 1
   ;  Y - Y1 =\= 2, X1 - X =\= 1
   ;  Y1 - Y =\= 2, X - X1 =\= 1
   ;  Y - Y1 =\= 2, X - X1 =\= 1
   ;  Y1 - Y =\= 1, X1 - X =\= 2
   ;  Y - Y1 =\= 1, X1 - X =\= 2
   ;  Y1 - Y =\= 1, X - X1 =\= 2
   ;  Y - Y1 =\= 1, X - X1 =\= 2
   ;  noattack(X/Y, Others).     

template([1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8]).

main :-
    open('knights.out',write,ID),
    (   ( template(X), solution(X), write(ID,X), nl(ID), fail )
       ; close(ID)
    ).

Basically, I more or less modeled this algorithm off of the standard 8-Queens Prolog algorithm, but instead of comparing Y and Y1 for potential "horizontal" potential attacks and Y1-Y =\= X1 - X and Y1-Y =\= X - X1 for diagonal potential attacks like I did with the queen, this time i am comparing every exact location of the next possible spot with anywhere the current Knight can attack, and unifying that to something that unifies with noattack. (Sorry, being a Python focused CS Student, I really suck at explaining this. If you don't get up until this point, please check out http://www.javaist.com/blog/2008/11/06/eight-queens-problem-in-prolog/) He does a good job explaining what the 8 Queens algorithm is.

Now the standard way to run this would be.

?- template(A), solution(A).

and then at the first unification, press "a" in order to print out all the solutions in the gprolog or swiprolog interactive console. For 8 queens, there are only 32 solutions so, one could just go line by line in the backtracking sequence and count for 32 in order to verify the algorithm. But for the 8 Knights Problem, there would be 379978716 valid solutions (according to http://oeis.org/search?q=nonattacking%20knights&sort=&language=&go=Search). That is where the "main" function at the end comes in hand. This basically prints out every unification in to a file called "knights.out," so I can open it in a code editor to see if there are 379978716 lines.

Running, some calculations, I calculated that the output file should be somewhere around 14 gigs, but my algorithm currently produces a file greater than 70G's (potentially could be infinite loop, but my Linux Partitian could only store 70G's so I don't know). But either way, this algorithm is double counting a few times, and I don't know how to fix this.

Any help would be appreciated. (For Brevity, I did not upload the code for Eight Bishops and Eight Rooks, but if you are interested, I keep them here: https://github.com/gilgameshskytrooper/eightqueens)

14GB? You can count answers in Prolog! And you even could count solutions. library(clpfd) is a way to go! — false
You need extra round brackets around your complex condition! You are enumerating almost all possibilities! — false
One thing I do not understand at all: You can place 32 Knights on a 8x8 chessboard without one attacking the other. So why do you want to place only 8? — false
@false Because that what the problem is. I want to know every viable solution of "how can you place 8 knights on an 8x8 board so they can't attack each other. — Gilgamesh Skytrooper

coder coder · Accepted Answer · 2016-11-06T09:43:17

Your solution as pointed in the comments is not correct. I would suggest some improvements: Instead of:

noattack(X/Y, [X1/Y1|Others]):-
    Y1 - Y =\= 2, X1 - X =\= 1;
    Y - Y1 =\= 2, X1 - X =\= 1;
    Y1 - Y =\= 2, X - X1 =\= 1;
    Y - Y1 =\= 2, X - X1 =\= 1;
    Y1 - Y =\= 1, X1 - X =\= 2;
    Y - Y1 =\= 1, X1 - X =\= 2;
    Y1 - Y =\= 1, X - X1 =\= 2;
    Y - Y1 =\= 1, X - X1 =\= 2;
    noattack(X/Y, Others).

You could simply use abs and write:

noattack(X/Y, [X1/Y1|Others]):-
  Y =\= Y1,
  abs(Y1-Y) =\= abs(X1-X),
  noattack(X/Y,Others).

In the above predicate we didn't need to write: X =\= X1, since due to template we assume the X's are distinct.

This doesn't answer the question but this a is much better way to write it and it wouldn't fit in a comment...

Implementation of the Eight (Non-attacking) Knights using Prolog

1 Answers