Đây là bài toán tìm vị trí và đặt N quân hậu trên bàn cờ NxN để các quân cờ không tấn công nhau.
# Find path
Tự đặt các quân cờ đến khi thỏa đề bài.
Idea:
result sẽ có dạng:[1, 6, 4, 7, 0, 3, 5, 2] với index là vị trí dòng, số tại index đó là vị trí cột.
1. Ta sẽ bắt đầu từ row 0 tới row N.
2. Node có cấu trúc bao gồm chi phí và kết quả hiện tại.
3. Tại mỗi row sẽ kiểm tra các cột, các cột nào valid thì đều add(node chứa cột ấy) vào hàng đợi, trong hàng đợi sẽ sắp xếp lại theo thứ tự chi phí thấp nhất đến chi phí cao nhất.
4. Cứ cho loop đến khi ra kết quả hoặc hàng đợi rỗng thì trả về False.

Source:

from queue import PriorityQueue
class Node:
    def __init__(self,state,cost):
        self.state=state
        self.cost=cost

    def __lt__(self, other):
        return self.cost < other.cost

def check_valid(board, row, col):
    # Kiểm tra xem vị trí (row, col) có hợp lệ để đặt quân hậu không
    for i in range(row):
        #same column
        #2 hang cheo
        if board[i] == col or \
           board[i] - i == col - row or \
           board[i] + i == col + row:
            return False
    return True

def ucs(N):
   initial_state = [-1] * N
   count=0
   node=Node(initial_state,0)
   frontier=PriorityQueue()
   frontier.put(node)

   while 1:
       if frontier.empty(): 
           return False
       node = frontier.get()
       state=node.state
       cost=node.cost

       #found solution
       if state.count(-1)==0: 
           return state
       
       row = state.index(-1)
       #explored.append()
       for col in range(N):
            if check_valid(state, row, col):
                new_state = state[:]
                new_state[row] = col
                new_cost = cost + 1
                new_node = Node(new_state, new_cost)
                frontier.put(new_node)

n = 100
solution = ucs(n)

if solution is None:
    print("No solution.")
else:
    print("Solution:")
    for row in range(n):
        line = ""
        for col in range(n):
            if solution[row] == col:
                line += "x "
            else:
                line += "- "
        print(line)
        
Solution:
[1, 6, 4, 7, 0, 3, 5, 2]
- x - - - - - - 
- - - - - - x - 
- - - - x - - - 
- - - - - - - x 
x - - - - - - - 
- - - x - - - - 
- - - - - x - - 
- - x - - - - - 

# Uniform-cost search (UCS)
Các quân cờ được đặt sẵn trên bàn (initial state), di chuyển quân cờ (change state) chi phí là 1, sao cho thỏa đề với chi phí thấp nhất.

import tracemalloc
import time
import random
class Node:
    def __init__(self,state,cost,nextAction):
        self.state=state
        self.cost=cost
        self.nextAction=nextAction
def check_valid(board, row, col):
    # Kiểm tra xem vị trí (row, col) có hợp lệ để đặt quân hậu không
    for i in range(row):
        #same column
        #2 hang cheo
        if board[i] == col or \
           board[i] - i == col - row or \
           board[i] + i == col + row:
            return False
    return True
def insert(ls,a):
    for i in range(len(ls)):
        if ls[i].cost>a.cost:
            ls.insert(i,a)
            return ls
    ls.append(a)
def check_exist_and_add(ls,a):
    for i in ls:
        if i.state == a.state:
            if i.cost != a.cost:
                ls.insert(i,a)
                ls.pop(i+1)
    insert(ls,a)
def check_solution(ls):
    for row in range(len(ls)):
        if(check_valid(ls,row,ls[row])==False):return False
    return True
def ucs(N):
   initial_state = []
   for i in range(N):
    initial_state.append(random.randint(0,N-1))
   count=0
   node=Node(initial_state,0,0)
   frontier=[]
   insert(frontier,node)

   while 1:
       if len(frontier)==0: 
           return False
       node = frontier[0]
       frontier.pop(0)
       state=node.state
       cost=node.cost
       action=node.nextAction

       #found solution
       if check_solution(state): 
           return state
       if action==N-1:
        continue
    #    print(state)

       row=action
       #explored.append()
       for col in range(N):
                new_state = state[:]
                new_cost=cost+abs(col-state[row])
                new_state[row] = col
                new_node = Node(new_state, new_cost,action+1)
                check_exist_and_add(frontier,new_node)                 
n=7
solution = ucs(n)
print(solution)
# print(check_solution([2, 0, 3, 1]))
if solution is None:
    print("No solution.")
else:
    print("Solution:")
    print(solution)
    for row in range(n):
        line = ""
        for col in range(n):
            if solution[row] == col:
                line += "x "
            else:
                line += "- "
        print(line)

# A*
Giống ucs nhưng có thêm hàm heuristic làm tăng tốc độ của thuật toán. Với heuristic cost là số các quân hậu tấn công nhau (attacking_pairs).

