Google Interview Question
Software Engineer in TestsCountry: United States
If the n is 3, then there will be no solution. When do you plan to stop?
Can you provide me with an algorithm that you are using in plain English rather than code?
One important thing to use is backtracking and figured that out.
Hey Thanks for your algo.
Can you please give me explanation of if condition in checker function?
Thanks.
//modified for generalized case
int *m;
int checker(int k,int i){
int j;
for(j=1;j<=k-1;j++)
{
if((m[j]==i)||(m[j]-i==j-k) || (m[j]-i==k-j))
{
return(0);
}
}
return(1);
}
void solve(int n, int nq){
if(n==nq+1) {
cout<<endl<<endl<<endl<<"soln"<<s++;
for(int i=1;i<n;i++)
{
cout<<endl;
for(int j=1;j<n;j++)
{
if( (m[i]==j))
cout<<"Q";
else
cout<<"-";
}
}
}
else
{
for(int i=1;i<=nq;i++)
{
if(checker(n,i)==1)
{
m[n]=i;
solve(n+1);
}
}
}
}
int main()
{
int nq;
cout<<"Enter number of queens:\n";
cin>>nq;
if (nq<=0)
{
cout<<"enter valid value of number of queens";
return 1;
}
m = new int[nq+1];
solve(0,nq);
}
//Making multi-threadedsafe
int checker(int k,int i){
int j;
for(j=1;j<=k-1;j++)
{
if((m[j]==i)||(m[j]-i==j-k) || (m[j]-i==k-j))
{
return(0);
}
}
return(1);
}
void solve(int n, int nq, int *m){
if(n==nq+1) {
cout<<endl<<endl<<endl<<"soln"<<s++;
for(int i=1;i<n;i++)
{
cout<<endl;
for(int j=1;j<n;j++)
{
if( (m[i]==j))
cout<<"Q";
else
cout<<"-";
}
}
}
else
{
for(int i=1;i<=nq;i++)
{
if(checker(n,i)==1)
{
m[n]=i;
solve(n+1);
}
}
}
}
int main()
{
int nq;
int *m;
cout<<"Enter number of queens:\n";
cin>>nq;
if (nq<=0)
{
cout<<"enter valid value of number of queens";
return 1;
}
m = new int[nq+1];
solve(1,nq, m);
}
int *queens(int *list,int *used,int level,int Ispossible)
{
if (level==N)
{ printf("the result is %s",list);
Ispossible=1; // find possible solution, set the mask
}
else
for(int i=0;i<N;i++) // variable i stands for each column
{
Is_diag=0;
if (used[i]==1) // used[] stores the already taken row number for previous column
continue;
for (int j=0;j<level;j++)
if (level-j==abs(i-list[j])) // check the diagonal and reversed diagonal
Is_diag=1;
if (Is_diag)
continue;
else {
list[level]=i; // store the row number for the level column
used[i]=1;
queue(N,list,used,level+1); // jump to the next recursion
used[i]=0;
}
}
}
void findsolution(int N)
{
int *list=(int *)malloc(sizeof(int)*N);
int level=0,Ispossible=0;
int *used(int *)malloc(sizeof(int)*N);
queens(list,used,level,Ispossible);
free(list); free(used);
if (!Ispossible)
printf("No Solution");
}
Here is an iterative solution using some trigonometry
<?php
$check = NQueen(8);
function NQueen($n) {
$positions = array();
for ($index = 0; $index < $n; $index++) {
$positions[] = -1;
}
$curColumn = 0;
while (true) {
$posFound = false;
for ($i = $positions[$curColumn] + 1; $i < $n; $i++) {
if (isSafe($curColumn, $i, $positions, $n)) {
$posFound = true;
$positions[$curColumn] = $i;
break;
}
}
if ($posFound) {
if ($curColumn >= $n - 1) {
return true;
}
$curColumn++;
} else {
if ($curColumn <= 0) {
return false;
}
if ($positions[$curColumn] >= 0) {
$positions[$curColumn] = -1;
}
$curColumn--;
if ($positions[$curColumn] == ($n -1)) {
$positions[$curColumn] = -1;
$curColumn--;
}
}
}
}
function isSafe($curColumn, $row, $positions, $n) {
$x2 = $curColumn;
$y2 = $row;
for ($index = 0; $index < $curColumn; $index++) {
$x1 = $index;
$y1 = $positions[$index];
$m = abs(($y2 - $y1) / ($x2 - $x1));
if ($m == 1 || $m == 0) {
return false;
}
}
return true;
}
- marti March 12, 2012