

Solve the eight queens puzzle.



You can extend the problem to solve the puzzle with a board of size   NxN.

For the number of solutions for small values of   N,   see   OEIS: A000170.



Related tasks

 A* search algorithm
 Solve a Hidato puzzle
 Solve a Holy Knight's tour
 Knight's tour
 Peaceful chess queen armies
 Solve a Hopido puzzle
 Solve a Numbrix puzzle
 Solve the no connection puzzle


let print_table = function (pos) {
	pos.foreach(function (_, i) {
		stdout.printf("  %c", 'a' + i);
	});
 
	stdout.write("\n");
 
	pos.foreach(function (col, row) {
		stdout.printf("%d", row + 1);
		stdout.printf("%s #\n", range(col).reduce("", function (s, t) {
			return s .. "   ";
		}));
	});
 
	stdout.write("\n\n");
};
 
let threatens = function (row_a, col_a, row_b, col_b) {
	return row_a == row_b
	    or col_a == col_b
	    or abs(row_a - row_b) == abs(col_a - col_b);
};
 
let good = function(pos, end_idx) {
	return pos.all(function (col_a, row_a) {
		return range(row_a + 1, end_idx).all(function (row_b) {
			let col_b = pos[row_b];
			return not threatens(row_a, col_a, row_b, col_b);
		});
	});
};
 
// Returns number of solutions
let n_queens = function (pos, index) {
	if index >= pos.length {
		if good(pos, index) {
			print_table(pos);
			return 1;
		}
 
		return 0;
	}
 
	if not good(pos, index) {
		return 0;
	}
 
	return pos.map(function (_, col) {
		pos[index] = col;
		return n_queens(pos, index + 1);
	}).reduce(0, function (a, b) { return a + b; });
};
 
stdout.printf("%d solutions\n", n_queens(range(8), 0));