Задача о N ферзях и распространение ограничений

Задача о N ферзях

# N-Queens constraints:
# 1. Exactly one queen per row
# 2. No two queens in the same column
# 3. No two queens on the same diagonal (top-left to bottom-right)
# 4. No two queens on the same anti-diagonal (top-right to bottom-left)

# For N=4, the 2 solutions:
sol1 = ['.Q..', '...Q', 'Q...', '..Q.']
sol2 = ['..Q.', 'Q...', '...Q', '.Q..']
print('N=4 solutions:')
for row in sol1: print(row)
print()
for row in sol2: print(row)

Размещение по одному ферзю в каждой строке

def solve_n_queens(n):
    results = []
    queens = []  # queens[row] = column of queen in that row
    
    def backtrack(row):
        if row == n:
            # Build the board representation
            board = []
            for r in range(n):
                board.append('.' * queens[r] + 'Q' + '.' * (n - queens[r] - 1))
            results.append(board)
            return
        for col in range(n):
            if is_valid(row, col):
                queens.append(col)   # CHOOSE
                backtrack(row + 1)   # EXPLORE
                queens.pop()         # UNCHOOSE
    
    def is_valid(row, col):
        for r, c in enumerate(queens):
            if c == col: return False             # same column
            if abs(row - r) == abs(col - c): return False  # diagonal
        return True
    
    backtrack(0)
    return results

print(len(solve_n_queens(4)), 'solutions for N=4')  # 2
print(len(solve_n_queens(8)), 'solutions for N=8')  # 92

Проверка ограничений за O(1) с помощью множеств

def solve_n_queens_fast(n):
    results = []
    cols = set()       # occupied columns
    diag = set()       # row - col (positive diagonal)
    anti = set()       # row + col (negative diagonal)
    queens = []
    
    def backtrack(row):
        if row == n:
            board = ['.' * c + 'Q' + '.' * (n-c-1) for c in queens]
            results.append(board)
            return
        for col in range(n):
            if col in cols or (row-col) in diag or (row+col) in anti:
                continue  # PRUNE: constraint violated
            # CHOOSE
            cols.add(col); diag.add(row-col); anti.add(row+col); queens.append(col)
            backtrack(row + 1)  # EXPLORE
            # UNCHOOSE
            cols.remove(col); diag.remove(row-col); anti.remove(row+col); queens.pop()
    
    backtrack(0)
    return results

print(len(solve_n_queens_fast(8)))  # 92

Объяснение инварианта диагоналей

# Visualise the diagonal invariants for a 4x4 board
n = 4
print('row-col values (same diagonal):')
for r in range(n):
    print([r-c for c in range(n)])

print('row+col values (same anti-diagonal):')
for r in range(n):
    print([r+c for c in range(n)])

# Verify: (0,0) and (2,2) share diag value 0
print('(0,0) diag:', 0-0, '| (2,2) diag:', 2-2)  # both 0
# Verify: (0,2) and (2,0) share anti-diag value 2
print('(0,2) anti:', 0+2, '| (2,0) anti:', 2+0)  # both 2

Подсчёт решений: задача о N ферзях II

def total_n_queens(n):
    count = [0]
    cols = set(); diag = set(); anti = set()
    def backtrack(row):
        if row == n:
            count[0] += 1
            return
        for col in range(n):
            if col in cols or (row-col) in diag or (row+col) in anti:
                continue
            cols.add(col); diag.add(row-col); anti.add(row+col)
            backtrack(row + 1)
            cols.remove(col); diag.remove(row-col); anti.remove(row+col)
    backtrack(0)
    return count[0]

for n in range(1, 11):
    print(f'N={n}: {total_n_queens(n)} solutions')

Задача о N ферзях с битовыми масками для ускорения

def total_n_queens_bitmask(n):
    full = (1 << n) - 1  # all n columns set
    count = [0]
    def bt(cols, left_diag, right_diag):
        if cols == full:
            count[0] += 1
            return
        available = full & ~(cols | left_diag | right_diag)
        while available:
            bit = available & -available  # lowest set bit
            available &= available - 1   # remove lowest bit
            bt(cols | bit,
               (left_diag | bit) << 1,
               (right_diag | bit) >> 1)
    bt(0, 0, 0)
    return count[0]

