King Placement

package facebook.onlinequiz;

import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.util.StringTokenizer;

public class Solution {

	int totalTests = 0;
	int[] pos; // represents filledin column positions
	BufferedReader br ;
	int N ;
	int k ;
	long[] res; // represents the no of ways to place kings for each testcase

	/**
	 * Method used to read inputs and call the appropriate method (getNoofWaysToPlaceKings) for each testcase
	 * @return array representing the no of ways to place kings for each testcase
	 */
	public long[] getNoofWays()
	{
		try{
			br = new BufferedReader(new InputStreamReader(System.in));
			String line = br.readLine();
			totalTests = Integer.parseInt(line);
			line = br.readLine();
			StringTokenizer strTokenizer = new StringTokenizer(line);
			int count = 0;
			res = new long[totalTests];
			while(count < totalTests)
			{

				N = Integer.parseInt(strTokenizer.nextToken());
				k = Integer.parseInt(strTokenizer.nextToken());
				pos = new int[k];
				line = br.readLine();
				if(k != 0){
					strTokenizer = new StringTokenizer(line);
					int posCount = 0;
					while(posCount < k)
						pos[posCount++] = Integer.parseInt(strTokenizer.nextToken());
				}
				if(k == N)
					res[count++] = 1;
				else
				res[count++] = getNoofWaysToPlaceKings(N, k, pos);
				if(count < totalTests){
					line = br.readLine();
					strTokenizer = new StringTokenizer(line);
				}
			}
		}
		catch(IOException e)
		{
			e.printStackTrace();
		}

		return res;
	}

	/**
	 * Entry point to get no of ways of king placement for a given board
	 * All initialization goes in this method
	 * @param N, size of board
	 * @param k, no of rows already filled 
	 * @param pos, array representing the filled in column positions
	 * @return no of ways to place Kings for the given board configuration
	 */
	private long getNoofWaysToPlaceKings(int N, int k, int[] pos)
	{
		/*System.out.println(" "+N+" "+k+" ");
		for(int i: pos)
			System.out.print(" "+i);
		System.out.println();*/
		int[][] used = new int[N][N];
		int[] filledCol = new int[N];
		int posK = 0;
		while(posK < k)
			used[posK][pos[posK++]] = 1;

		int colPos = 0;
		while(colPos < k)
		{
			filledCol[pos[colPos++]] = 1;
		}
		return getWaysofPlacement(N, used, k, filledCol);

	}

	/**
	 * Used to get the no of ways in which a king can be placed for the given board configuration
	 * @param N, size of the board
	 * @param used, represent board configuration
	 * @param row, current row
	 * @param filledCol, represents filledin col positions
	 * @return no of ways to place kings for the given board configuration
	 */
	private long getWaysofPlacement(int N, int[][] used, int row, int[] filledCol)
	{
		if(row == N)
		{
			return 1;
		}
		else{
			int i =0;
			long noOfways = 0;
			for(;i<N;i++)
			{
				if(isSafe(i, row, filledCol, used, N) )
				{
					used[row][i] = 1;
					filledCol[i] = 1;
					long temp = getWaysofPlacement(N, used, row+1, filledCol);
					if(temp != 0)
						noOfways += temp;
					used[row][i] = 0;
					filledCol[i] = 0;
				}
			}
			return noOfways;
		}
	}

	/**
	 * used to check if current position is a valid placement for king or not
	 * @param col, represents current column
	 * @param row, represents current row
	 * @param filledCol, represents row which has already filledin column positions
	 * @param used, represents board configuration
	 * @param N, total size of the board
	 * @return true if col, row is valid placement else false
	 */
	private boolean isSafe(int col, int row, int[] filledCol,int[][] used, int N)
	{
		if(filledCol[col] == 1) return false;
		if(row > 0)
		{
			if(col > 0)
				if(used[row-1][col-1] == 1) return false;
			if(col < N-1)
				if(used[row-1][col+1] == 1) return false;
		}
		return true;

	}

	public static void main(String args[])
	{
		Solution solution = new Solution();

		long[] res = solution.getNoofWays();
		for(long i:res)
			System.out.println(i);
	}


}