DEV Community

Cover image for How I Solved N-Queens Using Bitmasking (Step-by-Step Guide)
Abivarsan R
Abivarsan R

Posted on

How I Solved N-Queens Using Bitmasking (Step-by-Step Guide)

#python #algorithms #programming

🚀 Solving N-Queens Using Bitmasking (Step-by-Step Guide)

🧠 Problem Overview

The N-Queens problem:

Place n queens on an n × n chessboard such that no two queens attack each other.

⚡ Why Bitmasking?

Instead of using:

  • Sets ❌
  • Arrays ❌

We use:

  • Bits (0/1) ✅ → faster & efficient

🔥 Core Idea

We track:

  • cols → occupied columns
  • diag1 → main diagonals (↘)
  • diag2 → anti-diagonals (↙)

Each is stored as a binary number

🧩 Step-by-Step Explanation (VERY SIMPLE)

Let’s understand with n = 4

🔹 Step 1: Initial State 

Row = 0
cols  = 0000
diag1 = 0000
diag2 = 0000
Enter fullscreen mode Exit fullscreen mode

👉 All positions are free

🔹 Step 2: Find Available Positions 

available = ~(cols | diag1 | diag2) & ((1 << n) - 1)
Enter fullscreen mode Exit fullscreen mode

Result:

available = 1111
Enter fullscreen mode Exit fullscreen mode

👉 All 4 columns are available

🔹 Step 3: Pick One Position 

pos = available & -available
Enter fullscreen mode Exit fullscreen mode

👉 Picks rightmost 1

pos = 0001  → column 0
Enter fullscreen mode Exit fullscreen mode

🔹 Step 4: Place Queen

Board:

Q...
....
....
....
Enter fullscreen mode Exit fullscreen mode

Update masks:

cols  = 0001
diag1 = 0010   (shift left)
diag2 = 0000   (shift right)
Enter fullscreen mode Exit fullscreen mode

🔹 Step 5: Move to Next Row

Now row = 1

Find available:

available = ~(0001 | 0010 | 0000) = 1100
Enter fullscreen mode Exit fullscreen mode

👉 Only column 2 and 3 are free

🔹 Step 6: Repeat Process

Pick:

pos = 0100  → column 2
Enter fullscreen mode Exit fullscreen mode

Place queen:

Q...
..Q.
....
....
Enter fullscreen mode Exit fullscreen mode

Update masks and continue…

🔹 Step 7: Dead End? Backtrack!

If no positions available:
👉 Go back (remove previous queen)
👉 Try next possibility

🔹 Step 8: When Row == n 

All queens placed successfully 🎉
Enter fullscreen mode Exit fullscreen mode

👉 Save board as a solution

💻 Final Bitmask Code 

class Solution(object):
    def solveNQueens(self, n):
        result = []
        board = ["." * n for _ in range(n)]

        def backtrack(row, cols, diag1, diag2):
            if row == n:
                result.append(board[:])
                return

            available = ~(cols | diag1 | diag2) & ((1 << n) - 1)

            while available:
                pos = available & -available
                available = available & (available - 1)

                col = (pos.bit_length() - 1)

                board[row] = board[row][:col] + "Q" + board[row][col+1:]

                backtrack(
                    row + 1,
                    cols | pos,
                    (diag1 | pos) << 1,
                    (diag2 | pos) >> 1
                )

                board[row] = board[row][:col] + "." + board[row][col+1:]

        backtrack(0, 0, 0, 0)
        return result
Enter fullscreen mode Exit fullscreen mode

⚡ Key Tricks Explained

✔ Get all safe positions 

available = ~(cols | diag1 | diag2) & ((1 << n) - 1)
Enter fullscreen mode Exit fullscreen mode

✔ Pick one position 

pos = available & -available
Enter fullscreen mode Exit fullscreen mode

✔ Remove used position 

available = available & (available - 1)
Enter fullscreen mode Exit fullscreen mode

⏱️ Complexity 

Time: O(N!)
Space: O(N)
Enter fullscreen mode Exit fullscreen mode

👉 But very fast in practice 🚀

🧠 Easy Memory Trick

👉 “Use bits to mark attacks, and pick positions using binary tricks”

💡 Interview Tip

Say this confidently:

“I optimized N-Queens using bitmasking to reduce constraint checking to constant time.”

🔥 That’s a standout answer

🚀 Final Thought

Bitmasking turns a normal backtracking solution into a high-performance algorithm.

Once you understand this, you unlock a new level of problem-solving 💡

🔖 Tags

Algorithms #Backtracking #Bitmasking #LeetCode #CodingInterview #DSA

Top comments (0)