I am implementing a min-conflicts algorithm in this tutorial, to solve two constraint satisfaction problems (CSP). I am going to try to solve a sodoku puzzle and a n-queens problem in Python by using a local search algorithm.
A min-conflicts algorithm starts with a complete initial state, this initial state can be generated at random or by using some greedy approach to speed up the processing time. The inital state will probably have conflicts (constraints not fulfilled) and the min-conflicts algorithm will try to remove these conflicts step-by-step, by changing the value of one variable in each step.
A min-conflicts algorithm will select a variable in conflict at random in each step and assign the value with the minimum number of conflicts to this variable. The algorithm might get stuck in a local minimum and be unable to find a solution, if we don’t apply some randomness. We must break ties at random and also include less optimal candidates at random to be able to jump out from local minimas.
Sodoku
This implementation can be used to solve simple and hard sodoku puzzles, this algorithm is not guaranteed to find a solution every time. I am using some randomness (var_rate and val_rate) to include variables that not are in conflict and to include values that not are optimal. The algorithm can solve a puzzle very fast with some luck.
# 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-Queens problem
This problem is about placing N queens on a NxN chess board in such a way that none of the queens can attack another queen according to rules in chess, queens can move diagonal, vertical and horizontal in chess. The algorithm is not guaranteed to find a solution every time, but it can find a solution very fast with some luck. I have included som randomness (val_rate) to enable the algorithm to jump out from local minimas.
# 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 . . . . . . . . . |