2.

BFS and A* (both algo in 1 code)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define INF 1000000000

#define MAXM 100
#define MAXN 100

typedef struct { int r,c; } Cell;

typedef struct { int node, f, g, h; } PQItem;
typedef struct { PQItem* a; int n,cap; } MinHeap;
typedef struct { int* data; int sz,cap; } IntVec;

static int R=0, C=0;

static int start_r=-1, start_c=-1;
static int goal_r=-1, goal_c=-1;
static int grid[MAXM][MAXN];

// ---------- small utils ----------

static int inb(int r,int c){ return r>=0 && r<R && c>=0 && c<C; }
static int idx(int r,int c){ return r*C + c; }
static Cell from_idx(int id){ Cell t={ id/C, id% C }; return t; }
static int manhattan(int r1,int c1,int r2,int c2){
int dr=r1-r2; if(dr<0) dr=-dr;
int dc=c1-c2; if(dc<0) dc=-dc;
return dr+dc;
}
static void trim(char* s){
int n=(int)strlen(s);
while(n>0 && (s[n-1]=='\r'||s[n-1]=='\n')) s[--n]=0;
}

static void iv_init(IntVec* v){ v->data=NULL; v->sz=0; v->cap=0; }

static void iv_push(IntVec* v, int x){
if(v->sz==v->cap){ v->cap=v->cap?2*v->cap:64; v->data=(int*)realloc(v->data, v-
>cap*sizeof(int)); }
v->data[v->sz++]=x;
}
static void iv_clear(IntVec* v){ v->sz=0; }
static void iv_free(IntVec* v){ free(v->data); v->data=NULL; v->sz=v->cap=0; }
static int pq_less(PQItem x, PQItem y){
if(x.f!=y.f) return x.f<y.f;
return [Link]<[Link];
}
static void mh_init(MinHeap* h){ h->a=NULL; h->n=0; h->cap=0; }
static void mh_push(MinHeap* h, PQItem it){
if(h->n==h->cap){ h->cap=h->cap?2*h->cap:64; h->a=(PQItem*)realloc(h->a, h-
>cap*sizeof(PQItem)); }
int i=h->n++; h->a[i]=it;
while(i>0){
int p=(i-1)/2;
if(pq_less(h->a[i], h->a[p])){ PQItem t=h->a[i]; h->a[i]=h->a[p]; h->a[p]=t; i=p; }
else break;
}
}
static int mh_empty(MinHeap* h){ return h->n==0; }
static PQItem mh_top(MinHeap* h){ return h->a[0]; }
static void mh_pop(MinHeap* h){
int n=--h->n; if(n<=0){ h->n=0; return; }
h->a[0]=h->a[n];
int i=0;
while(1){
int l=2*i+1, r=2*i+2, m=i;
if(l<h->n && pq_less(h->a[l],h->a[m])) m=l;
if(r<h->n && pq_less(h->a[r],h->a[m])) m=r;
if(m==i) break;
PQItem t=h->a[i]; h->a[i]=h->a[m]; h->a[m]=t; i=m;
}
}
static void mh_free(MinHeap* h){ free(h->a); h->a=NULL; h->n=h->cap=0; }

static void print_grid(){

printf("\nGrid %dx%d:\n", R, C);
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
char ch='.';
if(grid[i][j]==-1) ch='0';
else if(grid[i][j]==2) ch='S';
else if(grid[i][j]==3) ch='G';
else ch='1';
printf(" %c ", ch);
}
 printf("\n");
}
}
static void print_open_closed(const char* lab, IntVec* v){
printf("%s: [", lab);
for(int i=0;i<v->sz;i++){
Cell t=from_idx(v->data[i]);
printf("%s(%d,%d)", (i?", ":""), t.r+1, t.c+1);
}
printf("]\n");
}
static void print_path_indices(int* path, int len){
printf("Path (coords): ");
for(int i=0;i<len;i++){
Cell t=from_idx(path[i]);
printf("(%d,%d)", t.r+1, t.c+1);
if(i+1<len) printf("->");
}
printf("\n");
}
static void print_grid_with_path(int* path, int len){
int mark[MAXM*MAXN]={0};
for(int i=0;i<len;i++) mark[path[i]]=1;
printf("\nAnswer path on grid:\n");
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
int id=idx(i,j);
if(grid[i][j]==2) printf(" S ");
else if(grid[i][j]==3) printf(" G ");
else if(grid[i][j]==-1) printf(" 0 ");
else if(mark[id]) printf(" * ");
else printf(" 1 ");
}
printf("\n");
}
}

