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 (687) chipmunk 2008-02-07 10:48:55
  • 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
• Sorry for misrepresent the problem! (1057) chipmunk 2008-02-09 23:37:46
  • 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