2023-01-29 21:20:58 +01:00
|
|
|
#!/usr/bin/env python3
|
2025-01-10 11:35:44 +01:00
|
|
|
# Copyright 2010-2025 Google LLC
|
2023-01-29 21:20:58 +01:00
|
|
|
# Licensed under the Apache License, Version 2.0 (the "License");
|
|
|
|
|
# you may not use this file except in compliance with the License.
|
|
|
|
|
# You may obtain a copy of the License at
|
|
|
|
|
#
|
|
|
|
|
# http://www.apache.org/licenses/LICENSE-2.0
|
|
|
|
|
#
|
|
|
|
|
# Unless required by applicable law or agreed to in writing, software
|
|
|
|
|
# distributed under the License is distributed on an "AS IS" BASIS,
|
|
|
|
|
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
|
|
|
|
# See the License for the specific language governing permissions and
|
|
|
|
|
# limitations under the License.
|
2023-07-01 06:06:53 +02:00
|
|
|
|
2025-07-23 17:38:49 +02:00
|
|
|
"""Use CP-SAT to solve a simple cryptarithmetic problem: SEND+MORE=MONEY."""
|
2023-01-29 21:20:58 +01:00
|
|
|
|
|
|
|
|
from absl import app
|
|
|
|
|
from ortools.sat.python import cp_model
|
|
|
|
|
|
|
|
|
|
|
2024-07-23 14:07:41 +02:00
|
|
|
def send_more_money() -> None:
|
2023-11-16 19:46:56 +01:00
|
|
|
"""solve the cryptarithmic puzzle SEND+MORE=MONEY."""
|
2023-01-29 21:20:58 +01:00
|
|
|
model = cp_model.CpModel()
|
|
|
|
|
|
|
|
|
|
# Create variables.
|
|
|
|
|
# Since s is a leading digit, it can't be 0.
|
2023-11-16 19:46:56 +01:00
|
|
|
s = model.new_int_var(1, 9, "s")
|
|
|
|
|
e = model.new_int_var(0, 9, "e")
|
|
|
|
|
n = model.new_int_var(0, 9, "n")
|
|
|
|
|
d = model.new_int_var(0, 9, "d")
|
2023-01-29 21:20:58 +01:00
|
|
|
# Since m is a leading digit, it can't be 0.
|
2023-11-16 19:46:56 +01:00
|
|
|
m = model.new_int_var(1, 9, "m")
|
|
|
|
|
o = model.new_int_var(0, 9, "o")
|
|
|
|
|
r = model.new_int_var(0, 9, "r")
|
|
|
|
|
y = model.new_int_var(0, 9, "y")
|
2023-01-29 21:20:58 +01:00
|
|
|
|
|
|
|
|
# Create carry variables. c0 is true if the first column of addends carries
|
|
|
|
|
# a 1, c2 is true if the second column carries a 1, and so on.
|
2023-11-16 19:46:56 +01:00
|
|
|
c0 = model.new_bool_var("c0")
|
|
|
|
|
c1 = model.new_bool_var("c1")
|
|
|
|
|
c2 = model.new_bool_var("c2")
|
|
|
|
|
c3 = model.new_bool_var("c3")
|
2023-01-29 21:20:58 +01:00
|
|
|
|
|
|
|
|
# Force all letters to take on different values.
|
2023-11-16 19:46:56 +01:00
|
|
|
model.add_all_different(s, e, n, d, m, o, r, y)
|
2023-01-29 21:20:58 +01:00
|
|
|
|
|
|
|
|
# Column 0:
|
2023-11-16 19:46:56 +01:00
|
|
|
model.add(c0 == m)
|
2023-01-29 21:20:58 +01:00
|
|
|
|
|
|
|
|
# Column 1:
|
2023-11-16 19:46:56 +01:00
|
|
|
model.add(c1 + s + m == o + 10 * c0)
|
2023-01-29 21:20:58 +01:00
|
|
|
|
|
|
|
|
# Column 2:
|
2023-11-16 19:46:56 +01:00
|
|
|
model.add(c2 + e + o == n + 10 * c1)
|
2023-01-29 21:20:58 +01:00
|
|
|
|
|
|
|
|
# Column 3:
|
2023-11-16 19:46:56 +01:00
|
|
|
model.add(c3 + n + r == e + 10 * c2)
|
2023-01-29 21:20:58 +01:00
|
|
|
|
|
|
|
|
# Column 4:
|
2023-11-16 19:46:56 +01:00
|
|
|
model.add(d + e == y + 10 * c3)
|
2023-01-29 21:20:58 +01:00
|
|
|
|
2023-11-16 19:46:56 +01:00
|
|
|
# solve model.
|
2023-01-29 21:20:58 +01:00
|
|
|
solver = cp_model.CpSolver()
|
2023-11-16 19:46:56 +01:00
|
|
|
if solver.solve(model) == cp_model.OPTIMAL:
|
2023-07-01 06:06:53 +02:00
|
|
|
print("Optimal solution found!")
|
2023-11-16 19:46:56 +01:00
|
|
|
print("s:", solver.value(s))
|
|
|
|
|
print("e:", solver.value(e))
|
|
|
|
|
print("n:", solver.value(n))
|
|
|
|
|
print("d:", solver.value(d))
|
|
|
|
|
print("m:", solver.value(m))
|
|
|
|
|
print("o:", solver.value(o))
|
|
|
|
|
print("r:", solver.value(r))
|
|
|
|
|
print("y:", solver.value(y))
|
2023-01-29 21:20:58 +01:00
|
|
|
|
|
|
|
|
|
2024-07-23 14:07:41 +02:00
|
|
|
def main(_) -> None:
|
2023-01-29 21:20:58 +01:00
|
|
|
send_more_money()
|
|
|
|
|
|
|
|
|
|
|
2023-07-01 06:06:53 +02:00
|
|
|
if __name__ == "__main__":
|
2023-01-29 21:20:58 +01:00
|
|
|
app.run(main)
|
