Решение задачи Головоломка про ферзей с Acmp

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

Вася недавно начал заниматься шахматами и где-то прочел головоломку, в которой нужно было расставить максимальное количество ферзей на доске 8х8 так, чтобы хотя бы одно поле оказалось небитым. Эта задача легко решается для доски 3х3, т.к. понятно, что более двух ферзей расставить таким образом на ней невозможно.

Помогите Васе решить эту задачу для доски N×N.