In fact, it means that two 'X' -- named A and B -- can be put in different '#'s if and only if both the positions (row_A,column_B) and 
(row_B,column_A) is not '#' -- instead of 'X'.

Sorry for described it incorrectly. I made a false analogue of 8 queens problem. It is quite different from 8 queens problem.


Does anyone knows the solutions?
Many Thanks!


> A square chess-borad is givern. It is diagonal symetric with striples
>  of '#' and '.'. An 'X' can be placed on to the '#', but without having 
> the same row or column with other 'X' placed before (like famous eight 
> queen problem :-)).
>  
> An example is below:
>  
> #...#..##
> ...#..##.
> ..#..##..
> .#..##..#
> #..##..#.
> ..##..#..
> .##..#..#
> ##..#..##
> #..#..##.
>  
> To this instance, the answer is 4 as follows:
> 
> X...#..##
> ...X..##.
> ..X..##..
> .X..##..#
> #..##..#.
> ..##..#..
> .##..#..#
> ##..#..##
> #..#..##.
> 
> Given a such chessborad of size n, how to solve it efficiently?
> Any comment or hint is welcome!
> Bow!

• up (390) chipmunk 2008-02-11 01:49:21
• up (390) chipmunk 2008-02-13 22:41:53
  • i guess maybe this problem is np-something... (0) frkstyc 2008-02-13 22:47:59
    • Maybe. But if it is, how to prove it? I mean, how to make the reduction? (0) chipmunk 2008-02-14 10:08:57
  • up (0) chipmunk 2008-02-17 02:27:53