for n in range(1, 13):
    print(f'N={n}: {total_n_queens_bitmask(n)}')

Концепция распространения ограничений

# Constraint propagation in Sudoku:
# After placing 5 in cell (0,0):
# - Row 0: no other cell can have 5
# - Column 0: no other cell can have 5
# - Box (0,0)-(2,2): no other cell can have 5
# This is propagated BEFORE branching further

# Simple demo: remaining valid columns after placing queens
def remaining_columns(n, queens):
    cols = set(q for q in queens)
    diags = set(r - q for r, q in enumerate(queens))
    anti_diags = set(r + q for r, q in enumerate(queens))
    row = len(queens)
    return [c for c in range(n)
            if c not in cols
            and (row-c) not in diags
            and (row+c) not in anti_diags]

print(remaining_columns(8, [0]))  # valid cols for row 1 after placing col 0 in row 0

Решатель судоку

def solve_sudoku(board):
    def is_valid(r, c, num):
        for i in range(9):
            if board[r][i] == num: return False  # row
            if board[i][c] == num: return False  # col
        br, bc = (r//3)*3, (c//3)*3
        for i in range(3):
            for j in range(3):
                if board[br+i][bc+j] == num: return False  # box
        return True
    
    def backtrack():
        for r in range(9):
            for c in range(9):
                if board[r][c] == '.':
                    for d in '123456789':
                        if is_valid(r, c, d):
                            board[r][c] = d
                            if backtrack(): return True
                            board[r][c] = '.'
                    return False  # no valid digit found
        return True  # no empty cells: solved
    
    backtrack()
    return board

# Mini test with a solvable board (simplified)
print('Sudoku solver implemented')

Эвристика наиболее ограниченной переменной

def solve_sudoku_mrv(board):
    '''Find cell with fewest valid choices (MRV heuristic).'''
    def valid_choices(r, c):
        nums = set('123456789')
        for i in range(9):
            nums.discard(board[r][i])
            nums.discard(board[i][c])
        br, bc = (r//3)*3, (c//3)*3
        for i in range(3):
            for j in range(3):
                nums.discard(board[br+i][bc+j])
        return nums
    
    def find_mrv():
        best = (10, -1, -1, set())  # (choices_count, r, c, choices)
        for r in range(9):
            for c in range(9):
                if board[r][c] == '.':
                    choices = valid_choices(r, c)
                    if len(choices) < best[0]:
                        best = (len(choices), r, c, choices)
        return best[1], best[2], best[3]
    
    def backtrack():
        r, c, choices = find_mrv()
        if r == -1: return True  # no empty cells
        for d in choices:
            board[r][c] = d
            if backtrack(): return True
            board[r][c] = '.'
        return False
    
    backtrack()
    return board

Таблица числа решений задачи о N ферзях

def count_queens(n):
    '''O(1) per constraint check using sets.'''
    count = [0]
    cols = set(); diag = set(); anti = set()
    def bt(row):
        if row == n: count[0] += 1; return
        for col in range(n):
            if col in cols or (row-col) in diag or (row+col) in anti: continue
            cols.add(col); diag.add(row-col); anti.add(row+col)
            bt(row+1)
            cols.discard(col); diag.discard(row-col); anti.discard(row+col)
    bt(0)
    return count[0]

sequence = [count_queens(n) for n in range(1, 12)]
print('N-Queens counts:', sequence)
# [1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680]

Построение доски для задачи о N ферзях

def n_queens_boards(n):
    results = []
    queens = []
    cols = set(); diag = set(); anti = set()
    def build_board():
        return ['.' * c + 'Q' + '.' * (n-c-1) for c in queens]
    def bt(row):
        if row == n:
            results.append(build_board())
            return
        for col in range(n):
            if col in cols or (row-col) in diag or (row+col) in anti: continue
            cols.add(col); diag.add(row-col); anti.add(row+col); queens.append(col)
            bt(row+1)
            cols.remove(col); diag.remove(row-col); anti.remove(row+col); queens.pop()
    bt(0)
    return results

for board in n_queens_boards(4):
    for row in board: print(row)
    print()

Быстрая проверка

Итоги урока