Pages

Wednesday 25 October 2017

A Tryst With Chess- Coding challenge Solved with Backtracking Algorithm | Developed by PY.

Today I m posting solution developed by me for this coding challenge. Got Crazy with the Backtracking Algorithm.

PROBLEM STATEMENT: 

 You are given a 10X10 chessboard with a knight on coordinate (I,J). You have to find the number of blocks on the chessboard that the knight can be at in exactly N moves.

NOTE:

The knight can move from its position in the diagram to all the coordinates marked by X
in the following diagram in one move. For the 10X10 chessboard (1,1) is the top-left corner,(1,10) is the top-right corner and (10,10) is the bottom-right corner.



INPUT :

Input will consist of three space separated integers I
,J,N

N is less than 10.

OUTPUT:
Print a single integer denoting the number of blocks on the chessboard that the knight can be at in exactly N
moves.

 Sample Input: 3 3 1
Sample Output: 8




My Code in C solving this Problem: 

 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/* 
  Problem : A Tryst with Chess
  Author : Pavan Yekabote
*/
#include<stdio.h>


struct mve{
    int x,y;
};
typedef struct mve Moves;


Moves getMoveFrom(int x,int y){
    Moves mv;
    mv.x = x;
    mv.y = y;
    return mv;
}

void fillBoard(int board[][11])
{
    int i,j;
    for(i=0; i< 10; i++)
    {
        for(j=0; j<10; j++)
            board[i][j] = 0;
       
    }   
}

int countOnes(int board[][11])
{
    int i,j,c=0;
    for(i=0; i< 10; i++)
    {
        for(j=0; j<10; j++)
            if(board[i][j] == 1)
                c++;
    }   
    return c;
}
void placeMove(Moves move, int board[][11])
{
    board[move.x][move.y] = 1;
}

void displayBoard(int board[][11])
{
    int i,j;
    for(i=0; i< 10; i++)
    {
        for(j=0; j<10; j++)
            printf("%d ",board[i][j]);
        printf("\n");
    }   
}


int getPossibleMoves(int x, int y, int boardSize, int* sizeOfPossibleMoves, Moves nPossibleMoves[])  
{
    int x1[8] = {-1, -2, 1, 2, -1, -2, 1, 2},y1[8] = {-2, -1, -2, -1, 2, 1, 2, 1},i,j,x2,y2;
   
    for(i=0,j=0; i< 8; i++)
    {
        x2 = x+x1[i];
        y2 = y+y1[i];
        if( x2 >= 0 && x2 < boardSize && y2 >= 0 && y2 < boardSize )
            nPossibleMoves[j++] = getMoveFrom(x2,y2);   
    }
    *sizeOfPossibleMoves = j;
}


int getNMovesOfKnight(int board[][11],Moves placedCoord, int n, int nthMove, int nMoves)
{
    int i,j, nPossMoves, ko,c=0;
    Moves moves[9];
   
           
    if(nthMove >= nMoves)
        return 0;
   
    getPossibleMoves(  placedCoord.x, placedCoord.y, 10, &nPossMoves, moves);
   
    for(j=0; j<nPossMoves; j++ )
    {
       
           
            if(!(getNMovesOfKnight(board, moves[j], n, nthMove+1, nMoves)))
                placeMove(moves[j],board);   

            else
            {                   
                board[moves[j].x][moves[j].y] = 0;
                c++;
            }
       

    }
   
    return nPossMoves-c;
}

int main()
{
    int board[11][11];
    int x,y, nMoves;
    Moves move;
    int i,j,n=10;
    scanf("%d%d%d",&x,&y,&nMoves);
    move.x = x-1;
    move.y = y-1;
    fillBoard(board);
    x = getNMovesOfKnight(board,move,n,0,nMoves);
    printf("%d",countOnes(board));

}
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)