Google OR-Tools: ortools/constraint_solver/count

Google OR-Tools: ortools/constraint_solver/count_cst.cc Source File

16#include <algorithm>

17#include <cstdint>

18#include <limits>

19#include <string>

20#include <utility>

21#include <vector>

23#include "absl/strings/str_format.h"

24#include "absl/strings/str_join.h"

33 int64_t max_count) {

34 std::vector<IntVar*> tmp_sum;

35 for (int i = 0; i < vars.size(); ++i) {

36 if (vars[i]->Contains(value)) {

37 if (vars[i]->Bound()) {

38 max_count--;

39 } else {

41 }

42 }

43 }

45}

49 if (max_count->Bound()) {

50 return MakeCount(vars, value, max_count->Min());

51 } else {

52 std::vector<IntVar*> tmp_sum;

53 int64_t num_vars_bound_to_v = 0;

54 for (int i = 0; i < vars.size(); ++i) {

55 if (vars[i]->Contains(value)) {

56 if (vars[i]->Bound()) {

57 ++num_vars_bound_to_v;

58 } else {

60 }

61 }

62 }

64 MakeSum(max_count, -num_vars_bound_to_v)->Var());

65 }

66}

70namespace {

72 public:

73 AtMost(Solver* const s, std::vector<IntVar*> vars, int64_t value,

74 int64_t max_count)

76 vars_(std::move(vars)),

77 value_(value),

78 max_count_(max_count),

79 current_count_(0) {}

81 ~AtMost() override {}

83 void Post() override {

84 for (IntVar* var : vars_) {

85 if (!var->Bound() && var->Contains(value_)) {

87 "OneBound", var);

88 var->WhenBound(d);

89 }

90 }

91 }

93 void InitialPropagate() override {

94 for (IntVar* var : vars_) {

95 if (var->Bound() && var->Min() == value_) {

96 current_count_.Incr(solver());

97 }

98 }

99 CheckCount();

100 }

101

102 void OneBound(IntVar* var) {

103 if (var->Min() == value_) {

104 current_count_.Incr(solver());

105 CheckCount();

106 }

107 }

108

109 void CheckCount() {

110 if (current_count_.Value() < max_count_) {

111 return;

112 }

113

114

115 int forced = 0;

116 for (IntVar* var : vars_) {

117 if (var->Bound()) {

118 if (var->Min() == value_) {

119 forced++;

120 }

121 } else {

122 var->RemoveValue(value_);

123 }

124 }

125 if (forced > max_count_) {

126 solver()->Fail();

127 }

128 }

129

130 std::string DebugString() const override {

131 return absl::StrFormat("AtMost(%s, %d, %d)",

133 }

134

135 void Accept(ModelVisitor* const visitor) const override {

138 vars_);

142 }

143

144 private:

145 const std::vector<IntVar*> vars_;

146 const int64_t value_;

147 const int64_t max_count_;

148 NumericalRev<int> current_count_;

149};

150

151class Distribute : public Constraint {

152 public:

153 Distribute(Solver* const s, const std::vector<IntVar*>& vars,

154 const std::vector<int64_t>& values,

155 const std::vector<IntVar*>& cards)

156 : Constraint(s),

157 vars_(vars),

158 values_(values),

159 cards_(cards),

160 undecided_(vars.size(), cards.size()),

161 min_(cards.size(), 0),

162 max_(cards.size(), 0) {}

163

164 ~Distribute() override {}

165

166 void Post() override;

167 void InitialPropagate() override;

168 void OneBound(int index);

169 void OneDomain(int index);

170 void CountVar(int cindex);

171 void CardMin(int cindex);

172 void CardMax(int cindex);

173 std::string DebugString() const override {

174 return absl::StrFormat(

175 "Distribute(vars = [%s], values = [%s], cards = [%s])",

178 }

179

180 void Accept(ModelVisitor* const visitor) const override {

183 vars_);

186 cards_);

188 }

189

190 private:

191 int64_t var_size() const { return vars_.size(); }

192 int64_t card_size() const { return cards_.size(); }

193

194 const std::vector<IntVar*> vars_;

195 const std::vector<int64_t> values_;

196 const std::vector<IntVar*> cards_;

197 RevBitMatrix undecided_;

198 NumericalRevArray<int> min_;

199 NumericalRevArray<int> max_;

200};

201

202void Distribute::Post() {

203 for (int i = 0; i < var_size(); ++i) {

204 IntVar* const var = vars_[i];

205 if (!var->Bound()) {

207 "OneBound", i);

208 var->WhenBound(d);

210 "OneDomain", i);

211 var->WhenDomain(d);

212 }

