Skip to content

Instantly share code, notes, and snippets.

@jthomas
Last active August 10, 2022 12:49
Show Gist options
  • Save jthomas/2b33224927c70b4aa612 to your computer and use it in GitHub Desktop.
Save jthomas/2b33224927c70b4aa612 to your computer and use it in GitHub Desktop.
Solving "N Queens Problem" with JavaScript
var iterations = 0
var print_board = function (columns) {
var n = columns.length, row = 0, col = 0
while (row < n) {
while (col < n) {
process.stdout.write(columns[row] === col ? 'Q ' : '# ')
col++
}
process.stdout.write('\n')
col = 0
row++
}
}
var has_conflict = function (columns) {
var len = columns.length, last = columns[len - 1], previous = len - 2
while (previous >= 0) {
if (columns[previous] === last) return true
if (last - (len - 1) === columns[previous] - previous) return true
if (last + (len - 1) === columns[previous] + previous) return true
previous--
}
return false
}
var place_next_queen = function (total, queens, columns) {
if (queens === 0) return columns
columns = columns || []
for (var column = 0; column < total; column++) {
columns.push(column)
iterations++
if (!has_conflict(columns) &&
place_next_queen(total, queens - 1, columns)) {
return columns
}
columns.pop(column)
}
return null
}
print_board(place_next_queen(28, 28))
console.log('\niterations: ', iterations)
@jthomas
Copy link
Author

jthomas commented Aug 18, 2015

18:50:00 ~/code/n-queens]$ node n-queens.js
Q # # # # # # # # # # # # # # # # # # # # # # # # # # #

# Q # # # # # # # # # # # # # # # # # # # # # # # #

# # # Q # # # # # # # # # # # # # # # # # # # # # #

Q # # # # # # # # # # # # # # # # # # # # # # # # #

# # Q # # # # # # # # # # # # # # # # # # # # # # #

# # # # # # # Q # # # # # # # # # # # # # # # # # #

# # # # # # # # # Q # # # # # # # # # # # # # # # #

# # # # # # # # # # # Q # # # # # # # # # # # # # #

# # # # # # # # # # # # # Q # # # # # # # # # # # #

# # # # # # # # # # # # # # # Q # # # # # # # # # #

# # # # # # # # # # # # # # # # # # # # # Q # # # #

# # # # # # # # # # # # # # # # # # # # # # # Q # #

# # # # # # # # # # # # # # # # # # # # Q # # # # #

# # # # # # # # # # # # # # # # # # # # # # # # # # Q

# # # # # # # # # # # # # # # # # # # # # # # # Q #

# # # # # # # # # # # # # # # # # # # # # # Q # # #

# # # # # # # # # # # # # # # # # # # # # # # # # Q

# # # # # Q # # # # # # # # # # # # # # # # # # # #

# # # # # # # # # # Q # # # # # # # # # # # # # # #

# # # # # # # # # # # # # # Q # # # # # # # # # # #

# # # # # # # # # # # # # # # # Q # # # # # # # # #

# # # # # # Q # # # # # # # # # # # # # # # # # # #

# # # # # # # # Q # # # # # # # # # # # # # # # # #

# # # # # # # # # # # # Q # # # # # # # # # # # # #

# # # # # # # # # # # # # # # # # # Q # # # # # # #

# # # # Q # # # # # # # # # # # # # # # # # # # # #

# # # # # # # # # # # # # # # # # # # Q # # # # # #

# # # # # # # # # # # # # # # # # Q # # # # # # # #

iterations: 84175966
[18:56:37 ~/code/n-queens]$

@jthomas
Copy link
Author

jthomas commented Aug 18, 2015

Generalised version of the Eight Queens problem.
Uses recursive backtracking algorithm to find valid solutions.

@dheeraj-p
Copy link

Could you please explain your algorithm?

@baruch1995
Copy link

The printBoard function can be written more simple:

var print_board = function (columns) {
  for (let i = 0; i < columns.length; i++) {
    for (let j = 0; j < columns.length; j++) {
      process.stdout.write(columns[i] === j ? "Q " : "# ");
    }
    process.stdout.write("\n");
  }
};

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment