Minst-konflikter, algoritm i Python

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

Lämna ett svar

Din e-postadress kommer inte publiceras. Obligatoriska fält är märkta *