213 }

214 for (int i = 0; i < card_size(); ++i) {

215 if (!cards_[i]->Bound()) {

216 Demon* d =

218 cards_[i]->WhenRange(d);

219 }

220 }

221}

222

223void Distribute::InitialPropagate() {

224 Solver* const s = solver();

225 for (int j = 0; j < card_size(); ++j) {

226 int min = 0;

227 int max = 0;

228 for (int i = 0; i < var_size(); ++i) {

229 IntVar* const var = vars_[i];

230 if (var->Bound()) {

231 if (var->Min() == values_[j]) {

232 min++;

233 max++;

234 }

235 } else {

236 if (var->Contains(values_[j])) {

237 max++;

238 undecided_.SetToOne(s, i, j);

239 }

240 }

241 }

242 cards_[j]->SetRange(min, max);

243 if (cards_[j]->Max() == min) {

244 CardMin(j);

245 } else if (cards_[j]->Min() == max) {

246 CardMax(j);

247 }

248 min_.SetValue(s, j, min);

249 max_.SetValue(s, j, max);

250 }

251}

252

253void Distribute::OneBound(int index) {

254 IntVar* const var = vars_[index];

255 Solver* const s = solver();

256 for (int j = 0; j < card_size(); ++j) {

257 if (undecided_.IsSet(index, j)) {

258 undecided_.SetToZero(s, index, j);

259 if (var->Min() == values_[j]) {

260 min_.Incr(s, j);

261 cards_[j]->SetMin(min_[j]);

262 if (min_[j] == cards_[j]->Max()) {

263 CardMin(j);

264 }

265 } else {

266 max_.Decr(s, j);

267 cards_[j]->SetMax(max_[j]);

268 if (max_[j] == cards_[j]->Min()) {

269 CardMax(j);

270 }

271 }

272 }

273 }

274}

275

276void Distribute::OneDomain(int index) {

277 IntVar* const var = vars_[index];

278 Solver* const s = solver();

279 for (int j = 0; j < card_size(); ++j) {

280 if (undecided_.IsSet(index, j)) {

281 if (!var->Contains(values_[j])) {

282 undecided_.SetToZero(s, index, j);

283 max_.Decr(s, j);

284 cards_[j]->SetMax(max_[j]);

285 if (max_[j] == cards_[j]->Min()) {

286 CardMax(j);

287 }

288 }

289 }

290 }

291}

292

293void Distribute::CountVar(int cindex) {

294 if (cards_[cindex]->Min() > max_[cindex] ||

295 cards_[cindex]->Max() < min_[cindex]) {

296 solver()->Fail();

297 }

298 if (cards_[cindex]->Min() == max_[cindex]) {

299 CardMax(cindex);

300 }

301 if (cards_[cindex]->Max() == min_[cindex]) {

302 CardMin(cindex);

303 }

304}

305

306void Distribute::CardMin(int cindex) {

307 for (int i = 0; i < var_size(); ++i) {

308 if (undecided_.IsSet(i, cindex)) {

309 vars_[i]->RemoveValue(values_[cindex]);

310 }

311 }

312}

313

314void Distribute::CardMax(int cindex) {

315 for (int i = 0; i < var_size(); ++i) {

316 if (undecided_.IsSet(i, cindex)) {

317 vars_[i]->SetValue(values_[cindex]);

318 }

319 }

320}

321

322

323

324class FastDistribute : public Constraint {

325 public:

326 FastDistribute(Solver* s, const std::vector<IntVar*>& vars,

327 const std::vector<IntVar*>& cards);

328 ~FastDistribute() override {}

329

330 void Post() override;

331 void InitialPropagate() override;

332 void OneBound(int index);

333 void OneDomain(int index);

334 void CountVar(int card_index);

335 void CardMin(int card_index);

336 void CardMax(int card_index);

337 std::string DebugString() const override;

338 void SetRevCannotContribute(int64_t var_index, int64_t card_index) {

339 Solver* const s = solver();

340 undecided_.SetToZero(s, var_index, card_index);

341 max_.Decr(s, card_index);

342 cards_[card_index]->SetMax(max_[card_index]);

343 if (max_[card_index] == cards_[card_index]->Min()) {

344 CardMax(card_index);

345 }

346 }

347 void SetRevDoContribute(int64_t var_index, int64_t card_index) {

348 Solver* const s = solver();

349 undecided_.SetToZero(s, var_index, card_index);

350 min_.Incr(s, card_index);

351 cards_[card_index]->SetMin(min_[card_index]);

352 if (min_[card_index] == cards_[card_index]->Max()) {

353 CardMin(card_index);

354 }

355 }

356

357 void Accept(ModelVisitor* const visitor) const override {

358 visitor->BeginVisitConstraint(ModelVisitor::kDistribute, this);

359 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,

360 vars_);

361 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kCardsArgument,

362 cards_);

