ibm2024jan.py

from itertools import permutations

#  Program to solve IBM's Ponder This puzzle for January 2024.
#  https://research.ibm.com/haifa/ponderthis/challenges/January2024.html
#
#  Using each of the numbers 1–16 exactly once, fill in the blank squares
#  in the grid below, so that the 16 equations are true.
# 
# ┌───┬───┬───┬───┬───┬───┬───┐
# │   │ + │   │ − │   │ − │   │  5 
# ├───┼───┼───┼───┼───┼───┼───┤
# │ + │ ▓ │ + │ ▓ │ − │ ▓ │ + │   
# ├───┼───┼───┼───┼───┼───┼───┤
# │   │ + │   │ - │   │ − │   │  10 
# ├───┼───┼───┼───┼───┼───┼───┤
# │ + │ ▓ │ − │ ▓ │ − │ ▓ │ + │  
# ├───┼───┼───┼───┼───┼───┼───┤
# │   │ − │   │ + │   │ + │   │  9 
# ├───┼───┼───┼───┼───┼───┼───┤
# │ − │ ▓ │ − │ ▓ │ + │ ▓ │ + │  
# ├───┼───┼───┼───┼───┼───┼───┤
# │   │ − │   │ + │   │ − │   │  0 
# └───┴───┴───┴───┴───┴───┴───┘
#  17       8      11      48 

#  This is a system of 8 linear equations in 16 variables, thus it
#  is under-determined, with 8 degrees of freedom.
#  A computation outside this program shows one way to choose the
#  8 free variable and the 8 determined variables is given by the 
#  equations expressed in the 'check' subroutine.
#  The free variables are a,b,c,e,f,g,i,k and the other 8 variables
#  are calculated via as shown below.

#  Given the values of the free variables, calculate the determined
#  values and see if the numbers 1–16 are used exactly once each,
#  indicating a solution has been found.

numbers = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}

def check(a,b,c,e,f,g,i,k):
    d =  a + b - c - 5
    h =  e + f + g - 10
    j = -a + c - e - g + 26
    l = -a + c - e - g - i - k + 35
    m =  a + e + i - 17
    n =  a + b - c + e + f + g - 34
    o = -c + g + k + 11
    p = -b - f + i + k + 28

    candidate = (a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p)
    ok = set(candidate) == numbers
    return candidate if ok else None

def show(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p):
    print(f'{a:4}{b:4}{c:4}{d:4}')
    print(f'{e:4}{f:4}{g:4}{h:4}')
    print(f'{i:4}{j:4}{k:4}{l:4}')
    print(f'{m:4}{n:4}{o:4}{p:4}')

#  Here we go through the 16!/8! = 518,918,400 possible assignments to
#  the 8 free variables, displaying solutions as they are found.

solutions = 0
for a,b,c,e,f,g,i,k in permutations(numbers, 8):
    if solution := check(a,b,c,e,f,g,i,k):
        solutions += 1
        show(*solution)
        print()

print(solutions, "solutions found")