Skip to content

Instantly share code, notes, and snippets.

@jthomas

jthomas/n-queens.js

Last active Jul 28, 2020
Embed
What would you like to do?
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

This comment has been minimized.

Copy link
Owner Author

@jthomas 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

This comment has been minimized.

Copy link
Owner Author

@jthomas jthomas commented Aug 18, 2015

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

@dheeraj-p

This comment has been minimized.

Copy link

@dheeraj-p dheeraj-p commented Oct 10, 2018

Could you please explain your algorithm?

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