asynchorous backtracking algorithm - 4 queens

type AgentID = number;
type Value = number;

export interface Assignment {
    agentID: AgentID;
    value: Value;
}

export type Nogood = Assignment[];

export type Message =
    | { type: 'OK'; from: AgentID; to: AgentID; payload: Value }
    | { type: 'NOGOOD'; from: AgentID; to: AgentID; payload: Nogood }
    | { type: 'ADD_NEIGHBOR'; from: AgentID; to: AgentID; payload: null };

export type ConstraintFunction = (a1: AgentID, v1: Value, a2: AgentID, v2: Value) => boolean;


export class Agent {
    public id: AgentID;
    public domain: Value[];
    public neighbors: Set<AgentID>;
    public environment: Environment;
    public constraint: ConstraintFunction;

    public currentValue: Value;
    public agentView: Map<AgentID, Value> = new Map();
    public nogoodList: Nogood[] = [];
    public inbox: Message[] = [];

    constructor(
        id: AgentID,
        domain: Value[],
        neighbors: AgentID[],
        environment: Environment,
        constraint: ConstraintFunction
    ) {
        this.id = id;
        this.domain = [...domain];
        this.neighbors = new Set(neighbors);
        this.environment = environment;
        this.constraint = constraint;
        this.currentValue = this.domain[0];
    }

    public enqueue(msg: Message) {
        this.inbox.push(msg);
    }

    public initialize() {
        this.notifyNeighbors();
    }

    public handleMessage(msg: Message) {
        if (!this.environment.running) return;


        switch (msg.type) {
            case 'OK':
                this.agentView.set(msg.from, msg.payload);
                this.cleanupNogoods(msg.from, msg.payload);
                this.checkAgentView();
                break;
            case 'NOGOOD':
                this.handleNogood(msg.payload, msg.from);
                break;
            case 'ADD_NEIGHBOR':
                this.neighbors.add(msg.from);
                this.environment.sendMessage('OK', this.id, msg.from, this.currentValue);
                break;
        }
    }

    private cleanupNogoods(changedAgent: AgentID, newValue: Value) {
        this.nogoodList = this.nogoodList.filter(nogood => {
            const relevant = nogood.find(a => a.agentID === changedAgent);
            return !relevant || relevant.value === newValue;
        });
    }

    private handleNogood(nogood: Nogood, from: AgentID) {
        this.nogoodList.push(nogood);

        for (const assignment of nogood) {
            if (assignment.agentID !== this.id && !this.agentView.has(assignment.agentID)) {
                this.agentView.set(assignment.agentID, assignment.value);
                if (!this.neighbors.has(assignment.agentID)) {
                    this.neighbors.add(assignment.agentID);
                    this.environment.sendMessage('ADD_NEIGHBOR', this.id, assignment.agentID, null);
                }
            }
        }

        this.checkAgentView();

        // The sender deleted its own view of us right before sending this
        // nogood (see backtrack()) and is now blind to our value until we
        // tell it. We must reply unconditionally, whether or not our value
        // actually changed above — if we were already consistent and stayed
        // put, the sender would otherwise wait forever for an update.
        this.environment.sendMessage('OK', this.id, from, this.currentValue);
    }

    private checkAgentView() {
        if (!this.isConsistent(this.currentValue)) {
            const candidate = this.domain.find(d => this.isConsistent(d));
            if (candidate !== undefined) {
                this.currentValue = candidate;

                this.notifyNeighbors();
            } else {
                this.backtrack();
            }
        }
    }

    private isNogoodCompatibleWithView(nogood: Nogood): boolean {
        for (const assignment of nogood) {
            if (assignment.agentID === this.id) continue;
            if (this.agentView.has(assignment.agentID)) {
                if (this.agentView.get(assignment.agentID) !== assignment.value) {
                    return false;
                }
            }
        }
        return true;
    }

    private isConsistent(val: Value): boolean {
        for (const [otherId, otherVal] of this.agentView) {
            if (otherId < this.id) {
                if (!this.constraint(this.id, val, otherId, otherVal)) return false;
            }
        }

        for (const nogood of this.nogoodList) {
            if (this.isNogoodCompatibleWithView(nogood)) {
                const forbidsMyValue = nogood.some(a =>
                    a.agentID === this.id && a.value === val
                );
                if (forbidsMyValue) return false;
            }
        }

        return true;
    }

