Matlab N-Queen Задача

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

Я пытаюсь найти максимальное количество способов размещения n-ферзя на доске n-n-n, чтобы эти королевы не атаковали друг друга. Я не могу понять проблему с приведенным выше кодом Matlab, я сомневаюсь, что это проблема с моей логикой, так как я проверил эту логику в Java, и она, кажется, там работает отлично Код компилируется, но проблема в том, что его результаты ошибочны.

Java-код, который работает:

               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

Рабочий код:

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

Я добавляю строку, если ~ любая (board == i), без этой проверки, я думаю, ваше решение Java медленнее, чем этот код Matlab Для скорейшего решения воспользуйтесь Google "Танцующие ссылки".

Answer 2

Есть много проблем с вашим кодом.

Вот лишь некоторые из них:

• вы инициализируете board как массив 1 на 8
• , который вы вызываете функциями sol2 и solv2, которыене определены
• для solv2 или back не выводятся выходные данные (помните, Matlab передает переменные по значению, а не по ссылке)
• в коде нет комментариев, которые бы объясняличто вы думаете и зачем хотите делать.

Кроме того: хотя Matlab имеет JIT-компилятор, который, помимо прочего, помогает ускорить циклы, код Matlab не может бытьсказал "компилировать" (если вы делаете что-то резко неправильно).