HardBacktracking

N-Queens

Q: Can a local fun call itself recursively?

Yes. A local fun place(row: Int) is in scope inside its own body, so it can recurse, and it captures cols, placements and n from the enclosing function by reference. A lambda stored in a val cannot refer to itself while it is being initialised, which is why the recursive helper is a local fun rather than a lambda.

Q: Why removeAt(cols.lastIndex) and not removeLast()?

Both drop the last queen. When the code is compiled against JDK 21 or later, removeLast() on a MutableList resolves to the new Java List.removeLast member instead of the Kotlin extension, and that member is missing on older Android runtimes. removeAt(cols.lastIndex) means the same thing on every platform.

Q: Why copyOf() before adding a board to the result?

An IntArray is a mutable reference type. Adding cols itself would put the same array in the list 92 times, and every entry would end up holding whatever the search wrote last. cols.copyOf() (or toIntArray() on a list) stores a snapshot.

Q: How do I count the solutions without collecting them?

Make place return an Int: 1 when r == n, otherwise the sum of its recursive calls, and drop placements. For n = 1 to 10 the BooleanArray version gives 1, 0, 0, 2, 10, 4, 40, 92, 352, 724; the 92 for the 8 × 8 board shrink to 12 when rotations and mirror images count as one.

Q: What does a bitmask version look like in Kotlin?

Keep the columns and both diagonal directions as three Int masks and compute var free = all and (cols or down or up).inv() with all = (1 shl n) - 1. free and -free isolates the lowest open column, Integer.numberOfTrailingZeros (or countTrailingZeroBits()) turns it into an index, and the next row gets (down or bit) shl 1 and (up or bit) ushr 1. Kotlin spells the bit operators as infix functions, but they compile to the same JVM instructions as Java.

You get a positive integer n. Place n queens on an n × n chessboard so that no two attack each other: no two may share a row, a column or a diagonal. Return every valid placement.

Every row holds exactly one queen, so a placement is described by its columns: an array of n integers whose entry r is the column of the queen in row r, rows counted from the top and columns from the left, both starting at 0. Return the placements in any order; inside a placement the entries are in row order. When n has no valid placement (that is n = 2 and n = 3), return an empty array. The classic 8 × 8 board has 92 placements.

Examples

Input

n = 4

Output[[1, 3, 0, 2], [2, 0, 3, 1]]WhyTwo placements, each the mirror image of the other. The first puts its queens in columns 1, 3, 0, 2 from the top row down.

Input

n = 1

Output[[0]]WhyOne square holds one queen, in column 0 of the only row.

Constraints

Size: 1 ≤ n ≤ 8
Answer: Every placement, in any order, each as the column of its queen per row.
Time limit: 10 s per run, all cases

Run your code 2 more times to open the solutions. The idea sticks better after an attempt.

3 reference approaches in Python, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every permutation

O(n!·n²) time · O(n) space

A valid placement has exactly one queen in each row and each column, so it is a permutation of the column numbers: cols[r] is the column of the queen in row r. itertools.permutations produces every such ordering, which settles rows and columns. Only the diagonals are left to check: two queens share one when the gap between their columns equals the gap between their rows. For n = 8 that is 40,320 permutations, each with up to 28 pairs to compare, to keep 92.

from itertools import permutations


def solve_n_queens(n: int) -> list[list[int]]:
    placements: list[list[int]] = []
    for cols in permutations(range(n)):  # cols[r] = column of the queen in row r
        if all(abs(cols[r1] - cols[r2]) != r2 - r1
               for r1 in range(n) for r2 in range(r1 + 1, n)):
            placements.append(list(cols))
    return placements

2 · Backtracking with a safety scan

O(n!·n) time · O(n) space

Instead of building whole boards, place queens one row at a time. Before a queen goes into a column, is_safe scans the queens already on the board for a shared column or diagonal. If no column in the current row is safe, the call returns and the row above moves its queen to the next column. A bad start is dropped the moment it appears, together with every placement that would have begun with it: for n = 8 this search places a queen only 2,056 times in total. Append a copy of cols when a board is complete, since the list itself keeps changing.

def solve_n_queens(n: int) -> list[list[int]]:
    placements: list[list[int]] = []
    cols: list[int] = []  # cols[r] = column of the queen in row r

    def is_safe(col: int) -> bool:
        row = len(cols)
        for r, c in enumerate(cols):
            if c == col or abs(c - col) == row - r:
                return False
        return True

    def place(row: int) -> None:
        if row == n:
            placements.append(cols.copy())
            return
        for col in range(n):
            if is_safe(col):
                cols.append(col)
                place(row + 1)
                cols.pop()

    place(0)
    return placements

3 · Backtracking with column and diagonal sets

O(n!) time · O(n) space

recommended

Every square on a diagonal running down to the right has the same r - c, and every square on a diagonal running down to the left has the same r + c. Keep three sets: the columns in use, the r - c values in use and the r + c values in use. Checking a square becomes three set lookups instead of a scan. Add the three values when you place a queen and remove them when you take it back; the undo lines must mirror the add lines exactly, or later rows see diagonals that are no longer taken.

def solve_n_queens(n: int) -> list[list[int]]:
    placements: list[list[int]] = []
    cols: list[int] = []  # cols[r] = column of the queen in row r
    used_cols: set[int] = set()
    down: set[int] = set()  # r - c is shared along each down-right diagonal
    up: set[int] = set()  # r + c is shared along each down-left diagonal

    def place(r: int) -> None:
        if r == n:
            placements.append(cols.copy())
            return
        for c in range(n):
            if c in used_cols or r - c in down or r + c in up:
                continue
            cols.append(c)
            used_cols.add(c); down.add(r - c); up.add(r + c)
            place(r + 1)
            cols.pop()
            used_cols.remove(c); down.remove(r - c); up.remove(r + c)

    place(0)
    return placements

3 reference approaches in JavaScript, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every permutation

O(n!·n²) time · O(n) space

Write the placement as an array cols where cols[r] is the column of the queen in row r. If the values are a permutation of 0 … n - 1, rows and columns are already clash-free. JavaScript has no built-in permutation helper, so a generator function (function*) yields them one at a time: it picks each item in turn, removes it with toSpliced and recurses on what is left. diagonalsClear then compares every pair of rows, since two queens sit on one diagonal exactly when their column distance equals their row distance. For n = 8 that hands over all 40,320 orders and runs up to 28 pair checks on each, only to keep 92.

function* permutations(items) {
  if (items.length <= 1) {
    yield items;
    return;
  }
  for (let i = 0; i < items.length; i++) {
    const rest = items.toSpliced(i, 1);
    for (const tail of permutations(rest)) yield [items[i], ...tail];
  }
}

function diagonalsClear(cols) {
  for (let r1 = 0; r1 < cols.length; r1++) {
    for (let r2 = r1 + 1; r2 < cols.length; r2++) {
      if (Math.abs(cols[r1] - cols[r2]) === r2 - r1) return false;
    }
  }
  return true;
}

function solveNQueens(n) {
  const placements = [];
  const columns = Array.from({ length: n }, (_, i) => i);
  // each permutation already has one queen per row and per column
  for (const cols of permutations(columns)) {
    if (diagonalsClear(cols)) placements.push([...cols]);
  }
  return placements;
}

2 · Backtracking with a safety scan

O(n!·n) time · O(n) space

Grow the board instead of generating it whole. The inner arrow function place(r) tries the columns of row r from left to right and asks isSafe first, which runs cols.every over the queens already placed and fails on a shared column or diagonal. A safe column is pushed onto cols, the next row is explored, and cols.pop() takes the queen back afterwards. When a row has no safe column, the loop simply ends and control returns to the row above, which shifts its own queen. Solving n = 8 places a queen just 2,056 times. Push a copy ([...cols]) when a board is finished, because cols keeps changing.

function solveNQueens(n) {
  const placements = [];
  const cols = []; // cols[r] is the column of the queen in row r
  const isSafe = (col) => {
    const r = cols.length;
    return cols.every((c, prev) => c !== col && Math.abs(c - col) !== r - prev);
  };
  const place = (r) => {
    if (r === n) {
      placements.push([...cols]);
      return;
    }
    for (let col = 0; col < n; col++) {
      if (!isSafe(col)) continue;
      cols.push(col);
      place(r + 1);
      cols.pop();
    }
  };
  place(0);
  return placements;
}

3 · Backtracking with column and diagonal sets

O(n!) time · O(n) space

recommended

Along a diagonal that falls to the right, row minus column never changes; along one that falls to the left, row plus column never changes. That turns every diagonal into a single number. Three Set objects hold the columns, the r - c values and the r + c values that are taken, so the safety test is three has() calls. Placing a queen adds three values and backing out deletes the same three. A Set is happy with the negative numbers that r - c produces, which a plain array index is not. Keep the delete calls a mirror of the add calls: miss one and a diagonal stays blocked for every board explored after it.

function solveNQueens(n) {
  const placements = [];
  const cols = []; // cols[r] is the column of the queen in row r
  const usedCols = new Set();
  const down = new Set(); // r - c is constant along a down-right diagonal
  const up = new Set(); // r + c is constant along a down-left diagonal
  const place = (r) => {
    if (r === n) {
      placements.push([...cols]);
      return;
    }
    for (let c = 0; c < n; c++) {
      if (usedCols.has(c) || down.has(r - c) || up.has(r + c)) continue;
      cols.push(c);
      usedCols.add(c);
      down.add(r - c);
      up.add(r + c);
      place(r + 1);
      cols.pop();
      usedCols.delete(c);
      down.delete(r - c);
      up.delete(r + c);
    }
  };
  place(0);
  return placements;
}

