This problem is driving me crazy... Place N bishops on NxN board in a way, where all squares would be occupied or attacked with at least one of them.
Could anyone help me out with an algorithm for solving this problem?
+6
A:
_ _ _ _ ♗ _ _ _ _ _ _ _ _ ♗ _ _ _ _ _ _ _ _ ♗ _ _ _ _ _ _ _ _ ♗ _ _ _ _ _ _ _ _ ♗ _ _ _ _ _ _ _ _ ♗ _ _ _ _ _ _ _ _ ♗ _ _ _ _ _ _ _ _ ♗ _ _ _ _ _ _ _ _ ♗ _ _ _ _
Mark Byers
2010-04-11 15:03:28
The word "backtracking" suggests that the OP wants _all_ the possible bishop arrangements.
Vlad
2010-04-11 15:10:21
I know the solution. I need help with the algorithm.
Cinnamon
2010-04-11 15:12:01
@Cinnamon: The algorithm - 1) Choose any row or column. 2) Place bishops in every cell in this row or column. Seriously though, if this isn't what you want it would help if you added a little more detail to your question. Explain: what you want, how and why backtracking should be used, what you've tried, your code if any, and what problems you are having getting it working.
Mark Byers
2010-04-11 15:22:48
@Mark: They have to be in the center.
Potatoswatter
2010-04-11 15:41:33
@Potatoswatter: Good point. I need one more step: 3) If your chosen row or column doesn't work, backtrack and try a new row/column. So now the algorithm also includes backtracking as requested. ;-)
Mark Byers
2010-04-11 15:42:59
@Mark: LOL.....
Potatoswatter
2010-04-11 15:47:53
+1 for clever use of Unicode
Anurag
2010-04-11 16:48:49
+2
A:
There is a minimum and a maximum solution for this problem it isn't as trivial.
Check this BishopsProblem or more detailed
I'm sure you will easily find an example in c.
stacker
2010-04-11 15:15:54
+1
A:
Why backtrack? Use the small number of solutions to obtain a proof.
Even a greedy algorithm will suffice: Count the number of squares reachable from each square. Pick a square with the greatest reach that doesn't overlap with a previously picked reach. Repeat.
Ambiguity generates horizontal, vertical, and side-of-center variations.
N bishops is only enough to reach each square with exactly one bishop. If you picked squares with overlapping reach, the final tally of reachable squares would be lower. Hmm, maybe you need to quantify how much lower for any given bad square. Sounds doable.
For such a huge problem space, brute-force backtracking doesn't sound promising.
Potatoswatter
2010-04-11 15:40:46
I started writing this algorithm with backtracking... And I thought there is no better way. But I love your idea! I will try to implement it. But before that, "number of squares reachable" is, essentially, number of squares which can be attacked from a certain square, right?
Cinnamon
2010-04-11 16:06:07
+2
A:
I'm assuming you're asking for some optimizations, since the backtracking algorithm is what it is.
First thing to notice is that you can separate the black and white - you take the sum of B_i * W_j where i + j = N. You can also visualize the diagonals as a simple grid (with constraints) as it'll likely make the code tighter and maybe easier to understand. Another optimization is noticing that the color does not necessarily matter -- the results for some blacks can be used for some whites. Figure out when this happen and when it doesn't.
Hope this is a good enough boost -- should be sufficient for some smallish N's.
Larry
2010-04-11 16:30:31