How to Solve N Queen Problem Implementation in PHP?

Implementation of Linear Search in PHP

The N-Queens problem is a classic puzzle that involves placing N queens on an N×N chessboard so that no two queens attack each other. In chess, a queen can move horizontally, vertically, or diagonally, making this problem challenging and interesting. In this article, we’ll explore implementing a solution to the N-Queens problem using PHP. We’ll use a backtracking algorithm to find all possible solutions for any given value of N.

Approach

We’ll solve the N-Queens problem using a backtracking algorithm. The idea is to place queens row by row, and at each step, we’ll check if the current placement is valid. If it’s valid, we’ll proceed to the next row; otherwise, we’ll backtrack and try a different position for the queen.

Here’s a high-level overview of the algorithm:

Start with an empty chessboard.
Place a queen in the first row.
Move to the next row and place a queen in a safe position.
Repeat step 3 until all queens are placed.
If all queens are successfully placed, print the solution.
Backtrack if a safe position cannot be found for the current queen.

Example: Let’s implement this algorithm in PHP.

PHP

<?php

class NQueens {
    private $board;
    private $size;

    public function __construct($size) {
        $this->size = $size;
        $this->board = array_fill(0, $size, 
                       array_fill(0, $size, 0));
    }

    public function solve() {
        if (!$this->placeQueens(0)) {
            echo "No solution exists for $this->size Queens.";
        }
    }

    private function placeQueens($col) {
        if ($col >= $this->size) {
            $this->printBoard();
            return true;
        }

        $placed = false;
        for ($i = 0; $i < $this->size; $i++) {
            if ($this->isSafe($i, $col)) {
                $this->board[$i][$col] = 1;
                if ($this->placeQueens($col + 1)) {
                    $placed = true;
                }
                $this->board[$i][$col] = 0;
            }
        }

        return $placed;
    }

    private function isSafe($row, $col) {
        for ($i = 0; $i < $col; $i++) {
            if ($this->board[$row][$i] == 1) {
                return false;
            }
        }

        for ($i = $row, $j = $col; $i >= 0 &&
             $j >= 0; $i--, $j--) {
            if ($this->board[$i][$j] == 1) {
                return false;
            }
        }

        for ($i = $row, $j = $col; $i < $this->size
                     && $j >= 0; $i++, $j--) {
            if ($this->board[$i][$j] == 1) {
                return false;
            }
        }

        return true;
    }

    private function printBoard() {
        for ($i = 0; $i < $this->size; $i++) {
            for ($j = 0; $j < $this->size; $j++) {
                echo $this->board[$i][$j] ? "Q " : "- ";
            }
            echo "\n";
        }
        echo "\n";
    }
}
$size = 4;
$nQueens = new NQueens($size);
$nQueens->solve();
?>

Output:

- - Q - Q - - - - - - Q - Q - - - Q - - - - - Q Q - - - - - Q -

Tags:

#PHP-Questions #PHP #Web Technologies

Implementation of Linear Search in PHP

How to Solve N Queen Problem Implementation in PHP?

Approach

Contact Us