3 reference approaches in TypeScript, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every permutation

O(n!·n²) time · O(n) space

Describe a board as cols: number[], the column of each row's queen. A permutation of 0 … n - 1 already keeps rows and columns apart, so only the diagonals are left to test. A generator typed Generator<number[]> yields the permutations one at a time without building all 40,320 for n = 8 up front, and diagonalsClear compares every pair of rows: two queens share a diagonal exactly when their column distance equals their row distance.

function* permutations(items: number[]): Generator<number[]> {
  if (items.length <= 1) {
    yield items;
    return;
  }
  for (let i = 0; i < items.length; i++) {
    const rest = [...items.slice(0, i), ...items.slice(i + 1)];
    for (const tail of permutations(rest)) yield [items[i], ...tail];
  }
}

function diagonalsClear(cols: number[]): boolean {
  for (let r1 = 0; r1 < cols.length; r1++) {
    for (let r2 = r1 + 1; r2 < cols.length; r2++) {
      if (Math.abs(cols[r1] - cols[r2]) === r2 - r1) return false;
    }
  }
  return true;
}

function solveNQueens(n: number): number[][] {
  const placements: number[][] = [];
  const columns = Array.from({ length: n }, (_, i) => i);
  // every permutation already has one queen per row and per column
  for (const cols of permutations(columns)) {
    if (diagonalsClear(cols)) placements.push(cols);
  }
  return placements;
}

2 · Backtracking with a safety scan

O(n!·n) time · O(n) space

Place queens row by row and reject a column as soon as a queen above attacks it. The inner arrow function place(r) tries each column, asks isSafe (a cols.every over the queens already down), pushes a safe column, recurses and pops it again. A row with no safe column just ends its loop, which sends the search back to the row above. For n = 8 that is about two thousand placements instead of forty thousand full boards. Store [...cols], not cols, when a board is complete.

function solveNQueens(n: number): number[][] {
  const placements: number[][] = [];
  const cols: number[] = []; // cols[r] is the column of the queen in row r
  const isSafe = (col: number): boolean => {
    const r = cols.length;
    return cols.every((c, prev) => c !== col && Math.abs(c - col) !== r - prev);
  };
  const place = (r: number): void => {
    if (r === n) {
      placements.push([...cols]);
      return;
    }
    for (let col = 0; col < n; col++) {
      if (!isSafe(col)) continue;
      cols.push(col);
      place(r + 1);
      cols.pop();
    }
  };
  place(0);
  return placements;
}

3 · Backtracking with column and diagonal sets

O(n!) time · O(n) space

recommended

Along a down-right diagonal r - c is constant, along a down-left one r + c is. Three Set<number> objects record the columns and both kinds of diagonal in use, so the safety check becomes three has() calls. Placing a queen adds three values and backing out deletes the same three. A Set stores the negative r - c values as they are; an array would need an offset of n - 1.

function solveNQueens(n: number): number[][] {
  const placements: number[][] = [];
  const cols: number[] = []; // cols[r] is the column of the queen in row r
  const usedCols = new Set<number>();
  const down = new Set<number>(); // r - c is constant along a down-right diagonal
  const up = new Set<number>(); // r + c is constant along a down-left diagonal
  const place = (r: number): void => {
    if (r === n) {
      placements.push([...cols]);
      return;
    }
    for (let c = 0; c < n; c++) {
      if (usedCols.has(c) || down.has(r - c) || up.has(r + c)) continue;
      cols.push(c);
      usedCols.add(c);
      down.add(r - c);
      up.add(r + c);
      place(r + 1);
      cols.pop();
      usedCols.delete(c);
      down.delete(r - c);
      up.delete(r + c);
    }
  };
  place(0);
  return placements;
}

3 reference approaches in Java, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every permutation

O(n!·n²) time · O(n) space

Since a queen per row and a queen per column are both required, every candidate is a rearrangement of 0 to n - 1, held in an int[] where index r stores the queen's column in that row. The JDK offers no permutation generator, so the code includes nextPermutation, the classic swap-and-reverse step that advances the array to its lexicographic successor and reports false when none exists. Filling the array with 0, 1, …, n - 1 already gives the smallest ordering, which is why the loop is a do/while: the body tests that first arrangement before the condition advances it. Each arrangement then needs one diagonal test per pair of rows, Math.abs(cols[r1] - cols[r2]) == r2 - r1, and a keeper is stored as cols.clone() because the array is rewritten in place.

import java.util.*;

public class Main {
    // Turns p into the next ordering in lexicographic order
    // and returns false once p was already the last one.
    static boolean nextPermutation(int[] p) {
        int i = p.length - 2;
        while (i >= 0 && p[i] >= p[i + 1]) {
            i--;
        }
        if (i < 0) {
            return false;
        }
        int j = p.length - 1;
        while (p[j] <= p[i]) {
            j--;
        }
        swap(p, i, j);
        for (int lo = i + 1, hi = p.length - 1; lo < hi; lo++, hi--) {
            swap(p, lo, hi);
        }
        return true;
    }

    static void swap(int[] p, int i, int j) {
        int tmp = p[i];
        p[i] = p[j];
        p[j] = tmp;
    }

    static int[][] solveNQueens(int n) {
        List<int[]> placements = new ArrayList<>();
        int[] cols = new int[n]; // cols[r] = column of the queen in row r
        for (int i = 0; i < n; i++) {
            cols[i] = i;
        }
        do {
            boolean ok = true;
            for (int r1 = 0; r1 < n && ok; r1++) {
                for (int r2 = r1 + 1; r2 < n; r2++) {
                    if (Math.abs(cols[r1] - cols[r2]) == r2 - r1) {
                        ok = false;
                        break;
                    }
                }
            }
            if (ok) {
                placements.add(cols.clone());
            }
        } while (nextPermutation(cols));
        return placements.toArray(new int[0][]);
    }
}

2 · Backtracking with a safety scan

O(n!·n) time · O(n) space

This version never assembles a bad board in full. Queens placed so far live in a List<Integer>; for each column of the next row, isSafe walks that list looking for a queen in the same column or on a diagonal, and the method recurses only when it finds none. A row with no usable column just lets its for loop finish, and the caller one level up carries on with its next column, so a single refusal cuts off every placement beginning that way. Java has no local functions, so place is a static method receiving n, the row, the partial list and the result list as arguments. Taking a queen back is cols.removeLast(), a sequenced-collection method added in Java 21, and a finished board is unboxed into a fresh int[] so later changes to cols cannot reach it.

import java.util.*;

public class Main {
    static boolean isSafe(List<Integer> cols, int col) {
        int row = cols.size();
        for (int r = 0; r < row; r++) {
            int c = cols.get(r);
            if (c == col || Math.abs(c - col) == row - r) {
                return false;
            }
        }
        return true;
    }

    static void place(int n, int row, List<Integer> cols, List<int[]> placements) {
        if (row == n) {
            placements.add(cols.stream().mapToInt(Integer::intValue).toArray());
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isSafe(cols, col)) {
                cols.add(col);
                place(n, row + 1, cols, placements);
                cols.removeLast();
            }
        }
    }

    static int[][] solveNQueens(int n) {
        List<int[]> placements = new ArrayList<>();
        place(n, 0, new ArrayList<>(), placements); // cols.get(r) = column of the queen in row r
        return placements.toArray(new int[0][]);
    }
}

3 · Backtracking with column and diagonal sets

O(n!) time · O(n) space

recommended

All squares on one down-right diagonal share the value r - c, and all squares on one down-left diagonal share r + c. Each quantity spans 2 * n - 1 values, few enough to index a boolean[] directly, provided r - c is moved up by n - 1 so it never lands below zero. Together with a boolean[] of length n for columns, that turns the scan into three reads. Java initialises a fresh boolean[] to false, so no setup loop is needed. The arrays travel as parameters of place, and since a method receives a reference to an array rather than a copy, every level of the recursion reads and updates the same flags. The three false assignments after the call must undo exactly the three true assignments before it, or a later row avoids an attack that is gone.

import java.util.*;

public class Main {
    static int[][] solveNQueens(int n) {
        List<int[]> placements = new ArrayList<>();
        int[] cols = new int[n]; // cols[r] = column of the queen in row r
        boolean[] usedCols = new boolean[n];
        boolean[] down = new boolean[2 * n - 1]; // r - c + n - 1 is shared along each down-right diagonal
        boolean[] up = new boolean[2 * n - 1]; // r + c is shared along each down-left diagonal
        place(0, cols, usedCols, down, up, placements);
        return placements.toArray(new int[0][]);
    }

    static void place(int r, int[] cols, boolean[] usedCols, boolean[] down, boolean[] up,
                      List<int[]> placements) {
        int n = cols.length;
        if (r == n) {
            placements.add(cols.clone());
            return;
        }
        for (int c = 0; c < n; c++) {
            int d = r - c + n - 1;
            int u = r + c;
            if (usedCols[c] || down[d] || up[u]) {
                continue;
            }
            cols[r] = c;
            usedCols[c] = true;
            down[d] = true;
            up[u] = true;
            place(r + 1, cols, usedCols, down, up, placements);
            usedCols[c] = false;
            down[d] = false;
            up[u] = false;
        }
    }
}

3 reference approaches in Go, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every permutation

O(n!·n²) time · O(n) space

