Looking for finite semigroups without identities

semigroup_search.py

from constraint import *

n = 6

problem = Problem()

problem.addVariables( range( 0, n**2 ), range( 0, n ) )

# Associativity:
# v[v[a,b],c] = v[a,v[b,c]]
# We can't specify which variables are affected because it is dynamic based
class AssociativeConstraint(Constraint):
    def __init__( self, a, b, c ):
        self.a = a
        self.b = b
        self.c = c
    
    def __call__( self, variables, domains, assignments, forwardcheck ):
        a = self.a
        b = self.b
        c = self.c
    
        v2 = a*n + b
        v4 = b*n + c
        if v2 not in assignments:
            return True
        if v4 not in assignments:
            return True
        ab = assignments[v2]
        bc = assignments[v4]
        v1 = ab*n + c
        v3 = a*n + bc
        #print( f"Checking associativity {assignments.get(v1)} = v{v1} = ({a}.{b}).{c} = {a}.({b}.{c}) = v{v3} = {assignments.get(v3)}" )
        if v1 in assignments and v3 in assignments:
            # Must be equal if both assigned
            return assignments[v1] == assignments[v3]

        if forwardcheck:
            if v1 in assignments and v3 not in assignments:
                domain = domains[v3]
                must_be = assignments[v1]
                #print( f"Hiding all values but {must_be} from domain {domain} for {v3}" )
                for value in domain[:]:
                    if value != must_be:
                        domain.hideValue( value )
                if len( domain ) == 0:
                    return False
                
            if v3 in assignments and v1 not in assignments:
                domain = domains[v1]
                must_be = assignments[v3]
                #print( f"Hiding all values but {must_be} from domain {domain} for {v1}" )
                for value in domain[:]:
                    if value != must_be:
                        domain.hideValue( value )
                if len( domain ) == 0:
                    return False

        return True

testAssign = { (a*n+b) : ((a+b) % 4) for a in range(0,n) for b in range(0,n) }

for a in range( 0, n ):
    for b in range( 0, n ):
        for c in range( 0, n ):
            cons =  AssociativeConstraint( a, b, c )
            if not cons( [], [], testAssign, False ):
                print( f"Failed associativity for {a},{b},{c}" )
                raise Exception
            problem.addConstraint( cons )
            


# Non-identity:
# v[a,x] != x for some x
# v[x,a] != x for some x
class NotIdentityConstraint(Constraint):
    def __init__( self, a ):
        self.a = a   

    def __call__( self, variables, domains, assignments, forwardcheck ):
        a = self.a

        #print( f"Checking whether {a} is the identity" )
        leftCounter = False
        rightCounter = False
        for x in range( 0, n ):
            v1 = a*n + x

            if v1 not in assignments:
                leftCounter = True
                break

            if assignments[v1] != x:
                #print( f"Counterexample: {a}.{x} = {assignments[v1]} != {x}" )
                leftCounter = True
                break
            
        for x in range( 0, n ):                
            v2 = x*n + a        
            if v2 not in assignments:
                rightCounter = True
                break

            if assignments[v2] != x:
                #print( f"Counterexample: {x}.{a} = {assignments[v2]} != {x}" )
                rightCounter = True
                break

        return leftCounter and rightCounter
    
for a in range( 0, n ):
    problem.addConstraint( NotIdentityConstraint( a ) )

# The semigroup operation should not be constant for some value
class NotAllEqualConstraint(Constraint):
    def __init__( self ):
        pass

    def __call__( self, variables, domains, assignments, forwardcheck ):
        vals = set()
        #print( variables, assignments )
        for v in variables:
            if v not in assignments:
                return True
            vals.add( assignments[v] )
            if len( vals ) > 1:
                return True

        return False
        

for a in range( 0, n ):
    problem.addConstraint( NotAllEqualConstraint(),
                           [ x*n + a for x in range( 0, n ) ] )
    problem.addConstraint( NotAllEqualConstraint(),
                           [ a*n + x for x in range( 0, n ) ] )

for a in range( 0, n ):
    problem.addConstraint( SomeInSetConstraint([a]) )

problem.addConstraint( NotInSetConstraint([5]), [5*n + 5] )
problem.addConstraint( NotInSetConstraint([2]), [2*n + 2] )
problem.addConstraint( NotInSetConstraint([1]), [1*n + 1] )
problem.addConstraint( NotInSetConstraint([0]), [0*n + 0] )

s = problem.getSolution()
if s is not None:
    print( "   ", end='' )
    for b in range( 0, n ):
        print( f"{b:2} ", end='' )
    print()
    for a in range( 0, n ):
        print( f"{a:2}|", end='' )
        for b in range( 0, n ):
            ab = s[a*n+b]
            print( f"{ab:2} ", end='' )
        print()
        
def op( a, b ):
    return s[a*n + b]