Queen Attack in Common-lisp: Complete Solution & Deep Dive Guide

a computer screen with a bunch of text on it

From Zero to Hero: Solving the Queen Attack Problem in Common Lisp

The Queen Attack problem is a classic programming puzzle that elegantly tests your understanding of coordinate geometry and logical conditions. It requires determining if two queens on a chessboard can attack each other by checking if they share the same row, column, or diagonal, a task perfectly suited for Common Lisp's expressive syntax.

You stare at the chessboard, not as a player, but as an architect of logic. The pieces aren't just wood or plastic; they are data points in a grid, governed by rules you must translate into code. The queen, the most powerful piece, moves with a simple yet deadly grace—horizontally, vertically, diagonally. Your challenge is to capture this grace in a function. It feels daunting, like trying to teach a machine the intuition of a grandmaster.

Many developers, especially those new to languages like Common Lisp, hit a wall here. The syntax feels alien, the logic of coordinate comparison seems convoluted, and debugging can feel like navigating a labyrinth. You're not just solving a chess puzzle; you're battling a new way of thinking.

This guide is your strategic manual. We will demystify the Queen Attack problem entirely, breaking it down into simple, manageable steps. You will learn not only the "how" but the "why" behind each line of Common Lisp code, transforming a complex challenge into a clear, elegant solution. By the end, you'll be able to implement this logic with the confidence of a seasoned developer.

What is the Queen Attack Problem?

At its core, the Queen Attack problem is a computational geometry challenge disguised as a chess puzzle. The objective is straightforward: given the coordinates of two queens on a standard 8x8 chessboard, we need to write a program that determines if they are positioned to attack each other.

In chess, a queen's power lies in her unrestricted movement. She can attack any piece that lies on the same horizontal row, the same vertical column, or either of the two diagonals passing through her position. Our program must algorithmically replicate these three attack vectors.

The Three Attack Conditions

Same Row: If two queens have the same row coordinate, they can attack each other.
Same Column: If two queens have the same column coordinate, they can attack each other.
Same Diagonal: This is the most complex condition. Two queens are on the same diagonal if the absolute difference of their row coordinates is equal to the absolute difference of their column coordinates.

We don't need to simulate a full chessboard with a 2D array. The problem can be solved purely by analyzing the two sets of coordinates. This makes it a fantastic exercise for practicing conditional logic and mathematical operations in a new programming language.

Why Use Common Lisp for This Logic Puzzle?

While the Queen Attack problem can be solved in any language, Common Lisp offers a unique and powerful environment for tackling such logical puzzles. Its design philosophy, rooted in symbolic computation and functional programming, makes it exceptionally well-suited for this task.

Key Advantages of Common Lisp:

Expressive and Concise Syntax: Lisp's prefix notation (e.g., (+ 1 2)) might seem unusual at first, but it allows for extremely clear and unambiguous logical expressions. Combining conditions with and and or becomes naturally nested and easy to read once you're familiar with it.
Functional Paradigm: The problem lends itself perfectly to a functional approach. We can create small, pure functions for each logical check (is on same row? is on same diagonal?) and then compose them into a final solution. This promotes clean, testable, and reusable code.
REPL-Driven Development: Common Lisp's Read-Eval-Print Loop (REPL) is legendary. It allows for interactive development where you can test each small function (like the diagonal check) in isolation before integrating it into the main program. This rapid feedback loop is invaluable for debugging and understanding complex logic.
Strong Mathematical Roots: As a descendant of LISP, which was designed for mathematical and symbolic computation, Common Lisp has robust built-in functions for arithmetic operations like abs (absolute value), which is crucial for the diagonal check.

For problems that involve transforming data and evaluating logical states, Common Lisp isn't just a choice; it's often a superior tool that encourages a more declarative and logical style of programming.

How to Model the Board and Implement the Logic

Let's break down the implementation strategy. We'll start by defining how we represent the data, then build helper functions for validation, and finally, combine everything into the main attack-checking function.

Step 1: Representing Queen Positions

A full 8x8 board matrix is unnecessary and inefficient for this problem. All we need are the coordinates. We'll represent each queen's position as a pair of integers: `(row, column)`. In Common Lisp, we can pass these as simple arguments to our functions.

We'll assume a zero-indexed board, where rows and columns range from 0 to 7. So, the top-left square is `(0, 0)` and the bottom-right is `(7, 7)`.