With one queen per row and one per column, a candidate placement is just an ordering of the numbers 0 to n - 1 in a []int. The standard library ships slices.Reverse but nothing that enumerates orderings, so the code carries its own nextPermutation: it rewrites the slice in place into its lexicographic successor and returns false once there is none. Rows and columns are then safe by construction. What remains is a diagonal clash, which the nested loop finds by comparing the column difference d of every pair with their row distance in both signs, because Go has no integer abs to fold the two cases into one. A surviving ordering is appended as slices.Clone(cols), since the next step rewrites cols in place.

package main

import "slices"

// nextPermutation turns p into the next ordering in lexicographic order
// and reports false once p was already the last one.
func nextPermutation(p []int) bool {
	i := len(p) - 2
	for i >= 0 && p[i] >= p[i+1] {
		i--
	}
	if i < 0 {
		return false
	}
	j := len(p) - 1
	for p[j] <= p[i] {
		j--
	}
	p[i], p[j] = p[j], p[i]
	slices.Reverse(p[i+1:])
	return true
}

func solveNQueens(n int) [][]int {
	placements := [][]int{}
	cols := make([]int, n) // cols[r] = column of the queen in row r
	for i := range n {
		cols[i] = i
	}
	for {
		ok := true
		for r1 := 0; r1 < n && ok; r1++ {
			for r2 := r1 + 1; r2 < n; r2++ {
				if d := cols[r1] - cols[r2]; d == r2-r1 || d == r1-r2 {
					ok = false
					break
				}
			}
		}
		if ok {
			placements = append(placements, slices.Clone(cols))
		}
		if !nextPermutation(cols) {
			return placements
		}
	}
}

2 · Backtracking with a safety scan

O(n!·n) time · O(n) space

Backtracking grows the board downward instead. cols starts as an empty slice, and a column is appended only after isSafe confirms that no queen above shares it or sits on one of its diagonals. When a row has no safe column, the loop simply ends, control returns to the row above, and that row tries its next column; one rejected square discards every placement that would have started with it. Go cannot refer to a closure from inside its own := declaration, so the code writes var place func(row int) first and assigns the body on the following line. Re-slicing with cols[:len(cols)-1] keeps the same backing array, so a finished board is stored as slices.Clone(cols), or the next append would overwrite it.

package main

import "slices"

func solveNQueens(n int) [][]int {
	placements := [][]int{}
	cols := []int{} // cols[r] = column of the queen in row r
	isSafe := func(col int) bool {
		row := len(cols)
		for r, c := range cols {
			if d := c - col; d == 0 || d == row-r || d == r-row {
				return false
			}
		}
		return true
	}
	var place func(row int)
	place = func(row int) {
		if row == n {
			placements = append(placements, slices.Clone(cols))
			return
		}
		for col := range n {
			if isSafe(col) {
				cols = append(cols, col)
				place(row + 1)
				cols = cols[:len(cols)-1]
			}
		}
	}
	place(0)
	return placements
}

3 · Backtracking with column and diagonal sets

O(n!) time · O(n) space

recommended

The scan can go, because diagonals can be numbered. Along a line heading down and to the right, r - c stays constant; along one heading down and to the left, r + c does. Each takes 2*n - 1 distinct values, so a []bool of that length stands in for a set, with r - c shifted by n - 1 to keep the index from going negative. A third slice of length n flags used columns. make zeroes all three, so every flag starts out false, and a single multiple assignment raises the three flags before the recursive call while its mirror lowers them afterwards. Indexing a slice involves no hashing, unlike a map[int]bool.

package main

import "slices"

func solveNQueens(n int) [][]int {
	placements := [][]int{}
	cols := make([]int, n) // cols[r] = column of the queen in row r
	usedCols := make([]bool, n)
	down := make([]bool, 2*n-1) // r - c + n - 1 is shared along each down-right diagonal
	up := make([]bool, 2*n-1)   // r + c is shared along each down-left diagonal
	var place func(r int)
	place = func(r int) {
		if r == n {
			placements = append(placements, slices.Clone(cols))
			return
		}
		for c := range n {
			d, u := r-c+n-1, r+c
			if usedCols[c] || down[d] || up[u] {
				continue
			}
			cols[r] = c
			usedCols[c], down[d], up[u] = true, true, true
			place(r + 1)
			usedCols[c], down[d], up[u] = false, false, false
		}
	}
	place(0)
	return placements
}

3 reference approaches in C#, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every permutation

O(n!·n²) time · O(n) space

A board with one queen per row and one per column is a rearrangement of the numbers 0 to n - 1, kept in an int[] where slot r is the column of the queen in row r. .NET has no permutation enumerator, so the code carries its own NextPermutation: find the last position that can still grow, swap it with the smallest larger value to its right, reverse the tail, and report false once the array is the final ordering. Enumerable.Range(0, n).ToArray() is the smallest ordering, which is why the body runs in a do/while: it tests that first arrangement before the condition advances to the next. Each arrangement then only needs the diagonal test for every pair of rows, Math.Abs(cols[r1] - cols[r2]) == r2 - r1, and a keeper is stored as cols.ToArray() because the array keeps being rewritten in place.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static int[][] SolveNQueens(int n)
    {
        var placements = new List<int[]>();
        int[] cols = Enumerable.Range(0, n).ToArray(); // cols[r] = column of the queen in row r
        do
        {
            bool ok = true;
            for (int r1 = 0; r1 < n && ok; r1++)
            {
                for (int r2 = r1 + 1; r2 < n; r2++)
                {
                    if (Math.Abs(cols[r1] - cols[r2]) == r2 - r1)
                    {
                        ok = false;
                        break;
                    }
                }
            }
            if (ok) placements.Add(cols.ToArray());
        } while (NextPermutation(cols));
        return placements.ToArray();
    }

    // Rewrites p as the next ordering in lexicographic order and
    // returns false when p was already the last one.
    static bool NextPermutation(int[] p)
    {
        int i = p.Length - 2;
        while (i >= 0 && p[i] >= p[i + 1]) i--;
        if (i < 0) return false;
        int j = p.Length - 1;
        while (p[j] <= p[i]) j--;
        (p[i], p[j]) = (p[j], p[i]);
        Array.Reverse(p, i + 1, p.Length - i - 1);
        return true;
    }
}

2 · Backtracking with a safety scan

O(n!·n) time · O(n) space

Rather than finishing a board and then judging it, this version places queens one row at a time and refuses a column as soon as a queen above attacks it. The queens placed so far live in a List<int>; IsSafe walks that list for a queen in the same column or on a diagonal, and Place recurses only when it finds none. A row with no safe column lets its for loop run out, the caller moves its own queen one column over, and every placement that would have begun with the bad start is skipped. The helpers are static members of Solution that receive n, the row, the partial list and the result list. Taking a queen back is cols.RemoveAt(cols.Count - 1), and a finished board is stored as cols.ToArray() so later edits to the list cannot reach it.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static int[][] SolveNQueens(int n)
    {
        var placements = new List<int[]>();
        Place(n, 0, new List<int>(), placements); // cols[r] = column of the queen in row r
        return placements.ToArray();
    }

    static bool IsSafe(List<int> cols, int col)
    {
        int row = cols.Count;
        for (int r = 0; r < row; r++)
        {
            int c = cols[r];
            if (c == col || Math.Abs(c - col) == row - r) return false;
        }
        return true;
    }

    static void Place(int n, int row, List<int> cols, List<int[]> placements)
    {
        if (row == n)
        {
            placements.Add(cols.ToArray());
            return;
        }
        for (int col = 0; col < n; col++)
        {
            if (!IsSafe(cols, col)) continue;
            cols.Add(col);
            Place(n, row + 1, cols, placements);
            cols.RemoveAt(cols.Count - 1);
        }
    }
}

3 · Backtracking with column and diagonal sets

O(n!) time · O(n) space

recommended

Every square on a down-right diagonal has the same r - c, and every square on a down-left diagonal has the same r + c. Each takes 2 * n - 1 distinct values, few enough to index a bool[] directly once r - c is shifted up by n - 1 so it never goes negative. With a third bool[] for the columns in use, the safety scan shrinks to three array reads. C# zero-initialises a new bool[] to false, so there is no setup loop, and because arrays are reference types every level of the recursion sees the same flags through the parameters of Place. The three false assignments after the recursive call must undo exactly the three true assignments before it, or a later row walks into an attack that no longer exists.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static int[][] SolveNQueens(int n)
    {
        var placements = new List<int[]>();
        int[] cols = new int[n]; // cols[r] = column of the queen in row r
        bool[] usedCols = new bool[n];
        bool[] down = new bool[2 * n - 1]; // r - c + n - 1 is shared along each down-right diagonal
        bool[] up = new bool[2 * n - 1]; // r + c is shared along each down-left diagonal
        Place(0, cols, usedCols, down, up, placements);
        return placements.ToArray();
    }

    static void Place(int r, int[] cols, bool[] usedCols, bool[] down, bool[] up, List<int[]> placements)
    {
        int n = cols.Length;
        if (r == n)
        {
            placements.Add(cols.ToArray());
            return;
        }
        for (int c = 0; c < n; c++)
        {
            int d = r - c + n - 1;
            int u = r + c;
            if (usedCols[c] || down[d] || up[u]) continue;
            cols[r] = c;
            usedCols[c] = true;
            down[d] = true;
            up[u] = true;
            Place(r + 1, cols, usedCols, down, up, placements);
            usedCols[c] = false;
            down[d] = false;
            up[u] = false;
        }
    }
}

3 reference approaches in C++, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every permutation

O(n!·n²) time · O(n) space

