[질문] N-Queen 일일히 dfs 말고 그래프 이용해서 푸는법 없음?

[ㅁㄴㅇ(211.59)]

다음 dfs 실행하기 전에

가로  세로   대각선

체크한다음에 안걸릴때만 실행하는거

이방법 말고 뭔가 더 빠르고 그래프틱한거 없음? 구글링 존나게 해도 저렇게 백트래킹으로 푼거밖에 안나오네

ㅅㅂ 그리고 백트래킹이라는 단어 존나 생소해서 보니까 종만북에서 한번도 본적없는단어였음

[옥토끼(moonrabbit2)]

빨라봤자 비트연산 오지게돌리는거 같은 시간 줄이는거 말곤 없음 NP여서 - dc App

[ㅁㄴㅇ(211.59)]

ㅅㅂ NP가 그런 뜻이었구나

[codefox(codefox)]

아니야ㅏ... - dc App

[하루룽(ailedear)]

퀸대신에 비숍이나 룩이면 니가원할만한 그래프틱한 풀이 가능

[시아닌(kimjg1119)]

와! 이분매칭 아시는구나!

[renard(wanderyonder)]

한가지 방법을 찾는거라거라면 랜덤한 방법도 있어요 길이 N인 순열 생성하고 마지막 몇개만 백트래킹으로 푼다던지.. N=500 이하에선 잘 나왔던거 같네요