363 visitor->EndVisitConstraint(ModelVisitor::kDistribute, this);

364 }

365

366 private:

367 int64_t var_size() const { return vars_.size(); }

368 int64_t card_size() const { return cards_.size(); }

369

370 const std::vector<IntVar*> vars_;

371 const std::vector<IntVar*> cards_;

372 RevBitMatrix undecided_;

373 NumericalRevArray<int> min_;

374 NumericalRevArray<int> max_;

375 std::vector<IntVarIterator*> holes_;

376};

377

378FastDistribute::FastDistribute(Solver* const s,

379 const std::vector<IntVar*>& vars,

380 const std::vector<IntVar*>& cards)

381 : Constraint(s),

382 vars_(vars),

383 cards_(cards),

384 undecided_(vars.size(), cards.size()),

385 min_(cards.size(), 0),

386 max_(cards.size(), 0),

387 holes_(vars.size()) {

388 for (int var_index = 0; var_index < var_size(); ++var_index) {

389 holes_[var_index] = vars_[var_index]->MakeHoleIterator(true);

390 }

391}

392

393std::string FastDistribute::DebugString() const {

394 return absl::StrFormat("FastDistribute(vars = [%s], cards = [%s])",

397}

398

399void FastDistribute::Post() {

400 for (int var_index = 0; var_index < var_size(); ++var_index) {

401 IntVar* const var = vars_[var_index];

402 if (!var->Bound()) {

404 "OneBound", var_index);

405 var->WhenBound(d);

407 "OneDomain", var_index);

408 var->WhenDomain(d);

409 }

410 }

411 for (int card_index = 0; card_index < card_size(); ++card_index) {

412 if (!cards_[card_index]->Bound()) {

414 "Var", card_index);

415 cards_[card_index]->WhenRange(d);

416 }

417 }

418}

419

420void FastDistribute::InitialPropagate() {

421 Solver* const s = solver();

422 for (int card_index = 0; card_index < card_size(); ++card_index) {

423 int min = 0;

424 int max = 0;

425 for (int var_index = 0; var_index < var_size(); ++var_index) {

426 IntVar* const var = vars_[var_index];

427 if (var->Bound() && var->Min() == card_index) {

428 min++;

429 max++;

430 } else if (var->Contains(card_index)) {

431 max++;

432 undecided_.SetToOne(s, var_index, card_index);

433 }

434 }

435 min_.SetValue(s, card_index, min);

436 max_.SetValue(s, card_index, max);

437 CountVar(card_index);

438 }

439}

440

441void FastDistribute::OneBound(int index) {

442 IntVar* const var = vars_[index];

443 for (int card_index = 0; card_index < card_size(); ++card_index) {

444 if (undecided_.IsSet(index, card_index)) {

445 if (var->Min() == card_index) {

446 SetRevDoContribute(index, card_index);

447 } else {

448 SetRevCannotContribute(index, card_index);

449 }

450 }

451 }

452}

453

454void FastDistribute::OneDomain(int index) {

455 IntVar* const var = vars_[index];

456 const int64_t oldmin = var->OldMin();

457 const int64_t oldmax = var->OldMax();

458 const int64_t vmin = var->Min();

459 const int64_t vmax = var->Max();

460 for (int64_t card_index = std::max(oldmin, int64_t{0});

461 card_index < std::min(vmin, card_size()); ++card_index) {

462 if (undecided_.IsSet(index, card_index)) {

463 SetRevCannotContribute(index, card_index);

464 }

465 }

466 for (const int64_t card_index : InitAndGetValues(holes_[index])) {

467 if (card_index >= 0 && card_index < card_size() &&

468 undecided_.IsSet(index, card_index)) {

469 SetRevCannotContribute(index, card_index);

470 }

471 }

472 for (int64_t card_index = std::max(vmax + 1, int64_t{0});

473 card_index <= std::min(oldmax, card_size() - 1); ++card_index) {

474 if (undecided_.IsSet(index, card_index)) {

475 SetRevCannotContribute(index, card_index);

476 }

477 }

478}

479

