조건부 자리배치에 대한 강력한 알고리즘 있나?

예를들면 교실이라 치면 한명을 앉히면 양 옆자리엔 앉힐수없다,

혹은 앞자리엔 앉힐수없다, 같은 조건 붙을때

최대한 많이 배치하는 방법 구하는 문제 같은거..

지금 내가 하는건 둘씩 짝지어서 격자점 두개 위에 앉혀야하는데

(0.5*(2i+1),0.5*(2j+1)) 단위로 장애물이 놓여있어 ㅠㅠ

i,j는 어디어디인지 입력에서 다 받아

그래서 둘 사이를 장애물이 가르게되면 못앉아

세로로 둘이 앉든 가로로 둘이 앉든 상관없는데 대각선으로는 못앉아

이거 풀만한 강력한 알고리즘 있으면 추천좀..

부탁좀할게