Jag implementerar en minst-konflikter-algoritm i denna handledning, detta för att lösa två problem med begränsningstillfredsställelse (CSP). Jag kommer att försöka lösa ett sodoku-pussel och ett N-drottningsproblem i Python med hjälp av en lokal sökalgoritm.
En minst-konflikter-algoritm startar med ett komplett initialtillstånd, detta initialtillstånd kan genereras slumpmässigt eller genom att man använder någon girig metod för att därigenom minska söktiden. Det initiala tillståndet kommer antagligen att ha konflikter (begränsningar som inte har uppfyllts), algoritmen kommer stegvis att försöka ta bort dessa konflikter genom att ändra värdet på en variabel i varje steg.
En minst-konflikter-algoritm kommer slumpmässigt att välja ut en variabel som är i konflikt i varje steg och tilldela ett värde med det minsta antalet konflikter till denna variabel. Algoritmen kan fastna i ett lokalt minimum utan att hitta någon lösning, detta om vi inte tillämpar någon slumpmässighet i urvalsprocessen. Vi måste slumpmässigt göra urval från värden som är lika bra och också inkludera mindre optimala kandidater i den mängd som vi gör urval från. Genom att införa lite slumpmässighet så kan algoritmen komma ut från lokala minimum.
Sodoku
Denna implementering kan användas för att lösa enklare och svårare sodoku-pussel, denna algoritm är inte garanterad att hitta en lösning varje gång. Jag använder lite slumpmässighet (var_rate och val_rate) för att inkludera variabler som inte är i konflikt och för att inkludera värden som inte är optimala. Algoritmen kan (med lite tur) lösa ett sodoku mycket snabbt.
# Import libraries
import sys
import copy
import random
# This class represent a sodoku
class Sodoku():
# Create a new sodoku
def __init__(self, state:[], size:int, sub_column_size:int, sub_row_size:int):
# Set values for instance variables
self.state = state
self.size = size
self.sub_column_size = sub_column_size
self.sub_row_size = sub_row_size
self.domains = {}
# Create domains for numbers by using Arc consistency
# Arc consistency: include only consistent numbers in the domain for each cell
self.update_domains()
# Update domains for cells
def update_domains(self):
# Reset domains
self.domains = {}
# Create an array with numbers
numbers = []
# Loop the state (puzzle or grid)
for y in range(self.size):
for x in range(self.size):
# Check if a cell is empty
if (self.state[y][x] == 0):
# Loop all possible numbers
numbers = []
for number in range(1, self.size + 1):
# Check if the number is consistent
if(self.is_consistent(number, y, x) == True):
numbers.append(number)
# Add numbers to a domain
if(len(numbers) > 0):
self.domains[(y, x)] = numbers
# Check if a number can be put in a cell
def is_consistent(self, number:int, row:int, column:int) -> bool:
# Check a row
for x in range(self.size):
# Return false if the number exists in the row
if (x != column and self.state[row][x] == number):
return False
# Check a column
for y in range(self.size):
# Return false if the number exists in the column
if (y != row and self.state[y][column] == number):
return False
# Calculate row start and column start
row_start = (row//self.sub_row_size)*self.sub_row_size
col_start = (column//self.sub_column_size)*self.sub_column_size;
# Check sub matrix
for y in range(row_start, row_start+self.sub_row_size):
for x in range(col_start, col_start+self.sub_column_size):
# Return false if the number exists in the submatrix
if (y != row and x != column and self.state[y][x]== number):
return False
# Return true if no conflicts has been found
return True
# Calculate number of conflicts
def number_of_conflicts(self, number:int, row:int, column:int) -> int:
# Number of conflicts
number_of_conflicts = 0
# Check a row
for x in range(self.size):
# Check if a conflict is found in a row
if (x != column and self.state[row][x] == number):
number_of_conflicts += 1
# Check a column
for y in range(self.size):
# Check if a conflict is found in a column
if (y != row and self.state[y][column] == number):
number_of_conflicts += 1
# Calculate row start and column start
row_start = (row//self.sub_row_size)*self.sub_row_size
col_start = (column//self.sub_column_size)*self.sub_column_size;
# Check sub matrix
for y in range(row_start, row_start+self.sub_row_size):
for x in range(col_start, col_start+self.sub_column_size):
# Check if a conflict is found in a submatrix
if (y != row and x != column and self.state[y][x]== number):
number_of_conflicts += 1
# Return the number of conflicts
return number_of_conflicts
# Create an initial solution
def create_initial_solution(self):
# Generate an initial solution (probably with conflicts)
for (y,x), numbers in self.domains.items():
# A dictionary to store numbers and the number of conflicts for each number
scores = {}
# Loop numbers
for number in numbers:
# Add to conflicts dictionary
scores[number] = self.number_of_conflicts(number, y, x)
# Sort scores on number of conflicts
scores = {key: value for key, value in sorted(scores.items(), key=lambda item: item[1])}
# Get best numbers
best_numbers = []
min = sys.maxsize
for key, value in scores.items():
# Add a number if it is less or equal to current minimum
if(value <= min):
best_numbers.append(key)
min = value
# Assign a number at random (one of the best numbers)
self.state[y][x] = random.choice(best_numbers)
# Print initial solution
print('\nInitial solution:')
self.print_state()
print()
# Min-conflicts algorithm
def min_conflicts(self, var_rate:float=0.04, val_rate:float=0.02, max_steps:int=100000) -> bool:
# Generate an initial solution (probably with conflicts)
self.create_initial_solution()
# Now repeatedly choose a random variable in conflict and change it
for i in range(max_steps):
# Print remaining steps
if((i + 1)%10000 == 0):
print(max_steps - i - 1)
# Variables
conflicts = []
conflict_count = 0
# Get all variables that are in conflict
for (y,x), numbers in self.domains.items():
# Check if the number is consistent
if(self.is_consistent(self.state[y][x], y, x) == False):
# Add the cell
conflicts.append((y,x))
# Add to the conflict count
conflict_count += 1
# Add at random to be able to jump out from a local minimum
elif (random.random() < var_rate):
# Add the cell
conflicts.append((y,x))
# Check if we have a valid solution
if(conflict_count <= 0):
return True
# Select a cell in conflict at random
y, x = random.choice(conflicts)
# Get numbers to chose from
numbers = self.domains.get((y, x))
# Loop numbers
scores = {}
for number in numbers:
# Add the number of conflicts as a score
scores[number] = self.number_of_conflicts(number, y, x)
# Sort scores on value
scores = {key: value for key, value in sorted(scores.items(), key=lambda item: item[1])}
# Get best numbers
best_numbers = []
min = sys.maxsize
for key, value in scores.items():
# Add a number if it is less or equal to current minimum
if (value <= min):
best_numbers.append(key)
min = value
# Add at random to be able to jump out from local minimum
elif (random.random() < val_rate):
best_numbers.append(key)
# Assign a number
self.state[y][x] = random.choice(best_numbers)
# No solution was found, return false
return False
# Print the current state
def print_state(self):
for y in range(self.size):
print('| ', end='')
if y != 0 and y % self.sub_row_size == 0:
for j in range(self.size):
print(' - ', end='')
if (j + 1) < self.size and (j + 1) % self.sub_column_size == 0:
print(' + ', end='')
print(' |')
print('| ', end='')
for x in range(self.size):
if x != 0 and x % self.sub_column_size == 0:
print(' | ', end='')
digit = str(self.state[y][x]) if len(str(self.state[y][x])) > 1 else ' ' + str(self.state[y][x])
print('{0} '.format(digit), end='')
print(' |')
# The main entry point for this module
def main():
# A simple puzzle 81 (9x9 matrix and 3x3 submatrixes)
#initial_state = [[0, 0, 4, 7, 2, 0, 9, 0, 0],
# [0, 3, 9, 0, 0, 8, 0, 0, 5],
# [0, 0, 1, 5, 0, 6, 0, 0, 4],
# [0, 4, 0, 0, 1, 0, 5, 2, 0],
# [0, 2, 8, 0, 5, 0, 1, 7, 0],
# [0, 1, 6, 0, 3, 0, 0, 9, 0],
# [4, 0, 0, 9, 0, 1, 3, 0, 0],
# [1, 0, 0, 3, 0, 0, 8, 4, 0],
# [0, 0, 7, 0, 8, 5, 6, 0, 0]]
#size = 9 # 9 columns and 9 rows
#sub_column_size = 3 # 3 columns in each submatrix
#sub_row_size = 3 # 3 rows in each submatrix
# Small puzzle 81 (9x9 matrix and 3x3 submatrixes)
data = '4173698.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'
data = data.strip().replace('.', '0')
numbers = [int(i) for i in data]
size = 9 # 9 columns and 9 rows
sub_column_size = 3 # 3 columns in each submatrix
sub_row_size = 3 # 3 rows in each submatrix
var_rate = 0.02
val_rate = 0.03
max_steps = 200000
# Larger puzzle 144 (12x12 matrix and 4x3 submatrixes)
#numbers = [7,0,5,0,4,0,0,1,0,0,3,6,9,6,0,0,7,0,0,0,0,1,4,0,0,2,0,0,0,0,3,6,0,0,0,8,0,0,0,10,8,0,0,9,3,0,0,0,11,0,12,1,0,0,0,0,10,0,5,9,0,0,6,0,0,3,12,0,0,0,0,0,0,0,0,0,0,7,4,0,0,9,0,0,2,12,0,7,0,0,0,0,4,10,0,5,0,0,0,11,5,0,0,2,7,0,0,0,1,0,0,0,3,6,0,0,0,0,8,0,0,11,3,0,0,0,0,5,0,0,9,7,10,5,0,0,2,0,0,7,0,3,0,1]
#size = 12 # 12 columns and 12 rows
#sub_column_size = 4 # 4 columns in each submatrix
#sub_row_size = 3 # 3 rows in each submatrix
#var_rate = 0.04
#val_rate = 0.02
#max_steps = 100000
# Create the initial state
initial_state = []
row = []
counter = 0
# Loop numbers and append to initial state
for number in numbers:
counter += 1
row.append(number)
if(counter >= size):
initial_state.append(row)
row = []
counter = 0
# Create a sodoku
sodoku = Sodoku(initial_state, size, sub_column_size, sub_row_size)
# Print sodoku
print('Puzzle input:')
sodoku.print_state()
# Solve sodoku with a min-conflicts algorithm
success = sodoku.min_conflicts(var_rate, val_rate, max_steps)
# Print sodoku
print('\nPuzzle solution:') if success == True else print('\nNo solution was found!!!\nEnd state:')
sodoku.print_state()
print()
# Tell python to run main method
if __name__ == "__main__": main()Puzzle input:
| 4 1 7 | 3 6 9 | 8 0 5 |
| 0 3 0 | 0 0 0 | 0 0 0 |
| 0 0 0 | 7 0 0 | 0 0 0 |
| - - - + - - - + - - - |
| 0 2 0 | 0 0 0 | 0 6 0 |
| 0 0 0 | 0 8 0 | 4 0 0 |
| 0 0 0 | 0 1 0 | 0 0 0 |
| - - - + - - - + - - - |
| 0 0 0 | 6 0 3 | 0 7 0 |
| 5 0 0 | 2 0 0 | 0 0 0 |
| 1 0 4 | 0 0 0 | 0 0 0 |
Initial solution:
| 4 1 7 | 3 6 9 | 8 2 5 |
| 9 3 6 | 1 5 8 | 7 4 1 |
| 8 5 2 | 7 4 2 | 3 9 6 |
| - - - + - - - + - - - |
| 3 2 5 | 9 7 4 | 1 6 8 |
| 6 7 1 | 5 8 6 | 4 3 9 |
| 6 4 8 | 9 1 5 | 2 3 7 |
| - - - + - - - + - - - |
| 2 8 9 | 6 4 3 | 5 7 1 |
| 5 6 3 | 2 9 7 | 9 8 4 |
| 1 7 4 | 8 5 8 | 6 2 3 |
190000
180000
170000
160000
150000
140000
130000
120000
110000
100000
90000
Puzzle solution:
| 4 1 7 | 3 6 9 | 8 2 5 |
| 6 3 2 | 1 5 8 | 9 4 7 |
| 9 5 8 | 7 2 4 | 3 1 6 |
| - - - + - - - + - - - |
| 8 2 5 | 4 3 7 | 1 6 9 |
| 7 9 1 | 5 8 6 | 4 3 2 |
| 3 4 6 | 9 1 2 | 7 5 8 |
| - - - + - - - + - - - |
| 2 8 9 | 6 4 3 | 5 7 1 |
| 5 7 3 | 2 9 1 | 6 8 4 |
| 1 6 4 | 8 7 5 | 2 9 3 |N-Drottningar
Detta problem handlar om att placera N drottningar på ett schackbräde med NxN-rutor, detta på ett sådant sätt att ingen av drottningarna kan attackera en annan drottning enligt reglerna i schack. Drottningar kan flytta diagonalt, vertikalt och horisontellt i schack. Algoritmen är inte garanterad att hitta en lösning varje gång, men den kan (med lite tur) hitta en lösning mycket snabbt. Jag har inkluderat slumpmässighet (val_rate) för att göra det möjligt för algoritmen att hoppa ut från lokala minimum.
# Import libraries
import sys
import random
# This class represent a queens chess board
class QueensBoard():
# Create a new queens board
def __init__(self, size:int):
# Set values for instance variables
self.size = size
# Create a board
self.state = []
for y in range(self.size):
row = []
for x in range(self.size):
row.append('.')
self.state.append(row)
# Create vectors
self.vectors = [(-1, -1), (-1, 1), (1, 1), (1, -1)]
# Check if a queen is consistent (no conflicts)
def is_consistent(self, position:()) -> bool:
# Get the row and column for the queen
row, column = position
# Check a row
for x in range(self.size):
# Return false if another queen exists in the row
if (x != column and self.state[row][x] == 'Q'):
return False
# Check a column
for y in range(self.size):
# Return false if another queen exists in the column
if (y != row and self.state[y][column] == 'Q'):
return False
# Check diagonals
for vector in self.vectors:
# Reset the start position
sy, sx = position
# Get vector deltas
dy, dx = vector
# Loop until we are outside the board or have moved the number of steps in the goal
while True:
# Update the position
sy += dy
sx += dx
# Check if the loop should terminate
if(sy < 0 or abs(sy) >= self.size or sx < 0 or abs(sx) >= self.size):
break
# Check if we found another queen
if (y != sy and x != sx and self.state[sy][sx] == 'Q'):
return False
# Return true if no conflicts has been found
return True
# Calculate number of conflicts
def number_of_conflicts(self, position:int) -> int:
# Number of conflicts
number_of_conflicts = 0
# Get the row and column for the queen
row, column = position
# Check a row
for x in range(self.size):
# Return false if another queen exists in the row
if (x != column and self.state[row][x] == 'Q'):
number_of_conflicts += 1
# Check a column
for y in range(self.size):
# Return false if another queen exists in the column
if (y != row and self.state[y][column] == 'Q'):
number_of_conflicts += 1
# Check diagonals
for vector in self.vectors:
# Reset the start position
sy, sx = position
# Get vector deltas
dy, dx = vector
# Loop until we are outside the board or have moved the number of steps in the goal
while True:
# Update the position
sy += dy
sx += dx
# Check if the loop should terminate
if(sy < 0 or abs(sy) >= self.size or sx < 0 or abs(sx) >= self.size):
break
# Check if we found another queen
if (y != sy and x != sx and self.state[sy][sx] == 'Q'):
number_of_conflicts += 1
# Return the number of conflicts
return number_of_conflicts
# Create an initial solution at random (probably with conflicts)
def create_initial_solution(self):
# Loop rows
for y in range(self.size):
# Get a column at random
x = int(random.random() * self.size) - 1
# Add a queen
self.state[y][x] = 'Q'
# Print initial solution
print('Initial solution:')
self.print_state()
print()
# Min-conflicts algorithm
def min_conflicts(self, val_rate:float=0.02, max_steps:int=100000) -> bool:
# Generate an initial solution (probably with conflicts)
self.create_initial_solution()
# Now repeatedly choose a random variable in conflict and change it
for i in range(max_steps):
# Print remaining steps
if((i + 1)%10000 == 0):
print(max_steps - i - 1)
# Variables
conflicts = []
# Get all queens that are in conflict
for y in range(self.size):
for x in range(self.size):
# Check if we have found a queen
if (self.state[y][x] == 'Q' and self.is_consistent((y, x)) == False):
# Add as a conflict
conflicts.append((y, x))
# Check if the puzzle is solved
if (len(conflicts) <= 0):
return True
# Select a conflict at random
y, x = random.choice(conflicts)
# A dictionary to store numbers and the number of conflicts for each number
scores = {}
# Loop each column in the row
for column in range(self.size):
# Count the number of conflicts
scores[(y, column)] = self.number_of_conflicts((y, column))
# Sort scores on number of conflicts
scores = {key: value for key, value in sorted(scores.items(), key=lambda item: item[1])}
# Get best positions
best_positions = []
min_conflicts = sys.maxsize
for key, value in scores.items():
# Add a position if it is less than or equal to current minimum
if(value <= min_conflicts):
best_positions.append(key)
min_conflicts = value
# Add at random to be able to jump out from local minimum
elif (random.random() < val_rate):
best_positions.append(key)
# Get one of the best positions at random
by, bx = random.choice(best_positions)
# Update queen position
self.state[y][x] = '.'
self.state[by][bx] = 'Q'
# No solution was found, return false
return False
# Print the current state
def print_state(self):
for y in range(self.size):
print('| ', end='')
for x in range(self.size):
print('{0} '.format(self.state[y][x]), end='')
print('|')
# The main entry point for this module
def main():
# Create a queens chess board
queens = QueensBoard(32)
# Solve n-queens problem with a min-conflicts algorithm
success = queens.min_conflicts()
# Print solution
print('\nPuzzle solution:') if success == True else print('\nNo solution was found!!!\nEnd state:')
queens.print_state()
print()
# Tell python to run main method
if __name__ == "__main__": main()Initial solution:
| Q . . . . . . . . . . . . . . . |
| . . . . . . . . . . . . . . . Q |
| . . . . . . . . . . Q . . . . . |
| . . . . . . . . . . . . Q . . . |
| . . . . . . . . . . . . . Q . . |
| . . . . . . . . . . . Q . . . . |
| . . Q . . . . . . . . . . . . . |
| . . . . . . . . . Q . . . . . . |
| . . . . . . . . . . . . . . Q . |
| . . . . . . . . Q . . . . . . . |
| . . . Q . . . . . . . . . . . . |
| . . . . . . . . . . . . . . Q . |
| . . Q . . . . . . . . . . . . . |
| . . . . . . . Q . . . . . . . . |
| . . . . . . . . . . . . . . Q . |
| . . . . . . . . . Q . . . . . . |
Puzzle solution:
| . Q . . . . . . . . . . . . . . |
| . . . . . Q . . . . . . . . . . |
| . . . . . . . . . . Q . . . . . |
| . . . . . . . . Q . . . . . . . |
| . . . Q . . . . . . . . . . . . |
| . . . . . . . . . . . . Q . . . |
| . . . . . . . . . . . . . . . Q |
| . . Q . . . . . . . . . . . . . |
| . . . . . . . . . . . . . . Q . |
| . . . . . . . . . Q . . . . . . |
| Q . . . . . . . . . . . . . . . |
| . . . . . . . . . . . . . Q . . |
| . . . . Q . . . . . . . . . . . |
| . . . . . . . Q . . . . . . . . |
| . . . . . . . . . . . Q . . . . |
| . . . . . . Q . . . . . . . . . |