N-Queens - Java Solution

1. Introduction

This blog post explores the classic N-Queens puzzle, which involves placing N queens on an N x N chessboard such that no two queens attack each other. It's a well-known problem in algorithm design, particularly in the use of backtracking to explore possible solutions.

Problem

Given an integer N, the challenge is to find all distinct solutions to the N-Queens puzzle. Each solution must ensure that no two queens are in a position to attack each other, which means they cannot be in the same row, column, or diagonal. The solutions should represent the chessboard configurations, with 'Q' denoting a queen and '.' denoting an empty space.

2. Solution Steps

1. Use backtracking to explore all possible placements of queens.

2. Place a queen in a row and recursively try placing queens in the following rows.

3. Before placing a queen, check for conflicts with already placed queens.

4. If a position is safe, place the queen and move to the next row.

5. If a solution is found, add it to the list of solutions.

6. Backtrack and try different placements for queens.

7. Return the list of all valid solutions.

3. Code Program

import java.util.ArrayList;
import java.util.List;

public class NQueens {
    public static void main(String[] args) {
        int n = 4; // Example size of the chessboard
        System.out.println(solveNQueens(n)); // Test the function
    }

    // Function to solve N-Queens puzzle
    public static List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        List<List<String>> result = new ArrayList<>();
        backtrack(board, 0, result);
        return result;
    }

    // Helper function for backtracking
    private static void backtrack(char[][] board, int row, List<List<String>> result) {
        if (row == board.length) {
            result.add(construct(board));
            return;
        }

        for (int col = 0; col < board.length; col++) {
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';
                backtrack(board, row + 1, result);
                board[row][col] = '.'; // Backtrack
            }
        }
    }

    // Check if it's valid to place a queen at the given position
    private static boolean isValid(char[][] board, int row, int col) {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < board.length; j++) {
                if (board[i][j] == 'Q' && (col == j || Math.abs(row - i) == Math.abs(col - j))) {
                    return false;
                }
            }
        }
        return true;
    }

    // Construct the board configuration from the 2D array
    private static List<String> construct(char[][] board) {
        List<String> res = new ArrayList<>();
        for (char[] row : board) {
            String s = new String(row);
            res.add(s);
        }
        return res;
    }
}

Output:

[
  [".Q..",
   "...Q",
   "Q...",
   "..Q."],
  ["..Q.",
   "Q...",
   "...Q",
   ".Q.."]
]

Explanation:

1. solveNQueens: Initializes the board and starts the backtracking process.

2. The board is initially filled with '.', indicating empty spaces.

3. backtrack: A recursive function that tries placing a queen in each column of the current row and checks if the placement is valid.

4. isValid: Checks if the queen can be placed at the given position without being attacked by other queens.

5. If a valid position is found, the function places a queen ('Q') and moves to the next row.

6. Once all queens are placed, the current board configuration is added to the result.

7. The function then backtracks to explore other possibilities.

8. The result is a list of all distinct solutions, where each solution is represented as a list of strings showing the queens' placement on the board.