    private backtrack() {
        // Combine reasons across the WHOLE domain, not just currentValue.
        // "currentValue fails because of X" only tells you one value is bad;
        // to justify giving up you need every value in the domain to be
        // accounted for. getReasonForFailure already strips self-referencing
        // entries, so this map only ever collects genuine external causes.
        const combinedNogoodMap = new Map<AgentID, Assignment>();

        for (const d of this.domain) {
            const reason = this.getReasonForFailure(d);
            if (reason) {
                reason.forEach(a => combinedNogoodMap.set(a.agentID, a));
            }
        }

        let newNogood = Array.from(combinedNogoodMap.values())
            .filter(a => a.agentID < this.id);

        if (newNogood.length === 0) {
            this.environment.broadcastTermination("No Solution Exists");
        } else {
            const target = newNogood.reduce((prev, curr) =>
                (curr.agentID > prev.agentID ? curr : prev)
            );



            this.environment.sendMessage('NOGOOD', this.id, target.agentID, newNogood);
            this.agentView.delete(target.agentID);

            this.nogoodList = this.nogoodList.filter(ng =>
                !ng.some(a => a.agentID === target.agentID)
            );
        }
    }

    private getReasonForFailure(val: Value): Assignment[] | null {
        for (const [otherId, otherVal] of this.agentView) {
            if (!this.constraint(this.id, val, otherId, otherVal)) {
                return [{ agentID: otherId, value: otherVal }];
            }
        }
        for (const nogood of this.nogoodList) {
            if (this.isNogoodCompatibleWithView(nogood) &&
                nogood.some(a => a.agentID === this.id && a.value === val)) {
                return nogood.filter(a => a.agentID !== this.id);
            }
        }
        return null;
    }

    private notifyNeighbors() {
        for (const neighborId of this.neighbors) {
            if (neighborId > this.id) {
                this.environment.sendMessage('OK', this.id, neighborId, this.currentValue);
            }
        }
    }
}

export class Environment {
    private agents: Map<AgentID, Agent> = new Map();
    public running: boolean = true;

    addAgent(agent: Agent) { this.agents.set(agent.id, agent); }

    sendMessage<T extends Message['type']>(
        type: T,
        from: AgentID,
        to: AgentID,
        payload: Extract<Message, { type: T }>['payload']
    ) {
        const msg = { type, from, to, payload } as Message;
        this.agents.get(to)?.enqueue(msg);
    }

    broadcastTermination(reason: string) {
        console.log(`[Termination] ${reason}`);
        this.running = false;
    }

    private hasPendingMessages(): boolean {
        for (const agent of this.agents.values()) {
            if (agent.inbox.length > 0) return true;
        }
        return false;
    }

    public process(maxSteps: number = 200000) {
        console.log("Starting ABT for N-Queens...");
        this.agents.forEach(a => a.initialize());

        let steps = 0;
        while (this.running && this.hasPendingMessages()) {
            if (steps++ >= maxSteps) {
                console.log("Safety limit reached - possible infinite loop.");
                this.running = false;
                return;
            }
            for (const agent of this.agents.values()) {
                if (!this.running) break;
                const msg = agent.inbox.shift();
                if (msg) agent.handleMessage(msg);
            }
        }

        if (this.running) {
            this.printSolution();
        }
        console.log(`Total steps: ${steps}`);
    }

    private printSolution() {
        console.log("\n=== SOLUTION FOUND ===");
        const solution = Array.from(this.agents.values())
            .sort((a, b) => a.id - b.id)
            .map(a => `Row ${a.id} -> Column ${a.currentValue}`);

        console.log(solution.join('\n'));

        const positions = Array.from(this.agents.values())
            .sort((a,b) => a.id - b.id)
            .map(a => a.currentValue);
        if (this.isValidQueensSolution(positions)) {
            console.log("Valid N-Queens solution!");
        } else {
            console.log("Solution found but failed validation.");
            // dump full state of every agent for debugging
            for (const agent of Array.from(this.agents.values()).sort((a,b)=>a.id-b.id)) {
                console.log(`  A${agent.id} val=${agent.currentValue} view=${JSON.stringify([...agent.agentView])} nogoods=${JSON.stringify(agent.nogoodList)}`);
            }
        }
    }

    private isValidQueensSolution(pos: number[]): boolean {
        for (let i = 0; i < pos.length; i++) {
            for (let j = i + 1; j < pos.length; j++) {
                if (pos[i] === pos[j] || Math.abs(i - j) === Math.abs(pos[i] - pos[j])) {
                    return false;
                }
            }
        }
        return true;
    }
}

const N = 10;
const env = new Environment();
const domain = Array.from({length: N}, (_, i) => i);

const queenConstraint: ConstraintFunction = (r1, c1, r2, c2) =>
    c1 !== c2 && Math.abs(r1 - r2) !== Math.abs(c1 - c2);

for (let i = 0; i < N; i++) {
    const neighbors = Array.from({length: N - i - 1}, (_, k) => i + 1 + k);
    const agent = new Agent(i, domain, neighbors, env, queenConstraint);
    env.addAgent(agent);
}

env.process();