N-QUEEN PROBLEM :

N=int(input("Enter the number of queens: "))

print(f"You entered: {N}")

b=[[0]*N for _ in range(N)]

def ok(r,c):

return all(not b[r][i] and not b[i][c] for i in range(N)) and \

all(not b[i][j] for i in range(N) for j in range(N)

if i+j==r+c or i-j==r-c)

def f(n):

if n==0:return 1

for i in range(N):

for j in range(N):

if ok(i,j):

b[i][j]=1

if f(n-1):return 1

b[i][j]=0

f(N)

for r in b:print(r)
DFS PATH :

class Graph:

def __init__(self): self.g={}

def add_edge(self,a,b):

[Link](a,[]).append(b)

[Link](b,[]).append(a)

def dfs(self,s,t,v=None):

v=v or set()

print(s,end=" -> ")

if s==t:return True

[Link](s)

return any(n not in v and [Link](n,t,v) for n in [Link](s,[]))

g=Graph()

g.add_edge('A','B'); g.add_edge('A','C')

g.add_edge('B','D'); g.add_edge('C','E')

g.add_edge('D','F'); g.add_edge('E','F')

print("DFS Path:")

[Link]('A','F')
BFS PATH :

from collections import deque

class Graph:

def __init__(self, directed=True):

[Link] = {}

[Link] = directed

def add_edge(self, node1, node2, reversed=False):

try:

neighbors = [Link][node1]

except KeyError:

neighbors = []

if node2 not in neighbors: # Avoid duplicates

[Link](node2)

[Link][node1] = neighbors

if not [Link] and not reversed:

self.add_edge(node2, node1, True)

def neighbors(self, node):

try:

return [Link][node]

except KeyError:

return []

def breadth_first_search(self, start, goal):

found = False

fringe = deque([start])

visited = set([start])

came_from = {start: None}

print('{:11s} {}'.format('Expand Node', 'Fringe'))

print()

print('{:11s}|{}'.format('-', start))

while not found and len(fringe):

current = [Link]()
 print('{:11s}'.format(current), end=' | ')

if current == goal:

found = True

break

for node in [Link](current):

if node not in visited:

[Link](node)

[Link](node)

came_from[node] = current

print(', '.join(fringe))

if found:

print()

return came_from

else:

print('No path from {} to {}'.format(start, goal))

return None

@staticmethod

def print_path(came_from, goal):

parent = came_from[goal]

if parent:

Graph.print_path(came_from, parent)

print(' => ', end='')

print(goal, end='')

def __str__(self):

return str([Link])

# Create the graph

graph = Graph(directed=False)

graph.add_edge('A', 'B')

graph.add_edge('A', 'S')

graph.add_edge('S', 'G')

graph.add_edge('S', 'C')
graph.add_edge('C', 'F')

graph.add_edge('G', 'F')

graph.add_edge('C', 'D')

graph.add_edge('C', 'E')

graph.add_edge('E', 'H')

graph.add_edge('G', 'H')

# Perform BFS

start, goal = 'A', 'H'

traced_path = graph.breadth_first_search(start, goal)

# Print the path if found

if traced_path:

print('Path: ', end='')

Graph.print_path(traced_path, goal)

print()
Propositional model :

import re

# ---------------- Literal Class ----------------

class Literal:

# name : literal name

# sign : True = positive, False = negative

def __init__(self, name, sign=True):

[Link] = str(name)

[Link] = sign

def __neg__(self):

# returns opposite sign literal

return Literal([Link], False)

def __str__(self):

return str([Link])

def __repr__(self):

if [Link]:

return "%r" % str(self.__str__())

else:

return "%r" % str("-" + self.__str__())

# ---------------- CNF Conversion ----------------

def CNFConvert(KB):

storage = []

for i in KB:

i = list(i)

[Link](i)

return storage

# ---------------- Variable Set ----------------

def VariableSet(KB):

KB = eval(CNFConvert(KB).__str__())

storage = []
 for obj in KB:

for item in obj:

if item[0] == '-' and item[1:] not in storage:

[Link](str(item[1:]))

elif item not in storage and item[0] != '-':

[Link](str(item))

return storage

# ---------------- Negative Literal ----------------

def Negativeofx(x):

check = [Link]("-", str(x))

if check:

return str(x[1:])

else:

return "-" + str(x)

# ---------------- Pick Literal ----------------

def pickX(literals, varList):

for x in varList:

if x not in literals:

break

return x

# ---------------- Split Functions ----------------

def splitFalseLiterals(cnf, x):

holder = []

for item in cnf:

if x in item:

[Link](x)

[Link](item)

return holder

def splitTrueLiteral(cnf, x):

holder = []

for item in cnf:

continue

else:

[Link](item)

return holder

# ---------------- Unit Resolution ----------------

def unitResolution(clauses):

literalholder = {}

i=0

while i < len(clauses):

newClauses = []

clause = clauses[i]

if len(clause) == 1:

literal = str(clause[0])

pattern = [Link]("-", literal)

if pattern:

nx = literal[1:]

literalholder[nx] = False

else:

nx = "-" + literal

literalholder[literal] = True

for item in clauses:

if item != clauses[i]:

if nx in item:

[Link](nx)

[Link](item)

i=0

clauses = newClauses

else:

i += 1

return literalholder, clauses

def dpll(clauses, varList):

literals, cnf = unitResolution(clauses)

if cnf == []:

return literals

elif [] in cnf:

return "notsatisfiable"

else:

while True:

x = pickX(literals, varList)

x = str(x)

nx = Negativeofx(x)

ncnf = splitTrueLiteral(cnf, x)

ncnf = splitFalseLiterals(ncnf, nx)

if ncnf == cnf:

[Link](x)

else:

break

# True branch

case1 = dpll(ncnf, varList)

if case1 != "notsatisfiable":

copy = [Link]()

[Link](literals)

[Link]({x: True})

return copy

# False branch

case1 = dpll(ncnf, varList)

if case1:

copy = [Link]()
 [Link](literals)

[Link]({x: False})

return copy

else:

return "notsatisfiable"

# ---------------- Final Output ----------------

def DPLL(KB):

KB = eval(CNFConvert(KB).__str__())

varList = VariableSet(KB)

result = dpll(KB, varList)

if result == "notsatisfiable":

return False

else:

for i in varList:

if i in result and result[i] is True:

result[i] = 'true'

elif i in result and result[i] is False:

result[i] = 'false'

else:

result[i] = 'free'

return [True, result]

# ---------------- Example ----------------

A = Literal('A')

B = Literal('B')

C = Literal('C')

D = Literal('D')

KB = [{A, B}, {A, -C}, {-A, B, D}]

print(DPLL(KB))