TIC TAC TOE

#include <iostream>
using namespace std;

char board[3][3] = { {' ', ' ', ' '}, {' ', ' ', ' '}, {' ', ' ', ' '} };
char currentMarker;
int currentPlayer;

void drawBoard() {
cout << "\n";
for (int i = 0; i < 3; i++) {
cout << " ";
for (int j = 0; j < 3; j++) {
cout << board[i][j];
if (j < 2) cout << " | ";
}
cout << "\n";
if (i < 2) cout << "---|---|---\n";
}
cout << "\n";
}

bool placeMarker(int slot) {

int row = (slot - 1) / 3;
int col = (slot - 1) % 3;

if (board[row][col] == ' ') {

board[row][col] = currentMarker;
return true;
} else {
return false;
}
}

int winner() {
for (int i = 0; i < 3; i++) {
if ((board[i][0] == board[i][1] && board[i][1] == board[i][2] && board[i][0] != ' ') ||
(board[0][i] == board[1][i] && board[1][i] == board[2][i] && board[0][i] != ' ')) {
return currentPlayer;
}
}

if ((board[0][0] == board[1][1] && board[1][1] == board[2][2] && board[0][0] != ' ') ||

(board[0][2] == board[1][1] && board[1][1] == board[2][0] && board[0][2] != ' ')) {
return currentPlayer;
}

return 0;
}

void swapPlayerAndMarker() {
if (currentMarker == 'X') currentMarker = 'O';
else currentMarker = 'X';

currentPlayer = (currentPlayer == 1) ? 2 : 1;
}
void printSlotGuide() {
cout << "\nSLOT GUIDE:\n";
int count = 1;
for (int i = 0; i < 3; i++) {
cout << " ";
for (int j = 0; j < 3; j++) {
cout << count++;
if (j < 2) cout << " | ";
}
cout << "\n";
if (i < 2) cout << "---|---|---\n";
}
cout << "\n";
}

int main() {
cout << "TIC TAC TOE\n";
cout << "Player 1, choose your marker (X or O): ";
cin >> currentMarker;

currentPlayer = 1;

int slot;
int moves = 0;

printSlotGuide();

while (true) {
drawBoard();
cout << "Player " << currentPlayer << ", enter your move (1-9): ";
cin >> slot;

if (slot < 1 || slot > 9) {

cout << "Invalid move. Try again.\n";
continue;
}

if (!placeMarker(slot)) {
cout << "Slot already taken. Try again.\n";
continue;
}

moves++;

if (winner() == currentPlayer) {
drawBoard();
cout << "Player " << currentPlayer << " wins!\n";
break;
} else if (moves == 9) {
drawBoard();
cout << "It's a draw!\n";
break;
}

swapPlayerAndMarker();
}
 return 0;
}

8 PUZZLE PROB
#include <iostream>
#include <vector>
#include <set>
#include <stack>

using namespace std;

#define N 3

struct PuzzleState {
vector<vector<int>> board;
int x, y;
int depth;

PuzzleState(vector<vector<int>> b, int i, int j, int d) : board(b), x(i), y(j), depth(d) {}

};

int row[] = {0, 0, -1, 1};

int col[] = {-1, 1, 0, 0};

bool isGoalState(vector<vector<int>>& board) {

vector<vector<int>> goal = {{1, 2, 3}, {4, 5, 6}, {7, 8, 0}};
return board == goal;
}

bool isValid(int x, int y) {

return (x >= 0 && x < N && y >= 0 && y < N);
}

void printBoard(vector<vector<int>>& board) {

for (auto& row : board) {
for (auto& num : row)
cout << (num == 0 ? "_" : to_string(num)) << " ";
cout << endl;
}
cout << "--------" << endl;
}

void solvePuzzleDFS(vector<vector<int>>& start, int x, int y) {

stack<PuzzleState> st;
set<vector<vector<int>>> visited;

st.push(PuzzleState(start, x, y, 0));
visited.insert(start);

while (!st.empty()) {
PuzzleState curr = st.top();
st.pop();

cout << "Depth: " << curr.depth << endl;

printBoard(curr.board);
 if (isGoalState(curr.board)) {
cout << "Goal state reached at depth " << curr.depth << endl;
return;
}

if (curr.depth >= 5) continue;

for (int i = 0; i < 4; i++) {

int newX = curr.x + row[i];
int newY = curr.y + col[i];

if (isValid(newX, newY)) {
vector<vector<int>> newBoard = curr.board;
swap(newBoard[curr.x][curr.y], newBoard[newX][newY]);

if (visited.find(newBoard) == visited.end()) {
visited.insert(newBoard);
st.push(PuzzleState(newBoard, newX, newY, curr.depth + 1));
}
}
}
}

cout << "Goal state not reached within depth 5." << endl;
}

int main() {
vector<vector<int>> start = {{1, 2, 3}, {4, 0, 6}, {7, 5, 8}};
int x = 1, y = 1;

cout << "Initial State: " << endl;

printBoard(start);

solvePuzzleDFS(start, x, y);

return 0;
}
WATER JUG PROB
#include <iostream>
#include <queue>
#include <unordered_set>
#include <tuple>
#include <vector>
#include <algorithm> // Include this header for __gcd

