package com.github.sbugat.nqueens.solvers.bruteforce;

import com.github.sbugat.nqueens.GenericNQueensSolver;
import com.github.sbugat.nqueens.tools.InvalidSolutionsException;
import com.github.sbugat.nqueens.tools.SequenceTools;

/**
 * Greedy algorithm for the N queens puzzle solver. This algorithm is not optimized at all and is a floor value for optimisations tests.
 * 
 * @author Sylvain Bugat
 * 
 */
public final class BruteForceNQueensSolverOneDimension extends GenericNQueensSolver {

	/** Chessboard only one one dimension with all lines. */
	private final boolean[] chessboard;
	/** Current number of placedQueens */
	private int placedQueens;

	public BruteForceNQueensSolverOneDimension(final int chessboardSizeArg, final boolean printSolutionArg) {

		super(chessboardSizeArg, printSolutionArg);

		chessboard = new boolean[chessboardSizeArg * chessboardSizeArg];
	}

	@Override
	public long solve() {

		// Start the algorithm at the first position
		solve(0);

		// Return the number of solutions found
		return solutionCount;
	}

	/**
	 * Solving recursive method, do a greedy algorithm by testing all combinations.
	 * 
	 * @param i index of the unique dimension
	 */
	private void solve(final int i) {

		// Place a queen on the current position
		chessboard[i] = true;
		placedQueens++;

		// All queens are sets on the chessboard then a solution may be present
		if (placedQueens >= chessboardSize) {
			if (checkSolutionChessboard()) {
				solutionCount++;
				print();
			}
		} else {

			if (i + 1 < chessboard.length) {
				solve(i + 1);
			}
		}
		placedQueens--;
		chessboard[i] = false;

		if (i + 1 < chessboard.length) {
			solve(i + 1);
		}
	}

	/**
	 * Check if a chessboard with N queens is a solution (only one queens per lines, columns and diagnonals).
	 * 
	 * @return true if the chessboard contain a solution, false otherwise
	 */
	private boolean checkSolutionChessboard() {

		// Check if 2 queens are on the same line
		for (int y = 0; y < chessboard.length; y += chessboardSize) {

			boolean usedLine = false;
			for (int x = y; x < y + chessboardSize; x++) {

				if (chessboard[x]) {
					if (usedLine) {
						return false;
					}
					usedLine = true;
				}
			}
		}

		// Check if 2 queens are on the same column
		for (int x = 0; x < chessboardSize; x++) {

			boolean usedColumn = false;
			for (int i = x; i < chessboard.length; i += chessboardSize) {

				if (chessboard[i]) {
					if (usedColumn) {
						return false;
					}
					usedColumn = true;
				}
			}
		}

		// Check if 2 queens are on the same descending diagonal
		for (int diagonal = 0; diagonal < chessboardSize * 2 - 1; diagonal++) {

			boolean usedDiagonal = false;

			for (int y = 0; y < chessboardSize; y++) {

				final int x = diagonal - y;

				if (x >= 0 && x < chessboardSize) {

					if (chessboard[y * chessboardSize + x]) {
						if (usedDiagonal) {
							return false;
						}
						usedDiagonal = true;
					}
				}
			}
		}

		// Check if 2 queens are on the same ascending diagonal
		for (int diagonal = 0; diagonal < chessboardSize * 2 - 1; diagonal++) {

			boolean usedDiagonal = false;

			for (int y = 0; y < chessboardSize; y++) {

				final int x = diagonal - chessboardSize + 1 + y;

				if (x >= 0 && x < chessboardSize) {

					if (chessboard[y * chessboardSize + x]) {
						if (usedDiagonal) {
							return false;
						}
						usedDiagonal = true;
					}
				}
			}
		}

		return true;
	}

	/**
	 * Main greedy program.
	 * 
	 * @param args options
	 * @throws InvalidSolutionsException
	 */
	public static void main(final String args[]) throws InvalidSolutionsException {

		// Chessboard size (8 is quite long for this algorithm)
		final int chessboardSize = 8;

		// Instantiate adn run the greedy solver
		final BruteForceNQueensSolverOneDimension genericNQueensSolver = new BruteForceNQueensSolverOneDimension(chessboardSize, true);
		final long solutionCount = genericNQueensSolver.solve();

		// End of the algorithm print the total of solution(s) found
		System.out.println("\nTotal number of solution(s):" + solutionCount); //$NON-NLS-1$
		// Check if the number of solutions found is correct
		SequenceTools.checkSolutionsFound(chessboardSize, solutionCount);
	}

	@Override
	public boolean getChessboardPosition(final int x, final int y) {
		return chessboard[y * chessboardSize + x];
	}
}

@@ -1223,20 +1223,18 @@
 %0A%0A%09%09// P
-lace
+ut
  a queen
@@ -1497,17 +1497,19 @@
 %0A%09%09%7D
- 
+%0A%09%09
 else %7B%0A%0A
 %09%09%09i
@@ -1504,16 +1504,50 @@
 else %7B%0A%0A
+%09%09%09// End of the chessboard check%0A
 %09%09%09if (i
@@ -1600,16 +1600,63 @@
 %09%09%09%7D%0A%09%09%7D
+%0A%0A%09%09// Remove the queen on the current position
 %0A%09%09place
@@ -1692,16 +1692,49 @@
 false;%0A%0A
+%09%09// End of the chessboard check%0A
 %09%09if (i 

Add coments