N-Queens @LeetCode

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

	package leetcode;
	import java.util.ArrayList;
	/**
	* Solution: classic recursion + backtrack problem
	* validQueen: 1. same column. 2. left-top to right-bottom 3. right-top to left-bottom
	*
	* The value is cols means which line the queen is. like cols.get(0) = 6. mean first column queen is located in 7th line.
	* So when we draw the chessBoard, we draw col by col but not line by line. This doesn't matter.
	*
	* @author jeffwan
	* @date Apr 7, 2014
	*/
	public class SolveNQueens {
	public ArrayList<String[]> solveNQueens(int n) {
	ArrayList<String[]> result = new ArrayList<String[]>();
	ArrayList<Integer> cols = new ArrayList<Integer>();
	if (n <= 0) {
	return result;
	}
	search(result, cols, n);
	return result;
	}
	public void search(ArrayList<String[]> result, ArrayList<Integer> cols, int n) {
	if (cols.size() == n) {
	result.add(drawChessBoard(cols));
	return;
	}
	for (int col = 0; col < n; col++) {
	if (!isValid(cols, col)) {
	continue;
	}
	cols.add(col);
	search(result, cols, n);
	cols.remove(cols.size() - 1);
	}
	}
	public boolean isValid(ArrayList<Integer> cols, int col) {
	int row = cols.size(); // this will be the index of new col.
	for (int i = 0; i < row; i++) {
	// Same column
	if (cols.get(i) == col) {
	return false;
	}
	// left-top to right-bottom
	if (i - cols.get(i) == row - col) {
	return false;
	}
	// right-top to left-bottom
	if (i + cols.get(i) == row + col) {
	return false;
	}
	}
	return true;
	}
	public String[] drawChessBoard(ArrayList<Integer> cols) {
	String[] chessBoard = new String[cols.size()];
	for (int i = 0; i < cols.size(); i++) {
	chessBoard[i] = "";
	for (int j = 0; j < cols.size(); j++) {
	if (j == cols.get(i)) {
	chessBoard[i] += 'Q';
	} else {
	chessBoard[i] += '.';
	}
	}
	}
	return chessBoard;
	}
	}

view raw SolveNQueens.java hosted with ❤ by GitHub