using namespace std;

struct JugState {
int jug1, jug2;
string action; // Stores the action taken to reach this state
JugState(int j1, int j2, string act) : jug1(j1), jug2(j2), action(act) {}
};

bool isGoalState(int jug1, int jug2, int z) {

return jug1 == z || jug2 == z;
}

void printSolution(const vector<JugState>& steps) {

cout << "Solution steps: " << endl;
cout << "Start -> ";
for (int i = 0; i < steps.size(); ++i) {
cout << steps[i].action;
if (i != steps.size() - 1) cout << " -> ";
}
cout << endl;
}

void bfs(int x, int y, int z) {

queue<JugState> q;
unordered_set<string> visited;
vector<JugState> steps; // To store the steps

q.push(JugState(0, 0, "start"));
visited.insert("0,0");

while (!q.empty()) {
JugState current = q.front();
q.pop();

int jug1 = current.jug1;

int jug2 = current.jug2;

// If we have reached the goal state

if (isGoalState(jug1, jug2, z)) {
steps.push_back(current); // Add the goal state to the steps
printSolution(steps); // Print solution
return;
}

vector<pair<JugState, string>> nextStates;

// Define the possible actions

nextStates.push_back({JugState(x, jug2, "fill B"), "fill B"});
nextStates.push_back({JugState(jug1, y, "fill A"), "fill A"});
 nextStates.push_back({JugState(0, jug2, "empty B"), "empty B"});
nextStates.push_back({JugState(jug1, 0, "empty A"), "empty A"});

int pour1to2 = min(jug1, y - jug2);

nextStates.push_back({JugState(jug1 - pour1to2, jug2 + pour1to2, "pour A to B"), "pour A to B"});

int pour2to1 = min(jug2, x - jug1);

nextStates.push_back({JugState(jug1 + pour2to1, jug2 - pour2to1, "pour B to A"), "pour B to A"});

// Explore all the possible next states

for (auto& nextState : nextStates) {
string stateStr = to_string(nextState.first.jug1) + "," + to_string(nextState.first.jug2);
if (visited.find(stateStr) == visited.end()) {
visited.insert(stateStr);
q.push(nextState.first);
// Track the steps by adding the action
nextState.first.action = current.action + " -> " + nextState.second;
steps.push_back(nextState.first); // Add state to steps
}
}
}

cout << "No solution found." << endl;

}

int main() {
int x, y, z;
cout << "Enter capacity of jug 1: ";
cin >> x;
cout << "Enter capacity of jug 2: ";
cin >> y;
cout << "Enter the desired amount of water: ";
cin >> z;

if (z > max(x, y)) {

cout << "Desired amount is greater than both jug capacities." << endl;
return 0;
}

if (z % __gcd(x, y) != 0) { // Now it should work

cout << "No solution possible using the given jugs." << endl;
return 0;
}

bfs(x, y, z);
return 0;
}
BFS
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Graph {
int V; // Number of vertices
vector<vector<int>> adj; // Adjacency list

public:
// Constructor
Graph(int V) {
this->V = V;
adj.resize(V);
}

// Add edge to the graph (undirected)

void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u); // For undirected graph
}

// BFS traversal starting from the node 'start'

void BFS(int start) {
vector<bool> visited(V, false); // To keep track of visited nodes
queue<int> q;
visited[start] = true;
q.push(start);

while (!q.empty()) {
int node = q.front(); // Get the front element
q.pop();
cout << node << " "; // Print the current node

// Visit all the neighbors of the current node

for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
};

int main() {
Graph g(6);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 4);
g.addEdge(3, 5);
g.addEdge(4, 5);

cout << "BFS Traversal starting from node 0: ";

 g.BFS(0);
cout << endl;

return 0;
}

DFS
#include <iostream>
#include <vector>
using namespace std;

class Graph {
int V;
vector<vector<int>> adj;

public:
Graph(int V) {
this->V = V;
adj.resize(V);
}

void addEdge(int u, int v) {

adj[u].push_back(v);
adj[v].push_back(u);
}

void DFSUtil(int node, vector<bool>& visited) {

visited[node] = true;
cout << node << " ";
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
DFSUtil(neighbor, visited);
}
}
}

void DFS(int start) {

vector<bool> visited(V, false);
DFSUtil(start, visited);
}
};

int main() {
Graph g(6);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 4);
g.addEdge(3, 5);
g.addEdge(4, 5);

cout << "DFS Traversal starting from node 0: ";

g.DFS(0);
cout << endl;
 return 0;
}

A*
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define ROW 5
#define COL 5

typedef struct {
int x, y;
} Point;

typedef struct Node {

Point position;
int g, h, f;
struct Node* parent;
} Node;

int heuristic(Point a, Point b) {

return abs(a.x - b.x) + abs(a.y - b.y);
}

int isValid(int grid[ROW][COL], int x, int y) {

return (x >= 0 && x < ROW && y >= 0 && y < COL && grid[x][y] == 0);
}