A board is a vector<int> whose entry r is the column of row r's queen, so every permutation of 0 … n - 1 already keeps rows and columns apart. std::iota fills the smallest order, and std::next_permutation steps through the rest in lexicographic order, returning false after the last one; the do/while loop tests the first order before advancing. Each order then needs a diagonal check per pair of rows: equal column and row distances mean an attack.

#include <algorithm>
#include <cstdlib>
#include <numeric>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> solveNQueens(int n) {
        vector<vector<int>> placements;
        vector<int> cols(n); // cols[r] = column of the queen in row r
        iota(cols.begin(), cols.end(), 0);
        do {
            if (diagonalsClear(cols)) placements.push_back(cols);
        } while (next_permutation(cols.begin(), cols.end()));
        return placements;
    }

private:
    bool diagonalsClear(const vector<int>& cols) {
        int n = (int)cols.size();
        for (int r1 = 0; r1 < n; r1++) {
            for (int r2 = r1 + 1; r2 < n; r2++) {
                if (abs(cols[r1] - cols[r2]) == r2 - r1) return false;
            }
        }
        return true;
    }
};

2 · Backtracking with a safety scan

O(n!·n) time · O(n) space

Build the board one row at a time and test a column before placing it. isSafe scans the queens already in cols for a shared column or diagonal; a safe column is push_back'ed, the next row is explored and pop_back takes the queen back. A row with no safe column ends its loop and the row above moves on. The helpers take cols and the result by reference, so the recursion shares one vector instead of copying it on every call.

#include <algorithm>
#include <cstdlib>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> solveNQueens(int n) {
        vector<vector<int>> placements;
        vector<int> cols; // cols[r] = column of the queen in row r
        cols.reserve(n);
        place(n, cols, placements);
        return placements;
    }

private:
    bool isSafe(const vector<int>& cols, int col) {
        int row = (int)cols.size();
        for (int r = 0; r < row; r++) {
            if (cols[r] == col || abs(cols[r] - col) == row - r) return false;
        }
        return true;
    }

    void place(int n, vector<int>& cols, vector<vector<int>>& placements) {
        if ((int)cols.size() == n) {
            placements.push_back(cols);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (!isSafe(cols, col)) continue;
            cols.push_back(col);
            place(n, cols, placements);
            cols.pop_back();
        }
    }
};

3 · Backtracking with column and diagonal sets

O(n!) time · O(n) space

recommended

Every square on a down-right diagonal shares r - c, every square on a down-left one shares r + c, and both range over 2 * n - 1 values. Three vector<bool> flags held as members (columns, r - c + n - 1, r + c) make the safety check three reads. Set them before the recursive call and clear the same three after it, or a diagonal stays blocked for every later board.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> solveNQueens(int n) {
        this->n = n;
        cols.assign(n, 0);
        usedCols.assign(n, false);
        down.assign(2 * n - 1, false); // r - c + n - 1 is shared along a down-right diagonal
        up.assign(2 * n - 1, false);   // r + c is shared along a down-left diagonal
        placements.clear();
        place(0);
        return placements;
    }

private:
    int n = 0;
    vector<int> cols; // cols[r] = column of the queen in row r
    vector<bool> usedCols, down, up;
    vector<vector<int>> placements;

    void place(int r) {
        if (r == n) {
            placements.push_back(cols);
            return;
        }
        for (int c = 0; c < n; c++) {
            int d = r - c + n - 1, u = r + c;
            if (usedCols[c] || down[d] || up[u]) continue;
            cols[r] = c;
            usedCols[c] = down[d] = up[u] = true;
            place(r + 1);
            usedCols[c] = down[d] = up[u] = false;
        }
    }
};

3 reference approaches in C, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every permutation

O(n!·n²) time · O(n) space

A board is an int array whose entry r is the column of row r's queen; any permutation of 0 … n - 1 keeps rows and columns apart. C has no permutation helper, so nextPermutation does the swap-and-reverse step and returns false after the last order. Each order that passes the pairwise diagonal test is copied with malloc + memcpy into a result list that realloc doubles when it fills; the list lives in a small struct handed to the helpers.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

struct Boards {
    int n;
    int** rows;
    int count;
    int capacity;
};

static void addBoard(struct Boards* b, const int* cols) {
    if (b->count == b->capacity) {
        b->capacity = b->capacity ? 2 * b->capacity : 16;
        int** grown = realloc(b->rows, b->capacity * sizeof *grown);
        if (!grown) abort();
        b->rows = grown;
    }
    int* copy = malloc(b->n * sizeof *copy);
    memcpy(copy, cols, b->n * sizeof *copy);
    b->rows[b->count++] = copy;
}

static void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

// Advances p to the next order in lexicographic sequence; false after the last.
static bool nextPermutation(int* p, int n) {
    int i = n - 2;
    while (i >= 0 && p[i] >= p[i + 1]) i--;
    if (i < 0) return false;
    int j = n - 1;
    while (p[j] <= p[i]) j--;
    swap(&p[i], &p[j]);
    for (int lo = i + 1, hi = n - 1; lo < hi; lo++, hi--) swap(&p[lo], &p[hi]);
    return true;
}

static bool diagonalsClear(const int* cols, int n) {
    for (int r1 = 0; r1 < n; r1++) {
        for (int r2 = r1 + 1; r2 < n; r2++) {
            if (abs(cols[r1] - cols[r2]) == r2 - r1) return false;
        }
    }
    return true;
}

/**
 * Note: the returned arrays and *returnColumnSizes must be malloc'ed; the caller frees them.
 */
int** solveNQueens(int n, int* returnSize, int** returnColumnSizes) {
    struct Boards b = { n, NULL, 0, 0 };
    int* cols = malloc(n * sizeof *cols); // cols[r] = column of the queen in row r
    for (int i = 0; i < n; i++) cols[i] = i;
    do {
        if (diagonalsClear(cols, n)) addBoard(&b, cols);
    } while (nextPermutation(cols, n));
    free(cols);

    *returnSize = b.count;
    *returnColumnSizes = b.count ? malloc(b.count * sizeof **returnColumnSizes) : NULL;
    for (int i = 0; i < b.count; i++) (*returnColumnSizes)[i] = n;
    return b.rows;
}

2 · Backtracking with a safety scan

O(n!·n) time · O(n) space

Place queens row by row and reject a column the moment a queen above attacks it. The search state (the partial board and the growing result) sits in one struct, and the static helper place takes a pointer to it plus the row. isSafe scans rows 0 … r - 1 for a shared column or diagonal. A finished board is copied, because cols is overwritten as the search moves on.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

struct Search {
    int n;
    int* cols; // cols[r] = column of the queen in row r
    int** rows;
    int count;
    int capacity;
};

static void addBoard(struct Search* s) {
    if (s->count == s->capacity) {
        s->capacity = s->capacity ? 2 * s->capacity : 16;
        int** grown = realloc(s->rows, s->capacity * sizeof *grown);
        if (!grown) abort();
        s->rows = grown;
    }
    int* copy = malloc(s->n * sizeof *copy);
    memcpy(copy, s->cols, s->n * sizeof *copy);
    s->rows[s->count++] = copy;
}

static bool isSafe(const struct Search* s, int row, int col) {
    for (int r = 0; r < row; r++) {
        int c = s->cols[r];
        if (c == col || abs(c - col) == row - r) return false;
    }
    return true;
}

static void place(struct Search* s, int row) {
    if (row == s->n) {
        addBoard(s);
        return;
    }
    for (int col = 0; col < s->n; col++) {
        if (!isSafe(s, row, col)) continue;
        s->cols[row] = col;
        place(s, row + 1);
    }
}

/**
 * Note: the returned arrays and *returnColumnSizes must be malloc'ed; the caller frees them.
 */
int** solveNQueens(int n, int* returnSize, int** returnColumnSizes) {
    struct Search s = { n, malloc(n * sizeof(int)), NULL, 0, 0 };
    place(&s, 0);
    free(s.cols);

    *returnSize = s.count;
    *returnColumnSizes = s.count ? malloc(s.count * sizeof **returnColumnSizes) : NULL;
    for (int i = 0; i < s.count; i++) (*returnColumnSizes)[i] = n;
    return s.rows;
}

3 · Backtracking with column and diagonal sets

O(n!) time · O(n) space

recommended

Squares on a down-right diagonal share r - c, squares on a down-left one share r + c, and each spans 2 * n - 1 values. Three bool arrays from calloc (zeroed, so all false) mark the columns, r - c + n - 1 and r + c in use, which makes the safety check three reads. Set the three flags before the recursive call, clear the same three after it, and free the arrays once the search is done.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

struct Search {
    int n;
    int* cols;      // cols[r] = column of the queen in row r
    bool* usedCols; // n flags
    bool* down;     // 2n - 1 flags, index r - c + n - 1
    bool* up;       // 2n - 1 flags, index r + c
    int** rows;
    int count;
    int capacity;
};

static void addBoard(struct Search* s) {
    if (s->count == s->capacity) {
        s->capacity = s->capacity ? 2 * s->capacity : 16;
        int** grown = realloc(s->rows, s->capacity * sizeof *grown);
        if (!grown) abort();
        s->rows = grown;
    }
    int* copy = malloc(s->n * sizeof *copy);
    memcpy(copy, s->cols, s->n * sizeof *copy);
    s->rows[s->count++] = copy;
}

static void place(struct Search* s, int r) {
    int n = s->n;
    if (r == n) {
        addBoard(s);
        return;
    }
    for (int c = 0; c < n; c++) {
        int d = r - c + n - 1, u = r + c;
        if (s->usedCols[c] || s->down[d] || s->up[u]) continue;
        s->cols[r] = c;
        s->usedCols[c] = s->down[d] = s->up[u] = true;
        place(s, r + 1);
        s->usedCols[c] = s->down[d] = s->up[u] = false;
    }
}