import tracemalloc
import time
import random
class Node:
    def __init__(self,state,cost,nextAction):
        self.state=state
        self.cost=cost
        self.nextAction=nextAction

def check_valid(board, row, col):
    # Kiểm tra xem vị trí (row, col) có hợp lệ để đặt quân hậu không
    for i in range(row):
        #same column
        #2 hang cheo
        if board[i] == col or \
           board[i] - i == col - row or \
           board[i] + i == col + row:
            return False
    return True
def insert(ls,a):
    for i in range(len(ls)):
        if ls[i].cost>a.cost:
            ls.insert(i,a)
            return ls
    ls.append(a)
def check_exist_and_add(ls,a):
    for i in ls:
        if i.state == a.state:
            if i.cost != a.cost:
                ls.insert(i,a)
                ls.pop(i+1)
    insert(ls,a)
def check_solution(ls):
    for row in range(len(ls)):
        if(check_valid(ls,row,ls[row])==False):return False
    return True
def heuristic(board,row,col):
    # Hàm heuristic: Số cặp quân hậu tấn công nhau
    n = len(board)
    attacking_pairs = 0
    for i in range(n):
      if i==row: continue
      if board[i] == col or \
         board[i] - i == col - row or \
         board[i] + i == col + row:
          attacking_pairs += 1
    return attacking_pairs
def A_star(N):
   initial_state = []
   for i in range(N):
    initial_state.append(random.randint(0,N-1))
   count=0
   node=Node(initial_state,0,0)
   frontier=[]
   insert(frontier,node)

   while 1:
       if len(frontier)==0: 
           return False
       node = frontier[0]
       frontier.pop(0)
       state=node.state
       cost=node.cost
       action=node.nextAction

       #found solution
       if check_solution(state): 
           return state
       if action==N-1:
        continue
    #    print(state)

       row=action
       #explored.append()
       for col in range(N):
                new_state = state[:]
                new_cost=cost+abs(col-state[row])
                new_state[row] = col
                heuristic_cost=heuristic(new_state,row,col)
                new_node = Node(new_state, new_cost+heuristic_cost,action+1)
                check_exist_and_add(frontier,new_node)
                     
n=7
solution = A_star(n)
if solution is None:
    print("No solution.")
else:
    print("Solution:")
    print(solution)
    for row in range(n):
        line = ""
        for col in range(n):
            if solution[row] == col:
                line += "x "
            else:
                line += "- "
        print(line)

# Genetic
### Comment
* Random exploration find solutions that local search does not: Can solve “hard” problem
* Rely on very little domain knowledge
### Idea
* Population: a set of k randomly generated states to begin with
* Fitness: The number of non-attacking pairs of queens (min =0, max = 8×7/2 = 28)
* Crossover: combine 2 gen of parent
* Mutation: Each location is subject to random mutation with a small independent probability.

import random

class Individual:
    def __init__(self, state):
        self.state = state
        self.fitness = self.calculate_fitness()

    def calculate_fitness(self):
        # Tính fitness của cá thể
        n = len(self.state)
        attacking_pairs = 0
        for i in range(n - 1):
            for j in range(i + 1, n):
                if self.state[i] == self.state[j] or \
                   self.state[i] - i == self.state[j] - j or \
                   self.state[i] + i == self.state[j] + j:
                    attacking_pairs += 1
        return attacking_pairs

def create_individual(n):
    state = random.sample(range(n), n)
    return Individual(state)

def create_population(n, population_size):
    population = []
    for i in range(population_size):
        individual = create_individual(n)
        population.append(individual)
    return population

def crossover(parent1, parent2):
    n = len(parent1.state)
    cut = random.randint(0, n - 1)
    child_state = parent1.state[:cut] + parent2.state[cut:]
    child = Individual(child_state)
    return child

def mutate(individual):
    n = len(individual.state)
    swap_indices = random.sample(range(n), 2)
    individual.state[swap_indices[0]], individual.state[swap_indices[1]] = \
        individual.state[swap_indices[1]], individual.state[swap_indices[0]]
    individual.fitness = individual.calculate_fitness()

def genetic_algorithm(n, population_size, max_generations):
    population = create_population(n, population_size)
    generation = 0

    while generation < max_generations:
        # Sort population based on fitness
        population.sort(key=lambda individual: individual.fitness)

        if population[0].fitness == 0:
            # found solution
            return population[0].state

        new_population = []

        #Add the best individual to new population
        new_population.append(population[0])

        while len(new_population) < population_size:
            # choose parent
            parent1 = random.choice(population[:population_size // 2])
            parent2 = random.choice(population[:population_size // 2])
            child = crossover(parent1, parent2)
            mutate(child)
            new_population.append(child)

        population = new_population
        generation += 1

    return None

n = 8
population_size = 100
max_generations = 1000
solution = genetic_algorithm(n, population_size, max_generations)

if solution is None:
    print("No solution.")
else:
    print("Solution:")
    print(solution)
    for row in range(n):
        line = ""
        for col in range(n):
            if solution[row] == col:
                line += "x "
            else:
                line += "- "
        print(line)