Ruby로 N-Queens 문제 해결하기

N-Queens는 N * N 보드에 N 퀸을 배치해야 하는 흥미로운 코딩 챌린지입니다. .

다음과 같습니다.

여왕은 모든 방향으로 이동할 수 있습니다.

• 세로
• 가로
• 대각선

솔루션(많을 수 있음)은 모든 퀸을 보드에 배치해야 합니다. &모든 여왕은 다른 모든 여왕의 손이 닿지 않는 곳에 있어야 합니다.

이 기사에서는 제가 어떻게 솔루션을 생각해 냈는지 배우게 될 것입니다.

계획

이러한 종류의 문제를 해결할 때 시작하기 좋은 곳은 계획을 평범한 영어로 작성하는 것입니다.

이렇게 하면 문제가 무엇인지 및 해결 단계를 명확하게 이해할 수 있습니다.

계획을 작성하는 데 문제가 있는 경우 문제를 100% 이해했는지 확인 .

N-Queens 솔루션에 대한 나의 계획:

• 위치 0,0에서 시작
• 유효한 위치인 경우:퀸을 넣고 열(+1)을 진행하고 행을 0으로 설정
  • 위, 아래, 왼쪽, 오른쪽, 대각선 확인
• 기타:1칸 진행
  • 현재 위치 ==n이 아닌 경우 위로 이동(행 + 1)
  • 현재 열에 퀸을 배치할 수 없는 경우 역추적
    • 마지막 여왕 제거
    • 행 + 1을 사용하여 행 및 열을 마지막 여왕의 위치로 설정

이것은 내가 처음에 쓴 것보다 더 깔끔한 버전입니다.

구현하기 전에 더 자세한 정보가 필요한 단계를 드릴다운합니다.

지금 :

귀하의 계획은 완벽하지 않지만(내 계획은 그렇지 않았습니다) 무엇을 위해 일해야 하는지에 대한 아이디어를 제공할 것입니다.

확실한 계획을 작성할 수 없다면 해결책을 찾는 데 아무런 문제가 없습니다 …

... 솔루션이 어떻게 작동하는지 이해한 다음 직접 작성하십시오.

유효한 동작 찾기

위치가 유효한지 확인하려면 여러 방향을 살펴봐야 합니다.

2D 보드를 어지럽히는 대신 퀸 배열을 사용하기로 결정했습니다. 자신의 위치와 함께 이사회에서.

그런 다음 검증하려는 위치에 대해 이 퀸 배열을 확인합니다.

예를 들어, 행 검사의 경우:

def queen_in_row(row) @queens_in_board.find { |r, c| r ==행 }끝

행이 선택되면 퀸을 반환하고 그렇지 않으면 0을 반환합니다.

퀸을 배치한 후 다음 열로 이동하기 때문에 열이 비어 있는지 확인할 필요가 없습니다. .

대각선의 경우 4개가 있기 때문에 약간의 추가 작업이 필요합니다.

오른쪽 상단 대각선에 대한 코드는 다음과 같습니다.

def right_upper_diagonal_for(행, 열, n) 대각선 =[] 행 ==n까지 || 열 ==n 대각선 <<[행 +=1, 열 +=1] 끝 대각선 보내기

다른 대각선은 동일하며 루프의 조건과 방향(행 + 1 / 행 - 1)만 다릅니다.

이 작업을 올바르게 수행하는 데 약간의 시행착오가 필요했지만 괜찮습니다.

이러한 방법이 제대로 작동하는지 테스트하는 것이 중요합니다. . 일련의 작업 방법이 있는 경우 이를 조합하여 완전한 솔루션을 구성할 수 있습니다.

다음은 모든 대각선을 모아 보드의 모든 여왕에 대해 확인하는 방법입니다.

def queen_in_diagonal(행, 열, n) 대각선 =right_upper_diagonal_for(행, 열, n) + left_upper_diagonal_for(행, 열, n) + left_lower_diagonal_for(행, 열, n) + right_lower_diagonal_for(행, 열, n) .어느? { |r, c| r ==행 &&c ==열 } || 대각선.아니? { |r, c| @queens_in_board.any? { |qr, qc| r ==qr &&c ==qc } }끝

백트래킹 구현 방법

이러한 사소한 문제를 해결하려면 핵심 통찰력, 기술 또는 알고리즘을 알아야 합니다.

N-Queens의 경우 기술이 역추적 .

역추적은 이전 작업(예:보드에 퀸 배치)을 취소하고 다른 구성으로 다시 시도하는 것입니다.

이 부분이 가장 어려울 줄 알았는데 의외로 쉬웠습니다.

