N Kueen - HackerRank Code Sprint - Interviewstreet.com

NKueen.java

import java.util.ArrayList;
import java.util.Scanner;


public class NKueen {
	
	private static ArrayList<Integer> kueens = new ArrayList<Integer>();
	static int N = 0;
	
	public static void main (String args[]){
		Scanner in = new Scanner(System.in);
		
		//input
		N = in.nextInt();
		
		//loop through 
		generatePositions();
		
		//output positions
		outputKueenPositions();
	}

	
	private static void outputKueenPositions() {
		System.out.println(N);
		for(int i = 0; i < kueens.size();i++){
			if(i == kueens.size() -1){
				System.out.print(kueens.get(i) + " ");
			}else{
				System.out.print(kueens.get(i) + " ");
			}
			
		}
	}

	

	private static void generatePositions() {
		boolean col1Empty = true;
		boolean col2Empty = true;
		int c = 3; //column number - start from column 3
		
		if(N <= 3){
			c = 1;
			kueens.add(c);
		}else{
			kueens.add(c);
			
			for(int r = 1; r < N;r++){
				if(c+3 <= N){
					c = c+3;
					kueens.add(c);
				}else{
					if(col1Empty){
						c = 1;
						col1Empty = false;
						kueens.add(c);
					}else if(col2Empty){
						c = 2;
						col2Empty = false;
						kueens.add(c);
					}else{
						c = (c+3) - N;
						kueens.add(c);
					}
					
				}
			}
		}
		
		
	}
}

The chess queens have become more powerful and apart from their normal moves they can also make knight moves. These pieces are now called Kueens.

Your task is to place N Kueens on an NxN chessboard such that no two of them attack each other.

Ouput format :

On the first line of standard output print N. In the next line print N space separated integers, where ith integer represent the column number of Kueen present in ith row. These N integers are in range 1 to N (inclusive)

Scoring : if your configuration is correct you get a score of N.

Example : One valid configuration for N = 10

• * Q * * * * * * *
• * * * * Q * * * *
• * * * * * * * Q *
  Q * * * * * * * * *
• * * Q * * * * * *
• * * * * * Q * * *
• * * * * * * * * Q
• Q * * * * * * * *
• * * * Q * * * * *
• * * * * * * Q * *

The column numbers corresponding to each row :
3 6 9 1 4 7 10 2 5 8

So printing

10
3 6 9 1 4 7 10 2 5 8

will give you a score of 10.

My first ever code sprint...
The solution is not good --> I ended up with a high score of 100. :(
Which is no where near the max (10,000).

Solved:
127 / 835

I'm impressed that you got to 100! My friends and I only got to 25-30 in the allotted time. The people who got 10,000 didn't use any kind of "traditional" approach like backtracking. Look at the given solution to 10x10. Can you see a pattern? Try generalizing that to 10^k x 10^k.

Yeah, it was a very basic attempt, I still haven't come up with any correct solution. The only pattern I could see was each queen was separated by 3 columns and 1 row, and no matter what N is, there will be 3 diagonal rows of Queens...

I need more practice :D

If it makes you feel better, we didn't get it either. Write out the numbers row-by-row. What do you notice about them? You already mentioned a pattern; see if you can write it out. It's a simple formula. Hint (rot13): Vg vaibyirf n zbqhyhf. - Christian

…

On Mon, Jul 23, 2012 at 5:08 PM, robbio87 < ***@***.*** > wrote: Yeah, it was a very basic attempt, I still haven't come up with any correct solution. The only pattern I could see was each queen was separated by 3 columns and 1 row, and no matter what N is, there will be 3 diagonal rows of Queens... I need more practice :D --- Reply to this email directly or view it on GitHub: https://gist.github.com/3163641