1

For practice I have started solving interviewstreet problems. I cam across this queens on board problem.

Queens on Board (50 Points)

You have an N * M chessboard on which some squares are blocked out. In how many ways can you place one or more queens on the board such that no two queens attack each other? Two queens attack each other if one can reach the other by moving horizontally, vertically or diagonally without passing over any blocked square. At most one queen can be placed on a square. A queen cannot be placed on a blocked square.

Input: The first line contains the number of test cases T. T test cases follow. Each test case contains integers N and M on the first line. The following N lines contain M characters each representing the board. A '#' represents a blocked square and a '.' represents an unblocked square.

Output: Output T lines containing the required answer for each test case. As the answers can be really large, output them modulo 1000000007.

https://www.interviewstreet.com/challenges/dashboard/#problem/4e904d63c5069

I am wondering what is the best algorithm to solve this problem?

Thank you.

Manas Paldhe
  • 766
  • 1
  • 10
  • 32
  • possible duplicate of [N-Queens Problem..How far can we go?](http://stackoverflow.com/questions/1863531/n-queens-problem-how-far-can-we-go) and [N Queens Placement Algorithm](http://stackoverflow.com/q/11476500/62576) – Ken White Jan 25 '13 at 00:29
  • @KenWhite This "**one or more** queens N*M" is algorithmically different than the classic N-Queens challenge, because the "termination condition" in the recursive placement method/function is a bit more complicated than "row==N". – WebViewer Nov 10 '22 at 16:10

1 Answers1

-1

This page provides an easy to follow implementation of the N-Queens problem. If you want to find all permutations, in the nQueenProblem method, instead of using the simple addQueen(0, queens, n);, just iterate with different values using a for loop. And instead of returning the correct board, just count the boards.

kasavbere
  • 5,873
  • 14
  • 49
  • 72
  • this is a brute-force method and takes a huge amount of time. I am looking for a faster algorithms. Thank you. – Manas Paldhe Jan 25 '13 at 01:16
  • @ManasPaldhe According to wikipedia (http://en.wikipedia.org/wiki/Eight_queens_puzzle#Counting_solutions), `There is currently no known formula for the exact number of solutions.` Perhaps someone else has a faster alternative than what I was able to find for you. – kasavbere Jan 25 '13 at 02:13
  • 1
    in this particular problem there are some constraints, there are some "blocked" squares – Manas Paldhe Jan 25 '13 at 17:18
  • 1
    Also since we need need not place n queens, I think some dynamic programming solution should work – Manas Paldhe Jan 25 '13 at 17:19