Brain-Teaser 13: [Fill out the grid]
From The Sunday Times, 28th May 1961 [link]
The numbers 1 to 9, in any order and using each once only, are to be placed one at a time in the nine squares A to J. As each number replaces a letter in a square, any numbers standing at that moment in adjacent squares (left, right, up or down, but not diagonally) are to be multiplied by three.
Thus, if we decided to begin with 4 in A, then 9 in E, 7 in B and 2 in D, etc., we should have:
and so on. On completion, the nine final numbers are added together to find the score.
There are obviously 81 ways of making the first move, and there are 131,681,894,400 ways of completing the array; yet the number of possible scores in quite small.
What is the smallest possible score?
This puzzle was originally published with no title.
[teaser13]
Frits and 
Tony Brooke-Taylor, and 
GeoffR, and 
hans droog, 
Hugh Casement, and 1 other are discussing. 
S2T2 
Jim Randell 10:28 am on 17 November 2020 Permalink |
We can drastically reduce the number of possibilities we have consider:
When the game is played the squares are filled out in a particular order. If, when we play the game, instead of filling in numbers we just note how many times the value in each particular square is trebled, then at the end we can find the minimum score for that particular ordering of squares by assigning 9 to the square that is trebled the fewest number of times (i.e. the final square filled out), 8 to the next lowest number of treblings, and so on until 1 is assigned to the square with the largest number of treblings.
This Python program considers all possible orderings for filling out the squares. It runs in 420ms.
Run: [ @repl.it ]
from enigma import grid_adjacency, subsets, irange, printf # numbers to fill out nums = list(irange(1, 9)) # grid adjacency matrix adj = grid_adjacency(3, 3) # multipliers (for number of treblings) mul = [1, 3, 9, 27, 81] # find the minimal score for a ordering of squares def play(js): # initial grid grid = [None] * 9 # place the numbers for j in js: # place the number grid[j] = 0 # and increase adjacent counts for i in adj[j]: if grid[i] is not None: grid[i] += 1 # determine the minimum score return sum(n * mul[k] for (n, k) in zip(nums, sorted(grid, reverse=1))) # choose an ordering for the squares, and find the minimum score r = min(play(js) for js in subsets(irange(9), size=len, select="P")) printf("min score = {r}")Solution: The smallest possible score is 171.
One way of getting this total is:
We can make the program run faster by exploiting the symmetry of the grid. For example, for the first move, we only need to consider one corner square, one edge square and the central square. It does make the program longer though.
LikeLike
Frits 11:02 am on 19 November 2020 Permalink |
The first part finds the minimum score for different kind of treblings under the condition that they add up to 12. It turns out this minimum can also be achieved by our number placing rules.
I didn’t immediately see how I could check if a list [A,B,C,D,E,F,G,H,J] from the result can be achieved so I reused Jim’s code to find the first permutation which has a score equal to this minimum.
from enigma import SubstitutedExpression, grid_adjacency, subsets # numbers to fill out nums = list(range(1, 10)) # grid adjacency matrix adj = grid_adjacency(3, 3) # multipliers (for number of treblings) mul = [1, 3, 9, 27, 81] score = lambda li: sum(n * mul[k] for (n, k) in zip(nums, sorted(li, reverse=1))) # the alphametic puzzle p = SubstitutedExpression( [ # if field x has adjacent fields x1...xn and k of them have already been set # # then k fields will now get trebled which previously didn't treble field x # and (n - k) fields will not get trebled now but later on will treble # field x (n - k) times. So for every trebling there is an instance of # non-trebling. # # adjacent field matrix; # # 2 3 2 sum of all elements is 24 # 3 4 3 half of them will not get trebled # 2 3 2 "sum([A,B,C,D,E,F,G,H,J]) == 12", ], answer="score([A,B,C,D,E,F,G,H,J]), A,B,C,D,E,F,G,H,J", digits=range(0, 5), env=dict(score=score), accumulate=min, d2i={3 : "ACGJ", 4: "ACGJBDFH"}, distinct="", verbose=0) # solve the puzzle r = p.run() min = list(r.accumulate)[0] lst = [] prt = ["A", "B", "C", "D", "E", "F", "G", "H", "J"] # check if this minimum can be achieved for js in subsets(range(9), size=len, select="P"): grid = [None] * 9 # place the numbers for j in js: # place the number grid[j] = 0 # and increase adjacent counts for i in adj[j]: if grid[i] is not None: grid[i] += 1 if score(grid) == min: print("smallest possible score:", min, "\n\nexample:\n") # sort grid (descending) lst = sorted(grid, reverse=True) # print all the steps for i in range(9): for k, j in enumerate(js): if j != i: continue g = grid[k] ind = lst.index(g) lst[ind] = -1 # set to "processed" prt[k] = ind + 1 # set field # treble adjacent fields for m in adj[k]: if type(prt[m]) == int: prt[m] *= 3 print(f"{prt[:3]} {prt[3:6]} {prt[6:]}") break # we only print one example # smallest possible score: 171 # # example: # # [2, 'B', 'C'] ['D', 'E', 'F'] ['G', 'H', 'J'] # [6, 3, 'C'] ['D', 'E', 'F'] ['G', 'H', 'J'] # [6, 9, 4] ['D', 'E', 'F'] ['G', 'H', 'J'] # [6, 27, 4] ['D', 1, 'F'] ['G', 'H', 'J'] # [18, 27, 4] [5, 3, 'F'] ['G', 'H', 'J'] # [18, 27, 12] [5, 9, 6] ['G', 'H', 'J'] # [18, 27, 12] [15, 9, 6] [7, 'H', 'J'] # [18, 27, 12] [15, 27, 6] [21, 8, 'J'] # [18, 27, 12] [15, 27, 18] [21, 24, 9]LikeLike