Блог

Все это связано со знаменитой проблемой NQueens. Моя программа работает нормально (обратный подход). Он находит все решения для данного размера платы. Код показан ниже.

Я пытаюсь изменить код, чтобы я мог найти все решения для данного столбца первого ферзя. Я не хочу менять позицию первой королевы. Для примера он предоставит мне решение

   [2, 0, 3, 1, 4] and [2, 4, 1, 3, 0]
 

когда я ставлю первую королеву на 2, размер доски 5 (третий столбец, индекс начинается с нуля).

Я попробовал это сделать, установив разные значения для k (а также для платы[k]), но не совсем достиг цели. Любые намеки будут оценены по достоинству.

Вот мой код. Удалены подробности о place методе, так как он не должен быть изменен для достижения моей новой цели.

 public class NQueensAllSolutions
{
    //  Board size
    static int size = 8;
    
    //  One dimensional array to store the column number for all queens.
    static int[] board = new int[size];
    
    //  This method will check the validity for a new queen. works fine.
    static boolean place(int k)
    {
        .
        .       
    }
    
    
    public static void main(String[] args) 
    {
        int k;
        
        long t=0;   //  for counting total found solutions

        k = 0;
        board[k] = -1;      

        while(k >= 0) {

            board[k]  ;

            while(board[k] < size amp;amp; !(place(k))) board[k]  ;

            if(board[k] < size) {
                if(k == size-1) {   //  a solution is found.
                    
                    t  ;                    
                    
                    //System.out.println("nnTotal: " t " --> " Arrays.toString(board));   
                }
                else {
                    k  ; board[k] = -1;
                }
            }
            else {              
                k--;    //  backtrack.              
            }
        }
        
        System.out.println("nnTotal: " t);
    }
}
 

Просто держите k в цикле значение больше 0 while :

 import java.util.Arrays;

public class Queens
{
    static int size = 5;
    static int[] board = new int[size];

    static boolean isValid(int k)
    {
        int c1 = board[k];
        int c2 = board[k];
        for(int r=k-1;r>=0;r--)
        {
            c1--;
            c2  ;
            if(board[r] == board[k] || board[r] == c1 || board[r] == c2)
                return false;
        }
        return true;
    }

    public static void main(String[] args) 
    {
        int t = 0;

        // Set the first queen position
        board[0] = 2;

        int k = 1;
        board[k] = -1;

        // k must stay greater than 0
        while(k >= 1) {
            board[k]  ;
            while(board[k] < size amp;amp; !isValid(k))
                board[k]  ;
            if(board[k] < size) {
                if(k == size-1) {
                    t  ;
                    System.out.println("Solution " t " --> " Arrays.toString(board));
                }
                else {
                    k  ;
                    board[k] = -1;
                }
            }
            else {
                k--;
            }
        }
    }
}
 

Выход:

 Solution 1 --> [2, 0, 3, 1, 4]
Solution 2 --> [2, 4, 1, 3, 0]
 

Обновить

Вот обобщенная версия, которая может заставить ферзя занять позицию ( fixedRow , fixedCol ). Ключевым изменением является новый getNextCol() метод, который используется для получения следующего возможного столбца для ферзя. В строке fixedRow единственным возможным столбцом является fixedCol . В других строках возможны все столбцы.

 import java.util.Arrays;

public class Queens
{
    static int size = 5;
    static int fixedRow = 2;
    static int fixedCol = 0;
    static int[] board = new int[size];

    static boolean isValid(int k)
    {
        int c1 = board[k];
        int c2 = board[k];
        for(int r=k-1;r>=0;r--)
        {
            c1--;
            c2  ;
            if(board[r] == board[k] || board[r] == c1 || board[r] == c2)
                return false;
        }
        return true;
    }

    static int getNextCol(int k, int col)
    {
        if(k == fixedRow) {
            // Only one possible move on this row
            return col == -1 ? fixedCol : size;
        }
        else {
            // Try the next column
            return col 1;
        }
    }

    public static void main(String[] args) 
    {
        int t = 0;
        int k = 0;
        board[k] = -1;

        while(k >= 0) {
            board[k] = getNextCol(k, board[k]);
            while(board[k] < size amp;amp; !isValid(k))
                board[k] = getNextCol(k, board[k]);
            if(board[k] < size) {
                if(k == size-1) {
                    t  ;
                    System.out.println("Solution " t " --> " Arrays.toString(board));
                }
                else {
                    k  ;
                    board[k] = -1;
                }
            }
            else {
                k--;
            }
        }
    }
}
 

Выход:

 Solution 1 --> [1, 3, 0, 2, 4]
Solution 2 --> [4, 2, 0, 3, 1]