Implementation of the Eight (Non-attacking) Knights using Prolog
<p>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?"</p>

<p>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)</p>

<p>Here is what I have so far.</p>

<pre><code>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)
    ).
</code></pre>

<p>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 <a href="http://www.javaist.com/blog/2008/11/06/eight-queens-problem-in-prolog/" rel="nofollow noreferrer">http://www.javaist.com/blog/2008/11/06/eight-queens-problem-in-prolog/</a>) He does a good job explaining what the 8 Queens algorithm is.</p>

<p>Now the standard way to run this would be.</p>

<pre><code>?- template(A), solution(A).
</code></pre>

<p>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 <a href="http://oeis.org/search?q=nonattacking%20knights&amp;sort=&amp;language=&amp;go=Search" rel="nofollow noreferrer">http://oeis.org/search?q=nonattacking%20knights&amp;sort=&amp;language=&amp;go=Search</a>). 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.</p>

<p>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.</p>

<p>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: <a href="https://github.com/gilgameshskytrooper/eightqueens" rel="nofollow noreferrer">https://github.com/gilgameshskytrooper/eightqueens</a>)</p>