Step 2: Input Validation is Crucial

Before checking for attacks, we must ensure the given coordinates are valid. A queen cannot be placed off the board. We'll create a helper function, valid-position-p, that checks two things:

The coordinates are not identical (a queen cannot attack itself in this context).
Both the row and column for each queen are within the valid range [0, 7].

This defensive programming practice prevents logical errors and makes our main function more robust.

Step 3: The Core Attack Logic

This is where we translate the chess rules into code. We will check the three conditions sequentially.

Same Row Check: This is a simple equality check. Given `(row1, col1)` and `(row2, col2)`, the condition is (= row1 row2).

Same Column Check: Similarly, this is (= col1 col2).

Same Diagonal Check: This is the heart of the puzzle. A key insight from coordinate geometry is that for any two points on a 45-degree line, the change in x is equal to the change in y. In our grid, this means the absolute difference in rows must equal the absolute difference in columns. The condition is (= (abs (- row1 row2)) (abs (- col1 col2))).

Step 4: Combining the Logic with `or`

Since a queen can attack if any of these three conditions are met, we use a logical OR to combine them. If the row check is true, OR the column check is true, OR the diagonal check is true, then the queens can attack.

Logic Flow Diagram

Here is a visual representation of our program's decision-making process.

    ● Start: Receive two queen positions (r1, c1), (r2, c2)
    │
    ▼
  ┌──────────────────┐
  │ Validate Inputs  │
  └─────────┬────────┘
            │
            ▼
  ◆ Are positions on board [0-7] and not identical?
   ╱                       ╲
 Yes (Valid)              No (Invalid)
  │                         │
  ▼                         ▼
┌───────────────────┐      ┌──────────────────┐
│ Check Attack Logic│      │ Throw Error/Exit │
└─────────┬─────────┘      └──────────────────┘
          │
          ├─→ ◆ Same Row? (r1 == r2) ─→ Yes: Attack (T)
          │
          ├─→ ◆ Same Col? (c1 == c2) ─→ Yes: Attack (T)
          │
          └─→ ◆ Same Diag? (|r1-r2| == |c1-c2|) ─→ Yes: Attack (T)
              │
              ▼
          ● No: No Attack (NIL)

Where the Logic is Implemented: The Common Lisp Solution

Now, let's translate our strategy into working Common Lisp code. We'll follow the structure discussed, creating a helper function for validation and a main function for the attack logic. This code is from the exclusive kodikra.com learning curriculum.

The Full Code

Here is the complete, well-commented solution. We define a package `queen-attack` to encapsulate our functions.


;;; This solution is part of the kodikra.com exclusive learning curriculum.

(defpackage :queen-attack
  (:use :cl)
  (:export :valid-position-p :can-attack-p))

(in-package :queen-attack)

(defun valid-position-p (row col)
  "Checks if a single position (row, col) is on the 8x8 board."
  (and (>= row 0) (<= row 7)
       (>= col 0) (<= col 7)))

(defun can-attack-p (queen-w-row queen-w-col queen-b-row queen-b-col)
  "Determines if two queens at the given positions can attack each other."
  ;; First, perform comprehensive input validation.
  (unless (and (valid-position-p queen-w-row queen-w-col)
               (valid-position-p queen-b-row queen-b-col))
    (error "One or both queen positions are off the board."))
  
  (when (= (+ queen-w-row queen-w-col)
           (+ queen-b-row queen-b-col))
    (when (= queen-w-row queen-b-row)
      (error "Queens cannot occupy the same position.")))

  ;; The core attack logic.
  ;; If any of these conditions are true, they can attack.
  (or
   ;; Condition 1: Are they on the same row?
   (= queen-w-row queen-b-row)

   ;; Condition 2: Are they on the same column?
   (= queen-w-col queen-b-col)

   ;; Condition 3: Are they on the same diagonal?
   ;; This is true if the absolute difference of rows equals
   ;; the absolute difference of columns.
   (= (abs (- queen-w-row queen-b-row))
      (abs (- queen-w-col queen-b-col)))))

Detailed Code Walkthrough

1. The Package Definition


(defpackage :queen-attack
  (:use :cl)
  (:export :valid-position-p :can-attack-p))

(in-package :queen-attack)

