Skip to content

Instantly share code, notes, and snippets.

@balbinus
Last active January 31, 2021 18:34
Show Gist options
  • Save balbinus/e3f8658603ca47af47319417e085d3c4 to your computer and use it in GitHub Desktop.
Save balbinus/e3f8658603ca47af47319417e085d3c4 to your computer and use it in GitHub Desktop.
#!/usr/bin/python3
import argparse
parser = argparse.ArgumentParser()
parser.add_argument("sum", type=int)
parser.add_argument("-s", "--start", type=int, default=1, help="start searching from a specific digit", metavar="DIGIT")
parser.add_argument("-t", "--stop", type=int, default=9, help="stop searching at a specific digit", metavar="DIGIT")
parser.add_argument("-n", "--min-addends", type=int, default=1, help="minimum number of addends", metavar="MIN")
parser.add_argument("-m", "--max-addends", type=int, default=9, help="maximum number of addends", metavar="MAX")
parser.add_argument("-a", "--addends", type=int, default=0, help="number of addends (implies -n X -m X)")
parser.add_argument("-x", "--x-sums", action="store_true", help="activate X-Sums Sudoku mode, where the number of addends must be present in the sums.")
parser.add_argument("--sandwich", action="store_true", help="activate Sandwich Sudoku mode. Implies --start 2 --stop 8 --min-addends 1 --max-addends 8")
parser.add_argument("--list-by-digit", action="store_true", help="make sub lists of addends by the digits they contain")
args = parser.parse_args()
total = args.sum
if args.sandwich:
args.start = 2
args.stop = 8
args.min_addends = 1
args.max_addends = 8
if args.addends > 0:
args.min_addends = args.max_addends = args.addends
args.start = min(max(args.start, 1), 9)
args.stop = min(max(args.stop, 1), 9)
if args.min_addends > 9 or args.max_addends > 9 or args.addends > 9 or args.min_addends < 1 or args.max_addends < 1:
print("This script cannot process more than 9 addends, or less than 1.")
exit(2)
def explore_tree(n, addends, sets, start=1, stop=9, min_addends=1, max_addends=9, x_sums=False):
base_sum = sum(addends)
last_max = addends[-1] if len(addends) > 0 else start - 1
addends.append(0)
for i in range(last_max + 1, stop + 1):
addends[-1] = i
if n >= min_addends and base_sum + i == total and (not x_sums or n in addends):
if n in sets:
sets[n].append(addends.copy())
else:
sets[n] = [addends.copy()]
if n + 1 <= max_addends and base_sum + i < total:
explore_tree(n + 1, addends.copy(), sets, start=start, stop=stop, min_addends=min_addends, max_addends=max_addends, x_sums=x_sums)
return sets
sets = explore_tree(1, [], {}, start=args.start, stop=args.stop, min_addends=args.min_addends, max_addends=args.max_addends, x_sums=args.x_sums)
if sets == []:
print("No solution found.")
else:
for n in range(args.min_addends, args.max_addends + 1):
if n in sets.keys():
print("Additions of %u digit(s) adding to %u:" % (n, total))
if args.list_by_digit:
print("Total sets: %u" % (len(sets[n])))
subsets = {}
for s in sets[n]:
print(s)
if args.list_by_digit:
for x in s:
if x in subsets:
subsets[x].append(s)
else:
subsets[x] = [s]
print()
if args.list_by_digit:
for (i,v) in sorted(subsets.items()):
print("With %u:" % (i))
for s in v:
print(s)
print("")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment