nqueen без връщане назад - алгоритъм

Може ли n кралица проблемът да бъде решен без връщане назад?

Аз се срещнах с много видове отговори на n кралица проблем, но всички те изискват връщане назад. Има ли начин за решаването му без връщане назад?

Отговори:

Да. Бихте могли да го насилвате чрез генериране на всички възможни табла и след това да тествате всеки.

Този подход обаче няма да се мащабира добре;

Моля, имайте предвид също, че Уикипедия статия изброява редица решения, включително "итеративен ремонт".

Генетичен алгоритъм, който развива най-доброторешението не би изисквало връщане назад, но това е различен начин за приближаване до проблема, отколкото алгоритъм за преминаване през графиката на пространственото пространство, което вашият въпрос изглежда предполага

Да. Уикипедия споменава някои от тях, включително и един, който се основава на определени детерминанти (за които сега съм любопитен, но не съм проследил). дословно:

Примерите по-горе могат да бъдат получени със следните формули. Нека (i, j) е квадрата в колона i и ред j на nx n шахматната дъска, k цяло число.

1. Ако n е равномерно и n ≠ 6k + 2, тогава дадени queens в (i, 2i) и (n / 2 + i, 2i - 1) за i = 1,2, ..., n / 2.
2. Ако n е равномерно и n ≠ 6k, тогава дадени queens (i 1 + (2i + n / 2 - 3 (mod n))) и n + 1 - i, n - (mod n))) за i = 1,2, ..., n / 2.
3. Ако n е странно, използвайте един от моделите по-горе за (n - 1) и добавете кралицата в (n, n).