Формулировка полного состояния начинается с установки на доску всех восьми ферзей и предусматривает их дальнейшее перемещение. В том и другом случае стоимость пути не представляет интереса, поскольку важно лишь достигнуть конечного состояния. Первая инкрементная формулировка, которая может применяться при осуществлении попыток решения этой задачи, приведена ниже.

•    Состояния. Состоянием является любое расположение ферзей на доске в количестве от 0 до 8.

•    Начальное состояние. Отсутствие ферзей на доске.

•    Функция определения преемника. Установка ферзя на любой пустой клетке.

•    Проверка цели. На доске находится восемь ферзей, и ни один из них не атакован.

В этой формулировке требуется проверить возможных последовательностей. В лучшей формулировке должно быть запрещено помещать ферзя на любую клетку, которая уже атакована, следующим образом.

•    Состояния. Состояниями являются расположения с п ферзями , по одному ферзю в каждой из находящихся слева п вертикалей, притом что ни один ферзь не нападает на другого.

•    Функция определения преемника. Установка ферзя на любой клетке в находящейся слева пустой вертикали таким образом, чтобы он не был атакован каким-либо другим ферзем.

Эта формулировка позволяет сократить пространство состояний задачи с восемью ферзями сдо 2 057, и поиск решений значительно упрощается. С другой стороны, для 100 ферзей первоначальная формулировка определяет приблизительно состояний, а улучшенная формулировка — около состояний. Это — колоссальное сокращение, но улучшенное пространство состояний все еще слишком велико для того, чтобы с ним могли справиться алгоритмы, рассматриваемые в данной главе. В главе 4 описана формулировка полного состояния, а в главе 5 приведен простой алгоритм, который позволяет легко решить задачу даже с миллионом ферзей.