Решение вариации задачи N-Queen для N <4 в Прологе? - PullRequest
Новая
       19

Решение вариации задачи N-Queen для N <4 в Прологе?

0 голосов
/ 07 декабря 2018

Мне нужно разрешить вариацию N-Queens, как указано в Wolfram

Максимальное количество ферзей, когда N = 2 или N = 3 - это N-1 королев, в противном случае -N, поэтому мне нужна помощь для реализации в Прологе для N <4. </p>

Например, для N = 2: 

?nqueens(2,Result).

Result = [2,empty]
Result = [empty,1]
Result = [empty,2]
Result = [1,empty]

, что означает 4 возможные конфигурации в таблице 2 * 2.Число в списке Результат указывает на строку, а позиция указывает на столбец.

Для N = 3: 

?nqueens(3,Result).

Result = [1,3, empty]
Result = [1,empty,2]
Result = [3,1,empty]
Result = [empty,1,3]
Result = [2,empty,1]
Result = [empty,3,1]
Result = [2,empty,3]
Result = [3,empty,2]

8 возможных конфигураций в таблице 3 * 3.

Здесь - стандартное решение для вариации задачи N-Queen (для N> = 4), оно не работает, когда N <4, и это моя проблема. </p>

Любойпомощь оценена.

РЕДАКТИРОВАНИЕ (ВОЗМОЖНОЕ РЕШЕНИЕ) Первый стабильный Я генерирую все комбинации, для N = 2 будет выглядеть так: 

permutInListN(List,N,Result) :- comb(N,List,Comb),permutation(Comb,Result).
comb(0,_,[]).
comb(N,[X|T],[X|Comb]) :-N>0,N1 is N-1,comb(N1,T,Comb).
comb(N,[_|T],Comb) :-N>0,comb(N,T,Comb).

?permutInListN([1,2,vacio],2,L).
%output
L = [1, 2]
L = [2, 1]
L = [1, empty]
L = [empty, 1]
L = [2, empty]
L = [empty, 2]

сбросить listResul, который не содержитпусто, потому что когда N = 2, возможная королева равна N-1 (только 1 ферзь), предикат для этого, используя member и setoff .. (тривиально), и решение для этого: 

%output solution
L = [1, empty]
L = [empty, 1]
L = [2, empty]
L = [empty, 2]

Nowдля N = 3, это точка, все ListResult для N = 3: 

?permutInListN([1,2,3,empty],3,L).
%output
L = [1, 2, 3]
L = [1, 3, 2]
L = [2, 1, 3]
L = [2, 3, 1]
L = [3, 1, 2]
L = [3, 2, 1]
L = [1, 2, empty]
L = [1, empty, 2]
L = [2, 1, empty]
L = [2, empty, 1]
L = [empty, 1, 2]
L = [empty, 2, 1]
L = [1, 3, empty]
L = [1, empty, 3]
L = [3, 1, empty]
L = [3, empty, 1]
L = [empty, 1, 3]
L = [empty, 3, 1]
L = [2, 3, empty]
L = [2, empty, 3]
L = [3, 2, empty]
L = [3, empty, 2]
L = [empty, 2, 3]
L = [empty, 3, 2]

отбрасывает listResul, который не содержит пустых, только 8 конфигураций для королев, которые не атакуют друг друга, действительны из вывода: 

%output
L = [1, 2, empty]
L = [1, empty, 2]
L = [2, 1, empty]
L = [2, empty, 1]
L = [empty, 1, 2]
L = [empty, 2, 1]
L = [1, 3, empty]
L = [1, empty, 3]
L = [3, 1, empty]
L = [3, empty, 1]
L = [empty, 1, 3]
L = [empty, 3, 1]
L = [2, 3, empty]
L = [2, empty, 3]
L = [3, 2, empty]
L = [3, empty, 2]
L = [empty, 2, 3]
L = [empty, 3, 2]

например, L = [1, пусто, 2] и L = [1,3, пусто], они действительны, и я тонкийИзмените алгоритм, который мог бы быть возможным решением:

, когда в первом столбце стоит ферзь, а в третьем столбце - другой, а между ними нет строки, его VALID ex: L = [1, пусто, 2] ---> [королева (первый столбец, первая строка), королева (3-й столбец, 2-я строка), _] не строка между ними

, когда королева следует за другой матрицей в следующем столбцеи между ними есть строка VALID, например: L = [1,3, пусто] ----> [queen (первый столбец, первый ряд), queen (2-й столбец, 3-й ряд), _] просто строка междуих

это работает для 8 конфигураций, есть идеи, как это реализовать ????????Надеюсь, я хорошо себя объяснил.

...