10
\$\begingroup\$

Print all the ways of arranging eight queens on an 8x8 board. Rules: Queens should not share the same row, column, of any diagonal.

Any comment on my solution? I didn't write unit tests but I checked visually the solutions.

public class solution {

  public static void printMatrix(char[][] board) {
    // 8x8 board
    int n = board.length;
    System.out.println("------------------------------");
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        System.out.print(board[i][j] + "|");
      }
      System.out.println();
    }
    System.out.println("------------------------------");

  }

  public static void updateBoard(int row, int col, boolean[][] logicalBoard) {
    // Turn all the cases corresponding to the row, column and diagonals of the element added to
    // false
    // 8x8 board
    int n = logicalBoard.length;

    // update the row
    for (int j = 0; j < n; j++) {
      logicalBoard[row][j] = false;
    }

    // update the column
    for (int j = 0; j < n; j++) {
      logicalBoard[j][col] = false;
    }

    // update the diagonals
    int r = row;
    int c = col;
    while (r >= 0 && c >= 0) {
      logicalBoard[r][c] = false;
      r--;
      c--;
    }

    r = row;
    c = col;
    while (r < 8 && c < 8) {
      logicalBoard[r][c] = false;
      r++;
      c++;
    }

    r = row;
    c = col;
    while (r < 8 && c >= 0) {
      logicalBoard[r][c] = false;
      r++;
      c--;
    }

    r = row;
    c = col;
    while (r >= 0 && c < 8) {
      logicalBoard[r][c] = false;
      r--;
      c++;
    }
  }

  public static char[][] copyArray(char[][] original) {
    char[][] copy = new char[original.length][];
    for (int i = 0; i < original.length; i++) {
      copy[i] = original[i].clone();
    }
    return copy;
  }

  public static boolean[][] copyArray(boolean[][] original) {
    boolean[][] copy = new boolean[original.length][];
    for (int i = 0; i < original.length; i++) {
      copy[i] = original[i].clone();
    }
    return copy;
  }

  public static void arrangeQueens(char[][] board, boolean[][] logicalBoard, int rowNumber) {
    if (rowNumber == 8) {
      printMatrix(board);
      return;
    }

    int n = board.length;
    for (int column = 0; column < n; column++) {
      if (logicalBoard[rowNumber][column]) {
        char[][] newBoard = copyArray(board);
        boolean[][] newLogicalBoard = copyArray(logicalBoard);
        newBoard[rowNumber][column] = 'Q';
        newLogicalBoard[rowNumber][column] = false;
        updateBoard(rowNumber, column, newLogicalBoard);
        arrangeQueens(newBoard, newLogicalBoard, rowNumber + 1);
      }
    }
  }

  public static void arrangeQueens() {
    int N = 8;
    char[][] board = new char[8][8];
    boolean[][] logicalBoard = new boolean[8][8];
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        board[i][j] = ' ';
        logicalBoard[i][j] = true;
      }
    }
    arrangeQueens(board, logicalBoard, 0);
  }

  public static void main(String[] args){
    arrangeQueens();
  }

}
\$\endgroup\$
1

1 Answer 1

6
\$\begingroup\$

Some points:

public class solution {

Java's conventions say that class names should be PascalCase, not camelCase:

public class Solution {

would be correct.

Another thing is that you print results like:

 | | | | | | |Q|
 |Q| | | | | | |
 | | | |Q| | | |
 | |Q| | | | | |
Q| | | | | | | |
 | | | | | |Q| |
 | | |Q| | | | |
 | | | | |Q| | |

Why not do:

| | | | | | | |Q|  
| |Q| | | | | | |  
| | | | |Q| | | |  
| | |Q| | | | | |  
|Q| | | | | | | |  
| | | | | | |Q| |  
| | | |Q| | | | |  
| | | | | |Q| | |

Therefore, printMatrix() will now be:

public static void printMatrix(char[][] board) {
    // 8x8 board
    int n = board.length;
    System.out.println("------------------------------");
    for (int i = 0; i < n; i++) {
        System.out.print("|");
        for (int j = 0; j < n; j++) {
            System.out.print(board[i][j] + "|");
        }
        System.out.println();
    }
    System.out.println("------------------------------");
}

Since this is Java, you might as well have some OOP in your code. It does not look like OOP at all. After some redesigning with OOP, your code will look like this:

public class Solution {

    public static void main(String[] args) {
        List<QueenBoard> solutions = new NQueensProblem(8).getAllSolutions();
        for(QueenBoard board : solutions) {
            System.out.println(board.toString());
        }
    }

}

class NQueensProblem {

    private int size;

    private List<QueenBoard> solutions;

    public NQueensProblem(int size) {
        this.size = size;
        this.solutions = new LinkedList<QueenBoard>();
        solve(size);
    }

    public void solve(int size) {
        QueenBoard board = new QueenBoard(size);
        LogicalBoard logicalBoard = new LogicalBoard(size);
        solve(board, logicalBoard, 0, size);
    }

    public List<QueenBoard> getAllSolutions() {
        return solutions;
    }

    private void solve(QueenBoard board, LogicalBoard logicalBoard,
            int rowNumber, int size) {
        if (rowNumber == size) {
            solutions.add(board);
            return;
        }
        for (int column = 0; column < size; column++) {
            if (logicalBoard.getPossible(rowNumber, column)) {
                QueenBoard newBoard = new QueenBoard(board);
                newBoard.setHasQueen(rowNumber, column, true);
                LogicalBoard newLogicalBoard = new LogicalBoard(logicalBoard);
                newLogicalBoard.setPossible(rowNumber, column, false);
                updateBoard(rowNumber, column, newLogicalBoard, size);
                solve(newBoard, newLogicalBoard, rowNumber + 1, size);
            }
        }
    }