static int parse_input_file(const char* fname){

FILE* f=fopen(fname,"r");
if(!f){ printf("Error: could not open %s\n", fname); return 0; }
char line[1024];

int gotDim=0;
while(fgets(line,sizeof(line),f)){
 trim(line);
if(line[0]==0) continue;
int m=0,n=0;
char *p=strchr(line, ':');
if(!p) p=line; else p++;
while(*p && isspace((unsigned char)*p)) p++;
if(sscanf(p, "%d*%d", &m, &n)==2){
R=m; C=n; gotDim=1; break;
}
}
if(!gotDim){ printf("Error: grid dimension line not found.\n"); fclose(f); return 0; }
if(R<=0||C<=0||R>MAXM||C>MAXN){ printf("Error: invalid grid size.\n"); fclose(f); return
0; }

for(int i=0;i<R;i++) for(int j=0;j<C;j++) grid[i][j]=0;

start_r=start_c=goal_r=goal_c=-1;

int r=0;
while(r<R && fgets(line,sizeof(line),f)){
trim(line);
if(line[0]==0) continue;
int c=0;
char* tok=strtok(line," \t");
while(tok && c<C){
if(strcmp(tok,"S")==0 || strcmp(tok,"s")==0){ grid[r][c]=2; start_r=r; start_c=c; }
else if(strcmp(tok,"G")==0 || strcmp(tok,"g")==0){ grid[r][c]=3; goal_r=r; goal_c=c; }
else if(strcmp(tok,"0")==0){ grid[r][c]=-1; }
else if(strcmp(tok,"1")==0){ grid[r][c]=0; }
else {

if(tok[0]=='0') grid[r][c]=-1;
else grid[r][c]=0;
}
c++; tok=strtok(NULL," \t");
}
if(c!=C){ printf("Error: row %d has %d tokens, expected %d.\n", r+1, c, C); fclose(f);
return 0; }
r++;
}
if(r!=R){ printf("Error: expected %d grid rows, got %d.\n", R, r); fclose(f); return 0; }
if(start_r<0||start_c<0||goal_r<0||goal_c<0){
printf("Error: missing S or G in input.\n"); fclose(f); return 0;
}
 fclose(f);
return 1;
}

// ---------- reconstruct ----------

static void reconstruct(int* parent, int s, int g, int* out, int* outlen){
int cap=R*C+5, n=0;
int* tmp=(int*)malloc(cap*sizeof(int));
int u=g;
while(u!=-1){ tmp[n++]=u; if(u==s) break; u=parent[u]; }
if(tmp[n-1]!=s){ *outlen=0; free(tmp); return; }
for(int i=0;i<n;i++) out[i]=tmp[n-1-i];
*outlen=n; free(tmp);
}

typedef enum { ALG_BESTFIRST=1, ALG_ASTAR=2 } Algo;

static void snapshot_heap(MinHeap* hp, IntVec* out){

iv_clear(out);
for(int i=0;i<hp->n;i++) iv_push(out, hp->a[i].node);
}

