# N Queen Problem

The N Queen, also known as eight queens puzzle, is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other.

```									```\$N = 4;

function PrintSolution(&\$board)
{
global \$N;

for (\$i = 0; \$i < \$N; ++\$i)
{
for (\$j = 0; \$j < \$N; ++\$j)
echo " " . \$board[\$i][\$j] . " ";

echo "<br/>";
}
}

function IsSafe(&\$board, \$row, \$col)
{
global \$N;
\$i; \$j;

for (\$i = 0; \$i < \$col; ++\$i)
if (\$board[\$row][\$i])
return false;

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

for (\$i = \$row, \$j = \$col; \$j >= 0 && \$i < \$N; ++\$i, --\$j)
if (\$board[\$i][\$j])
return false;

return true;
}

function SolveNQ(&\$board, \$col)
{
global \$N;

if (\$col >= \$N)
return true;

for (\$i = 0; \$i < \$N; ++\$i)
{
if (IsSafe(\$board, \$i, \$col))
{
\$board[\$i][\$col] = 1;

if (SolveNQ(\$board, \$col + 1))
return true;

\$board[\$i][\$col] = 0;
}
}

return false;
}

function Solve()
{
\$board = array(
array(0, 0, 0, 0),
array(0, 0, 0, 0),
array(0, 0, 0, 0),
array(0, 0, 0, 0)
);

if (SolveNQ(\$board, 0) == false)
return false;

PrintSolution(\$board);
return true;
}```
```

### Example

```									`\$isSolved = Solve();`
```

### Output

```									```isSolved: true

Output of Solve function:
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0```
```