Monday, April 29, 2013

N Queens Puzzle Using C Graphics

N Queens puzzle is one of the most popular interview questions. The problem is to place N queens in NxN chessboard so that no queen should attack the other queen. This can be solved using backtracking technique. The logic is , Place one queen in each row, and proceed placing the next row queen and so on. If it is found that there is no place in the current row to place the queen the revisit the already placed queens, adjust their position and proceed to the same row. Repeat the same, until you place the queen in the last row. If the queen is successfully placed in the last row, it means that we arrived to a solution. There may be such multiple solutions. 


This problem is solved in C Programming language in the current example, and I have also enhanced the program using C Graphics, which shows movements of queens in row graphically. It also shows which row currently it is processing using a BAR in the first column of the row. Each Queen is shown as circle in each row with different colors. This program is tested for N=26.
Controls:
1. N Value can be changed by modifying the "MAX_CELL" macro.
2. The Queens movement speed can be controlled by "SPEED" macro.
3. Board color can be modified using "BOARD_LINE_COLOR" macro.


/*
 N-Queens problem
 C Graphics Programs presented by
 www.ncooltips.com
*/

#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<graphics.h>
#include <alloc.h>


#define BOARD_LINE_COLOR (7)

/* Modify this paremeter to find a solution of N Queen 
   placements where N is this parameter
*/
#define MAX_CELL (8)
#define BASE MAX_CELL

/* Modify this parameter to control the speed of
   Queen movement 
*/
#define SPEED (50)

/*
  Margin from the edges - Board will be drawn with this margin
*/
#define MARGIN (50)

/* To track N Queens n[ROW]=Col position */
int Q[MAX_CELL];

struct box {
  int x1;  // X position of P(x,y) Cell
  int y1;  // Y position of P(x,y) Cell
};

/* To track each box in NXN matrix board */
struct box cell[MAX_CELL][MAX_CELL];

/* Shows text in the status bar, which is bottom of the board
   on screen
*/
void show_text(char *s)
{
   int x=getmaxx()/2;
   int y=getmaxy()-MARGIN+5;

   /* Justofy text to Center in verticle and horizantal */
   settextjustify(1,1);
   
   /* This function is used to write text in graphic mode */
   outtextxy(x,y,s);
}

/* 
  Draws Queen Based on Board size and with given color
*/
void draw_queen(int x, int y, int n,int color)
{

  int k=0;
  int margin=MARGIN;
  int xdiv=(getmaxx()-2*margin)/n;
  int ydiv=(getmaxy()-2*margin)/n;
  int maxx=n*xdiv;
  int maxy=n*ydiv;

  setcolor(color);
  circle(x+xdiv/2,y+ydiv/2,xdiv/4);

}

/* 
  Draws Board of N x N size
  Takes care of left,right,top,bottom margins
*/
void draw_board(int n)
{
  int j=0,k=0;
  int x,y;
  int margin=MARGIN;
  int xdiv=(getmaxx()-2*margin)/n;
  int ydiv=(getmaxy()-2*margin)/n;
  int maxx=n*xdiv;
  int maxy=n*ydiv;

  setcolor(BOARD_LINE_COLOR);
  
  /* Draw vertical and Horizantal lines */
  for(k=0;k<=n;k+=1) {
    line(margin+k*xdiv,margin,margin+k*xdiv,margin+maxy);
    line(margin,margin+k*ydiv,margin+maxx,margin+k*ydiv);

  }

  /*  Initialize each cell position */
  for(j=0;j<n;j+=1) {
   for(k=0;k<n;k+=1) {

    cell[k][j].x1=margin+j*xdiv;
    cell[k][j].y1=margin+k*ydiv;

    putpixel(cell[k][j].x1+3,cell[k][j].y1+3,10);
   }
  }
}

/* Clears all cells in given column */
void clear_column(int col)
{
  int k=0;
  for(;k<MAX_CELL;k++)
    draw_queen(cell[k][col].x1,cell[k][col].y1,MAX_CELL,0);
}

/* Clears all cell in given row */
void clear_row(int r)
{
  int k=0;
  for(;k<MAX_CELL;k++)
    draw_queen(cell[r][k].x1,cell[r][k].y1,MAX_CELL,0);
}

/* Shows currently processing row */
void show_current_row(int r)
{
   static int prev=-1;
   int height=((getmaxy()-2*MARGIN)/MAX_CELL)-3;
   int width=10;
   int m=5;

   setcolor(0);
   if(prev==-1) {
     /* Keep track of previous row so that it can be cleared */
     prev=r;
   }
   else  {
      /* Fill with black color */
      setfillstyle(1,0);
      bar(cell[prev][0].x1+m,cell[prev][0].y1+m,cell[prev][0].x1+width,cell[prev][0].y1+height);
   }

   /* Fill with unique color */
   setfillstyle(1,r+1);
   bar(cell[r][0].x1+m,cell[r][0].y1+m,cell[r][0].x1+width,cell[r][0].y1+height);
   
   /* Record Previous row */
   prev=r;
}


/* 
Prints N-Queen placement solution
*/
void printQ(int n)
{
  int i=0;
  for(;i<n;i++)
    printf("Q[%d] = %d | ", i, Q[i]);

  printf("\n");
}

/*
  tests whether the Queen can be places in given cell or not,
  by considering the previous queens position
*/
int place(int r,int c)
{
  int row;

  /* Q[R]= C indicates Queen is placed in Rth row and Cth column */
  for(row=0;row<=r-1;row++) {
    clear_row(r);
    draw_queen(cell[r][c].x1,cell[r][c].y1,MAX_CELL,7);
    if( (Q[row]==c) || ( abs(Q[row]-c) == abs(row-r))) {
      draw_queen(cell[r][c].x1,cell[r][c].y1,MAX_CELL,r+1);
      return  0;
    }

  }

  clear_row(r);
  draw_queen(cell[r][c].x1,cell[r][c].y1,MAX_CELL,r+1);
  return 1;
}
/* 
   Back tracking Function to place N-Queen problem
*/
int nqueen(int row,int n)
{
  int col;

  setcolor(14);
  show_text("In progress ...");

  for(col=0;col<n;col++)
  {
    delay(SPEED);
    show_current_row(row);

    if(place(row,col))
    {

      Q[row]=col;

      if(row==n-1) {

        setcolor(0);
        show_text("In progress ...");

        setcolor(2);
        show_text("SOLUTION ARRIVED");
        /* printQ(n); */
        getch();
        cleardevice();
        closegraph();
        exit(0);
      }
      else {
      nqueen(row+1,n);
          }
        }/*place*/
        clear_row(row+1);
  }/*for each column*/

  return 0;

}

/* MAIN FUNCTION */
void main() {
  int gdriver = DETECT, gmode = 0;

  initgraph(&gdriver, &gmode, "c:\\tc\\bgi");

  /* Draws N x N Board */
  draw_board(MAX_CELL);

  /* Start processing placement of N Queens */
  nqueen(0,BASE);

  getch();
  cleardevice();
  closegraph();
}
Pin It
Related Posts Plugin for WordPress, Blogger...