32. Backtracking, N queens - Part A
The chapter discusses the concept of backtracking through the lens of the N Queens problem, where the challenge is to place N queens on an N x N chessboard such that no two queens attack each other. It explores how backtracking allows for systematic exploration of potential solutions by building candidate solutions incrementally and undoing steps when dead ends are reached. The chapter also highlights specific implementations for the eight queens problem and the necessary representations needed to track queen positions and attacked squares on the board.
Sections
Navigate through the learning materials and practice exercises.
What we have learnt
- Backtracking is a systematic search method for solving problems by exploring possible solutions and undoing steps when necessary.
- The N Queens problem demonstrates that placing queens on a chessboard requires careful consideration of their attacking positions based on the rules of chess.
- The implementation of the N Queens solution can optimize board representation and track queen movements effectively.
Key Concepts
- -- Backtracking
- A recursive algorithmic technique that attempts to solve a problem by incrementally building candidates to the solution and abandoning those candidates ('backtrack') as soon as they are determined not to be valid.
- -- N Queens Problem
- A classic combinatorial problem that requires finding a way to place N queens on an N x N chessboard so that no two queens threaten each other.
- -- Queen's Attack
- In chess, a queen can attack any square horizontally, vertically, or diagonally from its position; thus, placing queens requires avoiding these attacked squares.
Additional Learning Materials
Supplementary resources to enhance your learning experience.