Min-Conflicts Algorithm in Python

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  .  .  .  .  .  .  .  .  .  |

Leave a Reply

Your email address will not be published. Required fields are marked *