/**
 * Note: the returned arrays and *returnColumnSizes must be malloc'ed; the caller frees them.
 */
int** solveNQueens(int n, int* returnSize, int** returnColumnSizes) {
    struct Search s = {
        .n = n,
        .cols = malloc(n * sizeof(int)),
        .usedCols = calloc(n, sizeof(bool)),
        .down = calloc(2 * n - 1, sizeof(bool)),
        .up = calloc(2 * n - 1, sizeof(bool)),
    };
    place(&s, 0);
    free(s.cols);
    free(s.usedCols);
    free(s.down);
    free(s.up);

    *returnSize = s.count;
    *returnColumnSizes = s.count ? malloc(s.count * sizeof **returnColumnSizes) : NULL;
    for (int i = 0; i < s.count; i++) (*returnColumnSizes)[i] = n;
    return s.rows;
}

3 reference approaches in Kotlin, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every permutation

O(n!·n²) time · O(n) space

One queen per row and one per column means every candidate board is a permutation of 0 until n, stored in an IntArray where cols[r] is the column of the queen in row r. The Kotlin standard library has no permutation generator for arrays, so nextPermutation steps the array to its lexicographic successor in place. A do/while loop tests the starting order 0, 1, …, n - 1 before the first step, and the labelled break@pairs leaves both pair loops at the first shared diagonal. A keeper is saved with copyOf(), because the next step rewrites cols.

import kotlin.math.abs

class Solution {
    fun solveNQueens(n: Int): Array<IntArray> {
        val placements = mutableListOf<IntArray>()
        val cols = IntArray(n) { it } // cols[r] = column of the queen in row r
        do {
            var ok = true
            pairs@ for (r1 in 0 until n) {
                for (r2 in r1 + 1 until n) {
                    if (abs(cols[r1] - cols[r2]) == r2 - r1) {
                        ok = false
                        break@pairs
                    }
                }
            }
            if (ok) placements.add(cols.copyOf())
        } while (nextPermutation(cols))
        return placements.toTypedArray()
    }

    // Turns p into the next ordering in lexicographic order
    // and returns false once p was already the last one.
    private fun nextPermutation(p: IntArray): Boolean {
        var i = p.size - 2
        while (i >= 0 && p[i] >= p[i + 1]) i--
        if (i < 0) return false
        var j = p.size - 1
        while (p[j] <= p[i]) j--
        p[i] = p[j].also { p[j] = p[i] }
        p.reverse(i + 1, p.size)
        return true
    }
}

2 · Backtracking with a safety scan

O(n!·n) time · O(n) space

Place one queen per row and give up on a row the moment no column is safe. Kotlin allows functions inside functions, so isSafe and place are local funs that read n, cols and placements from the enclosing scope instead of taking them as parameters. isSafe uses withIndex().none { … } to look for a queen above in the same column or on a diagonal. Taking a queen back is cols.removeAt(cols.lastIndex), and a finished board is copied out with toIntArray().

import kotlin.math.abs

class Solution {
    fun solveNQueens(n: Int): Array<IntArray> {
        val placements = mutableListOf<IntArray>()
        val cols = mutableListOf<Int>() // cols[r] = column of the queen in row r

        fun isSafe(col: Int): Boolean {
            val row = cols.size
            return cols.withIndex().none { (r, c) -> c == col || abs(c - col) == row - r }
        }

        fun place(row: Int) {
            if (row == n) {
                placements.add(cols.toIntArray())
                return
            }
            for (col in 0 until n) {
                if (isSafe(col)) {
                    cols.add(col)
                    place(row + 1)
                    cols.removeAt(cols.lastIndex)
                }
            }
        }

        place(0)
        return placements.toTypedArray()
    }
}

3 · Backtracking with column and diagonal sets

O(n!) time · O(n) space

recommended

Squares on a down-right diagonal share r - c and squares on a down-left diagonal share r + c, each in a range of 2 * n - 1 values. Three BooleanArrays (columns, r - c + n - 1 shifted to start at zero, and r + c) turn the safety scan into three reads. A new BooleanArray is all false, and the local place sets the three flags before recursing and clears exactly the same three after.

class Solution {
    fun solveNQueens(n: Int): Array<IntArray> {
        val placements = mutableListOf<IntArray>()
        val cols = IntArray(n) // cols[r] = column of the queen in row r
        val usedCols = BooleanArray(n)
        val down = BooleanArray(2 * n - 1) // r - c + n - 1 is shared along each down-right diagonal
        val up = BooleanArray(2 * n - 1) // r + c is shared along each down-left diagonal

        fun place(r: Int) {
            if (r == n) {
                placements.add(cols.copyOf())
                return
            }
            for (c in 0 until n) {
                val d = r - c + n - 1
                val u = r + c
                if (usedCols[c] || down[d] || up[u]) continue
                cols[r] = c
                usedCols[c] = true
                down[d] = true
                up[u] = true
                place(r + 1)
                usedCols[c] = false
                down[d] = false
                up[u] = false
            }
        }

        place(0)
        return placements.toTypedArray()
    }
}

3 reference approaches in Rust, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every permutation

O(n!·n²) time · O(n) space

With one queen per row and per column, a board is a permutation of 0..n: cols[r] is the column of the queen in row r. The standard library has no permutation iterator, so next_permutation rearranges a &mut [i32] into its lexicographic successor with swap and a slice reverse, and returns false after the last one. Each permutation is kept when nested all calls find no pair of rows whose column gap equals their row gap; the row gap is a usize, cast with as i32 before the comparison.

impl Solution {
    pub fn solve_n_queens(n: i32) -> Vec<Vec<i32>> {
        let n = n as usize;
        let mut placements = Vec::new();
        let mut cols: Vec<i32> = (0..n as i32).collect(); // cols[r] = column of the queen in row r
        loop {
            let ok = (0..n).all(|r1| {
                (r1 + 1..n).all(|r2| (cols[r1] - cols[r2]).abs() != (r2 - r1) as i32)
            });
            if ok {
                placements.push(cols.clone());
            }
            if !Self::next_permutation(&mut cols) {
                break;
            }
        }
        placements
    }

    // Turns p into the next ordering in lexicographic order
    // and returns false once p was already the last one.
    fn next_permutation(p: &mut [i32]) -> bool {
        let mut i = p.len() - 1;
        while i > 0 && p[i - 1] >= p[i] {
            i -= 1;
        }
        if i == 0 {
            return false;
        }
        let mut j = p.len() - 1;
        while p[j] <= p[i - 1] {
            j -= 1;
        }
        p.swap(i - 1, j);
        p[i..].reverse();
        true
    }
}

2 · Backtracking with a safety scan

O(n!·n) time · O(n) space

Grow the board one row at a time and abandon a row as soon as no column is safe. Rust fn items nested inside a function cannot capture its locals, so place receives the board as &mut Vec<i32> and the result as &mut Vec<Vec<i32>>, while is_safe only needs a shared &[i32] slice. push places a queen, pop takes it back, and a full board is stored with clone().

impl Solution {
    pub fn solve_n_queens(n: i32) -> Vec<Vec<i32>> {
        fn is_safe(cols: &[i32], col: i32) -> bool {
            let row = cols.len() as i32;
            cols.iter()
                .enumerate()
                .all(|(r, &c)| c != col && (c - col).abs() != row - r as i32)
        }

        fn place(n: i32, cols: &mut Vec<i32>, placements: &mut Vec<Vec<i32>>) {
            if cols.len() as i32 == n {
                placements.push(cols.clone());
                return;
            }
            for col in 0..n {
                if is_safe(cols, col) {
                    cols.push(col);
                    place(n, cols, placements);
                    cols.pop();
                }
            }
        }

        let mut placements = Vec::new();
        let mut cols = Vec::with_capacity(n as usize); // cols[r] = column of the queen in row r
        place(n, &mut cols, &mut placements);
        placements
    }
}

3 · Backtracking with column and diagonal sets

O(n!) time · O(n) space

recommended

Squares on a down-right diagonal share r - c and squares on a down-left diagonal share r + c. In usize arithmetic r - c would underflow, so the index is r + n - 1 - c, which runs from 0 to 2 * n - 2. The flags and the board live in a small local Board struct, and its place(&mut self, r) method sets three Vec<bool> flags, recurses, then clears the same three. Keeping the state in one struct means one &mut self instead of five &mut parameters.

impl Solution {
    pub fn solve_n_queens(n: i32) -> Vec<Vec<i32>> {
        struct Board {
            n: usize,
            cols: Vec<i32>, // cols[r] = column of the queen in row r
            used_cols: Vec<bool>,
            down: Vec<bool>, // r + n - 1 - c is shared along each down-right diagonal
            up: Vec<bool>,   // r + c is shared along each down-left diagonal
            placements: Vec<Vec<i32>>,
        }

        impl Board {
            fn place(&mut self, r: usize) {
                if r == self.n {
                    self.placements.push(self.cols.clone());
                    return;
                }
                for c in 0..self.n {
                    let (d, u) = (r + self.n - 1 - c, r + c);
                    if self.used_cols[c] || self.down[d] || self.up[u] {
                        continue;
                    }
                    self.cols[r] = c as i32;
                    self.used_cols[c] = true;
                    self.down[d] = true;
                    self.up[u] = true;
                    self.place(r + 1);
                    self.used_cols[c] = false;
                    self.down[d] = false;
                    self.up[u] = false;
                }
            }
        }

        let n = n as usize;
        let mut board = Board {
            n,
            cols: vec![0; n],
            used_cols: vec![false; n],
            down: vec![false; 2 * n - 1],
            up: vec![false; 2 * n - 1],
            placements: Vec::new(),
        };
        board.place(0);
        board.placements
    }
}