이를 파악하기 위해 약간의 시뮬레이션을 실행했습니다.

나는 스스로 판자와 여왕을 상징하는 상자를 그렸습니다. :

그런 다음 알고리즘을 시뮬레이션하기 위해 (마우스로 직접) 보드 주위의 상자를 이동했습니다.

코드는 다음과 같습니다.

행>=n 행 =@queens_in_board[-1][0] + 1 열 =@queens_in_board[-1][1] "역추적, 삭제됨:#{@queens_in_board.pop}" 종료

막혔을 때 다른 문제에 대해 이 작업을 수행할 수도 있습니다. 그리기 프로그램이나 종이에 그려서 가지고 놀 수도 있습니다.

작동 원리는 다음과 같습니다.

• 계속 올라갑니다. 보드의 맨 위에 도달하면 이 열에 여왕을 놓을 수 없다는 의미입니다.
• 현재 위치를 마지막 여왕으로 설정하고 보드에서 제거하여 역추적합니다.
• 이 위치에서 여왕을 배치할 수 없으면 다시 역추적합니다.

행 위치의 + 1은 마지막 여왕을 전진시켜 위치를 변경하는 방법입니다. &새 보드 구성을 엽니다.

n =4에 대해 이 코드를 실행할 때(n =2 &n =3에 대한 솔루션이 없음):

이 gif는 알고리즘의 시각적 예입니다.

전체 코드

def solve_n_queens(n) @queens_in_board =[] row =0 column =0 @queens_in_board.size ==n if queen_in_row(row) || Queen_in_diagonal(행, 열, n) 행 +=1 동안 행>=n 행 =@queens_in_board[-1][0] + 1 열 =@queens_in_board[-1][1]은 "역추적, 삭제됨:#{@ Queens_in_board.pop}" end else place_queen(행, 열) p "#{row} #{column}에 배치" 행 =0 열 +=1 끝 끝 @queens_in_boardenddef queen_in_row(행) @queens_in_board.find { |r, c | r ==행 }enddef queen_in_diagonal(행, 열, n) 대각선 =right_upper_diagonal_for(행, 열, n) + left_upper_diagonal_for(행, 열, n) + left_lower_diagonal_for(행, 열, n) + right_lower_diagonal,_forn(행 ) 대각선.아니요? { |r, c| r ==행 &&c ==열 } || 대각선.아니? { |r, c| @queens_in_board.any? { |qr, qc| r ==qr &&c ==qc } }enddef top_row?(행, n) 행 ==nenddef place_queen(행, 열) @queens_in_board <<[행, 열]enddef right_upper_diagonal_for(행, 열, n) 대각선 =[ ] 행 ==n ||까지 열 ==n 대각선 <<[행 +=1, 열 +=1] 끝 대각선enddef left_upper_diagonal_for(행, 열, n) 대각선 =[] 행 ==n까지 || 열 ==0 대각선 <<[행 +=1, 열 -=1] 끝 대각선senddef right_lower_diagonal_for(행, 열, n) 대각선 =[] 행 ==0까지 || 열 ==n 대각선 <<[행 -=1, 열 +=1] 끝 대각선enddef left_lower_diagonal_for(행, 열, n) 대각선 =[] 행 ==0까지 || 열 ==0 대각선 <<[행 -=1, 열 -=1] 끝 대각선enddef print_board(n) 보드 =Array.new(n) { Array.new(n) { "." } } @queens_in_board.each { |여왕| 보드[퀸[0]][퀸[1]] ="Q" } 보드.맵 { |n| n.join("|") }.reverseendp solve_n_queens(4)p solve_n_queens(5) puts print_board(5)

재귀 버전

이것은 가능한 모든 솔루션을 찾는 대체 버전입니다.

def solve_n_queens(n, column =0, queens_in_board =[]) @queens_in_board =queens_in_board n.times do |row| Queen_in_row(row)가 아니면 || Queen_in_diagonal(row, column, n) place_queen(row, column) solve_n_queens(n, column + 1, @queens_in_board) remove_last_queen end end는 @queens_in_board.size ==nend

변경되는 유일한 것은 solve_n_queens입니다. 방법.

이 버전은 재귀(자신을 호출하는 메서드)를 사용하여 모든 부분 솔루션을 탐색합니다.

완전한 솔루션이 발견되면 print_board를 사용하여 인쇄합니다. 방법.

요약

N-Queens 코딩 문제와 Ruby에서 해결하는 방법에 대해 배웠습니다. 문제 해결 능력을 향상시키는 방법도 배웠습니다.

이 기사가 마음에 들면 이 기사를 활용할 수 있는 사람과 공유하십시오.

읽어주셔서 감사합니다!