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

🚀 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

👉 All positions are free

🔹 Step 2: Find Available Positions

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

Result:

available = 1111

👉 All 4 columns are available

🔹 Step 3: Pick One Position

pos = available & -available

👉 Picks rightmost 1

pos = 0001  → column 0

🔹 Step 4: Place Queen

Board:

Q...
....
....
....

Update masks:

cols  = 0001
diag1 = 0010   (shift left)
diag2 = 0000   (shift right)

🔹 Step 5: Move to Next Row

Now row = 1

Find available:

available = ~(0001 | 0010 | 0000) = 1100

👉 Only column 2 and 3 are free

🔹 Step 6: Repeat Process

Pick:

pos = 0100  → column 2

Place queen:

Q...
..Q.
....
....

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 🎉

👉 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

⚡ Key Tricks Explained

✔ Get all safe positions

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

✔ Pick one position

pos = available & -available

✔ Remove used position

available = available & (available - 1)

⏱️ Complexity

Time: O(N!)
Space: O(N)

👉 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 💡

推荐订阅源

DEV Community