480void FastDistribute::CountVar(int card_index) {

481 const int64_t stored_min = min_[card_index];

482 const int64_t stored_max = max_[card_index];

483 cards_[card_index]->SetRange(min_[card_index], max_[card_index]);

484 if (cards_[card_index]->Min() == stored_max) {

485 CardMax(card_index);

486 }

487 if (cards_[card_index]->Max() == stored_min) {

488 CardMin(card_index);

489 }

490}

491

492void FastDistribute::CardMin(int card_index) {

493 for (int var_index = 0; var_index < var_size(); ++var_index) {

494 if (undecided_.IsSet(var_index, card_index)) {

495 vars_[var_index]->RemoveValue(card_index);

496 }

497 }

498}

499

500void FastDistribute::CardMax(int card_index) {

501 for (int var_index = 0; var_index < var_size(); ++var_index) {

502 if (undecided_.IsSet(var_index, card_index)) {

503 vars_[var_index]->SetValue(card_index);

504 }

505 }

506}

507

508

509

510class BoundedDistribute : public Constraint {

511 public:

512 BoundedDistribute(Solver* s, const std::vector<IntVar*>& vars,

513 const std::vector<int64_t>& values,

514 const std::vector<int64_t>& card_min,

515 const std::vector<int64_t>& card_max);

516 ~BoundedDistribute() override {}

517

518 void Post() override;

519 void InitialPropagate() override;

520 void OneBound(int index);

521 void OneDomain(int index);

522 void CountVar(int card_index);

523 void CardMin(int card_index);

524 void CardMax(int card_index);

525 std::string DebugString() const override;

526 void SetRevCannotContribute(int64_t var_index, int64_t card_index) {

527 Solver* const s = solver();

528 undecided_.SetToZero(s, var_index, card_index);

529 max_.Decr(s, card_index);

530 if (max_[card_index] < card_min_[card_index]) {

531 solver()->Fail();

532 }

533 if (max_[card_index] == card_min_[card_index]) {

534 CardMax(card_index);

535 }

536 }

537 void SetRevDoContribute(int64_t var_index, int64_t card_index) {

538 Solver* const s = solver();

539 undecided_.SetToZero(s, var_index, card_index);

540 min_.Incr(s, card_index);

541 if (min_[card_index] > card_max_[card_index]) {

542 solver()->Fail();

543 }

544 if (min_[card_index] == card_max_[card_index]) {

545 CardMin(card_index);

546 }

547 }

548

549 void Accept(ModelVisitor* const visitor) const override {

550 visitor->BeginVisitConstraint(ModelVisitor::kDistribute, this);

551 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,

552 vars_);

553 visitor->VisitIntegerArrayArgument(ModelVisitor::kValuesArgument, values_);

554 visitor->VisitIntegerArrayArgument(ModelVisitor::kMinArgument, card_min_);

555 visitor->VisitIntegerArrayArgument(ModelVisitor::kMaxArgument, card_max_);

556 visitor->EndVisitConstraint(ModelVisitor::kDistribute, this);

557 }

558

559 private:

560 int64_t var_size() const { return vars_.size(); }

561 int64_t card_size() const { return values_.size(); }

562

563 const std::vector<IntVar*> vars_;

564 const std::vector<int64_t> values_;

565 const std::vector<int64_t> card_min_;

566 const std::vector<int64_t> card_max_;

567 RevBitMatrix undecided_;

568 NumericalRevArray<int> min_;

569 NumericalRevArray<int> max_;

570 std::vector<IntVarIterator*> holes_;

571};

572

573BoundedDistribute::BoundedDistribute(Solver* const s,

574 const std::vector<IntVar*>& vars,

575 const std::vector<int64_t>& values,

576 const std::vector<int64_t>& card_min,

577 const std::vector<int64_t>& card_max)

578 : Constraint(s),

579 vars_(vars),

580 values_(values),

581 card_min_(card_min),

582 card_max_(card_max),

583 undecided_(vars.size(), values.size()),

584 min_(values.size(), 0),

585 max_(values.size(), 0),

586 holes_(vars.size()) {

587 for (int var_index = 0; var_index < var_size(); ++var_index) {

588 holes_[var_index] = vars_[var_index]->MakeHoleIterator(true);

589 }

590}

591

592std::string BoundedDistribute::DebugString() const {

593 return absl::StrFormat(

594 "BoundedDistribute([%s], values = [%s], card_min = [%s], card_max = "

595 "[%s]",

597 absl::StrJoin(card_min_, ", "), absl::StrJoin(card_max_, ", "));

598}

599

