All geek questions in one place

N-queens puzzle in Java with 1D array

I am working on a problem that is apparently somewhat well-known among novice programmers, a puzzle of 8 queens. I saw several solutions to these problems using 2D arrays, recursion, etc., but this problem is the task given in the chapter of the CS course book, which presents 1D arrays, so the available methods for solving this problem are limited.

The procedure I used was to first create a 1D array of size 64, which makes it possible to position the queen from index 0 to 63. Then a random position index is generated, and the test is pre-formed to check if there are any uterus attacking this position. If no queens attack this position, the queen is placed by setting board[position] = true. When the queen is placed, it queenCountgrows, and this process is repeated until 8 queens are set.

If the queens are placed in such a way that it is impossible to place 8, the board is reset after 1 millisecond, pre-forming a timecheck, and retries to place 8 queens. At best, I can place 7 queens, but the last remaining one never fits. Each attempt is printed with queenCountfor this attempt. Can this approach be used, or is it a dead end?

Sample code below:

package ch7;

public class Chapter_07_E22_EightQueens64bool {

    public static void main(String[] args) {

        int queenCount = 0;
        int attemptCount = 0;
        boolean[] board = new boolean[8 * 8];
        final long TIME_LIMIT = 1; //Milliseconds

        long startTime = System.currentTimeMillis();
        while (queenCount < 8) {

                int position = placeQueen(board.length);

                if(checkPosition(position, board) && !board[position]) {
                    board[position] = true;
                    queenCount++;
                }

                long timeCheck = System.currentTimeMillis();
                if (timeCheck - startTime > TIME_LIMIT) {
                    clearBoard(board);
                    queenCount = 0;
                    startTime = System.currentTimeMillis();
                }         
            System.out.println("Attempt #" + ++attemptCount);
            System.out.println(queenCount + " queens placed.");
            printBoard(board);
        }   
    }      

    public static void printBoard(boolean[] board) {

        for (int i = 0; i < board.length; i++) {

            if (board[i])
                System.out.print("|Q");
            else
                System.out.print("| ");

            if ((i + 1) % 8 == 0)
                System.out.println("|");    
        }
    }

    public static int placeQueen(int boardSize) {
        return (int)(Math.random() * boardSize);
    } 

    public static boolean[] clearBoard(boolean[] board) {

        for (int i = 0; i < board.length; i++)
            board[i] = false;

        return board;

    }

    public static boolean checkPosition(int position, boolean[] board) {

        return checkTop(position, board) && checkBottom(position, board) && checkLeft(position, board) &&
               checkRight(position, board) && checkTopLeft(position, board) && checkTopRight(position, board) &&
               checkBottomLeft(position, board) && checkBottomRight(position, board);
    }

    public static boolean checkTop(int position, boolean[] board) {
        // Checks each field above the current position while i >= 8  
        for (int i = position; i >= 8; i -= 8) {
            if (board[i - 8])
                    return false;  
        }
        return true;                
    }

    public static boolean checkBottom(int position, boolean[] board) {
        // Checks each field below the current position while i <= 55;
        for (int i = position; i <= 55; i += 8) {
            if (board[i + 8])
                    return false;
        }
        return true;                
    }

    public static boolean checkRight(int position, boolean[] board) {
        // Checks each field to the right of the current position while i % 8 < 7
        for (int i = position; i % 8 < 7; i += 1) {
            if (board[i + 1])
                return false;

        }
        return true;                
    }

    public static boolean checkLeft(int position, boolean[] board) {
        // Checks each field to the left of the current position while i % 8 != 0
        for (int i = position; i % 8 != 0; i -= 1) {
            if (board[i - 1])
                return false;  
        }
        return true;                
    }

    public static boolean checkTopLeft(int position, boolean[] board) {
        // Checks each field top left of the current position while i >= 9
        for (int i = position; i >= 9; i -= 9) {
            if (board[i - 9])
                return false;   
        }
        return true;                
    }

    public static boolean checkTopRight(int position, boolean[] board) {
        // Checks each field top right of the current position while i >= 7   
        for (int i = position; i >= 7; i -= 7) {
            if (board[i - 7])
                return false;   
        }
        return true;                
    }

    public static boolean checkBottomRight(int position, boolean[] board) {
        // Checks each field below the current position while i <= 54
        for (int i = position; i <= 54; i += 9) {
            if (board[i + 9])
                return false;    
        }
        return true;                
    }