defpackage: This creates a new namespace called queen-attack. This helps prevent naming conflicts with other Lisp code.
(:use :cl): It specifies that our package will use the standard symbols from the Common Lisp package (like defun, and, =).
(:export ...): This makes our functions valid-position-p and can-attack-p publicly available to other code that might use our package.
in-package: This switches the current working environment into our newly defined package.

2. The Validation Helper: `valid-position-p`


(defun valid-position-p (row col)
  "Checks if a single position (row, col) is on the 8x8 board."
  (and (>= row 0) (<= row 7)
       (>= col 0) (<= col 7)))

defun: Defines a function named valid-position-p that takes two arguments, row and col.
The string that follows is a "docstring," which explains what the function does. This is excellent practice for code documentation.
and: This is a macro that evaluates its arguments from left to right. It returns the value of the last argument if all are true, otherwise it returns NIL as soon as it encounters a false condition.
(>= row 0) and (<= row 7): These check if the row is between 0 and 7, inclusive. The same logic is applied to the column. The function returns T (true) only if all four conditions are met.

3. The Main Function: `can-attack-p`


(defun can-attack-p (queen-w-row queen-w-col queen-b-row queen-b-col)
  "..."
  (unless (and (valid-position-p queen-w-row queen-w-col)
               (valid-position-p queen-b-row queen-b-col))
    (error "One or both queen positions are off the board."))
  
  (when (= (+ queen-w-row queen-w-col)
           (+ queen-b-row queen-b-col))
    (when (= queen-w-row queen-b-row)
      (error "Queens cannot occupy the same position.")))
  ...)

The function takes four arguments representing the coordinates of the white (w) and black (b) queens.
unless: This is syntactic sugar for (if (not ...)). It executes its body only if the condition is false. Here, we call our helper valid-position-p for both queens. If either position is invalid, the and returns NIL, and the unless block is executed.
(error "..."): This signals an error and stops execution, providing a helpful message. This is more robust than just returning NIL.
The when block checks if the queens are on the same square, which is also an invalid state for this problem, and throws an error accordingly.


  (or
   ;; Condition 1: Same row
   (= queen-w-row queen-b-row)

   ;; Condition 2: Same column
   (= queen-w-col queen-b-col)

   ;; Condition 3: Same diagonal
   (= (abs (- queen-w-row queen-b-row))
      (abs (- queen-w-col queen-b-col)))))

or: This is the logical heart of the function. Like and, it evaluates its arguments from left to right. It returns the first non-NIL (true) value it finds, or NIL if all arguments are false.
(= queen-w-row queen-b-row): Checks the row condition.
(= queen-w-col queen-b-col): Checks the column condition.
(= (abs (- ...)) (abs (- ...))): This implements the diagonal check. - calculates the difference, and abs gets the absolute value. If the absolute differences are equal, they are on a diagonal. The function returns the result of this or expression, which will be T or NIL.

When to Apply This Kind of Logic? (Alternative Use Cases)

The logic underpinning the Queen Attack problem—coordinate comparison on a grid—is not limited to chess simulations. It's a fundamental pattern in computer science with applications across various domains.

Game Development: Beyond chess, this logic is used for line-of-sight calculations, collision detection for projectiles, and determining valid moves for units in strategy games like Fire Emblem or XCOM.
Robotics and Pathfinding: In a grid-based environment, a robot might need to determine if its path to a target is clear or if another object lies on a direct horizontal, vertical, or diagonal line.
Image Processing: Algorithms that analyze pixels might use similar logic to identify lines or patterns. For example, detecting a diagonal line of pixels of a certain color.
Computational Geometry: This is a foundational problem in a field that deals with algorithms for geometric objects. The principles extend to more complex problems like finding intersections between lines or polygons.

Visualizing the Diagonal Check

The diagonal check is the most clever part of the solution. This diagram illustrates why `|Δrow| = |Δcol|` works. For any two points on a diagonal, the "rise" (change in row) is equal to the "run" (change in column).

    Q1 (r1, c1)
    ●
    │ \
    │  \
  Δrow│   \
    │    \
    │     \
    └───────● Q2 (r2, c2)
       Δcol

  Condition: |r1 - r2| == |c1 - c2|
             |  Δrow | == |  Δcol |

This simple mathematical property allows us to avoid complex line-equation calculations and solve the problem with basic arithmetic, showcasing the power of finding the right abstraction.

