I have implemented the n-queens problem. However, on comparing with an online solution, I have more combinations than the actual answer.
Below is my code
public class Queens
{
static int rows = 5;
static int cols = 5;
public static void main(String[] args)
{
int[] column = {-1,-1,-1,-1,-1};
fun(0, column);
}
/* j is basically each column */
static void fun(int j, int[] column)
{
if(j == cols)
{
System.out.print("success : ");
for(int k = 0;k<column.length;k++)
{
System.out.print(column[k]);
}
System.out.println("");
return;
}
/* Each column could have the queen in any of the rows */
for(int i = 0;i <rows ;i++)
{
if(isValid(column,j,i) == 1)
{
int[] temp = new int[rows];
for(int k = 0;k<column.length;k++)
temp[k] = column[k];
column[j] = i;
fun(j+1,column);
for(int k = 0;k<temp.length;k++)
column[k] = temp[k];
}
}
}
static int isValid(int[] a, int row, int check)
{
int lastindex = 0;
/* check if they're in the same row */
for(int i = 0;i<a.length;i++)
{
if(a[i] == -1)
{
lastindex = i-1;
break;
}
if(a[i] == check)
return 0;
}
/* check if they're in the same diagonal */
if(lastindex >= 0)
{
/* diagonal on the rise */ /* falling diagonal */
if( (a[lastindex] == check-1) || (a[lastindex] == check+1) )
return 0;
}
/* Note : It can't be in the same column since you're selecting only one for each column, the for loop */
return 1;
}
}
This is my output for the 5-queens problem. (In code, you can get any n, by changing the values of rows and cols accordingly and changing the array )
success : 13524
success : 14253
success : 24135
success : 24153 -
success : 25314
success : 31425
success : 31524 -
success : 35142 -
success : 35241
success : 41352
success : 42513 -
success : 42531
success : 52413
success : 53142
However, the ones marked with a hyphen at the end, are missing from an online site I used to compare the output
Please tell me the reason for these four incosistencies. (For 8-queen, my code above gives 5242 combinations in output, surely I'm doing something wrong in the isValid function)
EDIT : Thanks a lot vish4071, I have changed the isValid() function now and get the correct output; I wasn't aware that diagonal has to be checked at every step.
Code
public class Queens
{
static int rows = 8;
static int cols = 8;
public static void main(String[] args)
{
int[] column = {-1,-1,-1,-1,-1,-1,-1,-1};
fun(0, column);
}
/* j is basically each column */
static void fun(int j, int[] column)
{
if(j == cols)
{
System.out.print("success : ");
for(int k = 0;k<column.length;k++)
{
System.out.print(column[k]);
}
System.out.println("");
return;
}
/* Each column could have the queen in any of the rows */
for(int i = 0;i <rows ;i++)
{
if(isValid(column,j,i) == 1)
{
int[] temp = new int[rows];
for(int k = 0;k<column.length;k++)
temp[k] = column[k];
column[j] = i;
fun(j+1,column);
for(int k = 0;k<temp.length;k++)
column[k] = temp[k];
}
}
}
static int isValid(int[] a, int col, int check)
{
for(int i = 0;i<a.length;i++)
{
if(a[i] == -1)
break;
/* check if they're in the same row */
if(check == a[i])
return 0;
/* check if they're in the same diagonal */
if( Math.abs(check-a[i]) == (col-i) )
return 0;
}
/* Note : It can't be in the same column since you're selecting only one for each column, the for loop */
return 1;
}
}
Your check for diagonal is wrong. Don't use lastindex. Check for same diagonal for all values in a which are not -1.
I'd explain using one of your outputs (you put hyphen against) as example. Lets take 24153.
Lets say your a is now [2,4,1,-1,-1], ie. you are now about to fill index 3. Your last index will be 1 and in a matrix, (2,1) and (3,5) don't lie in a same diagonal. So, it accepts 4th value as 5 not being in the same diagonal, while it is in same diagonal with your value at index 0, ie. 2, since (0,2) and (3,5) lie in same diagonal. So, check for all values.