Implementation of NQueen Algorithm with Backtracking Principle - C Code Example

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

//global variable to keep track of numbers of solutions
int solNum = 0;

void initBoard(int, char**); //initializes the boardvoid nqueen(int, int, char**, int); //puts the queen
//following backtrack method
int eraseQueen(int, int, char**);//erases a queen at the
//time of backtrack and gets its column positionint feasible(int,int,int,char**); //checks whether placing
// of a queen in a particular position is feasible or not 
void showBoard(int, char**);//shows the board

int main(void)
{
    int num,i,startingRow;
    char** board;
    printf("\n Enter the number of Queens::");
    scanf("%d", &num);
    board=(char**)malloc(num*sizeof(char*));
    for(i=0;i<num;i++)
        board[i]=(char*)malloc(num*sizeof(char));
    printf("\n Board is allocated Successfully");
    initBoard(num, board);
    startingRow = 0;
    nqueen(startingRow, num, board,0);
    return 0;   
}

//board gets initialized with a X
void initBoard(int size, char** brd)
{
    int i, j;
    for(i=0;i<size;i++)
        for(j=0;j<size;j++)
            brd[i][j]='X';
    printf("\n Board is initialized successfully");
}

//puts queen with backtrack in current row, it tries to put
//the queen starting from start column
void nqueen(int currRow, int size, char** brd, int startCol)
{
    int col, count = 0, prevQueenCol;
    if(currRow == 0 && startCol == size) // All queens have been //placed
    //or all positions have been checked        exit(0);
    if(startCol == size) // If you need to place a queen which is
    //out of the board in a row, that is queen in the previous //row
    //must be changed (Backtrack)
    {
        prevQueenCol = eraseQueen(currRow -1, size, brd); //get //the column
        //of previous queen        nqueen(currRow - 1, size, brd, prevQueenCol + 1);// calls //nqueen for the
        //previous row, and column just got + 1    
    }
    //oterwise -- normal scenario    for(col = startCol; col<size; col++)
    {
        if(feasible(currRow,col,size,brd)==0){ //if the queen can //be
        //placed at current row ith column
            brd[currRow][col]='Q'; //place the queen            if(currRow == size - 1) //if current row is the last //row
            //that is queen is placed in the last row, one //solution is
            //found
            {
                solNum = solNum + 1; //solution count increased
                printf("\n Solution #%d\n", solNum);
                showBoard(size, brd); //show the solution
                brd[currRow][col] = 'X'; //initialize the position again
                //to search for any other solution                count = count + 1; //Assume as it is a failure //(for he
                //next solutions
            }   
            else //if the row is not the last row, try to place the
            //queen in the next row
                nqueen(currRow+1,size,brd,0);           
        }else{ // queen placing not feasible, so failure            count = count + 1; //increase failure count
        }
    }
    //backtracking starts
    if(count == size - startCol) // if failure for all the column
    {
        prevQueenCol = eraseQueen(currRow -1, size, brd); // get //the column
        // of previous queen in previous column
        nqueen(currRow - 1, size, brd, prevQueenCol + 1); //that //placing was wrong
        //try to place the queen in the previous row starting //from the next column
    }
}
//erases the queen
int eraseQueen(int currRow, int size, char** brd)
{
    int col;
    for(col = 0; col<size; col++)
    {
        if(brd[currRow][col] == 'Q')
        {
            brd[currRow][col] = 'X';
            return col;
        }   
    }   
}
//test feasibility of queen placing
int feasible(int row,int col,int size, char** brd)
{
    int i, j;
    for(i = 0; i < size; i++)
    {
        for(j = 0; j < size; j++)
        {
            if(brd[i][j] == 'Q')
            {
                if(i == row || j == col || abs(i - row) == abs(j - col))//If no two Queens are placed in same row, column or //diagonals
                    return 1;       
            }           
        }   
    }   
    return 0;
}
//Shows board
void showBoard(int size, char** brd)
{
    int i, j;
    for(i = 0; i < size; i++)
    {
        for(j = 0; j < size; j++)
        {
            printf("%c ", brd[i][j]);           
        }   
        printf("\n");
    }
}

Elementary Discussion About State Space Search (Part II)

Example problem: 8 puzzle

In the 8-puzzle problem we have a 3×3 square board and 8 numbered tiles. The board has one blank position. Bocks can be slid to adjacent blank positions. We can alternatively and equivalently look upon this as the movement of the blank position up, down, left or right. The objective of this puzzle is to move the tiles starting from an initial position and arrive at a given goal configuration.

The 15-puzzle problems is similar to the 8-puzzle. It has a 4×4 square board and 15 numbered tiles

The state space representation for this problem is summarized below:

States: A state is a description of each of the eight tiles in each location that it can occupy.

Operators/Action: The blank moves left, right, up or down

Goal Test: The current state matches a certain state (e.g. one of the ones shown on previous slide)

Path Cost: Each move of the blank costs 1

A small portion of the state space of 8-puzzle is shown below. Note that we do not need to generate all the states before the search begins. The states can be generated when required.

 



tic-tac-toe

Another example we will consider now is the game of tic-tac-toe. This is a game that involves two players who play alternately. Player one puts a X in an empty position. Player 2 places an O in an unoccupied position. The player who can first get three of his symbols in the same row, column or diagonal wins. A portion of the state space of tic-tac-toe is depicted below.

8 queens’ problem

The problem is to place 8 queens on a chessboard so that no two queens are in the same row, column or diagonal

The picture below on the left shows a solution of the 8-queens problem. The picture on the right is not a correct solution, because some of the queens are attacking each other.

How do we formulate this in terms of a state space search problem? The problem formulation involves deciding the representation of the states, selecting the initial state representation, the description of the operators, and the successor states. We will now show that we can formulate the search problem in several different ways for this problem.

N queens problem formulation 1

            • States: Any arrangement of 0 to 8 queens on the board

            • Initial state: 0 queens on the board

            • Successor function: Add a queen in any square

            • Goal test: 8 queens on the board, none are attacked

The initial state has 64 successors. Each of the states at the next level have 63 successors, and so on. We can restrict the search tree somewhat by considering only those successors where no queen is attacking each other. To do that we have to check the new queen against all existing queens on the board. The solutions are found at a depth of 8.

N queens problem formulation 2

            • States: Any arrangement of 8 queens on the board

            • Initial state: All queens are at column 1

            • Successor function: Change the position of any one queen

            • Goal test: 8 queens on the board, none are attacked

If we consider moving the queen at column 1, it may move to any of the seven remaining columns.

N queens problem formulation 3

            • States: Any arrangement of k queens in the first k rows such that none are attacked

            • Initial state: 0 queens on the board

            • Successor function: Add a queen to the (k+1)th row so that none are attacked.

            • Goal test : 8 queens on the board, none are attacked

Now here is the end of the discussion about State Space Search and some of its implementations. Feel free to query about the topic.

 

Source:http://nptel.iitm.ac.in/courses/Webcourse-contents/IIT%20Kharagpur/Artificial%20intelligence/New_index1.html