как оптимизировать этот код, чтобы он выполнялся быстрее - PullRequest
Новая
       62

как оптимизировать этот код, чтобы он выполнялся быстрее

0 голосов
/ 01 июля 2019

Я пытаюсь закодировать проблему "Мирных армий королев". Цель состоит в том, чтобы поставить максимально возможное равное нет черно-белых королев на шахматной доске, чтобы они не атаковали друг друга, но могли атаковать одним цветом.

Я реализовал и попробовал следующий код на SICStus 4.3.2. Проблема с этим кодом состоит в том, что он выполняется быстрее до размера шахматной доски 8, но тогда это занимает много времени для N> 8. Здесь N - Максимум, равный нет. королев (черный и белый) S - матрица для отображения позиций чёрной и белой королев на шахматной доске. 7 - размер шахматной доски.

так что запрос, 

| ?- queens(S,7,N).

S = [[0,-1,-1,-1,0,0,0],[0,0,0,0,0,1,1],[-1,0,0,-1,0,0,0],[-1,-1,0,0,0,0,0],[0,0,0,0,1,0|...],[0,0,0,0,1|...],[0,0,0,0|...]],

N = 7 ?

yes

но это займет много времени для 

| ?- queens(S,10,N).

поэтому вопрос в том, как оптимизировать этот код, чтобы он выполнялся быстрее?

-1 -> Черная Королева

0 -> Свободное место

1 -> Белая Королева

Мат -> матрица для отображения позиций чёрной и белой королев на шахматной доске Дим -> Размер или Размер шахматной доски N -> Максимально возможное равное количество королев из черно-белой армии королев, размещенных на шахматной доске 

:-use_module(library(clpfd)),use_module(library(lists)).

queens(Mat,Dim,N):-
    Dim > 2,

    Ls is Dim*Dim,
    length(Sol, Ls), 
    N #> 0, N #< Ls/4,

    domain(Sol, -1,1),
    list_to_matrix(Sol, Dim, Mat),

    row(Mat, 1, Row1),
    domain(Row1, -1, 0),

    column(Mat, 1, Col1), 
    domain(Col1, -1, 0),

    row(Mat, Dim, RowDim), 
    domain(RowDim, 0, 1),

    column(Mat, Dim, ColDim), 
    domain(ColDim, 0, 1),

    diag(Mat, Dimiag, 0, Dim),
    domain(Dimiag, 0, 1),

    nth1(Dim, RowDim, LRow), 
    LRow is 1,

    global_cardinality(Sol, [-1-N, 1-N, 0-_]),

    check_rows(Mat), 
    transpose(Mat, B),
    check_rows(B),

    diag_to_list(Mat, X1, Dim), 
    check_rows(X1),

    matrix_reverse(Mat, C),

    diag_to_list(C, X2, Dim), 
    check_rows(X2),

    labeling([maximize(N), ffc],Sol).
...