I do every single one of Jane Street’s monthly puzzles1. I figured I’d do a little write up on last month’s2. I try to post my solutions to my GitHub3 after the solution has already been revealed to everyone, but I might start to detail out the thought process behind solving them here. This one I solved the first day it came out and was the 7th accepted submission4.
Fill the empty cells in the grid above with digits such that each row, column, and outlined 3-by-3 box contains the same set of nine unique digits[1], and such that the nine 9-digit numbers[2] formed by the rows of the grid has the highest-possible GCD over any such grid.
Some of the cells have already been filled in. The answer to this puzzle is the 9-digit number formed by the middle row in the completed grid.
that is, you’ll be using nine of the ten digits (0-9) in completing this grid
possibly with a leading 0
Solution
Solving this month’s puzzle was substantially easier if you put yourself in the shoes of the person that made this puzzle. They want you to maximize the GCD of your solution so your prior should be that the GCD is large, but now remember that generally all of these puzzles can be done by hand so the GCD should be something that one could arrive at by hand….
The sum of all elements is divisible by X is also divisible by X. This implies that the sum of all the rows, which can be expressed as (45 - k) * 111,111,111 inherits this divisibility. The prime factorization of 111,111,111 is 333,667 * 37 * 3^2 so we can reason that the GCD of each row will be a multiple of 333,667 conditioned on the fact that it is both large and doable by hand. (The reason it’s 45 - k is because we have to pick 9 numbers from [0, 9]. The sum of all the numbers from [0, 9] is 45 so our sum will be 45 minus the number not in the puzzle— ‘k’.)
We know that one of the columns has to have a leading 0, so the maximum possible GCD could be of the form 1x,xxx,xxx. We now just have to loop through multiples of 333,667 starting from the maximum allowable value and stop once we achieve one where the constraints of the puzzle can be met. I chose to use Z3 Theorem Prover for this because a constraint problem like sudoku is a perfect use case for Z3. Below is the code I used (with comments explaining what each constraint is).
Jane Street. Puzzles. https://www.janestreet.com/puzzles/.
Jane Street. Somewhat Square Sudoku. Retrieved from https://www.janestreet.com/puzzles/somewhat-square-sudoku-index/
GitHub. Jane Street Solutions. https://github.com/evansemet/Jane-Street-Solutions
Jane Street. Somewhat Square Sudoku Solution. https://www.janestreet.com/puzzles/somewhat-square-sudoku-solution/