N-Queens Problem

Definition

Definition

The N-Queens Problem is a classic computer science problem where the task is to place N chess queens on an NxN chessboard in such a way that no two queens threaten each other. This means that no two queens share the same row, column, or diagonal

Explanation

Recursively placing queens on the board and backtracking when a solution cannot be found. It begins by placing a queen in the first row of the first column and then attempts to place subsequent queens in the next rows, ensuring that no two queens threaten each other. If a conflict arises, the algorithm backtracks and tries a different position for the queen

Guidance

• Start with an empty chessboard
• Place the first queen in the first row and first column
• Move to the next row
  • Check if the queen can be placed in the current column without conflicting with existing queens
  • If it can be placed, mark the position and move to the next row
  • Repeat steps until all queens are placed
• If a conflict arises or all positions in the current row are tried, backtrack to the previous row and try the next available position
• Continue this process until a solution is found or all possibilities are exhausted

Tips

• use efficient data structures to represent the chessboard and track queen positions
• implement pruning techniques to reduce the search space and improve performance
• optimize the algorithm by considering symmetries and avoiding redundant calculations
• test the algorithm with different board sizes to ensure its correctness and scalability

Practice

Practice

solveNQueens(board, row):
  if row == size_of_board:
    return true // all queens are placed successfully
  for each column in size_of_board:
    if isSafe(board, row, column):
      placeQueen(board, row, column)
      if solveNQueens(board, row + 1):
        return true
      removeQueen(board, row, column)
  return false // no solution found

isSafe(board, row, column):
  for i from 0 to row - 1:
    if board[i][column] == true:
      return false // queen threatens in the same column
    if column - (row - i) >= 0 and board[i][column - (row - i)] == true:
      return false // queen threatens in the left diagonal
    if size_of_board > column + (row - i) and board[i][column + (row - i)] == true:
      return false // queen threatens in the right diagonal
  return true

placeQueen(board, row, column):
  board[row][column] = true

removeQueen(board, row, column):
  board[row][column] = false

Solution

package main

func solveNQueens(n int) [][]string {
	var result [][]string
	board := make([][]rune, n)
	for i := range board {
		board[i] = make([]rune, n)
		for j := range board[i] {
			board[i][j] = '.'
		}
	}
	backtrack(&result, board, 0)
	return result
}

func backtrack(result *[][]string, board [][]rune, row int) {
	if row == len(board) {
		var temp []string
		for i := 0; i < len(board); i++ {
			temp = append(temp, string(board[i]))
		}
		*result = append(*result, temp)
		return
	}

	for col := 0; col < len(board); col++ {
		if isValid(board, row, col) {
			board[row][col] = 'Q'
			backtrack(result, board, row+1)
			board[row][col] = '.'
		}
	}
}

func isValid(board [][]rune, row, col int) bool {
	for i := 0; i < row; i++ {
		if board[i][col] == 'Q' {
			return false
		}
	}

	for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
		if board[i][j] == 'Q' {
			return false
		}
	}

	for i, j := row-1, col+1; i >= 0 && j < len(board); i, j = i-1, j+1 {
		if board[i][j] == 'Q' {
			return false
		}
	}
	return true
}

import java.util.ArrayList;
import java.util.List;

public class NQueens {

  public List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();
    char[][] board = new char[n][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        board[i][j] = '.';
      }
    }
    backtrack(result, board, 0);
    return result;
  }

  private void backtrack(List<List<String>> result, char[][] board, int row) {
    if (row == board.length) {
      List<String> temp = new ArrayList<>();
      for (char[] rowArray : board) {
        temp.add(String.valueOf(rowArray));
      }
      result.add(temp);
      return;
    }

    for (int col = 0; col < board.length; col++) {
      if (isValid(board, row, col)) {
        board[row][col] = 'Q';
        backtrack(result, board, row + 1);
        board[row][col] = '.';
      }
    }
  }

  private boolean isValid(char[][] board, int row, int col) {
    for (int i = 0; i < row; i++) {
      if (board[i][col] == 'Q') {
        return false;
      }
    }
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] == 'Q') {
        return false;
      }
    }
    for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
      if (board[i][j] == 'Q') {
        return false;
      }
    }
    return true;
  }
}

