Skip to content

Instantly share code, notes, and snippets.

@soundsmitten
Created December 12, 2012 22:59
Show Gist options
  • Save soundsmitten/4272446 to your computer and use it in GitHub Desktop.
Save soundsmitten/4272446 to your computer and use it in GitHub Desktop.
Java- n-queens problem
// The eight queens puzzle is the problem of placing eight chess queens on an 8?8
// chessboard so that no two queens attack each other. Thus, a solution requires that no two
// queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general
// n-queens problem of placing n queens on an n?n chessboard,
// where solutions exist for all natural numbers n with the exception of 2 and 3.[
boolean promising (int i, int[] col) {
for (j=1; j<i; j++) {
if (col[i] == col[j]) {
return false;
}
else if (i+col[i] == j + col[j]) {
return false;
}
else if (col[i] - i == col[j] - j) {
return false;
}
}
return true;
}
void nqueens(int i, int n, int[] col)
{
if (promising(i, col)) {
if (i == n) {
printSolution(col);
}
}
for (k=1; k<=n; k++) {
col[i+1] = k
nqueens(i+1, n, col)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment