MAX, MIN = 1000, -1000

def minimax(depth, nodeIndex, maximizingPlayer,
			values, alpha, beta):
	if depth == 3:
		return values[nodeIndex]
	if maximizingPlayer:
		best = MIN
		for i in range(0, 2):
			val = minimax(depth + 1, nodeIndex * 2 + i,
						False, values, alpha, beta)
			best = max(best, val)
			alpha = max(alpha, best)
			if beta <= alpha:
				break
		return best
	else:
		best = MAX
		for i in range(0, 2):
			val = minimax(depth + 1, nodeIndex * 2 + i,
							True, values, alpha, beta)
			best = min(best, val)
			beta = min(beta, best)
			if beta <= alpha:
				break
		return best
if __name__ == "__main__":

	values = [3, 5, 6, 9, 1, 2, 0, -1]
	print("The optimal value is :", minimax(0, 0, True, values, MIN, MAX))
	
TSP



from sys import maxsize
from itertools import permutations
V = 4
def travellingSalesmanProblem(graph, s):
	vertex = []
	for i in range(V):
		if i != s:
		vertex.append(i)
	min_path = maxsize
	next_permutation=permutations(vertex)
	for i in next_permutation:
		current_pathweight = 0
		k = s
		for j in i:
		current_pathweight += graph[k][j]
		k = j
		current_pathweight += graph[k][s]
		min_path = min(min_path, current_pathweight)	
	            return min_path
if __name__ == "__main__":
graph = [[0, 10, 15, 20], [10, 0, 35, 25],
[15, 35, 0, 30], [20, 25, 30,0]]
s = 0
print(travellingSalesmanProblem(graph, s))

CONSTRAINTS SATISFACTION


colors = ['Red', 'Blue', 'Green', 'Yellow', 'Black']

states = ['Andhra', 'Karnataka', 'TamilNadu', 'Kerala']

neighbors = {}
neighbors['Andhra'] = ['Karnataka', 'TamilNadu']
neighbors['Karnataka'] = ['Andhra', 'TamilNadu', 'Kerala']
neighbors['TamilNadu'] = ['Andhra', 'Karnataka', 'Kerala']
neighbors['Kerala'] = ['Karnataka', 'TamilNadu']

colors_of_states = {}

def promising(state, color):
    for neighbor in neighbors.get(state): 
        color_of_neighbor = colors_of_states.get(neighbor)
        if color_of_neighbor == color:
            return False

    return True

def get_color_for_state(state):
    for color in colors:
        if promising(state, color):
            return color

def main():
    for state in states:
        colors_of_states[state] = get_color_for_state(state)

    print (colors_of_states)


main()


TIC TAC TOE

turn=0
arr=[-1,0,0,0,0,0,0,0,0,0]
def print_turn():
    global turn
    if turn % 2 == 0:
        print("Turn X")
    else:
        print("Turn O")
    print("Choose available choice")
    read()
    
def read():
    global turn
    global arr
    try:
        inp = int(input())
        if 0<inp<10:
            if arr[inp] == 0:
                if turn % 2==0:
                    arr[inp]=2
                else:
                    arr[inp]=5
                turn=turn+1
            else:
                print("Invalid choice(Already Occupied)")
        else:
            print("Invalid choice(must be between 0 and 10)");
        printTable()
    except ValueError:
        print("Invalid choice(must be between 0 and 10)\n\n")
        print_turn()
 
def checkWIN():
    if    (arr[1]==arr[2]==arr[3]==2) or (arr[4]==arr[5]==arr[6]==2) or (arr[7]==arr[8]==arr[9]==2) or (arr[1]==arr[4]==arr[7]==2) or (arr[2]==arr[5]==arr[8]==2) or (arr[3]==arr[6]==arr[9]==2) or (arr[1]==arr[5]==arr[9]==2) or (arr[3]==arr[5]==arr[7]==2):
        print("Player X won")
    elif (arr[1]==arr[2]==arr[3]==5) or (arr[4]==arr[5]==arr[6]==5) or (arr[7]==arr[8]==arr[9]==5) or (arr[1]==arr[4]==arr[7]==5) or (arr[2]==arr[5]==arr[8]==5) or (arr[3]==arr[6]==arr[9]==5) or (arr[1]==arr[5]==arr[9]==5) or (arr[3]==arr[5]==arr[7]==5):
        print("Player O won")
    else:
        if(turn != 9):
            print_turn()
        else:
            print("Match-Draw")
def printTable():
    for i in range(1,10):
        print("|",end="")
        if arr[i]==2:
            print(" X ",end="")
        elif arr[i]==5:
            print(" O ",end="")
        else:
            print("   ",end="")
        if i % 3 ==0:
            print("|")
    print("\n\n")
    checkWIN()
print ("\n\n\t\t\tTIC-TAC-TOE game)\n")
print("\t\t\t\t|  1  |  2  |  3  |")
print("\t\t\t\t|  4  |  5  |  6  |")
print("\t\t\t\t|  7  |  8  |  9  |\n\n")
print_turn()


BFS:
graph = {
  '5' : ['3','7'],
  '3' : ['2', '4'],
  '7' : ['8'],
  '2' : [],
  '4' : ['8'],
  '8' : []
}
visited = [] 
queue = [] 
def bfs(visited, graph, node):
    visited.append(node) 
    queue.append(node) 
    while queue: 
        m = queue.pop(0) 
        print(m, end = " ") 
        for neighbour in graph[m]: 
            if neighbour not in visited: 
                visited.append(neighbour) 
                queue.append(neighbour)
print("The following in the Breadth First Search")
bfs(visited,graph,'5');

Output:
The following in the Breadth First Search
5 3 7 2 4 8 

DFS:
graph = {
  '5' : ['3','7'],
  '3' : ['2', '4'],
  '7' : ['8'],
  '2' : [],
  '4' : ['8'],
  '8' : []
}
def dfs(visited, graph, node):  #
    if node not in visited:
        print (node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)
print("Following is the Depth-First Search")
dfs(visited, graph, '5')


WATER JUG



jug1=int(input("enter capacity of 1st Jug\n"))
jug2=int(input("enter Capacity of 2nd Jug\n"))
t1=int(input("enter goal state of first Jug\n"))
t2=int(input("enter goal state of second Jug\n"))
def water_jug(cap1,cap2):
    print("\n",cap1,cap2)
    if (cap1==t1 and cap2==t2) or (cap1==t2 and cap2==t1):
        return
    elif cap2==jug2:
        water_jug(cap1,0)
    elif cap1!=0:
        if cap1 <= jug2-cap2:
            water_jug(0,cap1+cap2)
        elif cap1 > jug2-cap2:
            water_jug(cap1-(jug2-cap2), cap2+(jug2-cap2))
    else:
        water_jug(jug1,cap2)
water_jug(0,0)