const solveNQueens = function (n) {
  const result = [];
  const board = Array.from({ length: n }, () =>
    Array.from({ length: n }, () => "."),
  );

  const backtrack = (row) => {
    if (row === n) {
      result.push(board.map((row) => row.join("")));
      return;
    }

    for (let col = 0; col < n; col++) {
      if (isValid(row, col)) {
        board[row][col] = "Q";
        backtrack(row + 1);
        board[row][col] = ".";
      }
    }
  };

  const isValid = (row, col) => {
    for (let i = 0; i < row; i++) {
      if (board[i][col] === "Q") {
        return false;
      }
    }
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] === "Q") {
        return false;
      }
    }
    for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
      if (board[i][j] === "Q") {
        return false;
      }
    }
    return true;
  };

  backtrack(0);
  return result;
};

fun solveNQueens(n: Int): List<List<String>> {
    val result = mutableListOf<List<String>>()
    val board = Array(n) { CharArray(n) { '.' } }

    fun backtrack(row: Int) {
        if (row == n) {
            result.add(board.map { it.joinToString("") })
            return
        }
        for (col in board.indices) {
            if (isValid(row, col)) {
                board[row][col] = 'Q'
                backtrack(row + 1)
                board[row][col] = '.'
            }
        }
    }

    fun isValid(row: Int, col: Int): Boolean {
        for (i in 0 until row) {
            if (board[i][col] == 'Q') return false
        }
        var i = row - 1
        var j = col - 1
        while (i >= 0 && j >= 0) {
            if (board[i--][j--] == 'Q') return false
        }
        i = row - 1
        j = col + 1
        while (i >= 0 && j < n) {
            if (board[i--][j++] == 'Q') return false
        }
        return true
    }

    backtrack(0)
    return result
}

def solveNQueens(n):
    result = []

    def backtrack(board, row):
        if row == n:
            result.append([''.join(row) for row in board])
            return
        for col in range(n):
            if isValid(board, row, col):
                board[row][col] = 'Q'
                backtrack(board, row + 1)
                board[row][col] = '.'

    def isValid(board, row, col):
        for i in range(row):
            if board[i][col] == 'Q':
                return False
        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if board[i][j] == 'Q':
                return False
            i, j = i - 1, j - 1
        i, j = row - 1, col + 1
        while i >= 0 and j < n:
            if board[i][j] == 'Q':
                return False
            i, j = i - 1, j + 1
        return True

    board = [['.'] * n for _ in range(n)]
    backtrack(board, 0)
    return result

fn solve_n_queens(n: i32) -> Vec<Vec<String>> {
    let mut result = Vec::new();
    let mut board = vec![vec!['.'; n as usize]; n as usize];

    fn backtrack(result: &mut Vec<Vec<String>>, board: &mut Vec<Vec<char>>, row: usize) {
        let n = board.len();
        if row == n {
            result.push(board.iter().map(|r| r.iter().collect()).collect());
            return;
        }

        for col in 0..n {
            if is_valid(&board, row, col) {
                board[row][col] = 'Q';
                backtrack(result, board, row + 1);
                board[row][col] = '.';
            }
        }
    }

    fn is_valid(board: &Vec<Vec<char>>, row: usize, col: usize) -> bool {
        let n = board.len();
        for i in 0..row {
            if board[i][col] == 'Q' {
                return false;
            }
        }
        let (mut i, mut j) = (row as i32 - 1, col as i32 - 1);
        while i >= 0 && j >= 0 {
            if board[i as usize][j as usize] == 'Q' {
                return false;
            }
            i -= 1;
            j -= 1;
        }
        let (mut i, mut j) = (row as i32 - 1, col as i32 + 1);
        while i >= 0 && j < n as i32 {
            if board[i as usize][j as usize] == 'Q' {
                return false;
            }
            i -= 1;
            j += 1;
        }
        true
    }

    backtrack(&mut result, &mut board, 0);
    result
}

function solveNQueens(n: number): string[][] {
  const result: string[][] = [];
  const board: string[][] = Array.from({ length: n }, () =>
    Array.from({ length: n }, () => "."),
  );

  function backtrack(row: number): void {
    if (row === n) {
      result.push(board.map((row) => row.join("")));
      return;
    }

    for (let col = 0; col < n; col++) {
      if (isValid(row, col)) {
        board[row][col] = "Q";
        backtrack(row + 1);
        board[row][col] = ".";
      }
    }
  }

  function isValid(row: number, col: number): boolean {
    for (let i = 0; i < row; i++) {
      if (board[i][col] === "Q") return false;
    }
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] === "Q") return false;
    }
    for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
      if (board[i][j] === "Q") return false;
    }
    return true;
  }

  backtrack(0);
  return result;
}