Python 8 황후 문제 해결 예시
8 황후 문 제 는 체스 를 배경 으로 하 는 문제 입 니 다.어떻게 8 에서×8.체스 판 에 8 개의 황 후 를 놓 아 어떤 황후 도 다른 황 후 를 직접 먹 지 못 하 게 한다?이 를 위해 두 황 후 는 같은 횡행,종행,사선 에 있 을 수 없다.8 황후 문 제 는 더욱 일반적인 n 황후 배치 문제 로 보급 할 수 있다.이때 바둑판 의 크기 는 n1 로 바 뀌 었 다.×n1,황후 개수 도 n2 로 변 했다.그리고 n2=1 또는 n1≥3 일 때 만 문제 가 해결 된다.
이것 은 전형 적 인 역 추적 알고리즘 으로 우 리 는 문 제 를 분해 할 수 있다.
우선,우 리 는 충돌 검 측 문 제 를 해결 하 는 어떤 방법 을 생각해 야 한다.즉,바둑 알 을 서로 먹 을 수 있 는 위치 에 놓 아 서 는 안 된다.즉,인접 하고 좌우 대각선 에 놓 아 서 는 안 된다.
그 다음으로 역 추적 방법 을 활용 하여 문제 의 해 를 구한다.여기 서 구체 적 으로 함수 의 재 귀적 호출 입 니 다.바둑판 의 마지막 줄 로 호출 되면 뛰 어 나 와 해 를 구 할 수 있 습 니 다.
마지막 으로 우리 의 해 제 를 인쇄 합 니 다.어 려 운 점 은 재 귀 호출 함수 에 대한 이해 에 있다.
이것 은 단지 사고방식 일 뿐,우리 가 반드시 해결 해 야 할 문제 이지 만,프로그램의 운행 절 차 를 대표 하 는 것 은 아니다.
구체 적 인 코드 는 다음 과 같다.
#-*- coding:utf-8 -*-
import random
# ， state ， state ， ， ， ： state[0]=3， 1 4
def conflict(state, nextX):
nextY = len(state)
# print(nextY),
for i in range(nextY):
# （ ， ） ， ，
if abs(state[i]-nextX) in (0, nextY-i):
# 0 i
return True
return False
# ， 。
def queens(num, state=()):
#num = 8
# print("%d "%len(state)),
for pos in range(num):
if not conflict(state, pos): #
#
if len(state) == num-1:
yield (pos, ) #
# ， ， ， 。
else:
for result in queens(num, state+(pos,)):
yield (pos, ) + result
#result quees
# pos in range(num) conflict(state, num) ,
# ,
# pos in range(num) conflict(state, pos),
# ,state , queens(num, state) state
# ， X
def prettyprint(solution):
def line(pos, length=len(solution)):
return '. ' * (pos) + 'X ' + '. '*(length-pos-1)
for pos in solution:
print line(pos)
if __name__ == "__main__":# .py
prettyprint(random.choice(list(queens(8))))
Python 관련 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있 습 니 다.
본 논문 에서 말 한 것 이 여러분 의 Python 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Python의 None과 NULL의 차이점 상세 정보그래서 대상 = 속성 + 방법 (사실 방법도 하나의 속성, 데이터 속성과 구별되는 호출 가능한 속성 같은 속성과 방법을 가진 대상을 클래스, 즉 Classl로 분류할 수 있다.클래스는 하나의 청사진과 같아서 하나의 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