static int run_search(Algo alg, int* ans, int* anslen){

int Ntot=R*C;
int s=idx(start_r,start_c);
int g=idx(goal_r,goal_c);

int* closed = (int*)calloc(Ntot,sizeof(int));

int* parent = (int*)malloc(Ntot*sizeof(int));
int* gscore = (int*)malloc(Ntot*sizeof(int));
int* fscore = (int*)malloc(Ntot*sizeof(int));
for(int i=0;i<Ntot;i++){ parent[i]=-1; gscore[i]=INF; fscore[i]=INF; }

MinHeap open; mh_init(&open);

IntVec openSnap, closedSnap; iv_init(&openSnap); iv_init(&closedSnap);

int h0 = manhattan(start_r,start_c,goal_r,goal_c);
int g0 = 0;
int f0 = (alg==ALG_BESTFIRST)? h0 : g0 + h0;

gscore[s]=g0; fscore[s]=f0;
mh_push(&open, (PQItem){ s, f0, g0, h0 });

int found=0, iter=0;

static const int DR[4]={-1,1,0,0};
static const int DC[4]={0,0,-1,1};

while(!mh_empty(&open)){
iter++;
snapshot_heap(&open, &openSnap);
iv_clear(&closedSnap);
for(int i=0;i<Ntot;i++) if(closed[i]) iv_push(&closedSnap, i);

printf("\nIteration %d:\n", iter);

print_open_closed("Open", &openSnap);
print_open_closed("Closed", &closedSnap);

PQItem cur = mh_top(&open); mh_pop(&open);

int u = [Link];
if(closed[u]) continue;
closed[u]=1;

Cell cu = from_idx(u);
int uh = manhattan(cu.r,cu.c,goal_r,goal_c);
printf("Expand: (%d,%d) g=%d h=%d f=%d\n", cu.r+1, cu.c+1, gscore[u], uh, fscore[u]);

if(u==g){ found=1; break; }

for(int k=0;k<4;k++){
int nr=cu.r+DR[k], nc=cu.c+DC[k];
if(!inb(nr,nc)) continue;
if(grid[nr][nc]==-1) continue;
int v=idx(nr,nc);
if(closed[v]) continue;

int h = manhattan(nr,nc,goal_r,goal_c);
if(alg==ALG_BESTFIRST){
int newg = gscore[u] + 1;
int newf = h;
if(newf < fscore[v] || (newf==fscore[v] && newg < gscore[v])){
gscore[v]=newg; fscore[v]=newf; parent[v]=u;
mh_push(&open, (PQItem){ v, newf, newg, h });
}
}else{
// A*: f = g + h
int tentative_g = gscore[u] + 1;
int newf = tentative_g + h;
if(tentative_g < gscore[v]){
 gscore[v]=tentative_g; fscore[v]=newf; parent[v]=u;
mh_push(&open, (PQItem){ v, newf, tentative_g, h });
}
}
}
}

int ok=0;
if(found){
reconstruct(parent, s, g, ans, anslen);
if(*anslen>0){
if(alg==ALG_BESTFIRST){
printf("\nFinal weight (steps = g): %d\n", *anslen-1);
}else{
printf("\nFinal weight (A* steps = g): %d\n", *anslen-1);
}
print_path_indices(ans, *anslen);
print_grid_with_path(ans, *anslen);
ok=1;
}
}else{
printf("\nNo path found.\n");
*anslen=0; ok=0;
}

free(closed); free(parent); free(gscore); free(fscore);

mh_free(&open); iv_free(&openSnap); iv_free(&closedSnap);
return ok;
}

int main(){
if(!parse_input_file("[Link]")) return 1;

printf("Parsed input from [Link]\n");

print_grid();

printf("\nChoose algorithm:\n");
printf("1) Best-First Search (f=h only; h=Manhattan)\n");
printf("2) A* (f=g+h; g=steps, h=Manhattan)\n");
int choice=0; scanf("%d",&choice);
if(choice!=1 && choice!=2){ printf("Invalid choice. Defaulting to A*.\n"); choice=2; }

int path[MAXM*MAXN]; int plen=0;

int ok = run_search((choice==1)? 1:2, path, &plen);
 if(ok){
printf("\nAnswer path length (steps) = %d\n", plen>0? plen-1:0);
}

}
--------------------------------------------------------------------------------------------------------------------------
3. n-queen
#include<iostream>
#include<vector>
using namespace std;

void addSolution(vector<vector<int>>&board,vector<vector<int>>&ans,int n){

vector<int>temp;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
temp.push_back(board[i][j]);
}
}
ans.push_back(temp);
}
bool isSafe(int row,int col,vector<vector<int>>&board,int n){
int x=row;
int y=col;
//check for same row
while(y>=0){
if(board[x][y]==1){
return false;
}
y--;
}
x=row;
y=col;
//check for upar diagonal
while(x>=0 && y>=0){
if(board[x][y]==1){
return false;
}
x--;
y--;
}
//check for lower diagonal
while(x<n && y>=0){
 if(board[x][y]==1){
return false;
}
x++;
y--;
}
return true;
}
void solve(int col,vector<vector<int>>&ans,vector<vector<int>>&board,int n){
//base case
if(col==n){
addSolution(board,ans,n);
return;
}
//solve 1 case and rest Recurssion will take care
for(int row=0;row<n;row++){
if(isSafe(row,col,board,n)){
//if placing queen is safe
board[row][col]=1;
solve(col+1,ans,board,n);
//back track
board[row][col]=0;
}
}
}
vector<vector<int>>nQueens(int n){
vector<vector<int>>board(n,vector<int>(n,0));
vector<vector<int>>ans;
solve(0,ans,board,n);
return ans;
}

int main(){
int n;
cout<<"Enter n:";
cin>>n;
vector<vector<int>>res=nQueens(n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<res[i][j]<<" ";
}
cout<<endl;
}
}