600void BoundedDistribute::Post() {

601 for (int var_index = 0; var_index < var_size(); ++var_index) {

602 IntVar* const var = vars_[var_index];

603 if (!var->Bound()) {

605 solver(), this, &BoundedDistribute::OneBound, "OneBound", var_index);

606 var->WhenBound(d);

608 "OneDomain", var_index);

609 var->WhenDomain(d);

610 }

611 }

612}

613

614void BoundedDistribute::InitialPropagate() {

615 Solver* const s = solver();

616

617 int64_t sum_card_min = 0;

618 for (int i = 0; i < card_size(); ++i) {

619 if (card_max_[i] < card_min_[i]) {

620 solver()->Fail();

621 }

622 sum_card_min += card_min_[i];

623 }

624 if (sum_card_min > var_size()) {

625 s->Fail();

626 }

627 if (sum_card_min == var_size()) {

628 for (int i = 0; i < var_size(); ++i) {

629 vars_[i]->SetValues(values_);

630 }

631 }

632

633 for (int card_index = 0; card_index < card_size(); ++card_index) {

634 const int64_t value = values_[card_index];

635 int min = 0;

636 int max = 0;

637 for (int i = 0; i < var_size(); ++i) {

638 IntVar* const var = vars_[i];

639 if (var->Bound()) {

640 if (var->Min() == value) {

641 min++;

642 max++;

643 }

644 } else if (var->Contains(value)) {

645 max++;

646 undecided_.SetToOne(s, i, card_index);

647 }

648 }

649 min_.SetValue(s, card_index, min);

650 max_.SetValue(s, card_index, max);

651 CountVar(card_index);

652 }

653}

654

655void BoundedDistribute::OneBound(int index) {

656 IntVar* const var = vars_[index];

657 const int64_t var_min = var->Min();

658 for (int card_index = 0; card_index < card_size(); ++card_index) {

659 if (undecided_.IsSet(index, card_index)) {

660 if (var_min == values_[card_index]) {

661 SetRevDoContribute(index, card_index);

662 } else {

663 SetRevCannotContribute(index, card_index);

664 }

665 }

666 }

667}

668

669void BoundedDistribute::OneDomain(int index) {

670 IntVar* const var = vars_[index];

671 for (int card_index = 0; card_index < card_size(); ++card_index) {

672 if (undecided_.IsSet(index, card_index)) {

673 if (!var->Contains(values_[card_index])) {

674 SetRevCannotContribute(index, card_index);

675 }

676 }

677 }

678}

679

680void BoundedDistribute::CountVar(int card_index) {

681 const int64_t stored_min = min_[card_index];

682 const int64_t stored_max = max_[card_index];

683 if (card_min_[card_index] > stored_max ||

684 card_max_[card_index] < stored_min) {

685 solver()->Fail();

686 }

687 if (card_min_[card_index] == stored_max) {

688 CardMax(card_index);

689 }

690 if (card_max_[card_index] == stored_min) {

691 CardMin(card_index);

692 }

693}

694

695void BoundedDistribute::CardMin(int card_index) {

696 for (int var_index = 0; var_index < var_size(); ++var_index) {

697 if (undecided_.IsSet(var_index, card_index)) {

698 vars_[var_index]->RemoveValue(values_[card_index]);

699 }

700 }

701}

702

703void BoundedDistribute::CardMax(int card_index) {

704 for (int var_index = 0; var_index < var_size(); ++var_index) {

705 if (undecided_.IsSet(var_index, card_index)) {

706 vars_[var_index]->SetValue(values_[card_index]);

707 }

708 }

709}

710

711

712

713class BoundedFastDistribute : public Constraint {

714 public:

715 BoundedFastDistribute(Solver* s, const std::vector<IntVar*>& vars,

716 const std::vector<int64_t>& card_min,

717 const std::vector<int64_t>& card_max);

718 ~BoundedFastDistribute() override {}

719

720 void Post() override;

721 void InitialPropagate() override;

722 void OneBound(int index);

723 void OneDomain(int index);

724 void CountVar(int card_index);

725 void CardMin(int card_index);

726 void CardMax(int card_index);

727 std::string DebugString() const override;

728 void SetRevCannotContribute(int64_t var_index, int64_t card_index) {

729 Solver* const s = solver();

730 undecided_.SetToZero(s, var_index, card_index);

731 max_.Decr(s, card_index);

732 if (max_[card_index] < card_min_[card_index]) {

733 solver()->Fail();

734 }

735 if (max_[card_index] == card_min_[card_index]) {

736 CardMax(card_index);

737 }

738 }

739 void SetRevDoContribute(int64_t var_index, int64_t card_index) {

740 Solver* const s = solver();

741 undecided_.SetToZero(s, var_index, card_index);

742 min_.Incr(s, card_index);

743 if (min_[card_index] > card_max_[card_index]) {

744 solver()->Fail();

745 }

746 if (min_[card_index] == card_max_[card_index]) {

747 CardMin(card_index);

748 }

749 }

750

751 void Accept(ModelVisitor* const visitor) const override {

752 visitor->BeginVisitConstraint(ModelVisitor::kDistribute, this);

753 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,

754 vars_);

755 visitor->VisitIntegerArrayArgument(ModelVisitor::kMinArgument, card_min_);

756 visitor->VisitIntegerArrayArgument(ModelVisitor::kMaxArgument, card_max_);

757 visitor->EndVisitConstraint(ModelVisitor::kDistribute, this);

758 }

