Facebook Interview Question Software Engineers
Country: United States
Interview Type: In-Person
The question does not have answer. I did not know it before I wrote the code. After I run it and saw it has no answer, I found the logic. If we consider the 3rd move for knights then there is no answer. If we do not consider the knight move (i.e. only cosider diagonal, vertical, and horizontal moves) then there is an answer.
I wrote it in a way that both can be shown.
Below is the two classes for Chess and SolveQueen in java:
Chess class:
class Chess{
boolean[][] table;
boolean[][] queens;
int N;
private int[] knightRow= {-2,-1,1,2, 2, 1,-1,-2};
private int[] knightCol= { 1, 2,2,1,-1,-2,-2,-1};
private int knight=8;
int lastCompleted;
boolean includeKnight;
public Chess(int size){
N=size;
table= new boolean[N][N];
queens=new boolean[N][N];
lastCompleted=-1;
}
public Chess(Chess chess){
this(chess.N);
includeKnight=chess.includeKnight;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++){
table[i][j]=chess.table[i][j];
queens[i][j]=chess.queens[i][j];
}
}
public boolean isAvailable(int row, int col){
return !table[row][col];
}
public void put(int row, int col){
//for vertical, horizontal, and diagonal
lastCompleted=row;
queens[row][col]=true;
for(int i=0;i<N;i++){
table[row][i]=true;
table[i][col]=true;
if(col-i>=0){
if(row-i>=0)
table[row-i][col-i]=true;
if(row+i<N)
table[row+i][col-i]=true;
}
if(col+i<N){
if(row-i>=0)
table[row-i][col+i]=true;
if(row+i<N)
table[row+i][col+i]=true;
}
}
//knight move check
if (includeKnight) {
for (int i = 0; i < knight; i++) {
int nRow = row + knightRow[i];
int nCol = col + knightCol[i];
if (nRow >= 0 && nRow < N && nCol >= 0 && nCol < N) {
table[nRow][nCol] = true;
}
}
}
}
public String toString(){
StringBuilder buffer= new StringBuilder();
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(queens[i][j])
buffer.append("*");
else
buffer.append("-");
}
buffer.append("\n");
}
return buffer.toString();
}
}
It is the SolveQueen class:
class SolveQueen{
int N;
boolean includeKnight;
public SolveQueen(int size){
N=size;
includeKnight=false;
}
public List<Chess> solveIt(){
Chess emptyChess= new Chess(N);
emptyChess.includeKnight=includeKnight;
List<Chess> chessesCompleted= new LinkedList<>();
Queue<Chess> fifo = new LinkedList<>();
fifo.offer(emptyChess);
while(!fifo.isEmpty()){
Chess currentChess=fifo.poll();
if(currentChess.lastCompleted==N-1)
chessesCompleted.add(currentChess);
else{
int row=currentChess.lastCompleted+1;
for(int col=0;col<N;col++){
if(currentChess.isAvailable(row,col)){
Chess newChess= new Chess(currentChess);
newChess.put(row,col);
fifo.offer(newChess);
}
}
}
}
return chessesCompleted;
}
}
Here it is the main method to solve it the with and without knight move:
public static void main(String[] args) {
//Create the problem
SolveQueen solve= new SolveQueen(4);
//Solve it without knight moves
List<Chess> solutions=solve.solveIt();
System.out.println("4x4: Total Solutions without knight move: "+ solutions.size());
for(Chess chess:solutions){
System.out.println(chess);
}
//Solve it with knight moves
solve.includeKnight=true;
solutions=solve.solveIt();
System.out.println("4x4: Total Solutions with knight move: "+ solutions.size());
for(Chess chess:solutions){
System.out.println(chess);
}
}
And here is the output of above code:
4x4: Total Solutions without knight move: 2
-*--
---*
*---
--*-
--*-
*---
---*
-*--
4x4: Total Solutions with knight move: 0
I disagree...
If my algorithm is correct then
if N = 10 there should be 1 way.
if N = 11 there should be 13 ways.
if N = 12 there should be 3 ways.
Run your code when N equals these values.
You are right @Alex. For 10 there is an answer. I was not patient enough to try it. But for N=10 there is 4 answers not 1. Two of them are the vertical mirror of the other two (i.e. 2 unique answers).
This is the output of my program for N=10:
10x10: Total Solutions with knight move: 4
--*-------
-----*----
--------*-
*---------
---*------
------*---
---------*
-*--------
----*-----
-------*--
---*------
-------*--
*---------
----*-----
--------*-
-*--------
-----*----
---------*
--*-------
------*---
------*---
--*-------
---------*
-----*----
-*--------
--------*-
----*-----
*---------
-------*--
---*------
-------*--
----*-----
-*--------
---------*
------*---
---*------
*---------
--------*-
-----*----
--*-------
My results:
N=10: 4 ways;
N=11: 44 ways;
N=12: 156 ways;
N=18: 8.924.976 ways
See my post for the not-slow-not-fast code.
The solution is:
1. Pick a position on the grid
2. Fill the grid with all the ways a queen can move,
3. Pick the next empty position
4. Repeat steps 2 and 3.
Once the grid is filled we see if we used N queens and increment the number of ways N queens can be positioned on the grid. We then clear the grid and repeat steps 1 - 4 again with the next position on the grid.
Sample:
N = 10
Output = 1
const int N = 10;
void fillQueenPositions(int row,int col,int (&grid)[N][N],int &count)
{
if(count == N)
return;
if(row < 0 || col < 0)
return;
if(row >= N || col >= N)
return;
//fill horizontal/vertical planes
for(int i = row+1;i<N; i++)
{
grid[i][col] = 2;
}
for(int i = row-1;i>=0; i--)
{
grid[i][col] = 2;
}
for(int i = col+1;i<N; i++)
{
grid[row][i] = 2;
}
for(int i = col-1;i>=0; i--)
{
grid[row][i] = 2;
}
//fill diagonals
int r=row+1,c=col+1;
while(r<N && c<N)
{
grid[r][c] = 2;
r++;
c++;
}
r=row-1,c=col-1;
while(r>=0 && c>=0)
{
grid[r][c] = 2;
r--;
c--;
}
r=row-1,c=col+1;
while(r>=0 && c<N)
{
grid[r][c] = 2;
r--;
c++;
}
r=row+1,c=col-1;
while(r<N && c>=0)
{
grid[r][c] = 2;
r++;
c--;
}
//fill knight move positions
if(row+2 < N && col+1<N)
{
grid[row+2][col+1] = 2;
}
if(row+2 < N && col-1>=0)
{
grid[row+2][col-1] = 2;
}
if(row+1 < N && col+2 < N)
{
grid[row+1][col+2] = 2;
}
if(row+1 < N && col-2 >=0)
{
grid[row+1][col-2] = 2;
}
if(row-2 >=0 && col-1>=0)
{
grid[row-2][col-1] = 2;
}
if(row-2 >=0 && col+1<N)
{
grid[row-2][col+1] = 2;
}
if(row-1 >=0 && col-2>=0)
{
grid[row-1][col-2] = 2;
}
if(row-1 >=0 && col+2<N)
{
grid[row-1][col+2] = 2;
}
grid[row][col] = 1;
count++;
bool bEmptySpotFound = false;
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
if(grid[j][i] == 0)
{
row = j;
col = i;
bEmptySpotFound = true;
break;
}
}
if(bEmptySpotFound)
break;
}
if(bEmptySpotFound)
{
fillQueenPositions(row,col,grid,count);
}
}
int countQueenPositions()
{
int count = 0;
int grid[N][N];
for(int r=0;r<N;r++)
{
for(int c=0;c<N;c++)
{
int nQueens = 0;
fillQueenPositions(r,c,grid,nQueens);
if(nQueens == N)
{
count++;
}
//reset the grid
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
grid[i][j] = 0;
}
}
}
return count;
}
This is definitely a hard problem to solve. If you have never heard of this problem, you will most likely get stuck while designing the problem because you won't accept the fact that the actual solution is n! (unless you knew it beforehand).
There is a solution available on the web, but I can't post the link since it is not allowed. Check on sanfoundry dot com. It is in c++. Only thing it does not have is knight. You just have to develop a function to check for knight position and add it to the program. Ideally, this problem should not be even asked in interview in my opinion because it would take at least an hour to solve it if you haven't heard of it before.
This problem can use CSP to reduce the search space
def CheckQueue(Q, ind):
if ind >= len(Q):
return True
for m in range(len(Q)):
Q[ind]=m
needCheck = True
if ind > 0:
for k in xrange(0, ind):
if Q[k] == Q[ind]:
needCheck = False
break
diff = ind-k
if diff < 0:
diff = -diff
if Q[k]+diff == Q[ind]:
needCheck = False
break
if Q[k]-diff == Q[ind]:
needCheck = False
break
if needCheck and CheckQueue(Q, ind+1):
return True
return False
N = 8
Q = [0 for i in range(0,N)]
CheckQueue(Q, 0)
Standard NQueen problem. But due to the Knight movement .. there will be no solution.
public class NQueens {
ArrayList<QNode> res = new ArrayList<QNode>();
public NQueens(){
}
public void printLocations(QNode[][] mat, int n){
// System.out.println(n);
if(n==mat.length){
printMat(mat);
}else{
for(int i=0;i<mat[0].length;i++){
mat[n][i] = new QNode(n,i);
//System.out.println(n + ""+i);
if(isFree(mat[n][i], mat)){
res.add(mat[n][i]);
printLocations(mat, n+1);
res.remove(mat[n][i]);
}
}
}
}
private void printMat(QNode[][] mat) {
for(int i=0;i<mat.length;i++){
for(int j=0;j<mat[0].length;j++){
if(res.contains(mat[i][j])){
System.out.printf("Q\t");
}else{
System.out.printf("*\t");
}
}
System.out.println();
}
System.out.println("----------------------------------");
System.out.println();
}
private boolean isFree(QNode node, QNode[][] mat) {
for(QNode cell : res){
if(cell.i == node.i || cell.j == node.j || ( Math.abs(node.i-cell.i)== Math.abs(node.j-cell.j))
||
(Math.abs(node.i-cell.i)==2 && Math.abs(node.j-cell.j)==1) ||
(Math.abs(node.i-cell.i)==1 && Math.abs(node.j-cell.j)==2)
){
return false;
}
}
return true;
}
public static void main(String[] args) {
NQueens q = new NQueens();
q.printLocations(new QNode[4][4], 0);
}
}
class QNode{
int i;
int j;
public QNode(int i, int j){
this.i = i;
this.j = j;
}
}
Here's a solution in C# using a recursive, backtracking algorithm. It gets there, but once you get around n >= 14, it's pretty slow.
using System;
using System.Collections.Generic;
namespace NQueens
{
class MainClass
{
// This is an array of the column positions for each row for each placed queen.
// So if placedQueens[3] == 2, then it means there's a queen on the 3rd row, 2nd column.
static int[] placedQueens;
static int matches;
public static void Main (string[] args)
{
Console.WriteLine("N Queens");
Console.WriteLine("---");
for (int i = 4; i <= 15; i++)
{
StartPlacingQueens(i);
}
}
static void StartPlacingQueens(int size)
{
Console.WriteLine("Placing " + size + " queens...");
matches = 0;
placedQueens = new int[size + 1]; // The value at placedQueens[0] is ignored
PlaceQueens(1, size);
Console.WriteLine("Total matches " + matches);
Console.WriteLine();
}
static void PlaceQueens(int row, int size)
{
for (int col = 1; col <= size; col++)
{
if(CanPlace(row, col))
{
placedQueens[row] = col;
if (row == size)
{
matches++;
}
else
{
PlaceQueens(row + 1, size);
}
}
}
}
static bool CanPlace(int row, int col)
{
// If we call this method, we assume that all the prior rows (i.e. <= row) already have queens on them
for(int queenRow = 1; queenRow < row; queenRow++)
{
int queenCol = placedQueens[queenRow];
if (DoesIntefere(row, col, queenRow, queenCol))
{
return false;
}
}
return true;
}
static bool DoesIntefere(int xRow, int xCol, int yRow, int yCol)
{
// Check matching row - you could remove this check in this context
if (xRow == yRow) { return true; }
// Check matching col
if (xCol == yCol) { return true; }
// Check diagonal
if (Math.Abs(xCol - yCol) == Math.Abs(xRow - yRow)) { return true; }
// Check for the knight collision
if (
(Math.Abs(xCol - yCol) == 2 && Math.Abs(xRow - yRow) == 1) ||
(Math.Abs(xCol - yCol) == 1 && Math.Abs(xRow - yRow) == 2)
)
{
return true;
}
// We're good
return false;
}
}
}
In Java:
public static void printQueenPositions(int n) {
int latestRow = 0;
for (int i = 0; i*2 < n; i++) {
if (i*3 < n) {
System.out.println("Queen Pos:" + latestRow + " - " + i*3);
} else {
break;
}
latestRow++;
}
latestRow += 2;
if (latestRow < n) {
for (int i = 0; i*2 < n; i++) {
if (i*3 + 2 < n) {
System.out.println("Queen Pos:" + latestRow + " - " + (i*3 + 1));
} else {
break;
}
latestRow++;
}
}
}
I just cranked this out this morning after tinkering with the backtracking algorithm to better understand recursive enumeration. I hope this helps someone, I didn't see a similar solution here so I thought I would post. I understand "backtracking" as a metaheuristic containing 6 "black box" procedures: root, first, next, reject, accept and output (see wikipedia entry for backtracking.)
Can someone help me with theoretical running time? I think it is something like O(n^2*n*log(n)). n^2 for the "queenTakes()" and n*log(n) for the "bt" although I think it is better than that given the potential search tree (n^n see my "first" and "next" methods) is heavily pruned at the root.. Any help is appreciated. I have an interview with FB in two weeks.
package algorist;
import java.util.Collection;
import java.util.Vector;
import org.junit.Test;
public class BacktrackingAlgo {
private static int N = 20;
private static Vector<Integer> v() { return new Vector<Integer>(); } // new vector compact
private static Vector<Integer> v(Collection<Integer> u) { return new Vector<Integer>(u); } // new vector compact
private static <T> int lst(Vector<T> v) { return v.size()-1; } // last element index
public Vector<Integer> root(int P) { return v(); }
public Vector<Integer> first(Vector<Integer> candidate) {
Vector<Integer> v = v(candidate);
v.add(0);
return v;
}
public Vector<Integer> next(int N, Vector<Integer> candidate) {
Vector<Integer> v = v(candidate);
int i = lst(v);
int next = candidate.get(i) + 1;
if (next == N) return null;
v.set(i, next);
return v;
}
public boolean reject(int N, Vector<Integer> c) {
if (c.size() > N) return true;
if (c.size() < 2) return false;
for (int i = 0; i < c.size(); i++) {
for (int j = 0; j < c.size(); j++) {
if (i == j) continue; // same position
if (queenTakes(c, i, j)) return true;
}
}
return false;
}
public boolean queenTakes(Vector<Integer> c, int j, int i) {
int[] q1 = new int[] {j, c.get(j)};
int[] q2 = new int[] {i, c.get(i)};
// queen takes like a rook
if (q1[0] == q2[0] || q1[1] == q2[1]) return true;
// queen takes like a bishop
if (Math.abs(q1[0] - q2[0]) == Math.abs(q1[1]-q2[1])) return true;
// queen takes like a knight, remembering condition where q2 shares col/row eliminated above
if (Math.abs(q1[0]-q2[0])+Math.abs(q1[1]-q2[1]) == 3) return true;
return false;
}
public boolean accept(int N, Vector<Integer> c) {
if (c.size() == N) return true;
return false;
}
private int numSolutions = 0;
public void output(Vector<Integer> c) {
numSolutions += 1;
// System.out.println(c);
}
public void bt(Vector<Integer> c) {
if (reject(N, c)) return;
if (accept(N, c)) {
output(c);
return;
}
// else
Vector<Integer> s = first(c);
while (s != null) {
bt(s);
s = next(N, s);
}
}
@Test
public void testBt() {
bt(root(N));
}
}
Yes, that is N=20! And it is still running on my lame-o laptop. I'll post the finish time later.
Computer fan crapped out, I think eclipse had a heart attack. Plus, I should have used long or BigInteger for the numSolutions type, although I can't see the number of solutions 20 queens with knight taking being more than 2 Billion..
How many ways are there for N=20? What is the run time of your program? It's interesting to know.
Here is my C++ version of solution
#include<math.h>
#include<iostream>
using namespace std;
class PlaceQueen{
public:
PlaceQueen(int size):N(size), answers(0)
{
diag1 = new bool[2*N];
diag2 = new bool[2*N];
row = new bool[N];
queen = new int[N];
int i, x, y;
for (i = 0; i < N; i++)
{
row[i] = true;
queen[i] = -1;
}
for (x = 0; x < N; x++)
{
for (y = 0; y < N; y++)
{
diag1[x+y] = true;
diag2[N-y+x] = true;
}
}
}
~PlaceQueen()
{
if (diag1) delete[] diag1;
if (diag2) delete[] diag2;
if (row) delete []row;
if (queen) delete []queen;
}
void place_queens()
{
put_queen(0);
cout << " result ways : " << answers << endl;
}
private:
int N;
bool * diag1;
bool *diag2;
bool *row;
int * queen;
int answers;
void put_queen(int x)
{
if (x >= N)
answers++;
else {
for (int y = 0; y < N; y++)
{
if (row[y] && diag1[x+y] && diag2[N-y+x] && (x==0 || (x==1 && (queen[x-1]==-1 || abs(queen[x-1]-y) !=2) ) || (x > 1 && (queen[x-1]==-1 || abs(queen[x-1]-y) !=2) && (queen[x-2] ==-1 ||abs(queen[x-2]-y)!=1 )) ) )
{
row[y] = false;
diag1[x+y] = false;
diag2[N-y+x] = false;
queen[x] = y;
put_queen(x+1);
row[y] = true;
diag1[x+y] = true;
diag2[N-y+x] = true;
queen[x] = -1;
}
}
}
}
};
int main (int argc, char *argv[])
{
int n = atoi(argv[1]);
PlaceQueen board(n);
board.place_queens();
}
class Board
{
public:
Board(int n)
{
size = n;
data = new char[n*n];
for (int i = 0; i < size*size; i++)
{
data[i] = ' ';
}
}//----------------------------------------------------------------------------------
Board(const Board &other)
{
size = other.size;
data = new char[size*size];
for (int i = 0; i < size*size; i++)
{
data[i] = other.data[i];
}
}//----------------------------------------------------------------------------------
~Board()
{
delete[] data;
}//----------------------------------------------------------------------------------
void set(int x, int y, char c)
{
assert(x < size);
assert(y < size);
data[x + y * size] = c;
}//----------------------------------------------------------------------------------
char get(int x, int y)const
{
assert(x < size);
assert(y < size);
return data[x + y * size];
}//----------------------------------------------------------------------------------
void print()const
{
for (int y = 0; y < size; y++)
{
for (int x = 0; x < size; x++)
{
printf("%c", get(x, y));
}
printf("\n");
}
}//----------------------------------------------------------------------------------
bool test_queen(int x, int y)const
{
if (get(x, y) != ' ')
{
return false;
}
if (!check_line(x, y, 1, 1))
{
return false;
}
if (!check_line(x, y, -1, 1))
{
return false;
}
if (!check_line(x, y, 0, 1))
{
return false;
}
if (!check_line(x, y, 1, 0))
{
return false;
}
return true;
}//----------------------------------------------------------------------------------
void add_queen(int x, int y)
{
set(x, y, 'Q');
set_line(x, y, 1, 1, 'X');
set_line(x, y, -1, 1, 'X');
set_line(x, y, 1, 0, 'X');
set_line(x, y, 0, 1, 'X');
print();
printf("\n");
}//----------------------------------------------------------------------------------
int get_size() const
{
return size;
}//----------------------------------------------------------------------------------
private:
void set_line(int x, int y, int dx, int dy, char c)
{
set_line_s(x, y, dx, dy, c);
set_line_s(x, y, -dx, -dy, c);
}//----------------------------------------------------------------------------------
void set_line_s(int x, int y, int dx, int dy, char c)
{
x = x + dx;
y = y + dy;
while (0 <= x && x < size && 0 <= y && y < size)
{
set(x, y, c);
x = x + dx;
y = y + dy;
}
}//----------------------------------------------------------------------------------
bool check_line(int x, int y, int dx, int dy)const
{
return check_line_s(x, y, dx, dy) || check_line_s(x, y, -dx, -dy);
}//----------------------------------------------------------------------------------
bool check_line_s(int x, int y, int dx, int dy)const
{
x = x + dx;
y = y + dy;
while (0 <= x && x < size && 0 <= y && y < size)
{
if (get(x, y) == 'Q')
{
return false;
}
x = x + dx;
y = y + dy;
}
return true;
}//----------------------------------------------------------------------------------
int size;
char *data;
};
int count_ways(const Board &b, int x, int y, int n);
int ways_with_queen_here(const Board &b, int x, int y, int n)
{
assert(n > 0);
printf("ways_with_queen_here %i,%i n = %i\n", x, y, n);
if (b.test_queen(x, y))
{
if (n == 1)
{
return 1;
}
Board m = b;
m.add_queen(x, y);
y++;
if (y == b.get_size())
{
return 0;
}
x = 0;
return count_ways(m, x, y, n - 1);
}
return 0;
}//----------------------------------------------------------------------------------------------
int count_ways(const Board &b, int x, int y, int n)
{
printf("count_ways %i,%i n = %i\n", x, y, n);
if (n == 0)
{
return 1;
}
int out = ways_with_queen_here(b, x, y, n);
// move to next spot
x++;
if (x == b.get_size())
{
y++;
if (y == b.get_size())
{
return out;
}
x = 0;
}
out = out + count_ways(b, x, y, n);
return out;
}//--------------------------------------------------------------------
int count_ways(int s)
{
Board b(s);
return count_ways(b,0,0,s);
}//--------------------------------------------------------------------
int _tmain(int argc, _TCHAR* argv[])
{
for (int i = 4; i < 11; i++)
{
int w = count_ways(i);
printf("i = %i w = %i\n", i, w);
}
return 0;
}
Here is a full search implementation it took me a long time to get it to work and it is still not fully tested.
class Board
{
public:
Board(int n)
{
size = n;
data = new char[n*n];
for (int i = 0; i < size*size; i++)
{
data[i] = ' ';
}
}//----------------------------------------------------------------------------------
Board(const Board &other)
{
size = other.size;
data = new char[size*size];
for (int i = 0; i < size*size; i++)
{
data[i] = other.data[i];
}
}//----------------------------------------------------------------------------------
~Board()
{
delete[] data;
}//----------------------------------------------------------------------------------
void set(int x, int y, char c)
{
assert(x < size);
assert(y < size);
data[x + y * size] = c;
}//----------------------------------------------------------------------------------
char get(int x, int y)const
{
assert(x < size);
assert(y < size);
return data[x + y * size];
}//----------------------------------------------------------------------------------
void print()const
{
for (int y = 0; y < size; y++)
{
for (int x = 0; x < size; x++)
{
printf("%c", get(x, y));
}
printf("\n");
}
}//----------------------------------------------------------------------------------
bool test_queen(int x, int y)const
{
if (get(x, y) != ' ')
{
return false;
}
if (!check_line(x, y, 1, 1))
{
return false;
}
if (!check_line(x, y, -1, 1))
{
return false;
}
if (!check_line(x, y, 0, 1))
{
return false;
}
if (!check_line(x, y, 1, 0))
{
return false;
}
return true;
}//----------------------------------------------------------------------------------
void add_queen(int x, int y)
{
set(x, y, 'Q');
set_line(x, y, 1, 1, 'X');
set_line(x, y, -1, 1, 'X');
set_line(x, y, 1, 0, 'X');
set_line(x, y, 0, 1, 'X');
print();
printf("\n");
}//----------------------------------------------------------------------------------
int get_size() const
{
return size;
}//----------------------------------------------------------------------------------
private:
void set_line(int x, int y, int dx, int dy, char c)
{
set_line_s(x, y, dx, dy, c);
set_line_s(x, y, -dx, -dy, c);
}//----------------------------------------------------------------------------------
void set_line_s(int x, int y, int dx, int dy, char c)
{
x = x + dx;
y = y + dy;
while (0 <= x && x < size && 0 <= y && y < size)
{
set(x, y, c);
x = x + dx;
y = y + dy;
}
}//----------------------------------------------------------------------------------
bool check_line(int x, int y, int dx, int dy)const
{
return check_line_s(x, y, dx, dy) || check_line_s(x, y, -dx, -dy);
}//----------------------------------------------------------------------------------
bool check_line_s(int x, int y, int dx, int dy)const
{
x = x + dx;
y = y + dy;
while (0 <= x && x < size && 0 <= y && y < size)
{
if (get(x, y) == 'Q')
{
return false;
}
x = x + dx;
y = y + dy;
}
return true;
}//----------------------------------------------------------------------------------
int size;
char *data;
};
int count_ways(const Board &b, int x, int y, int n);
int ways_with_queen_here(const Board &b, int x, int y, int n)
{
assert(n > 0);
printf("ways_with_queen_here %i,%i n = %i\n", x, y, n);
if (b.test_queen(x, y))
{
if (n == 1)
{
return 1;
}
Board m = b;
m.add_queen(x, y);
y++;
if (y == b.get_size())
{
return 0;
}
x = 0;
return count_ways(m, x, y, n - 1);
}
return 0;
}//----------------------------------------------------------------------------------------------
int count_ways(const Board &b, int x, int y, int n)
{
printf("count_ways %i,%i n = %i\n", x, y, n);
if (n == 0)
{
return 1;
}
int out = ways_with_queen_here(b, x, y, n);
// move to next spot
x++;
if (x == b.get_size())
{
y++;
if (y == b.get_size())
{
return out;
}
x = 0;
}
out = out + count_ways(b, x, y, n);
return out;
}//--------------------------------------------------------------------
int count_ways(int s)
{
Board b(s);
return count_ways(b,0,0,s);
}//--------------------------------------------------------------------
int _tmain(int argc, _TCHAR* argv[])
{
for (int i = 4; i < 11; i++)
{
int w = count_ways(i);
printf("i = %i w = %i\n", i, w);
}
return 0;
}
This problem is hard for big N. For small N, it can be fast.
Statistics of my simple program:
EDIT: Brief explanation:
- Always place the k-th queen at the k-th column;
- If you put a queen at k-th column and i-th row: mark row[i] not-safe, mark the 2 diagonals crossed at square (k,i) not-safe.
- In k-th column: try all "safe" positions. Position i is safe if: row[i], diag1[k+i], diag2[k-i] are safe, and square (k,i) is not knight-move reachable from (k-1)th and (k-2)th already-placed queens.
Note that queens (k-3)th and k-th are never knight-move reachable, since the column distance is 3 already.
My program is a simple backtrack:
- ninhnnsoc April 09, 2015#include <iostream> #include <cmath> //abs() using namespace std; const int Nmax = 20; bool row[Nmax], col[Nmax], diag1[2*Nmax], diag2[2*Nmax]; int N; long long nSolutions = 0; int Queens[Nmax]; void init(){ for(int i=0; i < Nmax; i++) row[i] = col[i] = true; for(int i=0; i < Nmax;i++) for(int j=0; j < Nmax;j++) diag1[i+j] = diag2[Nmax+i-j] = true; } void putAQueen(int k){ // always put k-th queen at column[k]; if (k >= N){ nSolutions++; // /* // Printing queens' placement: cout <<"Way #"<<nSolutions<<endl; for(int i=0; i<N; i++){ for(int j=0; j<N; j++){ if(j!=Queens[i]) cout <<"+"; else cout<<"Q"; }; cout<<endl; } cout<<endl; //*/ } else{ for(int i=0; i < N;i++) if (row[i] and diag1[i+k] and diag2[Nmax + i-k]) // normal queen if (k==0 or (k==1 and abs(Queens[k-1]-i) !=2 ) or (k>=2 and (abs(Queens[k-1]-i) !=2) and (abs(Queens[k-2]-i) !=1))){ // knight move check row[i] = false; diag1[i+k] = false; diag2[Nmax+i-k] = false; Queens[k] = i; putAQueen(k+1); row[i] = true; diag1[i+k] = true; diag2[Nmax+i-k] = true; } } }; int main() { init(); N = 16; // N =15: 32.516 ways; N=14: 5.180; N =16: 202.900 N = 17; // N =17: 1.330.622 ways (26 seconds without printing) N = 18; // N =18: 8.924.976 ways (190 seconds without printing) N = 10; putAQueen(0); cout << nSolutions << endl; return 0; } For explanation of how it works, you can check this post: capacode.com/?p=682