420yoloswag69's blog

Chess problem
By 420yoloswag69, history, 9 years ago, In English

Hi i need a bit of help !

Consider a chessboard of size NxN.

Your must find the maximum number of bishops that can be placed on the chessboard, such that no pair of bishops can attack each other. Some cells are damaged. Bishops cannot be placed on these cells, but they can attack through them. N<100

I can do a naive bruteforce but it keeps giving me timelimit. Any tip how to optimize it ?

Thanks!

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

It is maximal matching problem.

Let's build a graph:
Diagonals will be its vertices
There is an edge between two vertices if their diagonals share a cell.

We have to build maximum matching in this bicomponent graph.

It can be done with Hungarian algorithm in O(n3) time.

→ Reply