759

760 private:

761 int64_t var_size() const { return vars_.size(); }

762 int64_t card_size() const { return card_min_.size(); }

763

764 const std::vector<IntVar*> vars_;

765 const std::vector<int64_t> card_min_;

766 const std::vector<int64_t> card_max_;

767 RevBitMatrix undecided_;

768 NumericalRevArray<int> min_;

769 NumericalRevArray<int> max_;

770 std::vector<IntVarIterator*> holes_;

771};

772

773BoundedFastDistribute::BoundedFastDistribute(

774 Solver* const s, const std::vector<IntVar*>& vars,

775 const std::vector<int64_t>& card_min, const std::vector<int64_t>& card_max)

776 : Constraint(s),

777 vars_(vars),

778 card_min_(card_min),

779 card_max_(card_max),

780 undecided_(vars.size(), card_min.size()),

781 min_(card_min.size(), 0),

782 max_(card_max.size(), 0),

783 holes_(vars.size()) {

784 for (int var_index = 0; var_index < var_size(); ++var_index) {

785 holes_[var_index] = vars_[var_index]->MakeHoleIterator(true);

786 }

787}

788

789std::string BoundedFastDistribute::DebugString() const {

790 return absl::StrFormat(

791 "BoundedFastDistribute([%s], card_min = [%s], card_max = [%s]",

793 absl::StrJoin(card_max_, ", "));

794}

795

796void BoundedFastDistribute::Post() {

797 for (int var_index = 0; var_index < var_size(); ++var_index) {

798 IntVar* const var = vars_[var_index];

799 if (!var->Bound()) {

800 Demon* d =

802 "OneBound", var_index);

803 var->WhenBound(d);

805 &BoundedFastDistribute::OneDomain, "OneDomain",

806 var_index);

807 var->WhenDomain(d);

808 }

809 }

810}

811

812void BoundedFastDistribute::InitialPropagate() {

813 Solver* const s = solver();

814

815 int64_t sum_card_min = 0;

816 for (int i = 0; i < card_size(); ++i) {

817 if (card_max_[i] < card_min_[i]) {

818 solver()->Fail();

819 }

820 sum_card_min += card_min_[i];

821 }

822 if (sum_card_min > var_size()) {

823 s->Fail();

824 }

825 if (sum_card_min == var_size()) {

826 for (int i = 0; i < var_size(); ++i) {

827 vars_[i]->SetRange(0, card_size() - 1);

828 }

829 }

830

831 for (int card_index = 0; card_index < card_size(); ++card_index) {

832 int min = 0;

833 int max = 0;

834 for (int i = 0; i < var_size(); ++i) {

835 IntVar* const var = vars_[i];

836 if (var->Bound()) {

837 if (var->Min() == card_index) {

838 min++;

839 max++;

840 }

841 } else if (var->Contains(card_index)) {

842 max++;

843 undecided_.SetToOne(s, i, card_index);

844 }

845 }

846 min_.SetValue(s, card_index, min);

847 max_.SetValue(s, card_index, max);

848 CountVar(card_index);

849 }

850}

851

852void BoundedFastDistribute::OneBound(int index) {

853 IntVar* const var = vars_[index];

854 const int64_t var_min = var->Min();

855 for (int card_index = 0; card_index < card_size(); ++card_index) {

856 if (undecided_.IsSet(index, card_index)) {

857 if (var_min == card_index) {

858 SetRevDoContribute(index, card_index);

859 } else {

860 SetRevCannotContribute(index, card_index);

861 }

862 }

863 }

864}

865