void printPath(Node* node) {

if (node == NULL) return;
printPath(node->parent);
printf("(%d, %d) -> ", node->position.x, node->position.y);
}

void aStar(int grid[ROW][COL], Point start, Point goal) {

Node* openList[ROW * COL];
int openCount = 0;
Node* closedList[ROW * COL];
int closedCount = 0;

Node* startNode = (Node*)malloc(sizeof(Node));

startNode->position = start;
startNode->g = 0;
startNode->h = heuristic(start, goal);
startNode->f = startNode->g + startNode->h;
startNode->parent = NULL;
openList[openCount++] = startNode;

int dx[] = {-1, 1, 0, 0};

int dy[] = {0, 0, -1, 1};

while (openCount > 0) {

Node* current = openList[0];
int currentIndex = 0;
 for (int i = 1; i < openCount; i++) {
if (openList[i]->f < current->f) {
current = openList[i];
currentIndex = i;
}
}

openList[currentIndex] = openList[--openCount];
closedList[closedCount++] = current;

if (current->position.x == goal.x && current->position.y == goal.y) {

printf("Shortest Path: ");
printPath(current);
printf("Goal Reached\n");
return;
}

for (int i = 0; i < 4; i++) {

int newX = current->position.x + dx[i];
int newY = current->position.y + dy[i];

if (isValid(grid, newX, newY)) {

Node* neighbor = (Node*)malloc(sizeof(Node));
neighbor->position.x = newX;
neighbor->position.y = newY;
neighbor->g = current->g + 1;
neighbor->h = heuristic(neighbor->position, goal);
neighbor->f = neighbor->g + neighbor->h;
neighbor->parent = current;
openList[openCount++] = neighbor;
}
}
}

printf("No Path Found\n");

}

int main() {
int grid[ROW][COL] = {
{0, 1, 0, 0, 0},
{0, 1, 0, 1, 0},
{0, 0, 0, 1, 0},
{0, 1, 1, 1, 0},
{0, 0, 0, 0, 0}
};

Point start = {0, 0};

Point goal = {4, 4};

aStar(grid, start, goal);

return 0;
}
AO*
#include <iostream>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <algorithm>

using namespace std;

class Graph {
private:
unordered_map<int, vector<int>> adjList;

public:
void addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u);
}

void bfs(int start, int goal) {

queue<int> q;
unordered_map<int, int> parent;
unordered_set<int> visited;
unordered_map<int, int> cost;

q.push(start);
visited.insert(start);
parent[start] = -1;
cost[start] = 0;

while (!q.empty()) {
int node = q.front();
q.pop();

if (node == goal) {
vector<int> path;
int totalCost = cost[node];
while (node != -1) {
path.push_back(node);
node = parent[node];
}
reverse(path.begin(), path.end());

cout << "Optimal cost: " << totalCost << endl;

cout << "Solution path: " << endl;
for (int i : path) {
cout << "Node " << i << " solved with cost " << cost[i] << endl;
}
return;
}

for (int neighbor : adjList[node]) {

if (visited.find(neighbor) == visited.end()) {
q.push(neighbor);
visited.insert(neighbor);
parent[neighbor] = node;
 cost[neighbor] = cost[node] + 1;
}
}
}

cout << "No path found from " << start << " to " << goal << endl;
}
};

int main() {
Graph g;

g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(2, 5);
g.addEdge(3, 6);

int start, goal;

cout << "Enter the start node: ";
cin >> start;
cout << "Enter the goal node: ";
cin >> goal;

g.bfs(start, goal);

return 0;
}
HILL CLIMB ALGO
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define ROW 5
#define COL 5

typedef struct {
int x, y;
} Point;

int grid[ROW][COL] = {
{0, 1, 0, 0, 0},
{0, 1, 0, 1, 0},
{0, 0, 0, 1, 0},
{0, 1, 1, 1, 0},
{0, 0, 0, 0, 0}
};

int dx[] = {-1, 1, 0, 0};

int dy[] = {0, 0, -1, 1};

int isValid(int x, int y) {

return (x >= 0 && x < ROW && y >= 0 && y < COL && grid[x][y] == 0);
}

int heuristic(Point a, Point b) {

return abs(a.x - b.x) + abs(a.y - b.y);
}

void hillClimb(Point start, Point goal) {

Point current = start;

while (1) {
printf("Current: (%d, %d)\n", current.x, current.y);

if (current.x == goal.x && current.y == goal.y) {

printf("Goal Reached!\n");
break;
}

Point next = current;

int currentHeuristic = heuristic(current, goal);

for (int i = 0; i < 4; i++) {

int newX = current.x + dx[i];
int newY = current.y + dy[i];

if (isValid(newX, newY)) {
Point neighbor = {newX, newY};
int h = heuristic(neighbor, goal);
if (h < currentHeuristic) {
currentHeuristic = h;
next = neighbor;
}
}
 }

if (next.x == current.x && next.y == current.y) {

printf("Stuck at local optimum.\n");
break;
}

current = next;
}
}

int main() {
Point start = {0, 0};
Point goal = {4, 4};
hillClimb(start, goal);
return 0;
}