acm problem: firenet
-
http://acm.zju.edu.cn/show_problem.php?pid=1002[^] A description of the algorithm is enough, even better with an implementation. Thanks.
-
This appears to me to be a simple modification of the n-queens problem. Placing n queens on a board such that no queen can capture any other queen. I would persue this line of thought with a google search on the n-queens problem.
Hi, I beg to differ. On an n*n board (with n>2) you can place n queens, the only problem is finding one of the many solutions. In the problem at hand, you dont know beforehand how many "queens" you can put; you loose some squares to the walls, and in return the walls typically offer the possibility to put more than n. BTW the maximum seems to be n*n/2 (putting a wall on all the squares of one color). :)
Luc Pattyn [My Articles] [Forum Guidelines]
-
Hi, I beg to differ. On an n*n board (with n>2) you can place n queens, the only problem is finding one of the many solutions. In the problem at hand, you dont know beforehand how many "queens" you can put; you loose some squares to the walls, and in return the walls typically offer the possibility to put more than n. BTW the maximum seems to be n*n/2 (putting a wall on all the squares of one color). :)
Luc Pattyn [My Articles] [Forum Guidelines]
I agree with you totally on the number of queens that could be placed on this board due to wall constraints, this is why I suggested a modified version of n queens. The wall constraints could easily be taken into account and still allow for the same "Basic" n queens algorithm to function correctly.