    private void updateBoard(int row, int col, LogicalBoard logicalBoard, int size) {
        // update the row
        for (int j = 0; j < size; j++) {
            logicalBoard.setPossible(row, j, false);
        }
        // update the column
        for (int j = 0; j < size; j++) {
            logicalBoard.setPossible(j, col, false);
        }
        // update the diagonals
        int r = row;
        int c = col;
        while (r >= 0 && c >= 0) {
            logicalBoard.setPossible(r, c, false);
            r--;
            c--;
        }
        r = row;
        c = col;
        while (r < 8 && c < 8) {
            logicalBoard.setPossible(r, c, false);
            r++;
            c++;
        }
        r = row;
        c = col;
        while (r < 8 && c >= 0) {
            logicalBoard.setPossible(r, c, false);
            r++;
            c--;
        }
        r = row;
        c = col;
        while (r >= 0 && c < 8) {
            logicalBoard.setPossible(r, c, false);
            r--;
            c++;
        }
    }


}

class QueenBoard {

    private boolean[][] board;
    int size;

    public QueenBoard(int size) {
        this.size = size;
        this.board = new boolean[size][size];
    }

    public QueenBoard(QueenBoard oldBoard) {
        this.size = oldBoard.size;
        this.board = new boolean[size][size];
        for(int i = 0; i < size; i++) {
            for(int j = 0; j < size; j++) {
                this.board[i][j] = oldBoard.board[i][j];
            }
        }
    }

    public void setHasQueen(int x, int y, boolean value) {
        board[x][y] = value;
    }

    public boolean hasQueen(int x, int y) {
        return board[x][y];
    }

    @Override
    public String toString() {
        StringBuilder result = new StringBuilder();
        result.append("------------------------------\n");
        for (int i = 0; i < size; i++) {
            result.append("|");
            for (int j = 0; j < size; j++) {
                result.append((board[i][j] ? "Q" : " ") + "|");
            }
            result.append("\n");
        }
        result.append("------------------------------");
        return result.toString();
    }

}

class LogicalBoard {

    private boolean[][] board;
    int size;

    public LogicalBoard(int size) {
        this.size = size;
        board = new boolean[size][size];
        for(int i = 0; i < size; i++) {
            for(int j = 0; j < size; j++) {
                this.board[i][j] = true;
            }
        }
    }

    public LogicalBoard(LogicalBoard oldBoard) {
        this.size = oldBoard.size;
        this.board = new boolean[size][size];
        for(int i = 0; i < size; i++) {
            for(int j = 0; j < size; j++) {
                this.board[i][j] = oldBoard.board[i][j];
            }
        }
    }

    public void setPossible(int x, int y, boolean value) {
        board[x][y] = value;
    }

    public boolean getPossible(int x, int y) {
        return board[x][y];
    }

}

Major changes:

  1. The board is now a class
  2. The logical board is now a class
  3. Instead of printing all the solutions while solving, you get all the solutions through getAllSolutions() once it is finished solving the puzzle, and then print them one by one with System.out.println(board.toString())
  4. The solving methods are now non-static

This way, it looks much more Java-like.

Also:

private void updateBoard(int row, int col, LogicalBoard logicalBoard, int size) {
    // update the row
    for (int j = 0; j < size; j++) {
        logicalBoard.setPossible(row, j, false);
    }
    // update the column
    for (int j = 0; j < size; j++) {
        logicalBoard.setPossible(j, col, false);
    }
    // update the diagonals
    int r = row;
    int c = col;
    while (r >= 0 && c >= 0) {
        logicalBoard.setPossible(r, c, false);
        r--;
        c--;
    }
    r = row;
    c = col;
    while (r < 8 && c < 8) {
        logicalBoard.setPossible(r, c, false);
        r++;
        c++;
    }
    r = row;
    c = col;
    while (r < 8 && c >= 0) {
        logicalBoard.setPossible(r, c, false);
        r++;
        c--;
    }
    r = row;
    c = col;
    while (r >= 0 && c < 8) {
        logicalBoard.setPossible(r, c, false);
        r--;
        c++;
    }
}

looks over-repetitive. Try creating multiple methods to handle that:

private void updateBoard(int row, int col, LogicalBoard logicalBoard, int size) {
    updateRow(row, logicalBoard, size);
    updateColumn(col, logicalBoard, size);
    updateDiagonal(row, col, -1, -1, logicalBoard, size);
    updateDiagonal(row, col, 1, 1, logicalBoard, size);
    updateDiagonal(row, col, 1, -1, logicalBoard, size);
    updateDiagonal(row, col, -1, 1, logicalBoard, size);
}

private void updateRow(int row, LogicalBoard logicalBoard, int size) {
    for (int j = 0; j < size; j++) {
        logicalBoard.setPossible(row, j, false);
    }
}

private void updateColumn(int col, LogicalBoard logicalBoard, int size) {
    for (int j = 0; j < size; j++) {
        logicalBoard.setPossible(j, col, false);
    }
}

private void updateDiagonal(int row, int rowIncrement, int col, int colIncrement, LogicalBoard logicalBoard, int size) {
    while (row >= 0 && col < 8) {
        logicalBoard.setPossible(row, col, false);
        row += rowIncrement;
        col += colIncrement;
    }
}

This looks much nicer, and is less repetitive.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.