Задача о 8-ми ферзях

Сегодня статья не будет относиться как-либо к прикладному программированию под СУС 1С-Битрикс. Сегодня решаем задачу.

Есть примечательная шахматная задача о 8-ми ферзях. Суть ее сводится к следующему: требуется расположить 8 ферзей на шахматной доске таким образом, чтобы ни один из них не находился под боем какого-либо другого. С точки зрения программирование требуется найти массив из 8-ми точек, координаты которых должны принадлежать матрице с размерами 8 на 8. При этом ни у одного из элементов данного массива не должны быть одинаковые координаты по горизонтали, либо по вертикали, а также не должно быть пересечений между точками по диагоналям, если провести данные диагонали ото всех точек из набора.
Данная задача решается методом перебора и требуется как-то подобрать количество значений для перебора. Я решил, закодировать сразу целый вектор из восьми ферзей на доске 8-миричным числом, в котором позиция цифры в числе есть координата по высоте, а само число в данной позиции есть координата по горизонтали. Итого получается, что количество наборов ферзей есть 8*8*8*8*8*8*8*8=16777216 в десятичной системе счисления или 100000000 в восьмиричной системе счисления. А итерировать значение переменной внутри цикла перебора следует от числа 0 до числа 16777215 в десятичной системе счисления, тогда в восьмиричной системе будут наборы от 00000000 до 77777777 , что описывает все возможные комбинации расположения ферзей на доске.
Алгоритм программы сводится к следующему:
1. Получить новое число и конвертировать его в восьмиричную систему счисления, при этом нужно еще добавить лидирующих нулей, чтобы число имело форму XXXXXXXX.
2. Проверить набор точек, чтобы ферзи не пересекались по горизонтали и вертикали
3. Проверить набор точек, чтобы ферзи не пересекались по диагоналям.
4. Если все проверки пройдены, то вывести набор.

Программа имеет следующий вид:

<?php
set_time_limit(0);
$queens = 0; $max_queens = 8*8*8*8*8*8*8*8;
while($queens < $max_queens)
{
    foreach(str_split(str_pad(decoct($queens), 8, "0", STR_PAD_LEFT)) as $i=>$j)
        $q_places[$i] = Array($i, $j);

    $illegal_point = false;
    foreach($q_places as $key=>$q_place)
    {
        for($i=0; $i<8; $i++)
        {
            if ( ($i!=$key && $q_place[0] == $q_places[$i][0])
            || ($i!=$key && $q_place[1] == $q_places[$i][1]) )
                $illegal_point = true;

            for($j=1; $j<=7; $j++)
            {
                if ($i!=$key)
                {
                    if ( ($q_place[0]-$j == $q_places[$i][0] && $q_place[1]-$j == $q_places[$i][1]) ||
                        ($q_place[0]+$j == $q_places[$i][0] && $q_place[1]-$j == $q_places[$i][1]) ||
                        ($q_place[0]-$j == $q_places[$i][0] && $q_place[1]+$j == $q_places[$i][1]) ||
                        ($q_place[0]+$j == $q_places[$i][0] && $q_place[1]+$j == $q_places[$i][1])
                    )
                        $illegal_point = true;
                }
            }
        }
    }

    if(!$illegal_point)
    {
        echo str_pad(decoct($queens), 8, "0", STR_PAD_LEFT) . " is solvation! \n";
    }
    elseif($queens % 10000 == 0)
    {
        echo "Values processed - " . (number_format($queens/$max_queens*100, 2, '.', '')) . "% \n";
    }
    $queens++;
}
?>

Программа выдала 92 решения, что полностью соотносится с теорией.