3 reference approaches in Swift, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every permutation

O(n!·n²) time · O(n) space

A board with one queen per row and per column is a permutation of 0..<n, with cols[r] holding the column of the queen in row r. The standard library has no permutation generator, so nextPermutation(_:) takes the array inout and steps it to its lexicographic successor with swapAt and an in-place reverse() of the tail slice. The repeat/while loop checks the starting order before the first step, and the labelled break pairs leaves both pair loops at the first shared diagonal. Appending cols stores a copy, because Swift arrays are values.

class Solution {
    func solveNQueens(_ n: Int) -> [[Int]] {
        var placements: [[Int]] = []
        var cols = Array(0..<n) // cols[r] = column of the queen in row r
        repeat {
            var ok = true
            pairs: for r1 in 0..<n {
                for r2 in (r1 + 1)..<n where abs(cols[r1] - cols[r2]) == r2 - r1 {
                    ok = false
                    break pairs
                }
            }
            if ok {
                placements.append(cols)
            }
        } while nextPermutation(&cols)
        return placements
    }

    // Turns p into the next ordering in lexicographic order
    // and returns false once p was already the last one.
    private func nextPermutation(_ p: inout [Int]) -> Bool {
        var i = p.count - 2
        while i >= 0 && p[i] >= p[i + 1] {
            i -= 1
        }
        if i < 0 {
            return false
        }
        var j = p.count - 1
        while p[j] <= p[i] {
            j -= 1
        }
        p.swapAt(i, j)
        p[(i + 1)...].reverse()
        return true
    }
}

2 · Backtracking with a safety scan

O(n!·n) time · O(n) space

Place queens row by row and drop a row as soon as no column is safe. isSafe and place are nested functions inside solveNQueens, so they capture cols and placements by reference and modify the same vars without passing them around. isSafe scans cols.enumerated() for a queen in the same column or on a diagonal, the where clause on the column loop skips the unsafe ones, and removeLast() takes the queen back.

class Solution {
    func solveNQueens(_ n: Int) -> [[Int]] {
        var placements: [[Int]] = []
        var cols: [Int] = [] // cols[r] = column of the queen in row r

        func isSafe(_ col: Int) -> Bool {
            let row = cols.count
            for (r, c) in cols.enumerated() where c == col || abs(c - col) == row - r {
                return false
            }
            return true
        }

        func place(_ row: Int) {
            if row == n {
                placements.append(cols)
                return
            }
            for col in 0..<n where isSafe(col) {
                cols.append(col)
                place(row + 1)
                cols.removeLast()
            }
        }

        place(0)
        return placements
    }
}

3 · Backtracking with column and diagonal sets

O(n!) time · O(n) space

recommended

Squares on a down-right diagonal share r - c and squares on a down-left diagonal share r + c. Three [Bool] arrays built with Array(repeating: false, count:) mark the columns, the r - c + n - 1 values (shifted so the index is never negative) and the r + c values in use. The nested place captures all of them, sets three flags before recursing and clears the same three after, so a safety check is three array reads.

class Solution {
    func solveNQueens(_ n: Int) -> [[Int]] {
        var placements: [[Int]] = []
        var cols = Array(repeating: 0, count: n) // cols[r] = column of the queen in row r
        var usedCols = Array(repeating: false, count: n)
        var down = Array(repeating: false, count: 2 * n - 1) // r - c + n - 1 is shared along each down-right diagonal
        var up = Array(repeating: false, count: 2 * n - 1) // r + c is shared along each down-left diagonal

        func place(_ r: Int) {
            if r == n {
                placements.append(cols)
                return
            }
            for c in 0..<n {
                let d = r - c + n - 1
                let u = r + c
                if usedCols[c] || down[d] || up[u] {
                    continue
                }
                cols[r] = c
                usedCols[c] = true
                down[d] = true
                up[u] = true
                place(r + 1)
                usedCols[c] = false
                down[d] = false
                up[u] = false
            }
        }

        place(0)
        return placements
    }
}

3 reference approaches in PHP, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every permutation

O(n!·n²) time · O(n) space

One queen per row and per column makes every candidate a permutation of range(0, $n - 1), where $cols[$r] is the column of the queen in row $r. PHP has no permutation function, so nextPermutation takes the array by reference (array &$p) and steps it to its lexicographic successor with destructuring swaps. A do/while loop tests the starting order before the first step. Storing a keeper with $placements[] = $cols already copies it, because PHP arrays are values.

<?php

class Solution {
    /**
     * @param int $n
     * @return int[][]
     */
    function solveNQueens(int $n): array {
        $placements = [];
        $cols = range(0, $n - 1); // $cols[$r] = column of the queen in row $r
        do {
            $ok = true;
            for ($r1 = 0; $r1 < $n && $ok; $r1++) {
                for ($r2 = $r1 + 1; $r2 < $n; $r2++) {
                    if (abs($cols[$r1] - $cols[$r2]) === $r2 - $r1) {
                        $ok = false;
                        break;
                    }
                }
            }
            if ($ok) {
                $placements[] = $cols;
            }
        } while ($this->nextPermutation($cols));
        return $placements;
    }

    // Turns $p into the next ordering in lexicographic order
    // and returns false once $p was already the last one.
    private function nextPermutation(array &$p): bool {
        $i = count($p) - 2;
        while ($i >= 0 && $p[$i] >= $p[$i + 1]) {
            $i--;
        }
        if ($i < 0) {
            return false;
        }
        $j = count($p) - 1;
        while ($p[$j] <= $p[$i]) {
            $j--;
        }
        [$p[$i], $p[$j]] = [$p[$j], $p[$i]];
        for ($lo = $i + 1, $hi = count($p) - 1; $lo < $hi; $lo++, $hi--) {
            [$p[$lo], $p[$hi]] = [$p[$hi], $p[$lo]];
        }
        return true;
    }
}

2 · Backtracking with a safety scan

O(n!·n) time · O(n) space

Build the board one row at a time and back out of a row when no column is safe. The private place method takes $cols and $placements by reference so every level of the recursion works on the same two arrays; isSafe only reads, so it takes $cols by value, which costs nothing thanks to copy-on-write. $cols[] = $col places a queen and array_pop takes it back, which keeps the array a list.

<?php

class Solution {
    /**
     * @param int $n
     * @return int[][]
     */
    function solveNQueens(int $n): array {
        $placements = [];
        $cols = []; // $cols[$r] = column of the queen in row $r
        $this->place($n, $cols, $placements);
        return $placements;
    }

    private function place(int $n, array &$cols, array &$placements): void {
        if (count($cols) === $n) {
            $placements[] = $cols;
            return;
        }
        for ($col = 0; $col < $n; $col++) {
            if ($this->isSafe($cols, $col)) {
                $cols[] = $col;
                $this->place($n, $cols, $placements);
                array_pop($cols);
            }
        }
    }

    private function isSafe(array $cols, int $col): bool {
        $row = count($cols);
        foreach ($cols as $r => $c) {
            if ($c === $col || abs($c - $col) === $row - $r) {
                return false;
            }
        }
        return true;
    }
}

3 · Backtracking with column and diagonal sets

O(n!) time · O(n) space

recommended

Squares on a down-right diagonal share $r - $c and squares on a down-left diagonal share $r + $c. PHP arrays accept negative integer keys, so three associative arrays used as sets ($usedCols, $down, $up) store those values directly, and isset checks a square in constant time. They are properties of the object, reset at the start of solveNQueens, so place reads them through $this. Each unset after the recursive call undoes exactly one of the three assignments before it.

<?php

class Solution {
    private int $n = 0;
    private array $cols = []; // $cols[$r] = column of the queen in row $r
    private array $usedCols = [];
    private array $down = []; // $r - $c is shared along each down-right diagonal
    private array $up = []; // $r + $c is shared along each down-left diagonal
    private array $placements = [];

    /**
     * @param int $n
     * @return int[][]
     */
    function solveNQueens(int $n): array {
        $this->n = $n;
        $this->cols = array_fill(0, $n, 0);
        $this->usedCols = $this->down = $this->up = $this->placements = [];
        $this->place(0);
        return $this->placements;
    }

    private function place(int $r): void {
        if ($r === $this->n) {
            $this->placements[] = $this->cols;
            return;
        }
        for ($c = 0; $c < $this->n; $c++) {
            if (isset($this->usedCols[$c]) || isset($this->down[$r - $c]) || isset($this->up[$r + $c])) {
                continue;
            }
            $this->cols[$r] = $c;
            $this->usedCols[$c] = true;
            $this->down[$r - $c] = true;
            $this->up[$r + $c] = true;
            $this->place($r + 1);
            unset($this->usedCols[$c], $this->down[$r - $c], $this->up[$r + $c]);
        }
    }
}

3 reference approaches in Ruby, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every permutation

O(n!·n²) time · O(n) space

One queen per row and per column makes every board a permutation of the columns, so (0...n).to_a.permutation already covers rows and columns, with cols[r] the column of the queen in row r. select keeps the permutations in which no pair of rows has a column gap equal to its row gap. The row pairs come from combination(2), built once before the loop instead of once per permutation. Each permutation is a fresh array, so the kept ones need no copy.

