-----------PERMUTATION/MEMBER/CONCATENATION---------------------
% ---------------------------------------------------------------------------------------------------------
% Permuatation      input = perm([a,b,c,d],X).
perm(List,[H|Perm]):-delete(H,List,Rest),perm(Rest,Perm).
perm([],[]).

delete(X,[X|T],T).
delete(X,[H|T],[H|NT]):-delete(X,T,NT).

% ---------------------------------------------------------------------------------------------------------
% Memeber       input = list_member(b,[a,b,c]).
list_member(X,[X|_]).
list_member(X,[_|TAIL]) :- list_member(X,TAIL).

% ---------------------------------------------------------------------------------------------------------
% Concatenation         input = list_concat([1,2],[a,b,c],NewList).
list_concat([],L,L).
list_concat([X1|L1],L2,[X1|L3]) :- list_concat(L1,L2,L3).


----------------------INTERSECTION UNION----------------------------------
% ---------------------------------------------------------------------------------------------------------
% Union      input = list_union([a,b,c,d,e],[a,e,i,o,u],L3).
list_member(X,[X|_]).
list_member(X,[_|TAIL]) :- list_member(X,TAIL).

list_union([X|Y],Z,W) :- list_member(X,Z),list_union(Y,Z,W).
list_union([X|Y],Z,[X|W]) :- \+ list_member(X,Z), list_union(Y,Z,W).
list_union([],Z,Z).

% ---------------------------------------------------------------------------------------------------------
% Intersection      input = list_intersect([a,b,c,d,e],[],L3).
list_member(X,[X|_]).
list_member(X,[_|TAIL]) :- list_member(X,TAIL).

list_intersect([X|Y],Z,[X|W]) :-
   list_member(X,Z), list_intersect(Y,Z,W).
list_intersect([X|Y],Z,W) :-
   \+ list_member(X,Z), list_intersect(Y,Z,W).
list_intersect([],Z,[]).

---------------------------------MONKEY BANANA--------------------------------------------------------
% ---------------------------------------------------------------------------------------------------------
% Union      input = list_union([a,b,c,d,e],[a,e,i,o,u],L3).
list_member(X,[X|_]).
list_member(X,[_|TAIL]) :- list_member(X,TAIL).

list_union([X|Y],Z,W) :- list_member(X,Z),list_union(Y,Z,W).
list_union([X|Y],Z,[X|W]) :- \+ list_member(X,Z), list_union(Y,Z,W).
list_union([],Z,Z).

% ---------------------------------------------------------------------------------------------------------
% Intersection      input = list_intersect([a,b,c,d,e],[],L3).
list_member(X,[X|_]).
list_member(X,[_|TAIL]) :- list_member(X,TAIL).

list_intersect([X|Y],Z,[X|W]) :-
   list_member(X,Z), list_intersect(Y,Z,W).
list_intersect([X|Y],Z,W) :-
   \+ list_member(X,Z), list_intersect(Y,Z,W).
list_intersect([],Z,[]).



---------------------------------------------BFS------------------------------------------------------------------
from collections import defaultdict
graph = defaultdict(list)

def addEdge(u,v):
    graph[u].append(v)
    graph[v].append(u)

def BFS(source):
    open = []
    closed = []
    open.append(source)
    while len(open) > 0:
        node = open[0]
        print(node,sep=" ")
        closed.append(node)
        open.pop(0)
        # print(top)
        neighbours = graph[node]

        for neighbour in neighbours:
            if neighbour not in open and neighbour not in closed:
                # open = open.append(neighbour)
                open = open + [neighbour]


addEdge(1,2)
addEdge(1,3)
addEdge(2,4)
addEdge(2,5)
addEdge(3,6)
addEdge(3,7)
BFS(1)


--------------------------------------------DFS-----------------------------------------------------
from collections import defaultdict

graph = defaultdict(list)

def addEdge(u,v):
    graph[u].append(v)
    graph[v].append(u)

def BFS(source):
    open = []
    closed = []
    open.append(source)
    while len(open) > 0:
        node = open[0]
        print(node,sep=" ")
        closed.append(node)
        open.pop(0)
        # print(top)
        neighbours = graph[node]

        for neighbour in neighbours:
            if neighbour not in open and neighbour not in closed:
                # open = open.append(neighbour)
                open = [neighbour] + open

addEdge(1,2)
addEdge(1,3)
addEdge(2,4)
addEdge(2,5)
addEdge(3,6)
addEdge(3,7)
BFS(1)

----------------------------------------------------N-Queens--------------------------------------------------------------------
def isSafe(board,row,col):
    for i in range(col):
        if board[row][i] == 1:
            return False

    for i,j in zip(range(row,-1,-1),range(col,-1,-1)):
        if board[i][j] == 1:
            return False


    for i,j in zip(range(row,N),range(col,-1,-1)):
        if board[i][j] == 1:
            return False

    return True

def solve(board,col):
    if col >= N:
        return True

    for row in range(N):
        if isSafe(board,row,col):
            board[row][col] = 1

            if solve(board,col+1):
                return True

            board[row][col] = 0

    return False

N = 3
board = [[0 for _ in range(N)] for _ in range(N)]
if solve(board,0):
    for row in board:
        print(row)
else:
    print("Cant place "+ str(N) + " queens on NxN matrix")