> 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!

• It may be helpful to compute the Maximum Matching on the bipartite graph represented by the chessboard. (0) ArXoR 2008-02-07 20:05:32
  • Thanks! Any detail? Or any comment is helpful! (0) chipmunk 2008-02-09 00:04:46