# @param {Integer} n
# @return {Integer[][]}
def solve_n_queens(n)
  pairs = (0...n).to_a.combination(2).to_a # every [r1, r2] with r1 < r2
  (0...n).to_a.permutation.select do |cols| # cols[r] = column of the queen in row r
    pairs.all? { |r1, r2| (cols[r1] - cols[r2]).abs != r2 - r1 }
  end
end

2 · Backtracking with a safety scan

O(n!·n) time · O(n) space

Place queens row by row and back out of a row as soon as no column is safe. A def inside a method does not see that method's local variables, so place and safe? are top-level helpers that take the board and the result as arguments. Ruby passes object references, so push and pop inside place change the caller's array, and a finished board is stored with dup.

# @param {Integer} n
# @return {Integer[][]}
def solve_n_queens(n)
  placements = []
  place(n, [], placements) # cols[r] = column of the queen in row r
  placements
end

def place(n, cols, placements)
  if cols.length == n
    placements << cols.dup
    return
  end
  n.times do |col|
    next unless safe?(cols, col)

    cols.push(col)
    place(n, cols, placements)
    cols.pop
  end
end

def safe?(cols, col)
  row = cols.length
  cols.each_with_index.none? { |c, r| c == col || (c - col).abs == row - r }
end

3 · Backtracking with column and diagonal sets

O(n!) time · O(n) space

recommended

Squares on a down-right diagonal share r - c and squares on a down-left diagonal share r + c, so three Sets of the values in use make a safety check three lookups. The recursive step is a lambda stored in place: unlike a nested def, a lambda closes over the method's locals, including the place variable itself, which lets it call place.(r + 1). The three delete calls after the recursion undo the three add calls before it.

require 'set'

# @param {Integer} n
# @return {Integer[][]}
def solve_n_queens(n)
  placements = []
  cols = [] # cols[r] = column of the queen in row r
  used_cols = Set.new
  down = Set.new # r - c is shared along each down-right diagonal
  up = Set.new # r + c is shared along each down-left diagonal

  place = lambda do |r|
    if r == n
      placements << cols.dup
      next
    end
    n.times do |c|
      next if used_cols.include?(c) || down.include?(r - c) || up.include?(r + c)

      cols.push(c)
      used_cols.add(c)
      down.add(r - c)
      up.add(r + c)
      place.(r + 1)
      cols.pop
      used_cols.delete(c)
      down.delete(r - c)
      up.delete(r + c)
    end
  end

  place.(0)
  placements
end

3 reference approaches in Dart, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every permutation

O(n!·n²) time · O(n) space

One queen per row and per column makes every board a permutation of 0 to n - 1, held in a List<int> where cols[r] is the column of the queen in row r. Dart's core libraries have no permutation generator, so _nextPermutation steps the list to its lexicographic successor in place and returns false after the last one. The do/while loop tests the starting order first, the labelled break pairs leaves both pair loops at the first shared diagonal, and List.of(cols) stores a copy of each keeper.

class Solution {
  List<List<int>> solveNQueens(int n) {
    final placements = <List<int>>[];
    final cols = List<int>.generate(n, (i) => i); // cols[r] = column of the queen in row r
    do {
      var ok = true;
      pairs:
      for (var r1 = 0; r1 < n; r1++) {
        for (var r2 = r1 + 1; r2 < n; r2++) {
          if ((cols[r1] - cols[r2]).abs() == r2 - r1) {
            ok = false;
            break pairs;
          }
        }
      }
      if (ok) placements.add(List.of(cols));
    } while (_nextPermutation(cols));
    return placements;
  }

  // Turns p into the next ordering in lexicographic order
  // and returns false once p was already the last one.
  bool _nextPermutation(List<int> p) {
    var i = p.length - 2;
    while (i >= 0 && p[i] >= p[i + 1]) {
      i--;
    }
    if (i < 0) return false;
    var j = p.length - 1;
    while (p[j] <= p[i]) {
      j--;
    }
    final tmp = p[i];
    p[i] = p[j];
    p[j] = tmp;
    p.setAll(i + 1, p.sublist(i + 1).reversed);
    return true;
  }
}

2 · Backtracking with a safety scan

O(n!·n) time · O(n) space

Place queens one row at a time and back out of a row as soon as no column is safe. isSafe and place are local functions inside solveNQueens, so they read and change cols and placements directly. isSafe walks the queens above with a plain index loop, add places a queen, removeLast() takes it back, and List.of(cols) stores a finished board.

class Solution {
  List<List<int>> solveNQueens(int n) {
    final placements = <List<int>>[];
    final cols = <int>[]; // cols[r] = column of the queen in row r

    bool isSafe(int col) {
      final row = cols.length;
      for (var r = 0; r < row; r++) {
        final c = cols[r];
        if (c == col || (c - col).abs() == row - r) return false;
      }
      return true;
    }

    void place(int row) {
      if (row == n) {
        placements.add(List.of(cols));
        return;
      }
      for (var col = 0; col < n; col++) {
        if (isSafe(col)) {
          cols.add(col);
          place(row + 1);
          cols.removeLast();
        }
      }
    }

    place(0);
    return placements;
  }
}

3 · Backtracking with column and diagonal sets

O(n!) time · O(n) space

recommended

Squares on a down-right diagonal share r - c and squares on a down-left diagonal share r + c. Three List<bool>s made with List.filled(…, false) mark the columns, the r - c + n - 1 values (shifted so the index is never negative) and the r + c values in use. The local place sets the three flags before recursing and clears the same three after, so a safety check is three list reads.

class Solution {
  List<List<int>> solveNQueens(int n) {
    final placements = <List<int>>[];
    final cols = List<int>.filled(n, 0); // cols[r] = column of the queen in row r
    final usedCols = List<bool>.filled(n, false);
    final down = List<bool>.filled(2 * n - 1, false); // r - c + n - 1 is shared along each down-right diagonal
    final up = List<bool>.filled(2 * n - 1, false); // r + c is shared along each down-left diagonal

    void place(int r) {
      if (r == n) {
        placements.add(List.of(cols));
        return;
      }
      for (var c = 0; c < n; c++) {
        final d = r - c + n - 1;
        final u = r + c;
        if (usedCols[c] || down[d] || up[u]) continue;
        cols[r] = c;
        usedCols[c] = true;
        down[d] = true;
        up[u] = true;
        place(r + 1);
        usedCols[c] = false;
        down[d] = false;
        up[u] = false;
      }
    }

    place(0);
    return placements;
  }
}

3 reference approaches in Scala, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: try every permutation

O(n!·n²) time · O(n) space

One queen per row and per column makes every board a permutation of 0 until n, and the collections library generates them lazily with permutations, each an IndexedSeq where cols(r) is the column of the queen in row r. filter keeps a permutation when nested forall calls find no pair of rows whose column gap equals their row gap, then each keeper becomes an Array[Int]. The whole method is one expression, with no loop and no return.

object Solution {
  def solveNQueens(n: Int): Array[Array[Int]] =
    (0 until n).permutations // cols(r) = column of the queen in row r
      .filter { cols =>
        (0 until n).forall { r1 =>
          (r1 + 1 until n).forall(r2 => (cols(r1) - cols(r2)).abs != r2 - r1)
        }
      }
      .map(_.toArray)
      .toArray
}

2 · Backtracking with a safety scan

O(n!·n) time · O(n) space

Place queens row by row and back out of a row as soon as no column is safe. isSafe and place are nested defs, so they close over the ArrayBuffers cols and placements. isSafe is a forall over the rows placed so far, which avoids a return from inside a closure, and the guard in for (col <- 0 until n if isSafe(col)) skips the unsafe columns. += places a queen, dropRightInPlace(1) takes it back, and toArray stores a finished board.

import scala.collection.mutable.ArrayBuffer

object Solution {
  def solveNQueens(n: Int): Array[Array[Int]] = {
    val placements = ArrayBuffer.empty[Array[Int]]
    val cols = ArrayBuffer.empty[Int] // cols(r) = column of the queen in row r

    def isSafe(col: Int): Boolean = {
      val row = cols.length
      cols.indices.forall(r => cols(r) != col && (cols(r) - col).abs != row - r)
    }

    def place(row: Int): Unit =
      if (row == n) placements += cols.toArray
      else
        for (col <- 0 until n if isSafe(col)) {
          cols += col
          place(row + 1)
          cols.dropRightInPlace(1)
        }

    place(0)
    placements.toArray
  }
}

3 · Backtracking with column and diagonal sets

O(n!) time · O(n) space

recommended

Squares on a down-right diagonal share r - c and squares on a down-left diagonal share r + c. Three Array[Boolean]s, which start out all false, mark the columns, the r - c + n - 1 values (shifted so the index is never negative) and the r + c values in use. The nested place sets three flags before recursing and clears the same three after; a while loop keeps the hot path free of closures, and the if around the body replaces a continue, which Scala does not have.

import scala.collection.mutable.ArrayBuffer

object Solution {
  def solveNQueens(n: Int): Array[Array[Int]] = {
    val placements = ArrayBuffer.empty[Array[Int]]
    val cols = new Array[Int](n) // cols(r) = column of the queen in row r
    val usedCols = new Array[Boolean](n)
    val down = new Array[Boolean](2 * n - 1) // r - c + n - 1 is shared along each down-right diagonal
    val up = new Array[Boolean](2 * n - 1) // r + c is shared along each down-left diagonal

    def place(r: Int): Unit =
      if (r == n) placements += cols.clone()
      else {
        var c = 0
        while (c < n) {
          val d = r - c + n - 1
          val u = r + c
          if (!usedCols(c) && !down(d) && !up(u)) {
            cols(r) = c
            usedCols(c) = true
            down(d) = true
            up(u) = true
            place(r + 1)
            usedCols(c) = false
            down(d) = false
            up(u) = false
          }
          c += 1
        }
      }

    place(0)
    placements.toArray
  }
}