Pros & Cons of the Coordinate-Based Approach

Our solution is highly efficient because it avoids creating a data structure for the board. However, every design choice has trade-offs. Here's a comparison.

Aspect	Coordinate-Based Logic (Our Approach)	Full Board Representation (e.g., 2D Array)
Memory Usage	Extremely low. Only stores 4 integers for coordinates. O(1) space complexity.	Higher. Requires an 8x8 (64-element) array or list of lists. O(n^2) space complexity.
Performance	Very high. A few simple arithmetic operations and comparisons. O(1) time complexity.	Slower. Would require iterating through rows, columns, or diagonals from a queen's position.
Extensibility	Less extensible. Designed specifically for two pieces. Adding more pieces or different rules is difficult.	Highly extensible. A board state is necessary for a full chess game, piece obstruction checks, etc.
Simplicity	High. The logic is self-contained and easy to understand once the diagonal rule is known.	More complex. Requires managing the state of the board data structure.

For the specific problem defined in the kodikra module, the coordinate-based approach is unequivocally superior. It is a perfect example of solving the exact problem you're given without over-engineering.

Frequently Asked Questions (FAQ)

What happens if the two queens are in the same position?: Our code treats this as an invalid state and signals an error. In the context of the problem, two distinct queens are implied. If they were at the same coordinates, all three conditions (same row, same column, and same diagonal) would technically be true, as the difference in coordinates would be zero for all checks.
Why is input validation so important here?: Without validation, passing coordinates like `(-1, 10)` would not cause an immediate crash but could lead to incorrect logical outcomes. More importantly, it violates the problem's constraints (an 8x8 board). Robust software always validates its inputs to ensure it operates within expected parameters, preventing bugs and security vulnerabilities.
How would this logic scale to a larger N x N board?: Beautifully. The core logic is independent of board size. The only change required would be in the valid-position-p function, where the checks would be against (N-1) instead of 7. The attack logic (= (abs (- r1 r2)) (abs (- c1 c2))) works for any size grid.
What do `T` and `NIL` mean in Common Lisp?: T is the canonical symbol for "true." NIL represents "false." However, in Common Lisp's boolean logic, NIL is the only false value. *Any* other value, including numbers, strings, and the symbol T, is considered true in a boolean context.
Is it possible to solve the diagonal check without using the `abs` function?: Yes, you could. You would need to check the two types of diagonals separately. The condition would be (= (- r1 c1) (- r2 c2)) for one diagonal direction and (= (+ r1 c1) (+ r2 c2)) for the other. Using abs is generally considered more concise and readable as it covers both cases in one line.
How is this related to the famous N-Queens puzzle?: The Queen Attack problem is the fundamental building block for the N-Queens puzzle. The N-Queens puzzle asks you to place N queens on an N×N chessboard so that no two queens can attack each other. To solve it, you need an algorithm (like backtracking) that repeatedly uses the `can-attack-p` logic to validate each potential queen placement against all previously placed queens.

Conclusion: From Board Rules to Code Logic

We have successfully translated the abstract rules of a chess piece into concrete, efficient, and robust Common Lisp code. The journey from understanding the problem—the what—to implementing the solution—the how—revealed key programming principles: the importance of data representation, the necessity of input validation, and the power of breaking a complex problem into smaller, logical checks.

The Queen Attack problem is more than a simple puzzle; it's a lesson in algorithmic thinking. The elegance of the diagonal check, (= (abs (- r1 r2)) (abs (- c1 c2))), demonstrates how a bit of mathematical insight can lead to incredibly simple and powerful code. Common Lisp, with its functional nature and clear syntax for logical operations, proved to be an excellent tool for expressing this solution.

You now have a solid understanding of this classic problem and a reusable code pattern for any grid-based logical check. Continue honing your skills by applying these concepts to more complex challenges.

Ready for your next challenge? Explore the full Common Lisp 2 learning path on kodikra.com or dive deeper into the language with our complete Common Lisp guide.

Disclaimer: The code in this article is written for clarity and educational purposes. It has been tested with modern Common Lisp implementations like Steel Bank Common Lisp (SBCL) 2.4.x. Behavior may vary with older or different Lisp compilers.

Published by Kodikra — Your trusted Common-lisp learning resource.

kodikra

Search this blog