866void BoundedFastDistribute::OneDomain(int index) {

867 IntVar* const var = vars_[index];

868 const int64_t oldmin = var->OldMin();

869 const int64_t oldmax = var->OldMax();

870 const int64_t vmin = var->Min();

871 const int64_t vmax = var->Max();

872 for (int64_t card_index = std::max(oldmin, int64_t{0});

873 card_index < std::min(vmin, card_size()); ++card_index) {

874 if (undecided_.IsSet(index, card_index)) {

875 SetRevCannotContribute(index, card_index);

876 }

877 }

878 for (const int64_t card_index : InitAndGetValues(holes_[index])) {

879 if (card_index >= 0 && card_index < card_size() &&

880 undecided_.IsSet(index, card_index)) {

881 SetRevCannotContribute(index, card_index);

882 }

883 }

884 for (int64_t card_index = std::max(vmax + 1, int64_t{0});

885 card_index <= std::min(oldmax, card_size() - 1); ++card_index) {

886 if (undecided_.IsSet(index, card_index)) {

887 SetRevCannotContribute(index, card_index);

888 }

889 }

890}

891

892void BoundedFastDistribute::CountVar(int card_index) {

893 const int64_t stored_min = min_[card_index];

894 const int64_t stored_max = max_[card_index];

895 if (card_min_[card_index] > stored_max ||

896 card_max_[card_index] < stored_min) {

897 solver()->Fail();

898 }

899 if (card_min_[card_index] == stored_max) {

900 CardMax(card_index);

901 }

902 if (card_max_[card_index] == stored_min) {

903 CardMin(card_index);

904 }

905}

906

907void BoundedFastDistribute::CardMin(int card_index) {

908 for (int var_index = 0; var_index < var_size(); ++var_index) {

909 if (undecided_.IsSet(var_index, card_index)) {

910 vars_[var_index]->RemoveValue(card_index);

911 }

912 }

913}

914

915void BoundedFastDistribute::CardMax(int card_index) {

916 for (int var_index = 0; var_index < var_size(); ++var_index) {

917 if (undecided_.IsSet(var_index, card_index)) {

918 vars_[var_index]->SetValue(card_index);

919 }

920 }

921}

922

923

924

925class SetAllToZero : public Constraint {

926 public:

927 SetAllToZero(Solver* const s, const std::vector<IntVar*>& vars)

928 : Constraint(s), vars_(vars) {}

929

930 ~SetAllToZero() override {}

931

932 void Post() override {}

933

934 void InitialPropagate() override {

935 for (int i = 0; i < vars_.size(); ++i) {

936 vars_[i]->SetValue(0);

937 }

938 }

939

940 std::string DebugString() const override { return "SetAllToZero()"; }

941

942 void Accept(ModelVisitor* const visitor) const override {

943 visitor->BeginVisitConstraint(ModelVisitor::kDistribute, this);

944 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kCardsArgument,

945 vars_);

946 visitor->EndVisitConstraint(ModelVisitor::kDistribute, this);

947 }

948

949 private:

950 const std::vector<IntVar*> vars_;

951};

952}

953

954

955

957 int64_t max_count) {

958 CHECK_GE(max_count, 0);

959 if (max_count >= vars.size()) {

961 }

962 return RevAlloc(new AtMost(this, std::move(vars), value, max_count));

963}

964

966 const std::vector<int64_t>& values,

967 const std::vector<IntVar*>& cards) {

968 if (vars.empty()) {

969 return RevAlloc(new SetAllToZero(this, cards));

970 }

971 CHECK_EQ(values.size(), cards.size());

972 for (IntVar* const var : vars) {

973 CHECK_EQ(this, var->solver());

974 }

975

976

977 bool fast = true;

978 for (int i = 0; i < values.size(); ++i) {

979 if (values[i] != i) {

980 fast = false;

981 break;

982 }

983 }

984 for (IntVar* const card : cards) {

985 CHECK_EQ(this, card->solver());

986 }

987 if (fast) {

988 return RevAlloc(new FastDistribute(this, vars, cards));

989 } else {

990 return RevAlloc(new Distribute(this, vars, values, cards));

991 }

992}

993

995 const std::vector<int>& values,

996 const std::vector<IntVar*>& cards) {

998}

999

1001 const std::vector<IntVar*>& cards) {

1002 if (vars.empty()) {

1003 return RevAlloc(new SetAllToZero(this, cards));

1004 }

1005 for (IntVar* const var : vars) {

1006 CHECK_EQ(this, var->solver());

1007 }

1008 for (IntVar* const card : cards) {

1009 CHECK_EQ(this, card->solver());

1010 }

1011 return RevAlloc(new FastDistribute(this, vars, cards));

1012}