FAQ for Java

Why use boolean arrays rather than a HashSet of Integer?

Both give correct answers. A HashSet<Integer> converts each column or diagonal number to an Integer and hashes it on every add, remove and contains, while the values in this problem are dense integers from 0 to 2 * n - 2 that can index an array directly. The one adjustment is adding n - 1 to r - c, because an array has no negative slots; a set would simply have stored the negative number.

Why not call cols.remove(col) to take a queen back?

Because cols is a List<Integer> and col is an int, cols.remove(col) resolves to the remove(int index) overload and deletes whatever sits at position col, not the value col. Depending on the board, that silently corrupts the search or throws IndexOutOfBoundsException. The queen to drop is always the last one added, so cols.removeLast() on Java 21, or cols.remove(cols.size() - 1) on older versions, says exactly that.

Can the recursion overflow the stack in Java?

Not for this problem. place goes one call deeper per row, so the longest chain is n + 1 frames, each holding a few ints and references. That sits comfortably inside the thread stack the engine gives its JVM (-Xss512k), and the running time grows so steeply with n that you give up waiting long before depth could matter. Rewriting it with an explicit stack would add code without buying anything.

How do I count the solutions, or stop at the first one?

To count, give place an int return type: 1 at r == n, otherwise the sum over its recursive calls, with the placements list removed. The boolean[] version then yields [1, 0, 0, 2, 10, 4, 40, 92, 352, 724] for n = 1 to 10, and the 92 for 8 × 8 reduce to 12 once rotations and reflections are treated as one board. To stop early, return a boolean, pass true straight up as soon as a deeper call reports it, and clear the flags only on the false path; at n = 8 the first placement found prints as [0, 4, 7, 5, 2, 6, 1, 3] through Arrays.toString(cols).

Is a bitmask version faster in Java?

For counting, yes. Pack the used columns and the two diagonal directions into three int masks, one bit per column, with all = (1 << n) - 1. The open squares of a row are all & ~(cols | down | up); Integer.lowestOneBit(free), or the equivalent free & -free, isolates one of them, and Integer.numberOfTrailingZeros converts it to a column index. On the way down, shift one diagonal mask left and the other right. The search tree and the counts match the versions above; each node just costs a handful of bit operations instead of array writes.

FAQ for Go

Why is place declared with var before the function is assigned?

A variable declared with := comes into scope only after the whole statement, so a function literal cannot see its own name and a self-call inside it fails to compile with undefined: place. Writing var place func(r int) first puts the name in scope, and the literal assigned on the next line captures that variable. If you dislike the two-step form, use a top-level func that receives n, cols, the flag slices and the result through parameters or a pointer to a struct.

Should the n = 3 case return nil or an empty slice?

The code starts from [][]int{}, so it hands back a non-nil slice of length 0. fmt prints a nil slice and an empty one identically, and len is 0 for both. The difference shows up elsewhere: encoding/json encodes nil as null and the empty slice as [], and a caller that tests placements == nil gets different answers. Pick one and keep it consistent; a function that returns a list of results usually wants the empty slice.

How do I count the solutions instead of collecting them?

Change place to func(r int) int, return 1 when r == n, and add up the recursive results inside the column loop. Without the slices.Clone and placements no copies are made, so counting is faster and stores nothing. Using the []bool program, n = 1 through 10 give [1 0 0 2 10 4 40 92 352 724]. The 92 for the 8 × 8 board collapse to 12 if a placement and its rotations and reflections count as one solution.

Can Go split the search across goroutines?

Yes, by the top row: each column for the first queen roots a subtree that shares nothing with the others. Start one goroutine per column, give each its own cols and flag slices (sharing them would be a data race), let each fill its own result slice, then wait on a sync.WaitGroup and concatenate the parts in column order so the placements keep a stable order. With only n independent subtrees, the speed-up is capped by n and by the cores you have.

Is a bitmask version faster in Go?

It is the usual way to speed up counting. Hold the used columns and the two diagonal directions in three uint values with one bit per column, and let all := uint(1)<<n - 1 cover the board width. The open squares of a row are all &^ (cols | down | up), using the and-not operator; free & -free isolates the lowest one, which is fine because negating a uint wraps around; and bits.TrailingZeros from math/bits gives its column. Going down a row, one diagonal mask shifts left by one and the other right by one. The tree and the counts stay the same, [1 0 0 2 10 4 40 92 352 724] for n = 1 to 10; only the work per node shrinks to a few integer operations.

FAQ for C#

Why bool arrays instead of a HashSet of int?

Both are correct. A HashSet<int> hashes the value on every Add, Remove and Contains, while the columns and diagonal numbers here are dense integers from 0 to 2 * n - 2 that can index an array directly, so the bool[] version does less work per square. The only adjustment is adding n - 1 to r - c, because an array has no negative slots; a set would simply have stored the negative number. If you prefer the set version, keep three HashSet<int> fields and mirror every Add with a Remove on the way back.

Why store cols.ToArray() rather than cols itself?

A List<int> and an int[] are both reference types, and the search keeps rewriting the same one. Adding cols directly would put the same object in the result over and over, and by the time SolveNQueens returns every entry would show whatever the last row of the search left behind. cols.ToArray() takes a snapshot at the moment the board is complete; (int[])cols.Clone() does the same for an array without LINQ.

Can Place be a local function instead of a static method?

Yes. C# supports local functions, so void Place(int r) { … } can sit inside SolveNQueens and capture n, cols, the flag arrays and placements from the enclosing scope, which drops most of the parameters. The harness only needs Solution.SolveNQueens to be public static; how you split the helpers is up to you. Static members were used here so each piece reads on its own and nothing is captured by accident.

How do I count the solutions, or stop at the first one?

To count, give Place an int return type: 1 when r == n, otherwise the sum of its recursive calls, and drop the placements list. The bool[] version then produces [1, 0, 0, 2, 10, 4, 40, 92, 352, 724] for n = 1 to 10; the 92 boards for 8 × 8 collapse to 12 once rotations and reflections count as one. To stop early, return a bool, pass true straight up the moment a deeper call reports it, and clear the flags only on the false path. Trying columns left to right, the first placement for n = 8 is [0, 4, 7, 5, 2, 6, 1, 3].

Is a bitmask version faster in C#?

For counting, yes. Pack the used columns and the two diagonal directions into three int masks with one bit per column and int all = (1 << n) - 1. The open squares of a row are all & ~(cols | down | up); free & -free isolates the lowest one, and System.Numerics.BitOperations.TrailingZeroCount(bit) turns it into a column index when you need one. Moving down a row shifts one diagonal mask left and the other right. The search tree and the counts are the same as above; each node just costs a few bit operations instead of six array writes.

FAQ for Kotlin

Can a local fun call itself recursively?

Yes. A local fun place(row: Int) is in scope inside its own body, so it can recurse, and it captures cols, placements and n from the enclosing function by reference. A lambda stored in a val cannot refer to itself while it is being initialised, which is why the recursive helper is a local fun rather than a lambda.

Why removeAt(cols.lastIndex) and not removeLast()?

Both drop the last queen. When the code is compiled against JDK 21 or later, removeLast() on a MutableList resolves to the new Java List.removeLast member instead of the Kotlin extension, and that member is missing on older Android runtimes. removeAt(cols.lastIndex) means the same thing on every platform.

Why copyOf() before adding a board to the result?

An IntArray is a mutable reference type. Adding cols itself would put the same array in the list 92 times, and every entry would end up holding whatever the search wrote last. cols.copyOf() (or toIntArray() on a list) stores a snapshot.

How do I count the solutions without collecting them?

Make place return an Int: 1 when r == n, otherwise the sum of its recursive calls, and drop placements. For n = 1 to 10 the BooleanArray version gives 1, 0, 0, 2, 10, 4, 40, 92, 352, 724; the 92 for the 8 × 8 board shrink to 12 when rotations and mirror images count as one.

What does a bitmask version look like in Kotlin?

Keep the columns and both diagonal directions as three Int masks and compute var free = all and (cols or down or up).inv() with all = (1 shl n) - 1. free and -free isolates the lowest open column, Integer.numberOfTrailingZeros (or countTrailingZeroBits()) turns it into an index, and the next row gets (down or bit) shl 1 and (up or bit) ushr 1. Kotlin spells the bit operators as infix functions, but they compile to the same JVM instructions as Java.

Keep going

Edit Distance39 / 40 · Dynamic programming · Hard

Try N-Queens in Python (N-Queens in Python), JavaScript (N-Queens in JavaScript), TypeScript (N-Queens in TypeScript), Java (N-Queens in Java), Go (N-Queens in Go), C# (N-Queens in C#), C++ (N-Queens in C++), C (N-Queens in C), Rust (N-Queens in Rust), Swift (N-Queens in Swift), PHP (N-Queens in PHP), Ruby (N-Queens in Ruby), Dart (N-Queens in Dart) or Scala (N-Queens in Scala) instead.

solve_n_queens.kt

Kotlin 2.4

Not run yet

+ 6 hidden

Input

n = 4

Expected

[[1, 3, 0, 2], [2, 0, 3, 1]]

Two placements, each the mirror image of the other. The first puts its queens in columns 1, 3, 0, 2 from the top row down.