N Queens

Place N queens on N×N board so no two attack each other.

7 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode

Problem

Place N queens on N×N chessboard so no two queens attack each other (same row, column, or diagonal). Return all distinct solutions.

Backtracking with Sets

Place queens row by row. For each row, try all columns. Track used columns, positive diagonals (row+col), negative diagonals (row-col).

Gon-queens.go

46 linesLn 1, Col 1Go

Track occupied columns and diagonals with sets for O(1) validity check. Place queen, recurse to next row, backtrack.

Bit Optimization

Use integers as bitsets for columns and diagonals. Much faster for larger N. col, diag1, diag2 are bitmasks. Available positions = ~(col | diag1 | diag2) & ((1<<n)-1).

Gon-queens-bit-optimized.go

25 linesLn 1, Col 1Go

Bitsets for O(1) operations. pos = rightmost available bit. Shift diag1 left (next row, diagonal moves right), diag2 right (next row, diagonal moves left). &^ clears bits.

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.