    public static boolean checkBottomLeft(int position, boolean[] board) {
        // Checks each field below the current position while i <= 56
        for (int i = position; i <= 56; i += 7) {
            if (board[i + 7])
                return false;   
        }
        return true;                
    }

}
+4
source share
3 answers

After working on this problem for several days, I now have a solution that works for a reasonable amount of time for N <= 20. This happens as follows.

  • For i < N, queens[i] = i. 1 , . , .

  • , , , . , x1 x0 y1 y0. , (x0, y0) (x1, y1) .

  • shareDiagonal(int x0, int y0, int x1, int y1), , , , 7, 7. , . , , , 2 , 2 . 2 4, 4 .

  • checkRowForCollision(int[] queens, int row), . 1 , - 0, 2 , - 0 1, 3 , - 0, 1 2 ..

  • , , , .

:

package ch7;

public class Chapter_07_E22_EightQueens {

    static final int N = 8;

    public static void main(String[] args) {

        int[] queens = new int[N];
        int attempts = 0;

        for (int i = 0; i < N; i++) 
            queens[i] = i;

        while (checkBoardForCollision(queens)) {
            shuffleBoard(queens);
            attempts++;
        }
        printBoard(queens);
        System.out.println("Solution found in " + attempts + " attempts");
    }

    public static void printBoard(int[] queens) {

        for (int row = 0; row < N; row++) {
            System.out.printf("%-1c", '|');
            for (int column = 0; column < N; column++) {
                System.out.printf("%-1c|", (queens[row] == column) ? 'Q' : ' ');
            }
            System.out.println();
        }       
    }

    public static boolean shareDiagonal(int x0, int y0, int x1, int y1) {

        int dy = Math.abs(y1 - y0);
        int dx = Math.abs(x1 - x0);

        return dx == dy;
    }

    public static boolean checkRowForCollision(int[] queens, int row) {

        for (int i = 0; i < row; i++) {

            if (shareDiagonal(i, queens[i], row, queens[row]))
                return true;    
        }
        return false;
    }

    public static boolean checkBoardForCollision(int[] queens) {

        for (int row = 0; row < queens.length; row++)
            if (checkRowForCollision(queens, row))
                return true;

        return false;
    }

    public static int[] shuffleBoard(int[] queens) {

        for (int i = queens.length - 1;  i > 0; i--) {

            int j = (int)(Math.random() * (i + 1));

            int temp = queens[i];
            queens[i] = queens[j];
            queens[j] = temp;
        }
        return queens;
    }
}
+1

-, 8 .
, , .

[0, 2, 4, 6, 1, 3, 5, 7]

, , 3- , 3- 5- ..

, , , ​​ , , . , .

- (). , . , 8 - .

, . -
, # 0 №3.
?
# 2 # 4 (-1 +1)
# 1 # 5 (-2 +2)
# 0 # 6 (-3 +3)
, , , (newIndex - oldIndex) + oldRow == newRow, (newIndex - oldIndex) - oldRow == newRow

, ,

boolean canAdd(List<Integer> p, int newRow) {
    if (p.contains(newRow))
        return false;
    int insertIndex = p.size();
    for (int i = 0; i < p.size(); i++) {
        if (p.get(i) + (insertIndex - i) == newRow || p.get(i) - (insertIndex - i) == newRow)
            return false;
    }
    return true;
}


void solve(List<Integer> p, int index) {
    if (index == 8) {
        System.out.println(p);
        return;
    }

    for (int i = 0; i < 8; i++) {
        if (canAdd(p, i)) {
            p.add(i);
            solve(p, index + 1);
            p.remove(p.size() - 1);
        }
    }
}


solve(new ArrayList<Integer>(), 0);
+2

, , checkTop.

public static boolean checkTop(int position, boolean[] board)
{
    // Checks each field above the current position while i - 8 > - 1
    for (int i = position; i > (i - 8); i -= 8)
    {
        if ((i - 8) > -1)
        {
            if (board[i - 8])
                return false;
        }
    }
    return true;
}

There are times when a method does not find a slot ( board[i - 8] = true) and ireaches a value 7. After this point, condition for loop( i > (i - 8)) will always be true, and the condition of the most external ifinside the loop ( if ( (i - 8) > -1) will always be false. This causes the program to remain in the loop indefinitely.

Example ( ireaches -5):

i = -5;
i > ( i - 8) :  -5 > (-5 -8 = -13) (always true) 
(i - 8) > -1 :  -13 > -1           (false) always false for i <= 7
0
source

Source: https://habr.com/ru/post/1628568/

More articles:


All Articles