I was solving the N king problem which is
You are given N, and for a given N x N chessboard, find a way to place N Kings such that no king can attack any other king on the chessboard. Each row and column should contain exactly one king. You have to print the total number of such configurations.
I ran my code on hackerblocks and it showed TLE on a few test cases, please tell me how can I better this code I wrote.
#include
using namespace std;
bool isSafe(int board[][10], int i, int j, int n)
{
//for one up column
for(int row=0; row<i; row++)
{
if(board[row][j]==1)
{
return false;
}
}
//for one up diagonal and one down
if((i>0 && j<n-1 && board[i-1][j+1]==1) || (i>0 && j>0 && board[i-1][j-1]==1 ))
{
return false;
}
return true;
}
bool solveNking( int board[][10], int i, int n)
{
if(i==n)
{
//print board
for(int a=0; a<n; a++)
{
for(int b=0; b<n; b++)
{
if(board[a][b]==1)
{
cout<<"K “;
}
else{cout<<”_ ";}
}
cout<<endl;
}
return true;
}
for(int j=0; j<n; j++)
{
if(isSafe(board, i, j, n))
{
board[i][j]=1;
bool nextking = solveNking(board, i+1, n);
if(nextking)
{
return true;
}
board[i][j]=0; //BACKTRACK
}
}
return false;
}
int main()
{
int n;
cin>>n;
int board[10][10]={0};
solveNking(board, 0, n);
return 0;
}