1013

1015 int64_t card_min, int64_t card_max,

1016 int64_t card_size) {

1017 const int vsize = vars.size();

1018 CHECK_NE(vsize, 0);

1019 for (IntVar* const var : vars) {

1020 CHECK_EQ(this, var->solver());

1021 }

1022 if (card_min == 0 && card_max >= vsize) {

1024 } else if (card_min > vsize || card_max < 0 || card_max < card_min) {

1026 } else {

1027 std::vector<int64_t> mins(card_size, card_min);

1028 std::vector<int64_t> maxes(card_size, card_max);

1029 return RevAlloc(new BoundedFastDistribute(this, vars, mins, maxes));

1030 }

1031}

1032

1034 const std::vector<int64_t>& card_min,

1035 const std::vector<int64_t>& card_max) {

1036 const int vsize = vars.size();

1037 CHECK_NE(vsize, 0);

1038 int64_t cmax = std::numeric_limits<int64_t>::max();

1039 int64_t cmin = std::numeric_limits<int64_t>::min();

1040 for (int i = 0; i < card_max.size(); ++i) {

1041 cmax = std::min(cmax, card_max[i]);

1042 cmin = std::max(cmin, card_min[i]);

1043 }

1044 if (cmax < 0 || cmin > vsize) {

1046 } else if (cmax >= vsize && cmin == 0) {

1048 } else {

1049 return RevAlloc(new BoundedFastDistribute(this, vars, card_min, card_max));

1050 }

1051}

1052

1054 const std::vector<int>& card_min,

1055 const std::vector<int>& card_max) {

1057}

1058

1060 const std::vector<int64_t>& values,

1061 const std::vector<int64_t>& card_min,

1062 const std::vector<int64_t>& card_max) {

1063 CHECK_NE(vars.size(), 0);

1064 CHECK_EQ(card_min.size(), values.size());

1065 CHECK_EQ(card_min.size(), card_max.size());

1068 IsArrayInRange(vars, values.front(), values.back())) {

1070 } else {

1072 new BoundedDistribute(this, vars, values, card_min, card_max));

1073 }

1074}

1075

1077 const std::vector<int>& values,

1078 const std::vector<int>& card_min,

1079 const std::vector<int>& card_max) {

1082}

1083}

virtual bool Bound() const

Returns true if the min and the max of the expression are equal.

virtual int64_t Min() const =0

static const char kDistribute[]

static const char kValueArgument[]

static const char kValuesArgument[]

static const char kAtMost[]

static const char kVarsArgument[]

static const char kCountArgument[]

static const char kCardsArgument[]

bool IsSet(int64_t row, int64_t column) const

Returns whether the 'column' bit in the 'row' row is set.

void SetToZero(Solver *solver, int64_t row, int64_t column)

Erases the 'column' bit in the 'row' row.

void SetToOne(Solver *solver, int64_t row, int64_t column)

Sets the 'column' bit in the 'row' row.

Constraint * MakeDistribute(const std::vector< IntVar * > &vars, const std::vector< int64_t > &values, const std::vector< IntVar * > &cards)

Aggregated version of count: |{i | v[i] == values[j]}| == cards[j].

Definition count_cst.cc:965

Constraint * MakeSumEquality(const std::vector< IntVar * > &vars, int64_t cst)

IntVar * MakeIsEqualCstVar(IntExpr *var, int64_t value)

status var of (var == value)

IntExpr * MakeSum(IntExpr *left, IntExpr *right)

left + right.

Constraint * MakeAtMost(std::vector< IntVar * > vars, int64_t value, int64_t max_count)

|{i | vars[i] == value}| <= max_count

Definition count_cst.cc:956

Constraint * MakeCount(const std::vector< IntVar * > &vars, int64_t value, int64_t max_count)

|{i | vars[i] == value}| == max_count

Definition count_cst.cc:32

Constraint * MakeTrueConstraint()

This constraint always succeeds.

Constraint * MakeAllDifferent(const std::vector< IntVar * > &vars)

Constraint * MakeFalseConstraint()

This constraint always fails.

std::string JoinDebugStringPtr(const std::vector< T > &v, absl::string_view separator)

std::vector< int64_t > ToInt64Vector(const std::vector< int > &input)

bool IsIncreasingContiguous(const std::vector< T > &values)

bool IsArrayInRange(const std::vector< IntVar * > &vars, T range_min, T range_max)

Demon * MakeConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)

bool AreAllOnes(const std::vector< T > &values)