8 황후 문제 파 이 썬 버 전

제목:
N * N 정사각형 바둑판 을 정 하고 그 위 에 N 개의 바둑 알 을 놓 으 면 황후 라 고도 부 르 며 두 개의 바둑 알 이 모두 같은 횡선, 세로 선, 사선 에 있 지 않도록 한다.일반적으로 우 리 는 8 황 후 를 토론 하지만 N > 4 만 있 으 면 해 가 존재 할 것 이다.
분석:
방법 1: 정의 에 따라 처리 합 니 다. 즉, 바둑판 에 황 후 를 놓 을 때마다 어떤 위치 에 새로 가입 한 황 후 를 놓 을 수 있 는 지, 어떤 곳 에 황 후 를 놓 으 면 충돌 할 수 있 는 지 판단 해 야 합 니 다.내 가 아래 에 쓴 이 코드 는 바로 이것 에 기초 한 것 이다.
방법 2. 저 는 다른 사람의 최 적 화 를 보 았 습 니 다. 주로 비트 연산 으로 계산 복잡 도 를 낮 추 는 것 을 실 현 했 습 니 다. 저 는 Python 으로 이 를 실현 하지 않 았 습 니 다.
그래서 여기 구 덩이 를 하나 파 요.
코드:
코드 에 있 는 주석 은 상세 한 설명 이 있 습 니 다. N 값 을 설정 하면 요구 에 부 합 된 해 를 되 돌려 줍 니 다.그러나 이 문 제 는 또 하나의 진급 이 있다. 그것 은 바로 몇 개의 해 가 있 는 지 토론 하 는 것 이다. 그러면 수론 의 지식 이 필요 하 다. 그리고 나 는 이 수학 에 대해 연구 한 적 이 없 기 때문에 코드 도 실현 되 지 않 았 다.여러분, 코드 를 아 쉬 운 대로 사용 하 시 면 됩 니 다.

class EightQueensPuzzle(object):
    '''
           
          ：
        eight_q = EightQueensPuzzle(4, 5)
        print "EIGHT QUEEDS PUZZLE:"
        result = eight_q.eight_queens_puzzle()
        for i in result:
            print i
    '''
    def __init__(self, n, char):
        self.n = n  #     
        self.char = char  #       

    def init_chess_board(self, n):
        '''
               ，          n     ,        ，    8
        :return:     ，    8*8   
        '''
        chess_board = []
        for i in xrange(0, n):
            line = []
            for j in xrange(0, n):
                line.append(0)
            chess_board.append(line)
        return chess_board

    def update_conflict_board(self, conflict_board, position):
        for k in xrange(0, self.n):  #      1
            conflict_board[position[0]][k] = 1
        for id in xrange(position[0]+1, self.n):
            conflict_board[id][position[1]] = 1  #      1
            if position[0] + position[1] - id >= 0:  #       1
                conflict_board[id][position[0] + position[1] - id] = 1
            if position[1] - position[0] + id < self.n:  #       1
                conflict_board[id][position[1] - position[0] + id] = 1

    def queens_conflict(self, conflict_board, position):
        '''
                 conflict_board,       position          ，       。
                 False，         True
        '''
        if conflict_board[position[0]][position[1]] != 0:
            return False
        else:
            return True

    def eight_queens_puzzle(self):
        '''
                    。
        :return:         .
        '''
        import random
        while True:  #               
            chess_board = self.init_chess_board(self.n)
            conflict_board = self.init_chess_board(self.n)
            for i in xrange(0, self.n):
                flag = 0
                for cnt in conflict_board[i]:
                    if cnt != 0:
                        flag += 1
                if flag == self.n:  #     1    ，        
                    break

                while True:
                    pos = [i, random.randint(0, self.n-1)]  #          
                    if self.queens_conflict(conflict_board, pos):  #       
                        chess_board[i][pos[1]] = self.char
                        self.update_conflict_board(conflict_board, pos)
                        break
            if self.char in chess_board[self.n-1]:
                return chess_board