Matlab N-Queen Problem

Question

main.m

counter = 1;
n = 8;
board = zeros(1,n);
back(0, board);
disp(counter);

sol.m

function value = sol(board)

for ( i = 1:(length(board)))
   for ( j = (i+1): (length(board)-1))
       if (board(i) == board(j))
          value = 0;
          return;
       end
       if ((board(i) - board(j)) == (i-j))
          value = 0;
          return;
       end
       if ((board(i) - board(j)) == (j-i))
          value = 0;
          return;
       end
   end
end
value = 1;
return;

back.m

function back(depth, board)

disp(board);

if ( (depth == length(board)) && (sol2(board) == 1))
    counter = counter + 1;
end

if ( depth < length(board))
   for ( i = 0:length(board))
       board(1,depth+1) = i;
       depth = depth + 1;
       solv2(depth, board);
   end
end

I'm attempting to find the maximum number of ways n-queen can be placed on an n-by-n board such that those queens aren't attacking eachother. I cannot figure out the problem with the above matlab code, i doubt it's a problem with my logic since i've tested out this logic in java and it seems to work perfectly well there. The code compiles but the issue is that the results it produces are erroneous.

Java Code which works:

               public static int counter=0;

                public static boolean isSolution(final int[] board){
                    for (int i = 0; i < board.length; i++) {
                        for (int j = i + 1; j < board.length; j++) {
                            if (board[i] == board[j]) return false;    
                            if (board[i]-board[j] == i-j) return false; 
                            if (board[i]-board[j] == j-i) return false; 
                        }
                    }
                    return true;
                }

                public static void solve(int depth, int[] board){

                    if (depth == board.length && isSolution(board)) {
                        counter++;
                 }
               if (depth < board.length) {  // try all positions of the next row

                for (int i = 0; i < board.length; i++) {
                            board[depth] = i;
                            solve(depth + 1, board);
                        }
                    }
                }


                    public static void main(String[] args){
                        int n = 8;
                        solve(0, new int[n]);
                    System.out.println(counter);
                    }

Answer 1

There are many problems with your code.

Here are just a few:

• you initialize board as 1-by-8 array
• you call functions sol2 and solv2 that are undefined
• no output is captured for solv2, or back (remember, Matlab passes variables by value, not by reference)
• there are no comments in the code that would explain what you think you're doing and why you'd want to do that.

Also: While Matlab has a JIT compiler that, among others, helps speed up loops, Matlab code can't be said to "compile" (unless you're doing something dramatically wrong).

Answer 2

Worked code:

function queen
clc;
counter = 0;
n = 8;
board = zeros(1,n);
[board,counter] = back(1, board,counter);
fprintf('Solution count: %d\n',counter);
%%
function value =  isSolution(board)

for  i = 1:length(board)
   for  j = (i+1): length(board)
       if abs(board(i) - board(j)) == abs(i-j)
          value = false;
          return;
       end      
   end
end
value = true;
%%
function [board,counter] =  back(depth, board,counter)

if  (depth == length(board)+1) && isSolution(board)
    counter = counter + 1;
    disp(board);
end

if ( depth <= length(board))
   for  i = 1:length(board)
       if ~any(board==i)
           board(1,depth) = i;           
           [~,counter] = back(depth+1, board,counter);
       end       
   end
end

I add line if ~any(board==i), without this check, I think your java solution slower than this Matlab code. For fastest solution google "Dancing links".