1import pytest2 3from delivery.csp import AssignmentCSP, check_assignment4from delivery.instances import Instance, Order, Van, generate_instance5from delivery.integration import explain_no_solution6from conftest import line_tm7 8SOLVERS = [(False, False), (True, False), (True, True)]9 10 11def three_vans(cap=10, stops=10):12 return [Van(0, cap, 480, 1020, stops), Van(1, cap, 540, 1080, stops), Van(2, cap, 600, 1140, stops)]13 14 15# ----------------------------------------------------------------------------- normal cases16@pytest.mark.parametrize("seed", range(3))17def test_all_solvers_valid_and_identical(tm, seed):18 inst = generate_instance(18, seed, n_zones=tm.Z, cap_slack=1.15)19 csp = AssignmentCSP(inst, tm)20 sols = []21 for fc, ac3 in SOLVERS:22 r = csp.solve(fc=fc, ac3=ac3)23 assert r.status == "solved"24 assert check_assignment(csp, r.assignment) == []25 sols.append(r.assignment)26 assert sols[0] == sols[1] == sols[2] # same orderings -> same first solution27 28 29def test_forward_checking_never_needs_more_assignments(tm):30 for seed in range(5):31 inst = generate_instance(24, seed, n_zones=tm.Z, cap_slack=1.05, max_stops=8)32 csp = AssignmentCSP(inst, tm)33 bt = csp.solve(fc=False)34 fc = csp.solve(fc=True)35 mac = csp.solve(fc=True, ac3=True)36 assert fc.stats["assignments"] <= bt.stats["assignments"]37 assert mac.stats["assignments"] <= fc.stats["assignments"]38 39 40def test_ac3_prunes_triangle_with_a_fixed_order():41 # three mutually conflicting orders, order 0 can only use van 0 -> AC-3 forces the rest42 tm = line_tm()43 orders = [Order(0, 4, 480, 900, 1, 5), Order(1, 4, 480, 900, 1, 5), Order(2, 4, 480, 900, 1, 5)]44 inst = Instance(orders, three_vans(), 0, 1)45 csp = AssignmentCSP(inst, tm)46 csp.domains0 = {0: [0], 1: [0, 1], 2: [0, 1, 2]}47 for a, b in ((0, 1), (0, 2), (1, 2)):48 csp.add_edge(a, b, "nn")49 r = csp.solve(fc=True, ac3=True)50 assert r.assignment == {0: 0, 1: 1, 2: 2}51 assert r.stats["ac3_prunes"] >= 2 and r.stats["backtracks"] == 052 53 54def test_pairwise_conflict_edge_is_created_from_predicted_times():55 tm = line_tm() # 0 -> 4 takes 21 min, 4 -> 0 takes 21 min56 a = Order(0, 4, 480, 505, 1, 5) # must be at the far end by 08:2557 b = Order(1, 0, 495, 505, 1, 5) # and at the depot zone 08:15-08:2558 c = Order(2, 1, 480, 900, 1, 5) # unconstrained59 csp = AssignmentCSP(Instance([a, b, c], three_vans(), 0, 1), tm)60 assert frozenset((0, 1)) in csp.edges61 assert frozenset((0, 2)) not in csp.edges62 63 64# ----------------------------------------------------------------------------- edge case65def test_edge_late_shift_van_removed_from_domain_by_unary_constraint():66 tm = line_tm()67 o = Order(0, 2, 480, 560, 1, 5) # closes 09:20; van 2 starts 10:0068 csp = AssignmentCSP(Instance([o], three_vans(), 0, 1), tm)69 assert csp.domains0[0] == [0, 1]70 assert "van 2" in csp.unary_reasons[0][0]71 72 73# ----------------------------------------------------------------------------- impossible74def test_impossible_four_mutually_conflicting_orders_three_vans():75 tm = line_tm()76 orders = [Order(i, 4 if i % 2 else 0, 480, 900, 1, 5) for i in range(5)]77 inst = Instance(orders, three_vans(), 0, 1)78 csp = AssignmentCSP(inst, tm)79 for a in range(4):80 for b in range(a + 1, 4):81 csp.add_edge(a, b, "learned")82 for fc, ac3 in SOLVERS:83 assert csp.solve(fc=fc, ac3=ac3).status == "unsat"84 reasons = explain_no_solution(csp, inst, tm)85 assert any("pairwise incompatible" in r for _, r in reasons)86 assert {oid for oid, _ in reasons} == {0, 1, 2, 3}87 88 89def test_impossible_capacity():90 tm = line_tm()91 orders = [Order(i, 1, 480, 900, 3, 5) for i in range(4)] # 12 units92 inst = Instance(orders, three_vans(cap=3), 0, 1) # 9 units93 csp = AssignmentCSP(inst, tm)94 assert csp.solve(fc=True, ac3=True).status == "unsat"95 reasons = explain_no_solution(csp, inst, tm)96 print("\n".join(r for _, r in reasons))97 assert any("exceeds total van capacity" in r for _, r in reasons)