Skip to content

Instantly share code, notes, and snippets.

@VinayHajare

VinayHajare/A*.c

Last active May 19, 2025 08:52
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save VinayHajare/2f45cd0301d6ecae56ea61c19dd54c3f to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save VinayHajare/2f45cd0301d6ecae56ea61c19dd54c3f to your computer and use it in GitHub Desktop.
Download ZIP
AI Labs
Raw
A*.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define N 3
#define SIZE 9
typedef struct Node {
int puzzle[SIZE];
int level;
int cost;
struct Node* parent;
} Node;
int goal[] = {1,2,3,4,5,6,7,8,0};
int calculateCost(int puzzle[]) {
int cost = 0;
for (int i = 0; i < SIZE; i++) {
if (puzzle[i] != 0 && puzzle[i] != goal[i])
cost++;
}
return cost;
}
int isGoal(int puzzle[]) {
for (int i = 0; i < SIZE; i++)
if (puzzle[i] != goal[i])
return 0;
return 1;
}
void printPuzzle(int puzzle[]) {
for (int i = 0; i < SIZE; i++) {
if (i % N == 0) printf("\n");
printf("%d ", puzzle[i]);
}
printf("\n");
}
int isSafe(int x, int y) {
return (x >= 0 && x < N && y >= 0 && y < N);
}
void copyPuzzle(int* src, int* dest) {
for (int i = 0; i < SIZE; i++)
dest[i] = src[i];
}
Node* newNode(int puzzle[], int x, int y, int newX, int newY, int level, Node* parent) {
Node* node = (Node*)malloc(sizeof(Node));
copyPuzzle(puzzle, node->puzzle);
int pos = x * N + y;
int newPos = newX * N + newY;
int temp = node->puzzle[pos];
node->puzzle[pos] = node->puzzle[newPos];
node->puzzle[newPos] = temp;
node->parent = parent;
node->level = level;
node->cost = calculateCost(node->puzzle);
return node;
}
int directions[4][2] = {
{1, 0}, {-1, 0}, {0, 1}, {0, -1}
};
// Function to print solution path in correct order
void printSolutionPath(Node* goalNode) {
Node* path[1000]; // Array to store path nodes
int pathLength = 0;
// Collect all nodes from goal to root
Node* current = goalNode;
while (current != NULL) {
path[pathLength++] = current;
current = current->parent;
}
// Print path from root to goal (reverse order)
printf("\nSolution found in %d steps:\n", pathLength - 1);
printf("========================================\n");
for (int i = pathLength - 1; i >= 0; i--) {
printf("Step %d:", pathLength - 1 - i);
printPuzzle(path[i]->puzzle);
if (i > 0) printf("--------\n");
}
}
void solve(int initial[]) {
Node* root = (Node*)malloc(sizeof(Node));
copyPuzzle(initial, root->puzzle);
root->parent = NULL;
root->level = 0;
root->cost = calculateCost(initial);
Node* open[1000];
int openSize = 0;
open[openSize++] = root;
printf("Initial state:");
printPuzzle(initial);
printf("Target state:");
printPuzzle(goal);
printf("\nSearching for solution...\n");
while (openSize > 0) {
// Find node with minimum f(n) = g(n) + h(n)
int minIndex = 0;
for (int i = 1; i < openSize; i++) {
if (open[i]->cost + open[i]->level < open[minIndex]->cost + open[minIndex]->level)
minIndex = i;
}
Node* current = open[minIndex];
// Remove current node from open list
for (int i = minIndex; i < openSize - 1; i++)
open[i] = open[i + 1];
openSize--;
if (isGoal(current->puzzle)) {
printSolutionPath(current);
return;
}
// Find position of empty space (0)
int zeroIndex;
for (int i = 0; i < SIZE; i++)
if (current->puzzle[i] == 0)
zeroIndex = i;
int x = zeroIndex / N;
int y = zeroIndex % N;
// Generate all possible moves
for (int i = 0; i < 4; i++) {
int newX = x + directions[i][0];
int newY = y + directions[i][1];
if (isSafe(newX, newY)) {
Node* child = newNode(current->puzzle, x, y, newX, newY, current->level + 1, current);
open[openSize++] = child;
}
}
}
printf("No solution found.\n");
}
int main() {
int initial[] = {
1, 2, 3,
4, 0, 6,
7, 5, 8
};
solve(initial);
return 0;
}
Raw
BfsDFS.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 9
#define N 3
#define MAX_QUEUE 10000
typedef struct Node {
int puzzle[SIZE];
int level;
struct Node* parent;
} Node;
int goal[SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 0};
int directions[4][2] = {
{-1, 0}, {1, 0}, {0, -1}, {0, 1} // up, down, left, right
};
void printPuzzle(int puzzle[]) {
for (int i = 0; i < SIZE; i++) {
if (i % 3 == 0) printf("\n");
printf("%d ", puzzle[i]);
}
printf("\n");
}
int isGoal(int puzzle[]) {
for (int i = 0; i < SIZE; i++)
if (puzzle[i] != goal[i]) return 0;
return 1;
}
int isSafe(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < N;
}
int alreadyVisited(Node* closed[], int closedSize, int puzzle[]) {
for (int i = 0; i < closedSize; i++)
if (memcmp(closed[i]->puzzle, puzzle, sizeof(int)*SIZE) == 0)
return 1;
return 0;
}
Node* createNode(int puzzle[], Node* parent, int level) {
Node* node = (Node*)malloc(sizeof(Node));
memcpy(node->puzzle, puzzle, sizeof(int)*SIZE);
node->parent = parent;
node->level = level;
return node;
}
void printSolution(Node* node) {
if (node == NULL) return;
printSolution(node->parent);
printPuzzle(node->puzzle);
printf("\n");
}
void bfs(int initial[]) {
Node* queue[MAX_QUEUE];
Node* closed[MAX_QUEUE];
int front = 0, rear = 0, closedSize = 0;
Node* root = createNode(initial, NULL, 0);
queue[rear++] = root;
while (front < rear) {
Node* curr = queue[front++];
closed[closedSize++] = curr;
if (isGoal(curr->puzzle)) {
printf("Solution Found at Level: %d\n", curr->level);
printSolution(curr);
return;
}
int zeroPos;
for (int i = 0; i < SIZE; i++)
if (curr->puzzle[i] == 0) zeroPos = i;
int x = zeroPos / N;
int y = zeroPos % N;
for (int i = 0; i < 4; i++) {
int newX = x + directions[i][0];
int newY = y + directions[i][1];
if (isSafe(newX, newY)) {
int newPuzzle[SIZE];
memcpy(newPuzzle, curr->puzzle, sizeof(int)*SIZE);
int newPos = newX * N + newY;
newPuzzle[zeroPos] = newPuzzle[newPos];
newPuzzle[newPos] = 0;
if (!alreadyVisited(closed, closedSize, newPuzzle)) {
Node* child = createNode(newPuzzle, curr, curr->level + 1);
queue[rear++] = child;
}
}
}
}
printf("No solution found.\n");
}
#define MAX_DEPTH 20
int dfsVisited = 0;
int dfsRecursive(Node* node, int depth) {
dfsVisited++;
if (depth > MAX_DEPTH) return 0;
if (isGoal(node->puzzle)) {
printf("Solution Found at Depth: %d\n", node->level);
printSolution(node);
return 1;
}
int zeroPos;
for (int i = 0; i < SIZE; i++)
if (node->puzzle[i] == 0) zeroPos = i;
int x = zeroPos / N;
int y = zeroPos % N;
for (int i = 0; i < 4; i++) {
int newX = x + directions[i][0];
int newY = y + directions[i][1];
if (isSafe(newX, newY)) {
int newPuzzle[SIZE];
memcpy(newPuzzle, node->puzzle, sizeof(int)*SIZE);
int newPos = newX * N + newY;
newPuzzle[zeroPos] = newPuzzle[newPos];
newPuzzle[newPos] = 0;
Node* child = createNode(newPuzzle, node, node->level + 1);
if (dfsRecursive(child, depth + 1)) return 1;
}
}
return 0;
}
void dfs(int initial[]) {
Node* root = createNode(initial, NULL, 0);
if (!dfsRecursive(root, 0))
printf("No solution found within depth %d.\n", MAX_DEPTH);
}
int main() {
int initial[] = {
1, 2, 3,
4, 0, 6,
7, 5, 8
};
printf("Solving with BFS:\n");
bfs(initial);
printf("\nSolving with DFS:\n");
dfs(initial);
return 0;
}
Raw
exper_system.pl
:- initialization(main).
% FACTS
male(john).
male(paul).
male(robby).
male(mike).
female(susan).
female(lisa).
female(anna).
parent(johnny, paul).
parent(johnny, linda).
parent(susana, paul).
parent(susana, linda).
parent(paul, mikey).
parent(anna, mikey).
parent(linda , isha).
parent(robby , isha).
% RULES
father(X, Y) :- parent(X, Y), male(X).
mother(X, Y) :- parent(X, Y), female(X).
grandparent(X, Y) :- parent(X, Z), parent(Z, Y).
sibling(X, Y) :- parent(Z, X), parent(Z, Y), X \= Y.
cousin(A,B) :- parent(X,A) , parent(Y,B) , sibling(X,Y) , X \= Y.
main :-
(
parent(johnny , mike) ->
write('true');
write('false')
).
Raw
Lab1A.c
/**
Human vs Human Tic-Tac-Toe game
*/
#include <stdio.h>
#include <stdbool.h>
#define BOARD_SIZE 3
#define MIN_MOVES_FOR_DRAW_CHECK 5
char board[BOARD_SIZE][BOARD_SIZE];
bool checkWin(char player) {
// Check rows and columns for a win
for (int i = 0; i < BOARD_SIZE; i++) {
if ((board[i][0] == player && board[i][1] == player && board[i][2] == player) ||
(board[0][i] == player && board[1][i] == player && board[2][i] == player)) {
return true;
}
}
// Check diagonals for a win
if ((board[0][0] == player && board[1][1] == player && board[2][2] == player) ||
(board[0][2] == player && board[1][1] == player && board[2][0] == player)) {
return true;
}
return false;
}
// Function to check for a draw
bool checkDraw() {
// Check if any player has a potential winning move
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
if (board[i][j] == ' ') {
// Try placing 'X' in the empty spot
board[i][j] = 'X';
if (checkWin('X')) {
board[i][j] = ' ';
return false;
}
board[i][j] = ' ';
// Try placing 'O' in the empty spot
board[i][j] = 'O';
if (checkWin('O')) {
board[i][j] = ' ';
return false;
}
board[i][j] = ' ';
}
}
}
// If no player has a potential winning move, it's a draw
return true;
}
// Function to check for a win or draw
bool checkGameStatus(char currentPlayer, int moveCount) {
if (checkWin(currentPlayer)) {
printf("Player %c wins!\n", currentPlayer);
return true;
}
// Only check for a draw after a certain number of moves
if (moveCount >= MIN_MOVES_FOR_DRAW_CHECK && checkDraw()) {
printf("The game is a draw!\n");
return true;
}
return false;
}
// Function to print the board
void printBoard() {
printf("Current Board:\n");
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
printf(" %c ", board[i][j]);
if (j < BOARD_SIZE - 1) printf("|");
}
printf("\n");
if (i < BOARD_SIZE - 1) printf("---+---+---\n");
}
printf("\n");
}
// Function to take input from the user
void takeInput(char player) {
int row, col;
do {
printf("Player %c, enter your move (row and column): ", player);
scanf("%d %d", &row, &col);
if (row < 0 || row >= BOARD_SIZE || col < 0 || col >= BOARD_SIZE || board[row][col] != ' ') {
printf("Invalid move. Try again.\n");
} else {
board[row][col] = player;
break;
}
} while (true);
}
int main() {
// Initialize the board with empty spaces
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
board[i][j] = ' ';
}
}
char currentPlayer = 'X';
bool gameOver = false;
int moveCount = 0;
while (!gameOver) {
printBoard();
takeInput(currentPlayer);
moveCount++;
gameOver = checkGameStatus(currentPlayer, moveCount);
if (!gameOver) {
currentPlayer = (currentPlayer == 'X') ? 'O' : 'X';
}
}
printBoard();
return 0;
}
Raw
LAB1B.c
/**
AI vs Human Tic-Tac-Toe game using Alpha-Beta pruning with early draw
*/
#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#define BOARD_SIZE 3
#define MIN_MOVES_FOR_DRAW_CHECK 5
char board[BOARD_SIZE][BOARD_SIZE];
bool checkWin(char player) {
// Check rows and columns for a win
for (int i = 0; i < BOARD_SIZE; i++) {
if ((board[i][0] == player && board[i][1] == player && board[i][2] == player) ||
(board[0][i] == player && board[1][i] == player && board[2][i] == player)) {
return true;
}
}
// Check diagonals for a win
if ((board[0][0] == player && board[1][1] == player && board[2][2] == player) ||
(board[0][2] == player && board[1][1] == player && board[2][0] == player)) {
return true;
}
return false;
}
bool checkDraw() {
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
if (board[i][j] == ' ') {
// Try placing 'X' in the empty spot
board[i][j] = 'X';
if (checkWin('X')) {
board[i][j] = ' ';
return false;
}
board[i][j] = ' ';
// Try placing 'O' in the empty spot
board[i][j] = 'O';
if (checkWin('O')) {
board[i][j] = ' ';
return false;
}
board[i][j] = ' ';
}
}
}
return true;
}
bool checkGameStatus(char currentPlayer, int moveCount) {
if (checkWin(currentPlayer)) {
printf("Player %c wins!\n", currentPlayer);
return true;
}
if (moveCount >= MIN_MOVES_FOR_DRAW_CHECK && checkDraw()) {
printf("The game is a draw!\n");
return true;
}
return false;
}
void printBoard() {
printf("Current Board:\n");
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
printf(" %c ", board[i][j]);
if (j < BOARD_SIZE - 1) printf("|");
}
printf("\n");
if (i < BOARD_SIZE - 1) printf("---+---+---\n");
}
printf("\n");
}
void takeInput(char player) {
int row, col;
do {
printf("Player %c, enter your move (row and column): ", player);
scanf("%d %d", &row, &col);
if (row < 0 || row >= BOARD_SIZE || col < 0 || col >= BOARD_SIZE || board[row][col] != ' ') {
printf("Invalid move. Try again.\n");
} else {
board[row][col] = player;
break;
}
} while (true);
}
int evaluateBoard() {
if (checkWin('X')) return -10;
if (checkWin('O')) return +10;
return 0;
}
int minimax(int depth, int alpha, int beta, bool isMax) {
int score = evaluateBoard();
if (score == 10 || score == -10) return score;
if (checkDraw()) return 0;
if (isMax) {
int best = INT_MIN;
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
if (board[i][j] == ' ') {
board[i][j] = 'O';
int val = minimax(depth + 1, alpha, beta, false);
board[i][j] = ' ';
best = (val > best) ? val : best;
alpha = (alpha > best) ? alpha : best;
if (beta <= alpha) break;
}
}
if (beta <= alpha) break;
}
return best;
} else {
int best = INT_MAX;
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
if (board[i][j] == ' ') {
board[i][j] = 'X';
int val = minimax(depth + 1, alpha, beta, true);
board[i][j] = ' ';
best = (val < best) ? val : best;
beta = (beta < best) ? beta : best;
if (beta <= alpha) break;
}
}
if (beta <= alpha) break;
}
return best;
}
}
void findBestMove() {
int bestVal = INT_MIN;
int bestRow = -1, bestCol = -1;
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
if (board[i][j] == ' ') {
board[i][j] = 'O';
int moveVal = minimax(0, INT_MIN, INT_MAX, false);
board[i][j] = ' ';
if (moveVal > bestVal) {
bestRow = i;
bestCol = j;
bestVal = moveVal;
}
}
}
}
printf("AI chooses move: (%d, %d) with best value: %d\n", bestRow, bestCol, bestVal);
board[bestRow][bestCol] = 'O';
}
int main() {
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
board[i][j] = ' ';
}
}
char currentPlayer = 'X';
bool gameOver = false;
int moveCount = 0;
while (!gameOver) {
printBoard();
if (currentPlayer == 'O') {
findBestMove();
} else {
takeInput(currentPlayer);
}
moveCount++;
gameOver = checkGameStatus(currentPlayer, moveCount);
if (!gameOver) {
currentPlayer = (currentPlayer == 'X') ? 'O' : 'X';
}
}
printBoard();
return 0;
}
Raw
LAB1C.c
/**
AI vs Human Tic-Tac-Toe game using Minimax algorithm with early draw
*/
#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#define BOARD_SIZE 3
#define MIN_MOVES_FOR_DRAW_CHECK 5
char board[BOARD_SIZE][BOARD_SIZE];
bool checkWin(char player) {
// Check rows and columns for a win
for (int i = 0; i < BOARD_SIZE; i++) {
if ((board[i][0] == player && board[i][1] == player && board[i][2] == player) ||
(board[0][i] == player && board[1][i] == player && board[2][i] == player)) {
return true;
}
}
// Check diagonals for a win
if ((board[0][0] == player && board[1][1] == player && board[2][2] == player) ||
(board[0][2] == player && board[1][1] == player && board[2][0] == player)) {
return true;
}
return false;
}
bool checkDraw() {
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
if (board[i][j] == ' ') {
// Try placing 'X' in the empty spot
board[i][j] = 'X';
if (checkWin('X')) {
board[i][j] = ' ';
return false;
}
board[i][j] = ' ';
// Try placing 'O' in the empty spot
board[i][j] = 'O';
if (checkWin('O')) {
board[i][j] = ' ';
return false;
}
board[i][j] = ' ';
}
}
}
return true;
}
bool checkGameStatus(char currentPlayer, int moveCount) {
if (checkWin(currentPlayer)) {
printf("Player %c wins!\n", currentPlayer);
return true;
}
if (moveCount >= MIN_MOVES_FOR_DRAW_CHECK && checkDraw()) {
printf("The game is a draw!\n");
return true;
}
return false;
}
void printBoard() {
printf("Current Board:\n");
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
printf(" %c ", board[i][j]);
if (j < BOARD_SIZE - 1) printf("|");
}
printf("\n");
if (i < BOARD_SIZE - 1) printf("---+---+---\n");
}
printf("\n");
}
void takeInput(char player) {
int row, col;
do {
printf("Player %c, enter your move (row and column): ", player);
scanf("%d %d", &row, &col);
if (row < 0 || row >= BOARD_SIZE || col < 0 || col >= BOARD_SIZE || board[row][col] != ' ') {
printf("Invalid move. Try again.\n");
} else {
board[row][col] = player;
break;
}
} while (true);
}
int evaluateBoard() {
if (checkWin('X')) return -10;
if (checkWin('O')) return +10;
return 0;
}
int minimax(int depth, bool isMax) {
int score = evaluateBoard();
if (score == 10 || score == -10) return score;
if (checkDraw()) return 0;
if (isMax) {
int best = INT_MIN;
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
if (board[i][j] == ' ') {
board[i][j] = 'O';
int val = minimax(depth + 1, false);
board[i][j] = ' ';
best = (val > best) ? val : best;
}
}
}
return best;
} else {
int best = INT_MAX;
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
if (board[i][j] == ' ') {
board[i][j] = 'X';
int val = minimax(depth + 1, true);
board[i][j] = ' ';
best = (val < best) ? val : best;
}
}
}
return best;
}
}
void findBestMove() {
int bestVal = INT_MIN;
int bestRow = -1, bestCol = -1;
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
if (board[i][j] == ' ') {
board[i][j] = 'O';
int moveVal = minimax(0, false);
board[i][j] = ' ';
if (moveVal > bestVal) {
bestRow = i;
bestCol = j;
bestVal = moveVal;
}
}
}
}
printf("AI chooses move: (%d, %d) with best value: %d\n", bestRow, bestCol, bestVal);
board[bestRow][bestCol] = 'O';
}
int main() {
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
board[i][j] = ' ';
}
}
char currentPlayer = 'X';
bool gameOver = false;
int moveCount = 0;
while (!gameOver) {
printBoard();
if (currentPlayer == 'O') {
findBestMove();
} else {
takeInput(currentPlayer);
}
moveCount++;
gameOver = checkGameStatus(currentPlayer, moveCount);
if (!gameOver) {
currentPlayer = (currentPlayer == 'X') ? 'O' : 'X';
}
}
printBoard();
return 0;
}
Raw
LAB1D.c
/**
AI vs AI Tic-Tac-Toe Game using Alpha-Beta Pruning Algorithm with early draw
*/
#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#define BOARD_SIZE 3
#define MIN_MOVES_FOR_DRAW_CHECK 5
char board[BOARD_SIZE][BOARD_SIZE];
bool checkWin(char player) {
// Check rows and columns for a win
for (int i = 0; i < BOARD_SIZE; i++) {
if ((board[i][0] == player && board[i][1] == player && board[i][2] == player) ||
(board[0][i] == player && board[1][i] == player && board[2][i] == player)) {
return true;
}
}
// Check diagonals for a win
if ((board[0][0] == player && board[1][1] == player && board[2][2] == player) ||
(board[0][2] == player && board[1][1] == player && board[2][0] == player)) {
return true;
}
return false;
}
bool checkDraw() {
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
if (board[i][j] == ' ') {
// Try placing 'X' in the empty spot
board[i][j] = 'X';
if (checkWin('X')) {
board[i][j] = ' ';
return false;
}
board[i][j] = ' ';
// Try placing 'O' in the empty spot
board[i][j] = 'O';
if (checkWin('O')) {
board[i][j] = ' ';
return false;
}
board[i][j] = ' ';
}
}
}
return true;
}
bool checkGameStatus(char currentPlayer, int moveCount) {
if (checkWin(currentPlayer)) {
printf("Player %c wins!\n", currentPlayer);
return true;
}
if (moveCount >= MIN_MOVES_FOR_DRAW_CHECK && checkDraw()) {
printf("The game is a draw!\n");
return true;
}
return false;
}
void printBoard() {
printf("Current Board:\n");
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
printf(" %c ", board[i][j]);
if (j < BOARD_SIZE - 1) printf("|");
}
printf("\n");
if (i < BOARD_SIZE - 1) printf("---+---+---\n");
}
printf("\n");
}
int evaluateBoard() {
if (checkWin('X')) return +10;
if (checkWin('O')) return -10;
return 0;
}
int minimax(int depth, int alpha, int beta, bool isMax) {
int score = evaluateBoard();
if (score == 10 || score == -10) return score;
if (checkDraw()) return 0;
if (isMax) {
int best = INT_MIN;
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
if (board[i][j] == ' ') {
board[i][j] = 'X';
int val = minimax(depth + 1, alpha, beta, false);
board[i][j] = ' ';
best = (val > best) ? val : best;
alpha = (alpha > best) ? alpha : best;
if (beta <= alpha) break;
}
}
if (beta <= alpha) break;
}
return best;
} else {
int best = INT_MAX;
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
if (board[i][j] == ' ') {
board[i][j] = 'O';
int val = minimax(depth + 1, alpha, beta, true);
board[i][j] = ' ';
best = (val < best) ? val : best;
beta = (beta < best) ? beta : best;
if (beta <= alpha) break;
}
}
if (beta <= alpha) break;
}
return best;
}
}
void findBestMove(char player) {
int bestVal = (player == 'X') ? INT_MIN : INT_MAX;
int bestRow = -1, bestCol = -1;
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
if (board[i][j] == ' ') {
board[i][j] = player;
int moveVal = minimax(0, INT_MIN, INT_MAX, player == 'O');
board[i][j] = ' ';
if ((player == 'X' && moveVal > bestVal) || (player == 'O' && moveVal < bestVal)) {
bestRow = i;
bestCol = j;
bestVal = moveVal;
}
}
}
}
printf("AI (%c) chooses move: (%d, %d) with best value: %d\n", player, bestRow, bestCol, bestVal);
board[bestRow][bestCol] = player;
}
int main() {
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
board[i][j] = ' ';
}
}
char currentPlayer = 'X';
bool gameOver = false;
int moveCount = 0;
while (!gameOver) {
printBoard();
findBestMove(currentPlayer);
moveCount++;
gameOver = checkGameStatus(currentPlayer, moveCount);
if (!gameOver) {
currentPlayer = (currentPlayer == 'X') ? 'O' : 'X';
}
}
printBoard();
return 0;
}
Raw
LAB2.c
/**
Missionaries and Cannibals problem using DFS, BFS and Depth Limited Search (Uninformed Search Techniques)
*/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
// Structure to represent a state
typedef struct State {
int ml, cl; // missionaries and cannibals on left bank
int mr, cr; // missionaries and cannibals on right bank
int boat; // 1 if boat on left bank, 0 if on right bank
} State;
// Structure for tree node to visualize state space
typedef struct TreeNode {
State state;
struct TreeNode** children;
int num_children;
int depth;
char move_description[100];
} TreeNode;
// Function to create a new state
State newState(int ml, int cl, int mr, int cr, int boat) {
State state = {ml, cl, mr, cr, boat};
return state;
}
// Function to create a new tree node
TreeNode* createNode(State state, int depth, const char* move) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->state = state;
node->children = NULL;
node->num_children = 0;
node->depth = depth;
strcpy(node->move_description, move);
return node;
}
// Function to add child to tree node
void addChild(TreeNode* parent, TreeNode* child) {
parent->num_children++;
parent->children = realloc(parent->children, parent->num_children * sizeof(TreeNode*));
parent->children[parent->num_children - 1] = child;
}
// Function to describe state
void describeState(State state, char* buffer) {
sprintf(buffer, "Left Bank: %dM %dC | Right Bank: %dM %dC | Boat: %s",
state.ml, state.cl, state.mr, state.cr,
state.boat == 1 ? "Left" : "Right");
}
// Function to get move description
void getMoveDescription(State from, State to, char* buffer) {
int m_diff = abs(from.ml - to.ml);
int c_diff = abs(from.cl - to.cl);
if (m_diff > 0 && c_diff > 0)
sprintf(buffer, "Move %dM %dC to %s",
m_diff, c_diff, from.boat == 1 ? "right" : "left");
else if (m_diff > 0)
sprintf(buffer, "Move %d Missionaries to %s",
m_diff, from.boat == 1 ? "right" : "left");
else
sprintf(buffer, "Move %d Cannibals to %s",
c_diff, from.boat == 1 ? "right" : "left");
}
// Function to print state space tree level by level
void printStateLevelOrder(TreeNode* root) {
if (root == NULL) return;
// Create queue for level order traversal
TreeNode** queue = malloc(10000 * sizeof(TreeNode*));
int front = 0, rear = 0;
// Enqueue root
queue[rear++] = root;
int current_level = 0;
int nodes_at_current_level = 1;
int nodes_at_next_level = 0;
printf("\nInitial State:\n");
while (front < rear) {
TreeNode* current = queue[front++];
nodes_at_current_level--;
// Print state description
char state_desc[200];
describeState(current->state, state_desc);
// Print move description if not root
if (current->depth > 0) {
printf("\nStep %d: %s\n", current->depth, current->move_description);
printf("Result: %s\n", state_desc);
printf("--------------------------------------------------------\n");
} else {
printf("%s\n", state_desc);
printf("--------------------------------------------------------\n");
}
// Enqueue children
for (int i = 0; i < current->num_children; i++) {
queue[rear++] = current->children[i];
nodes_at_next_level++;
}
// Level change
if (nodes_at_current_level == 0) {
current_level++;
nodes_at_current_level = nodes_at_next_level;
nodes_at_next_level = 0;
}
}
free(queue);
}
// Function to check if state is valid
bool isValid(State state) {
if (state.ml < 0 || state.cl < 0 || state.mr < 0 || state.cr < 0)
return false;
if (state.ml > 3 || state.cl > 3 || state.mr > 3 || state.cr > 3)
return false;
if ((state.ml != 0 && state.ml < state.cl) ||
(state.mr != 0 && state.mr < state.cr))
return false;
return true;
}
// Function to check if state is goal state
bool isGoal(State state) {
return (state.ml == 0 && state.cl == 0 &&
state.mr == 3 && state.cr == 3 && state.boat == 0);
}
// DFS implementation with tree building
TreeNode* dfs(State current, State parent, bool visited[4][4][2], TreeNode* node) {
if (!isValid(current)) return NULL;
if (isGoal(current)) return node;
visited[current.ml][current.cl][current.boat] = true;
int moves[][2] = {{1,0}, {2,0}, {0,1}, {0,2}, {1,1}};
for (int i = 0; i < 5; i++) {
State next;
if (current.boat == 1) {
next = newState(
current.ml - moves[i][0], current.cl - moves[i][1],
current.mr + moves[i][0], current.cr + moves[i][1], 0
);
} else {
next = newState(
current.ml + moves[i][0], current.cl + moves[i][1],
current.mr - moves[i][0], current.cr - moves[i][1], 1
);
}
if (isValid(next) && !visited[next.ml][next.cl][next.boat]) {
char move_desc[100];
getMoveDescription(current, next, move_desc);
TreeNode* child = createNode(next, node->depth + 1, move_desc);
addChild(node, child);
TreeNode* result = dfs(next, current, visited, child);
if (result != NULL) return result;
}
}
return NULL;
}
// Depth-Limited Search
TreeNode* depthLimitedSearch(State current, State parent, int depth, TreeNode* node, bool visited[4][4][2]) {
if (depth < 0) return NULL;
if (!isValid(current)) return NULL;
if (isGoal(current)) return node;
visited[current.ml][current.cl][current.boat] = true;
int moves[][2] = {{1,0}, {2,0}, {0,1}, {0,2}, {1,1}};
for (int i = 0; i < 5; i++) {
State next;
if (current.boat == 1) {
next = newState(
current.ml - moves[i][0], current.cl - moves[i][1],
current.mr + moves[i][0], current.cr + moves[i][1], 0
);
} else {
next = newState(
current.ml + moves[i][0], current.cl + moves[i][1],
current.mr - moves[i][0], current.cr - moves[i][1], 1
);
}
if (isValid(next) && !visited[next.ml][next.cl][next.boat]) {
char move_desc[100];
getMoveDescription(current, next, move_desc);
TreeNode* child = createNode(next, node->depth + 1, move_desc);
addChild(node, child);
TreeNode* result = depthLimitedSearch(next, current, depth - 1, child, visited);
if (result != NULL) return result;
}
}
visited[current.ml][current.cl][current.boat] = false; // Backtrack
return NULL;
}
// BFS implementation with complete path tracking
TreeNode* bfs(State start) {
bool visited[4][4][2] = {false};
TreeNode* root = createNode(start, 0, "Start");
visited[start.ml][start.cl][start.boat] = true;
// Queue for BFS
TreeNode** queue = malloc(10000 * sizeof(TreeNode*));
int front = 0, rear = 0;
queue[rear++] = root;
TreeNode* goalNode = NULL; // Keep track of the goal node when found
while (front < rear && goalNode == NULL) {
TreeNode* current = queue[front++];
if (isGoal(current->state)) {
goalNode = current;
break;
}
int moves[][2] = {{1,0}, {2,0}, {0,1}, {0,2}, {1,1}};
for (int i = 0; i < 5; i++) {
State next;
if (current->state.boat == 1) {
next = newState(
current->state.ml - moves[i][0],
current->state.cl - moves[i][1],
current->state.mr + moves[i][0],
current->state.cr + moves[i][1],
0
);
} else {
next = newState(
current->state.ml + moves[i][0],
current->state.cl + moves[i][1],
current->state.mr - moves[i][0],
current->state.cr - moves[i][1],
1
);
}
if (isValid(next) && !visited[next.ml][next.cl][next.boat]) {
visited[next.ml][next.cl][next.boat] = true;
char move_desc[100];
getMoveDescription(current->state, next, move_desc);
TreeNode* child = createNode(next, current->depth + 1, move_desc);
addChild(current, child);
queue[rear++] = child;
}
}
}
free(queue);
return root; // Return the root node instead of the goal node
}
// Helper function to find goal node in the tree
TreeNode* findGoalNode(TreeNode* root) {
if (root == NULL) return NULL;
if (isGoal(root->state)) return root;
TreeNode* result = NULL;
for (int i = 0; i < root->num_children && result == NULL; i++) {
result = findGoalNode(root->children[i]);
}
return result;
}
// main function
int main() {
State initial = newState(3, 3, 0, 0, 1);
int choice, depth_limit;
printf("\n=== Missionaries and Cannibals Poblem Solver ===\n\n");
printf("Initial State: 3 Missionaries and 3 Cannibals on left bank\n");
printf("Goal State: All missionaries and cannibals must cross to right bank\n");
printf("Rule: Number of cannibals must not exceed missionaries on either bank\n\n");
printf("Choose your algorithm:\n");
printf("1. Depth First Search (DFS)\n");
printf("2. Breadth First Search (BFS)\n");
printf("3. Depth Limited Search\n");
printf("Enter choice (1-3): ");
scanf("%d", &choice);
TreeNode* root = NULL;
TreeNode* solution = NULL;
switch(choice) {
case 1: {
printf("\nSolving using Depth First Search...\n");
root = createNode(initial, 0, "Start");
bool visited[4][4][2] = {false};
solution = dfs(initial, initial, visited, root);
break;
}
case 2: {
printf("\nSolving using Breadth First Search...\n");
root = bfs(initial);
// Find solution node by traversing to a goal state
solution = findGoalNode(root);
break;
}
case 3: {
printf("Enter depth limit: ");
scanf("%d", &depth_limit);
printf("\nSolving using Depth Limited Search (limit: %d)...\n", depth_limit);
root = createNode(initial, 0, "Start");
bool visited[4][4][2] = {false};
solution = depthLimitedSearch(initial, initial, depth_limit, root, visited);
break;
}
default:
printf("Invalid choice!\n");
fclose(fp);
return 1;
}
if (solution != NULL) {
printf("\nSolution found! Here's the step by step solution:\n");
printStateLevelOrder(root);
printf("\nGoal state reached successfully!\n");
printf("Total steps: %d\n", solution->depth);
} else {
printf("\nNo solution found within the given constraints!\n");
if (choice == 3) {
printf("Try increasing the depth limit.\n");
}
}
fclose(fp);
return 0;
}
Raw
LAB3.c
/**
Informed Search Techniques BFS, A* & Hill Climbing
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#define GRID_SIZE 10
#define MAX_NODES 100
// Forward declaration
typedef struct Node Node;
// Represent a point/node in the grid
struct Node {
int x;
int y;
int f_score; // Total estimated cost
int g_score; // Cost from start to current node
int h_score; // Estimated cost from current to goal
Node* parent;
};
// Priority queue for open set
typedef struct {
Node* nodes[MAX_NODES];
int size;
} PriorityQueue;
// Grid representation
int grid[GRID_SIZE][GRID_SIZE] = {
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};
// Priority queue functions
void pq_init(PriorityQueue* pq) {
pq->size = 0;
}
void pq_push(PriorityQueue* pq, Node* node) {
if (pq->size >= MAX_NODES) return;
// Insert at the end and bubble up
int i = pq->size;
pq->nodes[i] = node;
pq->size++;
// Sort based on f_score
while (i > 0 && pq->nodes[(i-1)/2]->f_score > node->f_score) {
pq->nodes[i] = pq->nodes[(i-1)/2];
i = (i-1)/2;
}
pq->nodes[i] = node;
}
Node* pq_pop(PriorityQueue* pq) {
if (pq->size == 0) return NULL;
Node* top = pq->nodes[0];
pq->nodes[0] = pq->nodes[pq->size - 1];
pq->size--;
// Heapify down
int i = 0;
while (true) {
int smallest = i;
int left = 2*i + 1;
int right = 2*i + 2;
if (left < pq->size && pq->nodes[left]->f_score < pq->nodes[smallest]->f_score)
smallest = left;
if (right < pq->size && pq->nodes[right]->f_score < pq->nodes[smallest]->f_score)
smallest = right;
if (smallest == i) break;
// Swap
Node* temp = pq->nodes[i];
pq->nodes[i] = pq->nodes[smallest];
pq->nodes[smallest] = temp;
i = smallest;
}
return top;
}
// Heuristic function (Manhattan distance)
int heuristic(int x1, int y1, int x2, int y2) {
return abs(x1 - x2) + abs(y1 - y2);
}
// Check if a node is in the grid and walkable
bool is_valid_node(int x, int y) {
return x >= 0 && x < GRID_SIZE && y >= 0 && y < GRID_SIZE && grid[y][x] == 0;
}
// A* Search Algorithm
Node* a_star_search(int start_x, int start_y, int goal_x, int goal_y) {
PriorityQueue open_set;
pq_init(&open_set);
// Closed set (for visited nodes)
bool closed_set[GRID_SIZE][GRID_SIZE] = {false};
// Create start node
Node* start_node = malloc(sizeof(Node));
start_node->x = start_x;
start_node->y = start_y;
start_node->g_score = 0;
start_node->h_score = heuristic(start_x, start_y, goal_x, goal_y);
start_node->f_score = start_node->h_score;
start_node->parent = NULL;
pq_push(&open_set, start_node);
// Possible move directions (4-way movement)
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
while (open_set.size > 0) {
// Get the node with lowest f_score
Node* current = pq_pop(&open_set);
// Check if reached goal
if (current->x == goal_x && current->y == goal_y) {
return current;
}
// Mark as visited
closed_set[current->y][current->x] = true;
// Explore neighbors
for (int i = 0; i < 4; i++) {
int new_x = current->x + dx[i];
int new_y = current->y + dy[i];
// Skip invalid or visited nodes
if (!is_valid_node(new_x, new_y) || closed_set[new_y][new_x])
continue;
// Create neighbor node
Node* neighbor = malloc(sizeof(Node));
neighbor->x = new_x;
neighbor->y = new_y;
neighbor->g_score = current->g_score + 1;
neighbor->h_score = heuristic(new_x, new_y, goal_x, goal_y);
neighbor->f_score = neighbor->g_score + neighbor->h_score;
neighbor->parent = current;
pq_push(&open_set, neighbor);
}
}
// No path found
return NULL;
}
// Best First Search Algorithm
Node* best_first_search(int start_x, int start_y, int goal_x, int goal_y) {
PriorityQueue open_set;
pq_init(&open_set);
// Closed set (for visited nodes)
bool closed_set[GRID_SIZE][GRID_SIZE] = {false};
// Create start node
Node* start_node = malloc(sizeof(Node));
start_node->x = start_x;
start_node->y = start_y;
start_node->h_score = heuristic(start_x, start_y, goal_x, goal_y);
start_node->f_score = start_node->h_score; // Only use heuristic
start_node->parent = NULL;
pq_push(&open_set, start_node);
// Possible move directions (4-way movement)
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
while (open_set.size > 0) {
// Get the node with lowest heuristic score
Node* current = pq_pop(&open_set);
// Check if reached goal
if (current->x == goal_x && current->y == goal_y) {
return current;
}
// Mark as visited
closed_set[current->y][current->x] = true;
// Explore neighbors
for (int i = 0; i < 4; i++) {
int new_x = current->x + dx[i];
int new_y = current->y + dy[i];
// Skip invalid or visited nodes
if (!is_valid_node(new_x, new_y) || closed_set[new_y][new_x])
continue;
// Create neighbor node
Node* neighbor = malloc(sizeof(Node));
neighbor->x = new_x;
neighbor->y = new_y;
neighbor->h_score = heuristic(new_x, new_y, goal_x, goal_y);
neighbor->f_score = neighbor->h_score; // Only use heuristic
neighbor->parent = current;
pq_push(&open_set, neighbor);
}
}
// No path found
return NULL;
}
// Utility function to print the path
void print_path(Node* goal_node, bool print_grid) {
if (!goal_node) {
printf("No path found.\n");
return;
}
// Traverse back to start and store path
Node* current = goal_node;
int path[GRID_SIZE * GRID_SIZE][2];
int path_length = 0;
while (current) {
path[path_length][0] = current->x;
path[path_length][1] = current->y;
path_length++;
current = current->parent;
}
// Print coordinates
printf("Path found :\n");
for (int i = path_length - 1; i >= 0; i--) {
printf("(%d, %d) ", path[i][0], path[i][1]);
}
printf("\n");
// Print path on grid
if (print_grid) {
// Prepare grid copy
char grid_view[GRID_SIZE][GRID_SIZE];
for (int y = 0; y < GRID_SIZE; y++) {
for (int x = 0; x < GRID_SIZE; x++) {
// Copy original grid
grid_view[y][x] = grid[y][x] == 1 ? '#' : '.';
}
}
// Mark path
for (int i = 0; i < path_length; i++) {
int x = path[i][0];
int y = path[i][1];
grid_view[y][x] = (i == 0) ? 'S' : ((i == path_length-1) ? 'G' : 'O');
}
// Print grid
printf("\nPath Visualization:\n");
for (int y = 0; y < GRID_SIZE; y++) {
for (int x = 0; x < GRID_SIZE; x++) {
printf("%c ", grid_view[y][x]);
}
printf("\n");
}
// Print additional path details
printf("\nPath Details:\n");
printf("Path Length: %d\n", path_length);
printf("Start: (%d, %d)\n", path[path_length-1][0], path[path_length-1][1]);
printf("Goal: (%d, %d)\n", path[0][0], path[0][1]);
}
}
// Cleanup function to free memory
void cleanup_path(Node* goal_node) {
if (!goal_node) return;
Node* current = goal_node;
while (current) {
Node* parent = current->parent;
free(current);
current = parent;
}
}
// Hill Climbing Search Algorithm
Node* hill_climbing_search(int start_x, int start_y, int goal_x, int goal_y) {
// Create start node
Node* current = malloc(sizeof(Node));
current->x = start_x;
current->y = start_y;
current->g_score = 0;
current->h_score = heuristic(start_x, start_y, goal_x, goal_y);
current->f_score = current->h_score;
current->parent = NULL;
// Possible move directions (4-way movement)
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
// Keep track of visited nodes
bool visited[GRID_SIZE][GRID_SIZE] = {false};
visited[start_y][start_x] = true;
// Maintain path
typedef struct PathNode {
Node* node;
struct PathNode* next;
} PathNode;
PathNode* path = malloc(sizeof(PathNode));
path->node = current;
path->next = NULL;
PathNode* path_tail = path;
// Loop until we reach the goal or get stuck
while (current->x != goal_x || current->y != goal_y) {
// Find the best neighbor
Node* best_neighbor = NULL;
int best_score = INT_MAX;
for (int i = 0; i < 4; i++) {
int new_x = current->x + dx[i];
int new_y = current->y + dy[i];
// Skip invalid or visited nodes
if (!is_valid_node(new_x, new_y) || visited[new_y][new_x])
continue;
// Calculate score for this neighbor
int score = heuristic(new_x, new_y, goal_x, goal_y);
// If this neighbor is better than our current best
if (best_neighbor == NULL || score < best_score) {
// Free previous best if it exists
if (best_neighbor != NULL)
free(best_neighbor);
// Create new best neighbor
best_neighbor = malloc(sizeof(Node));
best_neighbor->x = new_x;
best_neighbor->y = new_y;
best_neighbor->g_score = current->g_score + 1;
best_neighbor->h_score = score;
best_neighbor->f_score = best_neighbor->h_score;
best_neighbor->parent = current;
best_score = score;
}
}
// If we have no better neighbors, we're stuck
if (best_neighbor == NULL) {
// Try to backtrack if possible
if (path->next != NULL) {
// Remove current node from path
PathNode* temp = path;
while (temp->next && temp->next->node != current)
temp = temp->next;
if (temp->next) {
PathNode* to_remove = temp->next;
temp->next = to_remove->next;
free(to_remove);
}
// Move to previous node
current = current->parent;
continue;
}
// If we can't backtrack, we failed
printf("Hill climbing got stuck. No path found.\n");
// Free the path linked list
while (path != NULL) {
PathNode* temp = path;
path = path->next;
free(temp);
}
return NULL;
}
// Move to the best neighbor
current = best_neighbor;
visited[current->y][current->x] = true;
// Add to path
path_tail->next = malloc(sizeof(PathNode));
path_tail = path_tail->next;
path_tail->node = current;
path_tail->next = NULL;
}
// We reached the goal! Return the goal node
Node* result = current;
// Free the path linked list (but not the nodes)
while (path != NULL) {
PathNode* temp = path;
path = path->next;
free(temp);
}
return result;
}
int main() {
int start_x = 0, start_y = 0;
int goal_x = 9, goal_y = 9;
printf("A* Search Path:\n");
Node* a_star_path = a_star_search(start_x, start_y, goal_x, goal_y);
print_path(a_star_path, true);
cleanup_path(a_star_path);
printf("\nBest First Search Path:\n");
Node* best_first_path = best_first_search(start_x, start_y, goal_x, goal_y);
print_path(best_first_path, true);
cleanup_path(best_first_path);
printf("\nHill Climbing Search Path:\n");
Node* hill_climbing_path = hill_climbing_search(start_x, start_y, goal_x, goal_y);
print_path(hill_climbing_path, true);
cleanup_path(hill_climbing_path);
return 0;
}
Raw
LAB4A.c
/**
8-Puzzle using A* algorithm
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
// Define the puzzle state
typedef struct {
int board[3][3];
int blank_row;
int blank_col;
int moves;
int manhattan_dist;
struct State* parent;
} State;
// Define the priority queue for A* search
typedef struct {
State** states;
int size;
int capacity;
} PriorityQueue;
// Function to create a new state
State* create_state(int board[3][3]) {
State* state = (State*)malloc(sizeof(State));
// Copy the board
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
state->board[i][j] = board[i][j];
// Find the blank position
if (board[i][j] == 0) {
state->blank_row = i;
state->blank_col = j;
}
}
}
state->moves = 0;
state->manhattan_dist = 0;
state->parent = NULL;
return state;
}
// Function to create a priority queue
PriorityQueue* create_queue(int capacity) {
PriorityQueue* queue = (PriorityQueue*)malloc(sizeof(PriorityQueue));
queue->states = (State**)malloc(capacity * sizeof(State*));
queue->size = 0;
queue->capacity = capacity;
return queue;
}
// Function to check if two states are equal
bool is_equal(State* a, State* b) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (a->board[i][j] != b->board[i][j]) {
return false;
}
}
}
return true;
}
// Function to compute Manhattan distance heuristic
int manhattan_distance(State* state, int goal[3][3]) {
int dist = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
int val = state->board[i][j];
if (val != 0) { // Skip the blank
// Find the position of val in the goal state
int goal_row, goal_col;
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
if (goal[r][c] == val) {
goal_row = r;
goal_col = c;
break;
}
}
}
// Add the Manhattan distance
dist += abs(i - goal_row) + abs(j - goal_col);
}
}
}
return dist;
}
// Function to insert a state into the priority queue
void insert_queue(PriorityQueue* queue, State* state) {
if (queue->size == queue->capacity) {
// Double the capacity if needed
queue->capacity *= 2;
queue->states = (State**)realloc(queue->states, queue->capacity * sizeof(State*));
}
// Insert the state at the end
queue->states[queue->size++] = state;
// Heapify up
int i = queue->size - 1;
while (i > 0) {
int parent = (i - 1) / 2;
int f1 = queue->states[i]->moves + queue->states[i]->manhattan_dist;
int f2 = queue->states[parent]->moves + queue->states[parent]->manhattan_dist;
if (f1 < f2) {
// Swap
State* temp = queue->states[i];
queue->states[i] = queue->states[parent];
queue->states[parent] = temp;
i = parent;
} else {
break;
}
}
}
// Function to remove and return the state with minimum f-value
State* pop_queue(PriorityQueue* queue) {
if (queue->size == 0) {
return NULL;
}
State* min_state = queue->states[0];
queue->states[0] = queue->states[--queue->size];
// Heapify down
int i = 0;
while (true) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int smallest = i;
if (left < queue->size) {
int f1 = queue->states[left]->moves + queue->states[left]->manhattan_dist;
int f2 = queue->states[smallest]->moves + queue->states[smallest]->manhattan_dist;
if (f1 < f2) {
smallest = left;
}
}
if (right < queue->size) {
int f1 = queue->states[right]->moves + queue->states[right]->manhattan_dist;
int f2 = queue->states[smallest]->moves + queue->states[smallest]->manhattan_dist;
if (f1 < f2) {
smallest = right;
}
}
if (smallest != i) {
// Swap
State* temp = queue->states[i];
queue->states[i] = queue->states[smallest];
queue->states[smallest] = temp;
i = smallest;
} else {
break;
}
}
return min_state;
}
// Function to check if a state is in the list
bool is_in_list(State** list, int size, State* state) {
for (int i = 0; i < size; i++) {
if (is_equal(list[i], state)) {
return true;
}
}
return false;
}
// Function to print a state
void print_state(State* state) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if(state->board[i][j] == 0) {
printf(" ", state->board[i][j]);
} else {
printf("%d ", state->board[i][j]);
}
}
printf("\n");
}
printf("\n");
}
// Function to check if a move is valid
bool is_valid_move(int row, int col) {
return row >= 0 && row < 3 && col >= 0 && col < 3;
}
// Function to generate the next state after a move
State* move(State* curr_state, int dr, int dc, int goal[3][3]) {
int new_row = curr_state->blank_row + dr;
int new_col = curr_state->blank_col + dc;
if (!is_valid_move(new_row, new_col)) {
return NULL;
}
// Create a new state
State* new_state = (State*)malloc(sizeof(State));
memcpy(new_state, curr_state, sizeof(State));
// Move the blank
new_state->board[curr_state->blank_row][curr_state->blank_col] =
curr_state->board[new_row][new_col];
new_state->board[new_row][new_col] = 0;
// Update the blank position
new_state->blank_row = new_row;
new_state->blank_col = new_col;
// Update the number of moves
new_state->moves = curr_state->moves + 1;
// Update the Manhattan distance
new_state->manhattan_dist = manhattan_distance(new_state, goal);
// Set the parent
new_state->parent = curr_state;
return new_state;
}
// Function to solve the 8-puzzle
void solve_8_puzzle(int initial[3][3], int goal[3][3]) {
// Create the initial state
State* initial_state = create_state(initial);
initial_state->manhattan_dist = manhattan_distance(initial_state, goal);
// Create the priority queue
PriorityQueue* open_list = create_queue(1000);
insert_queue(open_list, initial_state);
// Create the closed list
State** closed_list = (State**)malloc(1000 * sizeof(State*));
int closed_size = 0;
// Define the possible moves
int dr[] = {-1, 1, 0, 0}; // up, down, left, right
int dc[] = {0, 0, -1, 1};
// A* search
while (open_list->size > 0) {
// Get the state with the minimum f-value
State* current = pop_queue(open_list);
// Check if we've reached the goal
if (manhattan_distance(current, goal) == 0) {
printf("Solution found in %d moves!\n", current->moves);
// Reconstruct the path
int path_length = current->moves + 1;
State** path = (State**)malloc(path_length * sizeof(State*));
State* temp = current;
for (int i = path_length - 1; i >= 0; i--) {
path[i] = temp;
temp = temp->parent;
}
// Print the path
for (int i = 0; i < path_length; i++) {
printf("Step %d:\n", i);
print_state(path[i]);
}
free(path);
return;
}
// Add the current state to the closed list
closed_list[closed_size++] = current;
// Generate the next states
for (int i = 0; i < 4; i++) {
State* next_state = move(current, dr[i], dc[i], goal);
if (next_state != NULL) {
// Check if the state is already in the closed list
if (!is_in_list(closed_list, closed_size, next_state)) {
// Add the state to the open list
insert_queue(open_list, next_state);
} else {
free(next_state);
}
}
}
}
printf("No solution found.\n");
}
int main() {
// Define the initial state
int initial[3][3] = {
{1, 2, 3},
{4, 0, 6},
{7, 5, 8}
};
// Define the goal state
int goal[3][3] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 0}
};
printf("Initial state:\n");
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if(initial[i][j] == 0) {
printf(" ", initial[i][j]);
} else {
printf("%d ", initial[i][j]);
}
}
printf("\n");
}
printf("\n");
printf("Goal state:\n");
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if(goal[i][j] == 0) {
printf(" ", goal[i][j]);
} else {
printf("%d ", goal[i][j]);
}
}
printf("\n");
}
printf("\n");
solve_8_puzzle(initial, goal);
return 0;
}
Raw
LAB4B.c
/**
CSP Crypt-Arithmetic Problem using Backtracking
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <ctype.h>
#define MAX_WORD_LENGTH 10
#define MAX_WORDS 3
// Structure to represent a crypt arithmetic puzzle
typedef struct {
char* words[MAX_WORDS]; // Input words
char* result; // Result word
int word_count; // Number of words in the puzzle
char unique_chars[26]; // Unique characters in the puzzle
int unique_count; // Count of unique characters
} CryptPuzzle;
// Function to extract unique characters from the puzzle
void extract_unique_chars(CryptPuzzle* puzzle) {
bool char_seen[26] = {false};
puzzle->unique_count = 0;
// Reset unique characters array
memset(puzzle->unique_chars, 0, sizeof(puzzle->unique_chars));
// Collect all unique characters
for (int i = 0; i < puzzle->word_count; i++) {
for (int j = 0; puzzle->words[i][j]; j++) {
char c = toupper(puzzle->words[i][j]);
if (!char_seen[c - 'A']) {
puzzle->unique_chars[puzzle->unique_count++] = c;
char_seen[c - 'A'] = true;
}
}
}
// Check result word
for (int j = 0; puzzle->result[j]; j++) {
char c = toupper(puzzle->result[j]);
if (!char_seen[c - 'A']) {
puzzle->unique_chars[puzzle->unique_count++] = c;
char_seen[c - 'A'] = true;
}
}
}
// Function to convert word to number based on current digit mapping
long word_to_number(const char* word, int* digit_map) {
long number = 0;
for (int i = 0; word[i]; i++) {
int digit = digit_map[toupper(word[i]) - 'A'];
number = number * 10 + digit;
}
return number;
}
// Check if current digit assignment is valid
bool is_valid_assignment(CryptPuzzle* puzzle, int* digit_map) {
// Check for zero leading digit
for (int i = 0; i < puzzle->word_count; i++) {
if (digit_map[toupper(puzzle->words[i][0]) - 'A'] == 0) {
return false;
}
}
// Check result word leading digit
if (digit_map[toupper(puzzle->result[0]) - 'A'] == 0) {
return false;
}
// Check for unique digits
bool used_digits[10] = {false};
for (int i = 0; i < puzzle->unique_count; i++) {
int digit = digit_map[puzzle->unique_chars[i] - 'A'];
if (used_digits[digit]) {
return false;
}
used_digits[digit] = true;
}
// Calculate and verify the puzzle
long sum = 0;
for (int i = 0; i < puzzle->word_count; i++) {
sum += word_to_number(puzzle->words[i], digit_map);
}
long result = word_to_number(puzzle->result, digit_map);
return sum == result;
}
// Recursive backtracking to solve the puzzle
bool solve_cryptarithmetic(CryptPuzzle* puzzle, int* digit_map, int char_index) {
// Base case: all unique characters assigned
if (char_index == puzzle->unique_count) {
// Check if the current assignment satisfies the puzzle
if (is_valid_assignment(puzzle, digit_map)) {
// Print solution
printf("\nSolution Found:\n");
for (int i = 0; i < puzzle->unique_count; i++) {
printf(" %c = %d\n", puzzle->unique_chars[i],
digit_map[puzzle->unique_chars[i] - 'A']);
}
// Print equation
printf("\nEquation:\n");
for (int i = 0; i < puzzle->word_count; i++) {
long word_num = word_to_number(puzzle->words[i], digit_map);
printf(" %s = %ld\n", puzzle->words[i], word_num);
}
printf(" %s = %ld\n", puzzle->result,
word_to_number(puzzle->result, digit_map));
return true;
}
return false;
}
// Try digits 0-9 for the current character
char current_char = puzzle->unique_chars[char_index];
for (int digit = 0; digit <= 9; digit++) {
// Assign digit to current character
digit_map[current_char - 'A'] = digit;
// Recursively solve for next character
if (solve_cryptarithmetic(puzzle, digit_map, char_index + 1)) {
return true;
}
// Backtrack
digit_map[current_char - 'A'] = -1;
}
return false;
}
// Free allocated memory for the puzzle
void free_puzzle(CryptPuzzle* puzzle) {
for (int i = 0; i < puzzle->word_count; i++) {
free(puzzle->words[i]);
}
free(puzzle->result);
}
// Initialize the puzzle
void init_puzzle(CryptPuzzle* puzzle) {
puzzle->word_count = 0;
puzzle->result = NULL;
memset(puzzle->words, 0, sizeof(puzzle->words));
memset(puzzle->unique_chars, 0, sizeof(puzzle->unique_chars));
puzzle->unique_count = 0;
}
int main() {
CryptPuzzle puzzle;
init_puzzle(&puzzle);
// Input words and result
char input_words[MAX_WORDS][MAX_WORD_LENGTH];
char result_word[MAX_WORD_LENGTH];
// Get input from user
printf("Enter number of words (max %d): ", MAX_WORDS);
scanf("%d", &puzzle.word_count);
// Input words
for (int i = 0; i < puzzle.word_count; i++) {
printf("Enter word %d: ", i + 1);
scanf("%s", input_words[i]);
puzzle.words[i] = strdup(input_words[i]);
}
// Input result word
printf("Enter result word: ");
scanf("%s", result_word);
puzzle.result = strdup(result_word);
// Extract unique characters
extract_unique_chars(&puzzle);
// Check if too many unique characters
if (puzzle.unique_count > 10) {
printf("Too many unique characters. Maximum is 10.\n");
free_puzzle(&puzzle);
return 1;
}
// Digit mapping
int digit_map[26];
for (int i = 0; i < 26; i++) {
digit_map[i] = -1;
}
// Solve the puzzle
printf("\nSolving Crypt arithmetic Puzzle...\n");
bool found = solve_cryptarithmetic(&puzzle, digit_map, 0);
// Check if solution was found
if (!found) {
printf("No solution exists.\n");
}
// Free allocated memory
free_puzzle(&puzzle);
return 0;
}
Raw
LAB5.c
/**
N-Queens Problem
*/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
// Function to check if a queen can be placed at board[row][col]
bool isSafe(int **board, int row, int col, int n) {
// Check the column above
for (int i = 0; i < row; i++) {
if (board[i][col] == 1) {
return false;
}
}
// Check upper left diagonal
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 1) {
return false;
}
}
// Check upper right diagonal
for (int i = row, j = col; i >= 0 && j < n; i--, j++) {
if (board[i][j] == 1) {
return false;
}
}
return true;
}
// Recursive function to solve N Queen problem
bool solveNQueenUtil(int **board, int row, int n) {
// Base case: If all queens are placed, return true
if (row >= n) {
return true;
}
// Try placing queen in each column of current row
for (int col = 0; col < n; col++) {
// Check if queen can be placed at board[row][col]
if (isSafe(board, row, col, n)) {
// Place the queen
board[row][col] = 1;
// Recursively place rest of the queens
if (solveNQueenUtil(board, row + 1, n)) {
return true;
}
// If placing queen doesn't lead to a solution, backtrack
board[row][col] = 0; // Backtrack
}
}
// If queen cannot be placed in any column in this row
return false;
}
// Function to solve N Queen problem
void solveNQueen(int n) {
// Allocate 2D board memory
int **board = (int **)malloc(n * sizeof(int *));
for (int i = 0; i < n; i++) {
board[i] = (int *)malloc(n * sizeof(int));
// Initialize board with zeros
for (int j = 0; j < n; j++) {
board[i][j] = 0;
}
}
if (solveNQueenUtil(board, 0, n)) {
// Print the solution
printf("Solution exists:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", board[i][j]);
}
printf("\n");
}
} else {
printf("Solution does not exist.\n");
}
// Free allocated memory
for (int i = 0; i < n; i++) {
free(board[i]);
}
free(board);
}
// Main function
int main() {
int n;
printf("Enter the number of queens: ");
scanf("%d", &n);
solveNQueen(n);
return 0;
}
Raw
LAB6.c
/**
Graph-Coloring Problem
*/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
// Function to check if a color can be assigned
bool isSafe(int vertex, int graph[100][100], int color[], int c, int V) {
for (int i = 0; i < V; i++) {
// Check if the adjacent vertex has the same color
if (graph[vertex][i] && c == color[i]) {
return false;
}
}
return true;
}
// Recursive function to solve graph coloring
bool graphColoringUtil(int graph[100][100], int m, int color[], int vertex, int V) {
// Base case: If all vertices are colored
if (vertex == V) {
return true;
}
// Try different colors for vertex
for (int c = 1; c <= m; c++) {
// Check if color c can be assigned to vertex
if (isSafe(vertex, graph, color, c, V)) {
color[vertex] = c;
// Recursively color rest of the vertices
if (graphColoringUtil(graph, m, color, vertex + 1, V)) {
return true;
}
// If coloring doesn't lead to a solution, backtrack
color[vertex] = 0;
}
}
// If no color can be assigned to this vertex
return false;
}
// Function to solve graph coloring problem
void graphColoring(int graph[100][100], int m, int V) {
// Initialize color array with 0 (no color)
int *color = (int *)malloc(V * sizeof(int));
for (int i = 0; i < V; i++) {
color[i] = 0;
}
// Call the recursive utility function
if (graphColoringUtil(graph, m, color, 0, V)) {
printf("Solution exists. The colors assigned to vertices are:\n");
for (int i = 0; i < V; i++) {
printf("Vertex %d: Color %d\n", i, color[i]);
}
} else {
printf("Solution does not exist. Cannot color the graph with %d colors.\n", m);
}
free(color);
}
int main() {
int V, E, m;
int graph[100][100] = {0};
printf("Enter the number of vertices: ");
scanf("%d", &V);
printf("Enter the number of edges: ");
scanf("%d", &E);
printf("Enter the edges (vertex pairs, 0-indexed):\n");
for (int i = 0; i < E; i++) {
int u, v;
scanf("%d %d", &u, &v);
// Since it's an undirected graph
graph[u][v] = 1;
graph[v][u] = 1;
}
printf("Enter the number of colors: ");
scanf("%d", &m);
graphColoring(graph, m, V);
return 0;
}
Raw
LAB7.c
/**
AO* Implementation for Pathfinding
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#include <limits.h>
#define GRID_SIZE 10
#define MAX_NODES 100
#define MAX_CHILDREN 4 // For 4-way movement
// Forward declaration
typedef struct Node Node;
typedef struct HyperNode HyperNode;
// Represent a point/node in the grid
struct Node {
int x;
int y;
int f_score; // Total estimated cost
int g_score; // Cost from start to current node
int h_score; // Estimated cost from current to goal
Node* parent;
};
// HyperNode for AO* (represents AND-OR nodes)
struct HyperNode {
int x;
int y;
bool is_solved; // Whether this node is part of solution
bool is_expanded; // Whether this node has been expanded
int cost; // Cost to reach this node
int h_score; // Heuristic value
HyperNode* parent; // Parent node
HyperNode* children[MAX_CHILDREN]; // Child nodes
int num_children; // Number of children
bool is_and_node; // Whether this is an AND node (all children must be traversed)
// For this pathfinding problem, we'll use OR nodes
};
// Grid representation
int grid[GRID_SIZE][GRID_SIZE] = {
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};
// Heuristic function (Manhattan distance)
int heuristic(int x1, int y1, int x2, int y2) {
return abs(x1 - x2) + abs(y1 - y2);
}
// Check if a node is in the grid and walkable
bool is_valid_node(int x, int y) {
return x >= 0 && x < GRID_SIZE && y >= 0 && y < GRID_SIZE && grid[y][x] == 0;
}
// Create a new HyperNode
HyperNode* create_hyper_node(int x, int y, HyperNode* parent, int goal_x, int goal_y) {
HyperNode* node = (HyperNode*) malloc(sizeof(HyperNode));
node->x = x;
node->y = y;
node->is_solved = false;
node->is_expanded = false;
node->cost = (parent == NULL) ? 0 : parent->cost + 1; // Cost is distance from start
node->h_score = heuristic(x, y, goal_x, goal_y);
node->parent = parent;
node->num_children = 0;
node->is_and_node = false; // In this problem, we're using OR nodes
return node;
}
// Find a HyperNode in the graph by coordinates
HyperNode* find_node(HyperNode* root, int x, int y) {
if (root == NULL) {
return NULL;
}
if (root->x == x && root->y == y) {
return root;
}
// Search through children
for (int i = 0; i < root->num_children; i++) {
HyperNode* found = find_node(root->children[i], x, y);
if (found != NULL) {
return found;
}
}
return NULL;
}
// Expand a HyperNode to generate its children
void expand_node(HyperNode* node, int goal_x, int goal_y, bool visited[GRID_SIZE][GRID_SIZE]) {
if (node->is_expanded) {
return;
}
// Possible move directions (4-way movement)
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
// Generate children
for (int i = 0; i < 4; i++) {
int new_x = node->x + dx[i];
int new_y = node->y + dy[i];
// Skip invalid or visited nodes
if (!is_valid_node(new_x, new_y) || visited[new_y][new_x]) {
continue;
}
// Create child node
HyperNode* child = create_hyper_node(new_x, new_y, node, goal_x, goal_y);
// If this is the goal, mark it as solved
if (new_x == goal_x && new_y == goal_y) {
child->is_solved = true;
}
// Add to children array
if (node->num_children < MAX_CHILDREN) {
node->children[node->num_children++] = child;
}
// Mark visited
visited[new_y][new_x] = true;
}
node->is_expanded = true;
}
// Revise the cost and solution status of nodes in the graph
void revise_costs(HyperNode* node) {
if (node == NULL || !node->is_expanded || node->is_solved) {
return;
}
// If this is an AND node, all children must be solved
if (node->is_and_node) {
bool all_solved = true;
int total_cost = 0;
for (int i = 0; i < node->num_children; i++) {
if (!node->children[i]->is_solved) {
all_solved = false;
break;
}
total_cost += node->children[i]->cost;
}
if (all_solved) {
node->is_solved = true;
node->cost = total_cost;
}
}
// For OR nodes, at least one child must be solved
else {
int min_cost = INT_MAX;
bool any_solved = false;
for (int i = 0; i < node->num_children; i++) {
if (node->children[i]->is_solved) {
any_solved = true;
if (node->children[i]->cost < min_cost) {
min_cost = node->children[i]->cost;
}
}
}
if (any_solved) {
node->is_solved = true;
node->cost = min_cost + 1; // Add 1 for the cost of moving to this node
}
}
}
// Find the best unsolved leaf node in the graph
HyperNode* find_best_leaf(HyperNode* node, bool visited[GRID_SIZE][GRID_SIZE]) {
if (node == NULL) {
return NULL;
}
// If this is a leaf (not expanded) and not solved, return it
if (!node->is_expanded && !node->is_solved && !visited[node->y][node->x]) {
return node;
}
// If this node is solved, don't explore its children
if (node->is_solved) {
return NULL;
}
// Find the best child
HyperNode* best_leaf = NULL;
int best_score = INT_MAX;
for (int i = 0; i < node->num_children; i++) {
visited[node->y][node->x] = true;
HyperNode* leaf = find_best_leaf(node->children[i], visited);
visited[node->y][node->x] = false;
if (leaf != NULL) {
int f_score = leaf->cost + leaf->h_score;
if (best_leaf == NULL || f_score < best_score) {
best_leaf = leaf;
best_score = f_score;
}
}
}
return best_leaf;
}
// AO* Search Algorithm
HyperNode* ao_star_search(int start_x, int start_y, int goal_x, int goal_y) {
// Create the root node
HyperNode* root = create_hyper_node(start_x, start_y, NULL, goal_x, goal_y);
// If start is goal, return immediately
if (start_x == goal_x && start_y == goal_y) {
root->is_solved = true;
return root;
}
// Keep track of visited nodes
bool visited[GRID_SIZE][GRID_SIZE] = {false};
visited[start_y][start_x] = true;
// Main loop
while (!root->is_solved) {
// Reset visited array for finding best leaf
bool leaf_visited[GRID_SIZE][GRID_SIZE] = {false};
// Find the best unsolved leaf node
HyperNode* best_leaf = find_best_leaf(root, leaf_visited);
// If no more leaves to expand, no solution exists
if (best_leaf == NULL) {
printf("No solution exists.\n");
return NULL;
}
// Expand the best leaf
expand_node(best_leaf, goal_x, goal_y, visited);
// Revise costs up the tree
HyperNode* current = best_leaf;
while (current != NULL) {
revise_costs(current);
current = current->parent;
}
}
return root;
}
// Utility function to extract path from solved AO* graph
void extract_path(HyperNode* node, int goal_x, int goal_y, int path[][2], int* path_length) {
if (node == NULL) {
return;
}
// Add this node to the path
path[*path_length][0] = node->x;
path[*path_length][1] = node->y;
(*path_length)++;
// If this is the goal, we're done
if (node->x == goal_x && node->y == goal_y) {
return;
}
// Find the best child (with lowest cost)
HyperNode* best_child = NULL;
int best_cost = INT_MAX;
for (int i = 0; i < node->num_children; i++) {
if (node->children[i]->is_solved && node->children[i]->cost < best_cost) {
best_child = node->children[i];
best_cost = node->children[i]->cost;
}
}
// Recursively extract path from best child
if (best_child != NULL) {
extract_path(best_child, goal_x, goal_y, path, path_length);
}
}
// Utility function to print the path
void print_ao_star_path(HyperNode* root_node, int goal_x, int goal_y, bool print_grid) {
if (!root_node || !root_node->is_solved) {
printf("No path found.\n");
return;
}
// Extract the path
int path[GRID_SIZE * GRID_SIZE][2];
int path_length = 0;
extract_path(root_node, goal_x, goal_y, path, &path_length);
// Print coordinates
printf("Path found :\n");
for (int i = 0; i < path_length; i++) {
printf("(%d, %d) ", path[i][0], path[i][1]);
}
printf("\n");
// Print path on grid
if (print_grid) {
// Prepare grid copy
char grid_view[GRID_SIZE][GRID_SIZE];
for (int y = 0; y < GRID_SIZE; y++) {
for (int x = 0; x < GRID_SIZE; x++) {
// Copy original grid
grid_view[y][x] = grid[y][x] == 1 ? '#' : '.';
}
}
// Mark path
for (int i = 0; i < path_length; i++) {
int x = path[i][0];
int y = path[i][1];
grid_view[y][x] = (i == 0) ? 'S' : ((i == path_length-1) ? 'G' : 'O');
}
// Print grid
printf("\nPath Visualization:\n");
for (int y = 0; y < GRID_SIZE; y++) {
for (int x = 0; x < GRID_SIZE; x++) {
printf("%c ", grid_view[y][x]);
}
printf("\n");
}
// Print additional path details
printf("\nPath Details:\n");
printf("Path Length: %d\n", path_length);
printf("Start: (%d, %d)\n", path[0][0], path[0][1]);
printf("Goal: (%d, %d)\n", path[path_length-1][0], path[path_length-1][1]);
}
}
// Free the memory allocated for the AO* graph
void cleanup_ao_star_graph(HyperNode* node) {
if (node == NULL) {
return;
}
// Recursively free all children
for (int i = 0; i < node->num_children; i++) {
cleanup_ao_star_graph(node->children[i]);
}
// Free this node
free(node);
}
int main() {
int start_x = 0, start_y = 0;
int goal_x = 9, goal_y = 9;
printf("AO* Search Path:\n");
HyperNode* ao_star_result = ao_star_search(start_x, start_y, goal_x, goal_y);
print_ao_star_path(ao_star_result, goal_x, goal_y, true);
cleanup_ao_star_graph(ao_star_result);
return 0;
}
Raw
PlainBFSDFS.c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Structure for the graph
typedef struct Graph {
int vertices;
int** adjacencyMatrix;
} Graph;
// Structure for queue used in BFS
typedef struct Queue {
int front, rear, size;
unsigned capacity;
int* array;
} Queue;
// Create a new graph with v vertices
Graph* createGraph(int v) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->vertices = v;
// Create adjacency matrix
graph->adjacencyMatrix = (int**)malloc(v * sizeof(int*));
for (int i = 0; i < v; i++) {
graph->adjacencyMatrix[i] = (int*)malloc(v * sizeof(int));
for (int j = 0; j < v; j++) {
graph->adjacencyMatrix[i][j] = 0;
}
}
return graph;
}
// Add an edge to the graph
void addEdge(Graph* graph, int src, int dest) {
// Add edge from src to dest
graph->adjacencyMatrix[src][dest] = 1;
// Add edge from dest to src for undirected graph
graph->adjacencyMatrix[dest][src] = 1;
}
// Create a new queue
Queue* createQueue(unsigned capacity) {
Queue* queue = (Queue*)malloc(sizeof(Queue));
queue->capacity = capacity;
queue->front = queue->size = 0;
queue->rear = capacity - 1;
queue->array = (int*)malloc(queue->capacity * sizeof(int));
return queue;
}
// Check if queue is full
bool isQueueFull(Queue* queue) {
return (queue->size == queue->capacity);
}
// Check if queue is empty
bool isQueueEmpty(Queue* queue) {
return (queue->size == 0);
}
// Add an item to queue
void enqueue(Queue* queue, int item) {
if (isQueueFull(queue))
return;
queue->rear = (queue->rear + 1) % queue->capacity;
queue->array[queue->rear] = item;
queue->size = queue->size + 1;
}
// Remove an item from queue
int dequeue(Queue* queue) {
if (isQueueEmpty(queue))
return -1;
int item = queue->array[queue->front];
queue->front = (queue->front + 1) % queue->capacity;
queue->size = queue->size - 1;
return item;
}
// Breadth First Search
void BFS(Graph* graph, int startVertex) {
// Create a visited array
bool* visited = (bool*)malloc(graph->vertices * sizeof(bool));
for (int i = 0; i < graph->vertices; i++)
visited[i] = false;
// Create a queue for BFS
Queue* queue = createQueue(graph->vertices);
// Mark the current node as visited and enqueue it
visited[startVertex] = true;
enqueue(queue, startVertex);
printf("Breadth First Traversal starting from vertex %d: ", startVertex);
while (!isQueueEmpty(queue)) {
// Dequeue a vertex and print it
int currentVertex = dequeue(queue);
printf("%d ", currentVertex);
// Get all adjacent vertices of the dequeued vertex
// If an adjacent vertex is not visited, mark it visited and enqueue it
for (int i = 0; i < graph->vertices; i++) {
if (graph->adjacencyMatrix[currentVertex][i] == 1 && !visited[i]) {
visited[i] = true;
enqueue(queue, i);
}
}
}
printf("\n");
free(visited);
free(queue->array);
free(queue);
}
// Recursive helper function for DFS
void DFSUtil(Graph* graph, int vertex, bool* visited) {
// Mark the current node as visited and print it
visited[vertex] = true;
printf("%d ", vertex);
// Recur for all the adjacent vertices
for (int i = 0; i < graph->vertices; i++) {
if (graph->adjacencyMatrix[vertex][i] == 1 && !visited[i])
DFSUtil(graph, i, visited);
}
}
// Depth First Search
void DFS(Graph* graph, int startVertex) {
// Create a visited array
bool* visited = (bool*)malloc(graph->vertices * sizeof(bool));
for (int i = 0; i < graph->vertices; i++)
visited[i] = false;
// Call the recursive helper function
printf("Depth First Traversal starting from vertex %d: ", startVertex);
DFSUtil(graph, startVertex, visited);
printf("\n");
free(visited);
}
// Main function to demonstrate BFS and DFS
int main() {
// Create a graph with 6 vertices
Graph* graph = createGraph(6);
// Add edges
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 4);
addEdge(graph, 3, 5);
addEdge(graph, 4, 5);
// Perform BFS starting from vertex 0
BFS(graph, 0);
// Perform DFS starting from vertex 0
DFS(graph, 0);
// Free allocated memory
for (int i = 0; i < graph->vertices; i++)
free(graph->adjacencyMatrix[i]);
free(graph->adjacencyMatrix);
free(graph);
return 0;
}
Raw
prolog.pl
% Preferences and Strengths
preference(ravi, analytical).
preference(ravi, tech_savvy).
preference(ravi, problem_solving).
preference(ravi, solitary).
preference(ravi, structured).
preference(sona, artistic).
preference(sona, creative).
preference(sona, communication).
preference(sona, social).
preference(sona, unstructured).
preference(amit, tech_savvy).
preference(amit, communication).
preference(amit, structured).
preference(amit, teamwork).
% Career rules
career(Person, software_engineer) :-
preference(Person, tech_savvy),
preference(Person, problem_solving),
preference(Person, analytical).
career(Person, data_analyst) :-
preference(Person, analytical),
preference(Person, structured),
preference(Person, tech_savvy).
career(Person, graphic_designer) :-
preference(Person, artistic),
preference(Person, creative),
preference(Person, unstructured).
career(Person, marketing_manager) :-
preference(Person, communication),
preference(Person, social),
preference(Person, creative).
career(Person, project_manager) :-
preference(Person, communication),
preference(Person, structured),
preference(Person, teamwork).
% Main entry point
:- initialization(main).
main :-
( career(sona, Career) ->
format("Ravi is suitable for: ~w~n", [Career])
;
write('No matching career found for Ravi.')
).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment