AI Full Practical Code (Missionaries and Cannibals problem, implement depth first search algorithm, tic-tac-toe game)
1 (A): Write a program to implement depth first search algorithm.
// PYTHON CODE//
graph1= {'A':set(['B','C']),
'B':set(['A','D','E']),
'C':set(['A','F']),
'D':set(['B']),
'E':set(['B','F']),
'F':set(['C','E'])
}
def dfs(graph,node,visited):
if node not in visited:
visited.append(node)
for n in graph[node]:
dfs(graph,n,visited)
return visited
visited= dfs(graph1,'A',[])
print(visited)
************************************END************************************
************************************END************************************
1(b): Write a program to implement breadth first search algorithm.
//PYTHON CODE//
graph = {'A': ['B', 'C', 'E'],
'B': ['A','D', 'E'],
'C': ['A', 'F', 'G'],
'D': ['B'],
'E': ['A', 'B','D'],
'F': ['C'],
'G': ['C']}
def bfs_connected_component(graph, start):
explored = []
queue = [start]
levels = {}
levels[start]= 0
visited= [start]
while queue:
node = queue.pop(0)
explored.append(node)
neighbours = graph[node]
for neighbour in neighbours:
if neighbour not in visited:
queue.append(neighbour)
visited.append(neighbour)
levels[neighbour]= levels[node]+1
print(levels)
return explored
ans = bfs_connected_component(graph,'A')
print(ans)
**************************************END*********************************
**************************************END*********************************
2(a): Write a program to simulate 4 Queen / N-queen problem.
//PYTHON CODE//
class QueenChessBoard:
def __init__(self, size):
self.size = size
self.columns = []
def place_in_next_row(self, column):
self.columns.append(column)
def remove_in_current_row(self):
return self.columns.pop()
def is_this_column_safe_in_next_row(self, column):
row = len(self.columns)
for queen_column in self.columns:
if column == queen_column:
return False
for queen_row, queen_column in enumerate(self.columns):
if queen_column - queen_row == column - row:
return False
for queen_row, queen_column in enumerate(self.columns):
if ((self.size - queen_column) - queen_row
== (self.size - column) - row):
return False
return True
def display(self):
for row in range(self.size):
for column in range(self.size):
if column == self.columns[row]:
print('Q', end=' ')
else:
print('.', end=' ')
print()
def solve_queen(size):
"""Display a chessboard for each possible configuration of placing n queens
on an n x n chessboard and print the number of such configurations."""
board = QueenChessBoard(size)
number_of_solutions = 0
row = 0
column = 0
while True:
while column < size:
if board.is_this_column_safe_in_next_row(column):
board.place_in_next_row(column)
row += 1
column = 0
break
else:
column += 1
if (column == size or row == size):
if row == size:
board.display()
print()
number_of_solutions += 1
board.remove_in_current_row()
row -= 1
try:
prev_column = board.remove_in_current_row()
except IndexError:
break
row -= 1
column = 1 + prev_column
print('Number of solutions:', number_of_solutions)
n = int(input('Enter n: '))
solve_queen(n)
*************************************END*****************************
*************************************END*****************************
2(b): Write a program to solve tower of hanoi problem.
//PYTHON CODE://
def TowerOfHanoi(n , from_rod, to_rod, aux_rod):
if n == 1:
print( "Move disk 1 from rod",from_rod,"to rod",to_rod )
return
TowerOfHanoi(n-1, from_rod, aux_rod, to_rod)
print ("Move disk",n,"from rod",from_rod,"to rod",to_rod )
TowerOfHanoi(n-1, aux_rod, to_rod, from_rod)
n = 4
TowerOfHanoi(n,'A','C', 'B')
*************************************END*****************************
*************************************END*****************************
3(a): Write a program to implement alpha beta search.
//PYTHON CODE://
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))
***************************************END*************************************
***************************************END*************************************
3(b): Write a program for hill climbing problem.
//JAVA CODE://
import java.util.Scanner;
public class hillclimbing {
public static void main(String[] args) {
int n,i,j;
Scanner sc=new Scanner(System.in);
System.out.println("Enter number of nodes in graph");
n=sc.nextInt();
int[][] graph=new int[n][n];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
graph[i][j]=0;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
System.out.println("Is "+i+" is connected to "+ j);
graph[i][j]=sc.nextInt();
}
}
System.out.println("The adjacency matrix is:");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{ System.out.print(graph[i][j]+ "\t");
}
System.out.println();
}
}
}
***************************************END*************************************
***************************************END*************************************
Practical-4(a): Write a program to implement A* algorithm.
Step1) Set path in cmd -> cd C:\Users\DELL\AppData\Local\Programs\Python\Python37-32\Scripts
Step2) pip install simpleai
Step3) pip install pydot flask
Step4) Run the python code
//PYTHON CODE://
from simpleai.search import SearchProblem, astar
GOAL = 'HELLO WORLD'
class HelloProblem(SearchProblem):
def actions(self, state):
if len(state) < len(GOAL):
return list(' ABCDEFGHIJKLMNOPQRSTUVWXYZ')
else:
return []
def result(self, state, action):
return state + action
def is_goal(self, state):
return state == GOAL
def heuristic(self, state):
wrong = sum([1 if state[i] != GOAL[i] else 0
for i in range(len(state))])
missing = len(GOAL) - len(state)
return wrong + missing
problem = HelloProblem(initial_state='')
result = astar(problem)
print(result.state)
print(result.path())
***************END*****************
***************END*****************
Practical-5(A): Write a Program to Solve water jug problem.
*****PYTHON CODE:******
def pour(jug1,jug2):
max1,max2,fill=5,7,4
print("%d\t%d"%(jug1,jug2))
if jug2 is fill:
return
elif jug2 is max2:
pour(0,jug1)
elif jug1 !=0 and jug2 is 0:
pour(0,jug1)
elif jug1 is fill:
pour(jug1,0)
elif jug1<max1:
pour(max1,jug2)
elif jug1<(max2-jug2):
pour(0,(jug1+jug2))
else:
pour(jug1-(max2-jug2),(max2-jug2)+jug2)
print("JUG1\tJUG2")
pour(0,0)
**************************END************************************
**************************END************************************
Practical-5(b) : Design the simulation of tic-tac-toe game.
*****JAVA CODE:******
import java.util.Scanner;
/**
* Tic-Tac-Toe: Two-player console, non-graphics, non-OO version.
* All variables/methods are declared as static (belong to the class)
* in the non-OO version.
*/
public class TTTConsoleNonOO2P {
// Name-constants to represent the seeds and cell contents
public static final int EMPTY = 0;
public static final int CROSS = 1;
public static final int NOUGHT = 2;
// Name-constants to represent the various states of the game
public static final int PLAYING = 0;
public static final int DRAW = 1;
public static final int CROSS_WON = 2;
public static final int NOUGHT_WON = 3;
// The game board and the game status
public static final int ROWS = 3, COLS = 3; // number of rows and columns
public static int[][] board = new int[ROWS][COLS]; // game board in 2D array
// containing (EMPTY, CROSS, NOUGHT)
public static int currentState; // the current state of the game
// (PLAYING, DRAW, CROSS_WON, NOUGHT_WON)
public static int currentPlayer; // the current player (CROSS or NOUGHT)
public static int currntRow, currentCol; // current seed's row and column
public static Scanner in = new Scanner(System.in); // the input Scanner
/** The entry main method (the program starts here) */
public static void main(String[] args) {
// Initialize the game-board and current status
initGame();
// Play the game once
do {
playerMove(currentPlayer); // update currentRow and currentCol
updateGame(currentPlayer, currntRow, currentCol); // update currentState
printBoard();
// Print message if game-over
if (currentState == CROSS_WON) {
System.out.println("'X' won! Bye!");
} else if (currentState == NOUGHT_WON) {
System.out.println("'O' won! Bye!");
} else if (currentState == DRAW) {
System.out.println("It's a Draw! Bye!");
}
// Switch player
currentPlayer = (currentPlayer == CROSS) ? NOUGHT : CROSS;
} while (currentState == PLAYING); // repeat if not game-over
}
/** Initialize the game-board contents and the current states */
public static void initGame() {
for (int row = 0; row < ROWS; ++row) {
for (int col = 0; col < COLS; ++col) {
board[row][col] = EMPTY; // all cells empty
}
}
currentState = PLAYING; // ready to play
currentPlayer = CROSS; // cross plays first
}
/** Player with the "theSeed" makes one move, with input validation.
Update global variables "currentRow" and "currentCol". */
public static void playerMove(int theSeed) {
boolean validInput = false; // for input validation
do {
if (theSeed == CROSS) {
System.out.print("Player 'X', enter your move (row[1-3] column[1-3]): ");
} else {
System.out.print("Player 'O', enter your move (row[1-3] column[1-3]): ");
}
int row = in.nextInt() - 1; // array index starts at 0 instead of 1
int col = in.nextInt() - 1;
if (row >= 0 && row < ROWS && col >= 0 && col < COLS && board[row][col] == EMPTY) {
currntRow = row;
currentCol = col;
board[currntRow][currentCol] = theSeed; // update game-board content
validInput = true; // input okay, exit loop
} else {
System.out.println("This move at (" + (row + 1) + "," + (col + 1)
+ ") is not valid. Try again...");
}
} while (!validInput); // repeat until input is valid
}
/** Update the "currentState" after the player with "theSeed" has placed on
(currentRow, currentCol). */
public static void updateGame(int theSeed, int currentRow, int currentCol) {
if (hasWon(theSeed, currentRow, currentCol)) { // check if winning move
currentState = (theSeed == CROSS) ? CROSS_WON : NOUGHT_WON;
} else if (isDraw()) { // check for draw
currentState = DRAW;
}
// Otherwise, no change to currentState (still PLAYING).
}
/** Return true if it is a draw (no more empty cell) */
// TODO: Shall declare draw if no player can "possibly" win
public static boolean isDraw() {
for (int row = 0; row < ROWS; ++row) {
for (int col = 0; col < COLS; ++col) {
if (board[row][col] == EMPTY) {
return false; // an empty cell found, not draw, exit
}
}
}
return true; // no empty cell, it's a draw
}
/** Return true if the player with "theSeed" has won after placing at
(currentRow, currentCol) */
public static boolean hasWon(int theSeed, int currentRow, int currentCol) {
return (board[currentRow][0] == theSeed // 3-in-the-row
&& board[currentRow][1] == theSeed
&& board[currentRow][2] == theSeed
|| board[0][currentCol] == theSeed // 3-in-the-column
&& board[1][currentCol] == theSeed
&& board[2][currentCol] == theSeed
|| currentRow == currentCol // 3-in-the-diagonal
&& board[0][0] == theSeed
&& board[1][1] == theSeed
&& board[2][2] == theSeed
|| currentRow + currentCol == 2 // 3-in-the-opposite-diagonal
&& board[0][2] == theSeed
&& board[1][1] == theSeed
&& board[2][0] == theSeed);
}
/** Print the game board */
public static void printBoard() {
for (int row = 0; row < ROWS; ++row) {
for (int col = 0; col < COLS; ++col) {
printCell(board[row][col]); // print each of the cells
if (col != COLS - 1) {
System.out.print("|"); // print vertical partition
}
}
System.out.println();
if (row != ROWS - 1) {
System.out.println("-----------"); // print horizontal partition
}
}
System.out.println();
}
/** Print a cell with the specified "content" */
public static void printCell(int content) {
switch (content) {
case EMPTY: System.out.print(" "); break;
case NOUGHT: System.out.print(" O "); break;
case CROSS: System.out.print(" X "); break;
}
}
}
****************************END******************************************
****************************END******************************************
Practical-6(a): Write a program to solve Missionaries and Cannibals problem.
****Python Code:*****
#! /usr/bin/env python
"""
This is a solution to the Missionaries and Cannibalis problem.
Uses a breadth first search and the representation as described
in the lecture. Call without any arguments
$ ./search.py
to search for a solution from the initial state (3,3,1).
"""
from copy import deepcopy
from collections import deque
import sys
import time
# Within this object, the state is represented as described in the lecture:
# The triple (m,c,b) holds the number of missionaries, cannibals and boats
# on the original shore.
class State(object):
def __init__(self, missionaries, cannibals, boats):
self.missionaries = missionaries
self.cannibals = cannibals
self.boats = boats
def successors(self):
if self.boats == 1:
sgn = -1
direction = "from the original shore to the new shore"
else:
sgn = 1
direction = "back from the new shore to the original shore"
for m in range(3):
for c in range(3):
newState = State(self.missionaries+sgn*m, self.cannibals+sgn*c, self.boats+sgn*1);
if m+c >= 1 and m+c <= 2 and newState.isValid(): # check whether action and resulting state are valid
action = "take %d missionaries and %d cannibals %s. %r" % ( m, c, direction, newState)
yield action, newState
def isValid(self):
# first check the obvious
if self.missionaries < 0 or self.cannibals < 0 or self.missionaries > 3 or self.cannibals > 3 or (self.boats != 0 and self.boats != 1):
return False
# then check whether missionaries outnumbered by cannibals
if self.cannibals > self.missionaries and self.missionaries > 0: # more cannibals then missionaries on original shore
return False
if self.cannibals < self.missionaries and self.missionaries < 3: # more cannibals then missionaries on other shore
return False
return True
def is_goal_state(self):
return self.cannibals == 0 and self.missionaries == 0 and self.boats == 0
def __repr__(self):
return "< State (%d, %d, %d) >" % (self.missionaries, self.cannibals, self.boats)
class Node(object):
def __init__(self, parent_node, state, action, depth):
self.parent_node = parent_node
self.state = state
self.action = action
self.depth = depth
def expand(self):
for (action, succ_state) in self.state.successors():
succ_node = Node(
parent_node=self,
state=succ_state,
action=action,
depth=self.depth + 1)
yield succ_node
def extract_solution(self):
solution = []
node = self
while node.parent_node is not None:
solution.append(node.action)
node = node.parent_node
solution.reverse()
return solution
def breadth_first_tree_search(initial_state):
initial_node = Node(
parent_node=None,
state=initial_state,
action=None,
depth=0)
fifo = deque([initial_node])
num_expansions = 0
max_depth = -1
while True:
if not fifo:
print ("%d expansions" % num_expansions)
return None
node = fifo.popleft()
if node.depth > max_depth:
max_depth = node.depth
print ("[depth = %d] %.2fs" % (max_depth, time.clock()))
if node.state.is_goal_state():
print ("%d expansions" % num_expansions)
solution = node.extract_solution()
return solution
num_expansions += 1
fifo.extend(node.expand())
def usage():
print >> sys.stderr, "usage:"
print >> sys.stderr, " %s" % sys.argv[0]
raise SystemExit(2)
def main():
initial_state = State(3,3,1)
solution = breadth_first_tree_search(initial_state)
if solution is None:
print ("no solution")
else:
print ("solution (%d steps):" % len(solution))
for step in solution:
print ("%s" % step)
print ("elapsed time: %.2fs" % time.clock())
if __name__ == "__main__":
main()
********************************END******************************
********************************END******************************
Practical-6(b): Design an application to simulate number Puzzle problem.
***PYTHON CODE:
t=0
lis=[
1,2,3,
4,5,6,
7,t,8
]
print (lis)
def sort(i):
for i in l:
if l[i]==0:
move=int(input("Enter 1 to move back or ) to move ahead"))
if move==1:
temp=l[i-1]
l[i-1]=l[i]
l[i]=temp
print (l)
sort(i)
try:
if move==0:
if i!=l[-1]:
temp=l[i+1]
l[i+1]=l[i]
l[i]=temp
print (l)
except:
print ("Error! Cannot Move Ahead, Last Index")
sort(l)
if move==9:
break
sort(lis)
******************************END********************************
******************************END********************************
Practical-7(a): Write a program to shuffle Deck of cards.
****PYTHON CODE****
# import modules
import itertools, random
# make a deck of cards
deck = list(itertools.product(range(1,14),['Spade','Heart','Diamond','Club']))
# shuffle the cards
random.shuffle(deck)
# draw five cards
print("You got:")
for i in range(5):
print(deck[i][0], "of", deck[i][1])
---OR---
****JAVA CODE:****
// Java Code for Shuffle a deck of cards
import java.util.Random;
class GFG {
// Function which shuffle and print the array
public static void shuffle(int card[], int n)
{
Random rand = new Random();
for (int i = 0; i < n; i++)
{
// Random for remaining positions.
int r = i + rand.nextInt(52 - i);
//swapping the elements
int temp = card[r];
card[r] = card[i];
card[i] = temp;
}
}
// Driver code
public static void main(String[] args)
{
// Array from 0 to 51
int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8,
9, 10, 11, 12, 13, 14, 15,
16, 17, 18, 19, 20, 21, 22,
23, 24, 25, 26, 27, 28, 29,
30, 31, 32, 33, 34, 35, 36,
37, 38, 39, 40, 41, 42, 43,
44, 45, 46, 47, 48, 49, 50,
51};
shuffle(a, 52);
// Printing all shuffled elements of cards
for (int i = 0; i < 52; i ++)
System.out.print(a[i]+" ");
}
}
****************************END***********************
****************************END***********************
Practical 7(b): Solve travelling salesman problem using AI technique.
***JAVA CODE***
import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.Stack;
public class TSPNearestNeighbour
{
private int numberOfNodes;
private Stack<Integer> stack;
public TSPNearestNeighbour()
{
stack = new Stack<Integer>();
}
public void tsp(int adjacencyMatrix[][])
{
numberOfNodes = adjacencyMatrix[1].length - 1;
int[] visited = new int[numberOfNodes + 1];
visited[1] = 1;
stack.push(1);
int element, dst = 0, i;
int min = Integer.MAX_VALUE;
boolean minFlag = false;
System.out.print(1 + "\t");
while (!stack.isEmpty())
{
element = stack.peek();
i = 1;
min = Integer.MAX_VALUE;
while (i <= numberOfNodes)
{
if (adjacencyMatrix[element][i] > 1 && visited[i] == 0)
{
if (min > adjacencyMatrix[element][i])
{
min = adjacencyMatrix[element][i];
dst = i;
minFlag = true;
}
}
i++;
}
if (minFlag)
{
visited[dst] = 1;
stack.push(dst);
System.out.print(dst + "\t");
minFlag = false;
continue;
}
stack.pop();
}
}
public static void main(String... arg)
{
int number_of_nodes;
Scanner scanner = null;
try
{
System.out.println("Enter the number of nodes in the graph");
scanner = new Scanner(System.in);
number_of_nodes = scanner.nextInt();
int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
System.out.println("Enter the adjacency matrix");
for (int i = 1; i <= number_of_nodes; i++)
{
for (int j = 1; j <= number_of_nodes; j++)
{
adjacency_matrix[i][j] = scanner.nextInt();
}
}
for (int i = 1; i <= number_of_nodes; i++)
{
for (int j = 1; j <= number_of_nodes; j++)
{
if (adjacency_matrix[i][j] == 1
&& adjacency_matrix[j][i] == 0)
{
adjacency_matrix[j][i] = 1;
}
}
}
System.out.println("The cities are visited as follows: ");
TSPNearestNeighbour tspNearestNeighbour = new TSPNearestNeighbour();
tspNearestNeighbour.tsp(adjacency_matrix);
}
catch (InputMismatchException inputMismatch)
{
System.out.println("Wrong Input format");
}
scanner.close();
}
}
*********************************END**********************************
*********************************END**********************************
Practical-8(a): Solve the Block of World Problem.
//PYTHON CODE://
def bow(n, m, f, t, au):
if(n==1 and m==1):
print ("Move for 1 box is from place "+f+"to place"+au)
print ("Move for 2 box is from place "+t+"to place"+f)
print ("Move for 1 box is from place "+au+"to place"+t)
print ("Move for 2 box is from place "+f+"to place"+t)
return
if(n==1):
print ("Move for 1 box is from place "+f+"to place"+t)
return
if(m==1):
print ("Move for 1 box is from place "+f+"to place"+t)
return
bow(n-1, m-1, f, au, t)
print ("Move for"+str(n)+" box is from place"+f+"to place"+t)
bow(n-1, m-1, t, f, au)
print ("Enter the number of box in P1:")
n = int(input())
print ("Enter the Number of box in P2 :")
m = int(input())
print ("it's Done:\n")
bow(n, m,'P1','P3','P2')
*****************************END**********************
*****************************END**********************
Practical-9(a): Derive the Expression based on Associative law.
//PYTHON CODE://
import random
a = random.randint(0, 99)
b = random.randint(0, 99)
c = random.randint(0, 99)
print ("Associative Law->")
print( "A + (B + C)->",(a+(b+c)))
print ("(A + B) + C -> ",((a+b)+c))
********************************END***************************
********************************END***************************
Practical-9(b): Derive the expression based Distributive law.
//PYTHON CODE://
import random
a = random.randint(0, 99)
b = random.randint(0, 99)
c = random.randint(0, 99)
print ("Distributive Law->")
print ("A(B + C)->",(a*(b+c)))
print ("(AB) + (AC)->",((a*b)+(a*c)))
************************************END****************************
************************************END****************************
Practical -10(a): Write a Program to derive the predicate.
Step1) Set path in cmd -> cd C:\Users\DELL\AppData\Local\Programs\Python\Python37-32\Scripts
Step2) Install Package in CMD: pip install simpleai
Step3) Install Package in CMD: pip install pydot flask
Step4) Run the python code
//PYTHON CODE://
prd=input("Enter a structure:")
pd2=input("Enter a Predicate:")
arg=input("Enter an Argument:")
print (prd+"->"+arg)
print (arg+"->"+pd2)
print (prd+"->"+pd2)
************************************END**************************************
************************************END**************************************
Practical-10(b): Write a program which contains three predicates.
Step1) Set path in cmd -> cd C:\Users\DELL\AppData\Local\Programs\Python\Python37-32\Scripts
Step) Install Package in CMD : pip install ete3
//PYTHON CODE://
from ete3 import Tree
t=Tree('(male, female, (((((ME, Brother, Sister)Father Mother))Grandfather Grandmother))parent)Tree;',format=1)
print (t.get_ascii(show_internal=True))
**************************************END******************************************
**************************************END******************************************
// PYTHON CODE//
graph1= {'A':set(['B','C']),
'B':set(['A','D','E']),
'C':set(['A','F']),
'D':set(['B']),
'E':set(['B','F']),
'F':set(['C','E'])
}
def dfs(graph,node,visited):
if node not in visited:
visited.append(node)
for n in graph[node]:
dfs(graph,n,visited)
return visited
visited= dfs(graph1,'A',[])
print(visited)
************************************END************************************
************************************END************************************
1(b): Write a program to implement breadth first search algorithm.
//PYTHON CODE//
graph = {'A': ['B', 'C', 'E'],
'B': ['A','D', 'E'],
'C': ['A', 'F', 'G'],
'D': ['B'],
'E': ['A', 'B','D'],
'F': ['C'],
'G': ['C']}
def bfs_connected_component(graph, start):
explored = []
queue = [start]
levels = {}
levels[start]= 0
visited= [start]
while queue:
node = queue.pop(0)
explored.append(node)
neighbours = graph[node]
for neighbour in neighbours:
if neighbour not in visited:
queue.append(neighbour)
visited.append(neighbour)
levels[neighbour]= levels[node]+1
print(levels)
return explored
ans = bfs_connected_component(graph,'A')
print(ans)
**************************************END*********************************
**************************************END*********************************
2(a): Write a program to simulate 4 Queen / N-queen problem.
//PYTHON CODE//
class QueenChessBoard:
def __init__(self, size):
self.size = size
self.columns = []
def place_in_next_row(self, column):
self.columns.append(column)
def remove_in_current_row(self):
return self.columns.pop()
def is_this_column_safe_in_next_row(self, column):
row = len(self.columns)
for queen_column in self.columns:
if column == queen_column:
return False
for queen_row, queen_column in enumerate(self.columns):
if queen_column - queen_row == column - row:
return False
for queen_row, queen_column in enumerate(self.columns):
if ((self.size - queen_column) - queen_row
== (self.size - column) - row):
return False
return True
def display(self):
for row in range(self.size):
for column in range(self.size):
if column == self.columns[row]:
print('Q', end=' ')
else:
print('.', end=' ')
print()
def solve_queen(size):
"""Display a chessboard for each possible configuration of placing n queens
on an n x n chessboard and print the number of such configurations."""
board = QueenChessBoard(size)
number_of_solutions = 0
row = 0
column = 0
while True:
while column < size:
if board.is_this_column_safe_in_next_row(column):
board.place_in_next_row(column)
row += 1
column = 0
break
else:
column += 1
if (column == size or row == size):
if row == size:
board.display()
print()
number_of_solutions += 1
board.remove_in_current_row()
row -= 1
try:
prev_column = board.remove_in_current_row()
except IndexError:
break
row -= 1
column = 1 + prev_column
print('Number of solutions:', number_of_solutions)
n = int(input('Enter n: '))
solve_queen(n)
*************************************END*****************************
*************************************END*****************************
2(b): Write a program to solve tower of hanoi problem.
//PYTHON CODE://
def TowerOfHanoi(n , from_rod, to_rod, aux_rod):
if n == 1:
print( "Move disk 1 from rod",from_rod,"to rod",to_rod )
return
TowerOfHanoi(n-1, from_rod, aux_rod, to_rod)
print ("Move disk",n,"from rod",from_rod,"to rod",to_rod )
TowerOfHanoi(n-1, aux_rod, to_rod, from_rod)
n = 4
TowerOfHanoi(n,'A','C', 'B')
*************************************END*****************************
*************************************END*****************************
3(a): Write a program to implement alpha beta search.
//PYTHON CODE://
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))
***************************************END*************************************
***************************************END*************************************
3(b): Write a program for hill climbing problem.
//JAVA CODE://
import java.util.Scanner;
public class hillclimbing {
public static void main(String[] args) {
int n,i,j;
Scanner sc=new Scanner(System.in);
System.out.println("Enter number of nodes in graph");
n=sc.nextInt();
int[][] graph=new int[n][n];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
graph[i][j]=0;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
System.out.println("Is "+i+" is connected to "+ j);
graph[i][j]=sc.nextInt();
}
}
System.out.println("The adjacency matrix is:");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{ System.out.print(graph[i][j]+ "\t");
}
System.out.println();
}
}
}
***************************************END*************************************
***************************************END*************************************
Practical-4(a): Write a program to implement A* algorithm.
Step1) Set path in cmd -> cd C:\Users\DELL\AppData\Local\Programs\Python\Python37-32\Scripts
Step2) pip install simpleai
Step3) pip install pydot flask
Step4) Run the python code
//PYTHON CODE://
from simpleai.search import SearchProblem, astar
GOAL = 'HELLO WORLD'
class HelloProblem(SearchProblem):
def actions(self, state):
if len(state) < len(GOAL):
return list(' ABCDEFGHIJKLMNOPQRSTUVWXYZ')
else:
return []
def result(self, state, action):
return state + action
def is_goal(self, state):
return state == GOAL
def heuristic(self, state):
wrong = sum([1 if state[i] != GOAL[i] else 0
for i in range(len(state))])
missing = len(GOAL) - len(state)
return wrong + missing
problem = HelloProblem(initial_state='')
result = astar(problem)
print(result.state)
print(result.path())
***************END*****************
***************END*****************
Practical-5(A): Write a Program to Solve water jug problem.
*****PYTHON CODE:******
def pour(jug1,jug2):
max1,max2,fill=5,7,4
print("%d\t%d"%(jug1,jug2))
if jug2 is fill:
return
elif jug2 is max2:
pour(0,jug1)
elif jug1 !=0 and jug2 is 0:
pour(0,jug1)
elif jug1 is fill:
pour(jug1,0)
elif jug1<max1:
pour(max1,jug2)
elif jug1<(max2-jug2):
pour(0,(jug1+jug2))
else:
pour(jug1-(max2-jug2),(max2-jug2)+jug2)
print("JUG1\tJUG2")
pour(0,0)
**************************END************************************
**************************END************************************
Practical-5(b) : Design the simulation of tic-tac-toe game.
*****JAVA CODE:******
import java.util.Scanner;
/**
* Tic-Tac-Toe: Two-player console, non-graphics, non-OO version.
* All variables/methods are declared as static (belong to the class)
* in the non-OO version.
*/
public class TTTConsoleNonOO2P {
// Name-constants to represent the seeds and cell contents
public static final int EMPTY = 0;
public static final int CROSS = 1;
public static final int NOUGHT = 2;
// Name-constants to represent the various states of the game
public static final int PLAYING = 0;
public static final int DRAW = 1;
public static final int CROSS_WON = 2;
public static final int NOUGHT_WON = 3;
// The game board and the game status
public static final int ROWS = 3, COLS = 3; // number of rows and columns
public static int[][] board = new int[ROWS][COLS]; // game board in 2D array
// containing (EMPTY, CROSS, NOUGHT)
public static int currentState; // the current state of the game
// (PLAYING, DRAW, CROSS_WON, NOUGHT_WON)
public static int currentPlayer; // the current player (CROSS or NOUGHT)
public static int currntRow, currentCol; // current seed's row and column
public static Scanner in = new Scanner(System.in); // the input Scanner
/** The entry main method (the program starts here) */
public static void main(String[] args) {
// Initialize the game-board and current status
initGame();
// Play the game once
do {
playerMove(currentPlayer); // update currentRow and currentCol
updateGame(currentPlayer, currntRow, currentCol); // update currentState
printBoard();
// Print message if game-over
if (currentState == CROSS_WON) {
System.out.println("'X' won! Bye!");
} else if (currentState == NOUGHT_WON) {
System.out.println("'O' won! Bye!");
} else if (currentState == DRAW) {
System.out.println("It's a Draw! Bye!");
}
// Switch player
currentPlayer = (currentPlayer == CROSS) ? NOUGHT : CROSS;
} while (currentState == PLAYING); // repeat if not game-over
}
/** Initialize the game-board contents and the current states */
public static void initGame() {
for (int row = 0; row < ROWS; ++row) {
for (int col = 0; col < COLS; ++col) {
board[row][col] = EMPTY; // all cells empty
}
}
currentState = PLAYING; // ready to play
currentPlayer = CROSS; // cross plays first
}
/** Player with the "theSeed" makes one move, with input validation.
Update global variables "currentRow" and "currentCol". */
public static void playerMove(int theSeed) {
boolean validInput = false; // for input validation
do {
if (theSeed == CROSS) {
System.out.print("Player 'X', enter your move (row[1-3] column[1-3]): ");
} else {
System.out.print("Player 'O', enter your move (row[1-3] column[1-3]): ");
}
int row = in.nextInt() - 1; // array index starts at 0 instead of 1
int col = in.nextInt() - 1;
if (row >= 0 && row < ROWS && col >= 0 && col < COLS && board[row][col] == EMPTY) {
currntRow = row;
currentCol = col;
board[currntRow][currentCol] = theSeed; // update game-board content
validInput = true; // input okay, exit loop
} else {
System.out.println("This move at (" + (row + 1) + "," + (col + 1)
+ ") is not valid. Try again...");
}
} while (!validInput); // repeat until input is valid
}
/** Update the "currentState" after the player with "theSeed" has placed on
(currentRow, currentCol). */
public static void updateGame(int theSeed, int currentRow, int currentCol) {
if (hasWon(theSeed, currentRow, currentCol)) { // check if winning move
currentState = (theSeed == CROSS) ? CROSS_WON : NOUGHT_WON;
} else if (isDraw()) { // check for draw
currentState = DRAW;
}
// Otherwise, no change to currentState (still PLAYING).
}
/** Return true if it is a draw (no more empty cell) */
// TODO: Shall declare draw if no player can "possibly" win
public static boolean isDraw() {
for (int row = 0; row < ROWS; ++row) {
for (int col = 0; col < COLS; ++col) {
if (board[row][col] == EMPTY) {
return false; // an empty cell found, not draw, exit
}
}
}
return true; // no empty cell, it's a draw
}
/** Return true if the player with "theSeed" has won after placing at
(currentRow, currentCol) */
public static boolean hasWon(int theSeed, int currentRow, int currentCol) {
return (board[currentRow][0] == theSeed // 3-in-the-row
&& board[currentRow][1] == theSeed
&& board[currentRow][2] == theSeed
|| board[0][currentCol] == theSeed // 3-in-the-column
&& board[1][currentCol] == theSeed
&& board[2][currentCol] == theSeed
|| currentRow == currentCol // 3-in-the-diagonal
&& board[0][0] == theSeed
&& board[1][1] == theSeed
&& board[2][2] == theSeed
|| currentRow + currentCol == 2 // 3-in-the-opposite-diagonal
&& board[0][2] == theSeed
&& board[1][1] == theSeed
&& board[2][0] == theSeed);
}
/** Print the game board */
public static void printBoard() {
for (int row = 0; row < ROWS; ++row) {
for (int col = 0; col < COLS; ++col) {
printCell(board[row][col]); // print each of the cells
if (col != COLS - 1) {
System.out.print("|"); // print vertical partition
}
}
System.out.println();
if (row != ROWS - 1) {
System.out.println("-----------"); // print horizontal partition
}
}
System.out.println();
}
/** Print a cell with the specified "content" */
public static void printCell(int content) {
switch (content) {
case EMPTY: System.out.print(" "); break;
case NOUGHT: System.out.print(" O "); break;
case CROSS: System.out.print(" X "); break;
}
}
}
****************************END******************************************
****************************END******************************************
Practical-6(a): Write a program to solve Missionaries and Cannibals problem.
****Python Code:*****
#! /usr/bin/env python
"""
This is a solution to the Missionaries and Cannibalis problem.
Uses a breadth first search and the representation as described
in the lecture. Call without any arguments
$ ./search.py
to search for a solution from the initial state (3,3,1).
"""
from copy import deepcopy
from collections import deque
import sys
import time
# Within this object, the state is represented as described in the lecture:
# The triple (m,c,b) holds the number of missionaries, cannibals and boats
# on the original shore.
class State(object):
def __init__(self, missionaries, cannibals, boats):
self.missionaries = missionaries
self.cannibals = cannibals
self.boats = boats
def successors(self):
if self.boats == 1:
sgn = -1
direction = "from the original shore to the new shore"
else:
sgn = 1
direction = "back from the new shore to the original shore"
for m in range(3):
for c in range(3):
newState = State(self.missionaries+sgn*m, self.cannibals+sgn*c, self.boats+sgn*1);
if m+c >= 1 and m+c <= 2 and newState.isValid(): # check whether action and resulting state are valid
action = "take %d missionaries and %d cannibals %s. %r" % ( m, c, direction, newState)
yield action, newState
def isValid(self):
# first check the obvious
if self.missionaries < 0 or self.cannibals < 0 or self.missionaries > 3 or self.cannibals > 3 or (self.boats != 0 and self.boats != 1):
return False
# then check whether missionaries outnumbered by cannibals
if self.cannibals > self.missionaries and self.missionaries > 0: # more cannibals then missionaries on original shore
return False
if self.cannibals < self.missionaries and self.missionaries < 3: # more cannibals then missionaries on other shore
return False
return True
def is_goal_state(self):
return self.cannibals == 0 and self.missionaries == 0 and self.boats == 0
def __repr__(self):
return "< State (%d, %d, %d) >" % (self.missionaries, self.cannibals, self.boats)
class Node(object):
def __init__(self, parent_node, state, action, depth):
self.parent_node = parent_node
self.state = state
self.action = action
self.depth = depth
def expand(self):
for (action, succ_state) in self.state.successors():
succ_node = Node(
parent_node=self,
state=succ_state,
action=action,
depth=self.depth + 1)
yield succ_node
def extract_solution(self):
solution = []
node = self
while node.parent_node is not None:
solution.append(node.action)
node = node.parent_node
solution.reverse()
return solution
def breadth_first_tree_search(initial_state):
initial_node = Node(
parent_node=None,
state=initial_state,
action=None,
depth=0)
fifo = deque([initial_node])
num_expansions = 0
max_depth = -1
while True:
if not fifo:
print ("%d expansions" % num_expansions)
return None
node = fifo.popleft()
if node.depth > max_depth:
max_depth = node.depth
print ("[depth = %d] %.2fs" % (max_depth, time.clock()))
if node.state.is_goal_state():
print ("%d expansions" % num_expansions)
solution = node.extract_solution()
return solution
num_expansions += 1
fifo.extend(node.expand())
def usage():
print >> sys.stderr, "usage:"
print >> sys.stderr, " %s" % sys.argv[0]
raise SystemExit(2)
def main():
initial_state = State(3,3,1)
solution = breadth_first_tree_search(initial_state)
if solution is None:
print ("no solution")
else:
print ("solution (%d steps):" % len(solution))
for step in solution:
print ("%s" % step)
print ("elapsed time: %.2fs" % time.clock())
if __name__ == "__main__":
main()
********************************END******************************
********************************END******************************
Practical-6(b): Design an application to simulate number Puzzle problem.
***PYTHON CODE:
t=0
lis=[
1,2,3,
4,5,6,
7,t,8
]
print (lis)
def sort(i):
for i in l:
if l[i]==0:
move=int(input("Enter 1 to move back or ) to move ahead"))
if move==1:
temp=l[i-1]
l[i-1]=l[i]
l[i]=temp
print (l)
sort(i)
try:
if move==0:
if i!=l[-1]:
temp=l[i+1]
l[i+1]=l[i]
l[i]=temp
print (l)
except:
print ("Error! Cannot Move Ahead, Last Index")
sort(l)
if move==9:
break
sort(lis)
******************************END********************************
******************************END********************************
Practical-7(a): Write a program to shuffle Deck of cards.
****PYTHON CODE****
# import modules
import itertools, random
# make a deck of cards
deck = list(itertools.product(range(1,14),['Spade','Heart','Diamond','Club']))
# shuffle the cards
random.shuffle(deck)
# draw five cards
print("You got:")
for i in range(5):
print(deck[i][0], "of", deck[i][1])
---OR---
****JAVA CODE:****
// Java Code for Shuffle a deck of cards
import java.util.Random;
class GFG {
// Function which shuffle and print the array
public static void shuffle(int card[], int n)
{
Random rand = new Random();
for (int i = 0; i < n; i++)
{
// Random for remaining positions.
int r = i + rand.nextInt(52 - i);
//swapping the elements
int temp = card[r];
card[r] = card[i];
card[i] = temp;
}
}
// Driver code
public static void main(String[] args)
{
// Array from 0 to 51
int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8,
9, 10, 11, 12, 13, 14, 15,
16, 17, 18, 19, 20, 21, 22,
23, 24, 25, 26, 27, 28, 29,
30, 31, 32, 33, 34, 35, 36,
37, 38, 39, 40, 41, 42, 43,
44, 45, 46, 47, 48, 49, 50,
51};
shuffle(a, 52);
// Printing all shuffled elements of cards
for (int i = 0; i < 52; i ++)
System.out.print(a[i]+" ");
}
}
****************************END***********************
****************************END***********************
Practical 7(b): Solve travelling salesman problem using AI technique.
***JAVA CODE***
import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.Stack;
public class TSPNearestNeighbour
{
private int numberOfNodes;
private Stack<Integer> stack;
public TSPNearestNeighbour()
{
stack = new Stack<Integer>();
}
public void tsp(int adjacencyMatrix[][])
{
numberOfNodes = adjacencyMatrix[1].length - 1;
int[] visited = new int[numberOfNodes + 1];
visited[1] = 1;
stack.push(1);
int element, dst = 0, i;
int min = Integer.MAX_VALUE;
boolean minFlag = false;
System.out.print(1 + "\t");
while (!stack.isEmpty())
{
element = stack.peek();
i = 1;
min = Integer.MAX_VALUE;
while (i <= numberOfNodes)
{
if (adjacencyMatrix[element][i] > 1 && visited[i] == 0)
{
if (min > adjacencyMatrix[element][i])
{
min = adjacencyMatrix[element][i];
dst = i;
minFlag = true;
}
}
i++;
}
if (minFlag)
{
visited[dst] = 1;
stack.push(dst);
System.out.print(dst + "\t");
minFlag = false;
continue;
}
stack.pop();
}
}
public static void main(String... arg)
{
int number_of_nodes;
Scanner scanner = null;
try
{
System.out.println("Enter the number of nodes in the graph");
scanner = new Scanner(System.in);
number_of_nodes = scanner.nextInt();
int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
System.out.println("Enter the adjacency matrix");
for (int i = 1; i <= number_of_nodes; i++)
{
for (int j = 1; j <= number_of_nodes; j++)
{
adjacency_matrix[i][j] = scanner.nextInt();
}
}
for (int i = 1; i <= number_of_nodes; i++)
{
for (int j = 1; j <= number_of_nodes; j++)
{
if (adjacency_matrix[i][j] == 1
&& adjacency_matrix[j][i] == 0)
{
adjacency_matrix[j][i] = 1;
}
}
}
System.out.println("The cities are visited as follows: ");
TSPNearestNeighbour tspNearestNeighbour = new TSPNearestNeighbour();
tspNearestNeighbour.tsp(adjacency_matrix);
}
catch (InputMismatchException inputMismatch)
{
System.out.println("Wrong Input format");
}
scanner.close();
}
}
*********************************END**********************************
*********************************END**********************************
Practical-8(a): Solve the Block of World Problem.
//PYTHON CODE://
def bow(n, m, f, t, au):
if(n==1 and m==1):
print ("Move for 1 box is from place "+f+"to place"+au)
print ("Move for 2 box is from place "+t+"to place"+f)
print ("Move for 1 box is from place "+au+"to place"+t)
print ("Move for 2 box is from place "+f+"to place"+t)
return
if(n==1):
print ("Move for 1 box is from place "+f+"to place"+t)
return
if(m==1):
print ("Move for 1 box is from place "+f+"to place"+t)
return
bow(n-1, m-1, f, au, t)
print ("Move for"+str(n)+" box is from place"+f+"to place"+t)
bow(n-1, m-1, t, f, au)
print ("Enter the number of box in P1:")
n = int(input())
print ("Enter the Number of box in P2 :")
m = int(input())
print ("it's Done:\n")
bow(n, m,'P1','P3','P2')
*****************************END**********************
*****************************END**********************
Practical-9(a): Derive the Expression based on Associative law.
//PYTHON CODE://
import random
a = random.randint(0, 99)
b = random.randint(0, 99)
c = random.randint(0, 99)
print ("Associative Law->")
print( "A + (B + C)->",(a+(b+c)))
print ("(A + B) + C -> ",((a+b)+c))
********************************END***************************
********************************END***************************
Practical-9(b): Derive the expression based Distributive law.
//PYTHON CODE://
import random
a = random.randint(0, 99)
b = random.randint(0, 99)
c = random.randint(0, 99)
print ("Distributive Law->")
print ("A(B + C)->",(a*(b+c)))
print ("(AB) + (AC)->",((a*b)+(a*c)))
************************************END****************************
************************************END****************************
Practical -10(a): Write a Program to derive the predicate.
Step1) Set path in cmd -> cd C:\Users\DELL\AppData\Local\Programs\Python\Python37-32\Scripts
Step2) Install Package in CMD: pip install simpleai
Step3) Install Package in CMD: pip install pydot flask
Step4) Run the python code
//PYTHON CODE://
prd=input("Enter a structure:")
pd2=input("Enter a Predicate:")
arg=input("Enter an Argument:")
print (prd+"->"+arg)
print (arg+"->"+pd2)
print (prd+"->"+pd2)
************************************END**************************************
************************************END**************************************
Practical-10(b): Write a program which contains three predicates.
Step1) Set path in cmd -> cd C:\Users\DELL\AppData\Local\Programs\Python\Python37-32\Scripts
Step) Install Package in CMD : pip install ete3
//PYTHON CODE://
from ete3 import Tree
t=Tree('(male, female, (((((ME, Brother, Sister)Father Mother))Grandfather Grandmother))parent)Tree;',format=1)
print (t.get_ascii(show_internal=True))
**************************************END******************************************
**************************************END******************************************
Comments
Post a Comment