9-16-25 2D Matrix

Question

Given three grids and the sum of rows and columns of each grid, your task is:

• Grid ×ばつ3\$: Fill the grid from \1ドル\$ to \9ドル\$, ensure no repeats within the grid.
  
• Grid ×ばつ4\$: Fill the grid from \1ドル\$ to \16ドル\$, ensure no repeats within the grid.
  
• Grid ×ばつ5\$: Fill the grid from \1ドル\$ to \25ドル\$, ensure no repeats within the grid.
  

Output ONLY one solution if many solutions exist. All solutions that meet the criteria are accepted.
Input ensures a solution exists.

Test Case

Format is flexible.

Inp×ばつ3 grid:
[[12, 18, 15], # sum of row 1 2 3
 [9, 18, 18]] # sum of column 1 2 ×ばつ4 grid:
[[33, 21, 43, 39], # sum of row 1 2 3 4
 [24, 36, 41, 35]] # sum of column 1 2 3 ×ばつ5 grid:
[[43, 79, 58, 60, 85], # sum of row 1 2 3 4 5
 [76, 66, 44, 70, 69]] # sum of column 1 2 3 4 5
One possible solution For ×ばつ3, ×ばつ4, ×ばつ5 grid For the given Input:
[[1, 7, 4],
 [3, 9, 6],
 [5, 2, 8]]
[[1, 3, 15, 14],
 [6, 9, 2, 4],
 [12, 8, 13, 10],
 [5, 16, 11, 7]]
[[1, 9, 12, 6, 15],
 [24, 19, 3, 11, 22],
 [8, 20, 10, 16, 4],
 [18, 5, 2, 14, 21],
 [25, 13, 17, 23, 7]]

Criteria

The time measurement will be conducted with AMD Ryzen 9 7900X3D with 64GB RAM.
Only \1ドル\$ core is utilized.
This is a competition per language.

Lowest runtime performance wins. If many code snippets have similar runtime, priority will be given to the snippet submitted first.

Standing

Fastest Code	Language	Runtime
Bubbler	Picat	10 - 40 ms
Tobias Grothe	Java	29 - 100 ms
dingledooper	Python	2.2 - 2.8 s
Fatalize	Brachylog	3.6 - 5.4 s

• mousetail: You can edit your post, you don't need to post a new one every time
• Tobias: @HaDong Please update again. ;-) codegolf.stackexchange.com/a/273625/120216

Answer 1

Picat

import cp.
puzzle(Rows, Cols, N) = A =>
	A = new_array(N,N),
	A :: 1..N*N,
	all_distinct([A[R,C]: R in 1..N, C in 1..N]),
	foreach(R in 1..N) sum(A[R]) #= Rows[R] end,
	foreach(C in 1..N) sum([A[R,C]: R in 1..N]) #= Cols[C] end,
	solve(A).
main =>
	println(puzzle([12, 18, 15], [9, 18, 18], 3)),
	println(puzzle([33, 21, 43, 39], [24, 36, 41, 35], 4)),
	println(puzzle([43, 79, 58, 60, 85], [76, 66, 44, 70, 69], 5)).

Output:

{{1,4,7},{3,6,9},{5,8,2}}
{{1,2,14,16},{3,6,8,4},{11,15,7,10},{9,13,12,5}}
{{1,2,3,12,25},{6,15,17,21,20},{22,14,4,10,8},{23,16,7,9,5},{24,19,13,18,11}}

Attempt This Online!

Solves all three puzzles in 0.1 second on ATO.

• Arnauld: Right tool for the job! 👍
• Jonathan Allan: I imagine, since we are guaranteed the input has a solution, that foreach(R in 1..N-1) or foreach(C in 1..N-1) will shave a little time.
• Jonathan Allan: "or" -> "and" ...because the remaining row/column will have the correct sum in both cases.
• Bubbler: @JonathanAllan The situation is a bit different in constraint programming. It is often better to pass in as much information as possible, so that the engine can backtrack more often and/or save time spent on inferring the information by itself. For this particular program, it doesn't seem to visibly change the running time.
• Jonathan Allan: Uh-huh, and for larger grids it can degrade performance.

Answer 2

Brachylog, 43 bytes

{hlL;Mṁ(+m~h?∧M\+m~t?∧Mc≠{>0∧.^2≥?∧}vL∧M≜}m

Try it online!

Takes about 5 seconds for all 3 cases on TIO.

Explanation

Since Brachylog uses constraint logic arithmetic by default for all integer operations, we don’t even need to do anything special to be able to solve this kind of problem relatively efficiently. The performance of the solve will depend on the performance of the clp(fd) library of SWI-Prolog which is used by Brachylog.

Note that this code is not golfed.

{ }m Map for each input list:
 hlL L is the number of sums
 L;Mṁ( M is a square matrix of size L
 M +m~h? Sums of rows of M is the first element of the input
 ∧
 M\+m~t? Sums of columns of M is the last element of the input
 ∧
 Mc≠ All elements of M are different
 { }vL For each element:
 >0 It is strictly greater than 0
 ∧
 .^2≥?∧ It is greater or equal to L2
 ∧
 M≜ Find values for elements of M that match all these
 constraints, M is the output

• SanguineL: "Note that this code is not golfed." Would never have assumed that! Wow.

Answer 3

Java

(Simple) backtracking approach with random candidates:

import java.util.*;
import java.util.concurrent.atomic.AtomicLong;
public class Main {
 public static void main(String[] args) {
 long start = System.currentTimeMillis();
 System.out.println(Arrays.deepToString(calcSolution(new int[][]{{12, 18, 15}, {9, 18, 18}})));
 System.out.println(Arrays.deepToString(calcSolution(new int[][]{{33, 21, 43, 39}, {24, 36, 41, 35}})));
 System.out.println(Arrays.deepToString(calcSolution(new int[][]{{43, 79, 58, 60, 85}, {76, 66, 44, 70, 69}})));
 long end = System.currentTimeMillis();
 System.out.println("Time: " + (end - start) + "ms");
 int n = 20;
 long time1 = 0;
 for (int i = 0; i < n; i++) {
 start = System.currentTimeMillis();
 System.out.println(Arrays.deepToString(calcSolution(new int[][]{{43, 79, 58, 60, 85}, {76, 66, 44, 70, 69}})));
 end = System.currentTimeMillis();
 time1 += end - start;
 }
 time1 /= n;
 System.out.println("Time (average): " + time1 + "ms for " + n + " times");
 }
 public static int[][] calcSolution(int[][] grid) {
 final int n1 = grid[0].length;
 final int n2 = n1 * n1;
 final ArrayList<ArrayList<Integer>> randoms = new ArrayList<>();
 for (int i = 0; i < n2; i++) {
 ArrayList<Integer> list = new ArrayList<>();
 for (int j = 0; j < n2; j++) {
 list.add(j + 1);
 }
 Collections.shuffle(list);
 randoms.add(list);
 }
 int[][] solution = new int[n1][n1];
 while (calcSolution2(grid, n1, n2, solution, 0, new int[2][n1], new HashSet<>(), randoms, new AtomicLong()) == 2) {
 //System.out.println("new round");
 for (int i = 0; i < n2; i++) {
 Collections.shuffle(randoms.get(i));
 }
 solution = new int[n1][n1];
 }
 // (Only for testing/checking for me)
 test(grid, n1, solution);
 return solution;
 }
 private static int calcSolution2(int[][] grid, int n1, int n2, int[][] solution, int idx, int[][] sums, HashSet<Integer> seen, ArrayList<ArrayList<Integer>> randoms, AtomicLong callsCounter) {
 if (idx == n2) {
 return 1;
 }
 if (callsCounter.incrementAndGet() == 1_000_000) {
 return 2;
 }
 int r = idx / n1;
 int c = idx % n1;
 for (int i : randoms.get(idx)) {
 if (seen.contains(i)) {
 continue;
 }
 solution[r][c] = i;
 sums[0][r] += i;
 sums[1][c] += i;
 if (sums[0][r] > grid[0][r] || sums[1][c] > grid[1][c]) {
 sums[0][r] -= i;
 sums[1][c] -= i;
 continue;
 }
 if ((idx + 1) % n1 == 0 && sums[0][r] != grid[0][r]) {
 sums[0][r] -= i;
 sums[1][c] -= i;
 continue;
 }
 if (idx / n1 == n1 - 1 && sums[1][c] != grid[1][c]) {
 sums[0][r] -= i;
 sums[1][c] -= i;
 continue;
 }
 seen.add(i);
 int retVal = calcSolution2(grid, n1, n2, solution, idx + 1, sums, seen, randoms, callsCounter);
 if (retVal > 0) {
 return retVal;
 }
 seen.remove(i);
 sums[0][r] -= i;
 sums[1][c] -= i;
 }
 return 0;
 }
 // (Only for testing/checking for me)
 private static void test(int[][] grid, int n1, int[][] solution) {
 int[][] sums = new int[2][n1];
 for (int i = 0; i < n1; i++) {
 for (int j = 0; j < n1; j++) {
 sums[0][i] += solution[i][j];
 sums[1][i] += solution[j][i];
 }
 }
 for (int i = 0; i < n1; i++) {
 if (sums[0][i] != grid[0][i] || sums[1][i] != grid[1][i]) {
 System.out.println(false);
 return;
 }
 }
 System.out.println(true);
 }
}

Try it online!

Average time on my CPU:

< 200ms

Log:

• 2024年06月14日: I use random candidates to fill now.
• 2024年06月17日: Improved exit condition. Runs in under 200ms now!

• Tobias: The code can possibly be improved by a better termination condition of the recursion (earlier termination or truncation of branches) - but I have no idea at the moment. Also, the (magic) value of calls (5 million) to shuffle all candidates again may not be perfectly chosen. Overall, BT search may not be the best choice for this.
• user123147: The code seems to consistently run in under 100ms when I changed the calls counter to 1000 on my CPU.
• Tobias: @HaDong true, 1_000_000 might be a bit too high. The trick is to find a trade-off between too many re-shuffles and too much time costs. "1k" seems to be a reasonable value.
• Tobias: And please comment test(grid, n1, solution); out - that was just a check for me.

Answer 4

Python

To run the code, install the z3-solver package. It can usually solve all three cases in ~1s.

from z3 import *
def solve(rows, cols, n):
 grid = [Int(f'a{i}') for i in range(n * n)]
 s = Solver()
 s.add(Distinct(grid))
 for i in range(n * n):
 s.add(Or([grid[i] == j + 1 for j in range(n * n)]))
 
 for i in range(n):
 s.add(sum(grid[i*n:i*n+n]) == rows[i])
 s.add(sum(grid[i::n]) == cols[i])
 
 assert s.check() == sat
 model = s.model()
 sol = [model[g].as_long() for g in grid]
 return [sol[i*n:i*n+n] for i in range(n)]
print(solve([12, 18, 15], [9, 18, 18], 3))
print(solve([33, 21, 43, 39], [24, 36, 41, 35], 4))
print(solve([43, 79, 58, 60, 85], [76, 66, 44, 70, 69], 5))

• Jonathan Allan: Not checking the final column or row sum saves ~18% of the time (the input is guaranteed to have a solution).
• Bubbler: Maybe you can use SolverFor('QF_FD') instead of simply Solver()? QF_FD-specific engine tends to work well on puzzle-like problems.
• dingledooper: @Bubbler Wow that is impressive, the time went down to ~200ms!

Answer 5

Nekomata + -1, 21 bytes

a#*R↕v#Š:m∑dv=¿:∑d§=¿

Attempt This Online!

I just wanted to see how fast my golfing language can go. The language uses a simple backtracking algorithm, and it's not optimized for speed.

The 3x3 and 4x4 grids can be solved in around 4 seconds on ATO. Better than I expected.

Do not try the 5x5 grid. It will eat up all your memory and will never finish.

a#*R↕v#Š:m∑dv=¿:∑d§=¿
a#* Multiply the lengths of both inputs
 R Range from 1 to the product
 ↕ Find a permutation of the range
 v#Š Split into slices of the lengths of the inputs
 :m∑dv=¿ Check if the sums of each slice are equal to the first input
 :∑d§=¿ Check if the (vectorized) sum of all slices is equal to the second input

-1 finds only the first solution.

If you want to run it on your machine, you need to install cabal and ghc, then run the following commands:

git clone https://github.com/AlephAlpha/Nekomata.git
cd Nekomata
cabal build
cabal run Nekomata -- -c 'a#*R↕v#Š:m∑dv=¿:∑d§=¿' -1 -i '[12,18,15] [9,18,18]'
cabal run Nekomata -- -c 'a#*R↕v#Š:m∑dv=¿:∑d§=¿' -1 -i '[33,21,43,39] [24,36,41,35]'

Answer 6

Julia

Needs JuMP and MiniZinc.jl. Takes ~0.5 seconds on my machine to solve all 3.

using JuMP
using MiniZinc
# Only need this for Windows.
ENV["JULIA_LIBMINIZINC_DIR"] = "C:\\Program Files\\MiniZinc"
function find_matrix(mat_sum)
 n = length(mat_sum[1, :])
 model = Model(() -> MiniZinc.Optimizer{Float64}("highs"))
 @variable(model, 1 ≤ x[1:n, 1:n] ≤ n^2, Int)
 @constraint(model, vec(x) in MOI.AllDifferent(n^2))
 for i in 1:n
 @constraint(model, sum(x[i, :]) == mat_sum[1, i])
 @constraint(model, sum(x[:, i]) == mat_sum[2, i])
 end
 optimize!(model)
 display(value.(x))
end
find_matrix([12 18 15; 9 18 18])
find_matrix([33 21 43 39; 24 36 41 35])
find_matrix([43 79 58 60 85; 76 66 44 70 69])
```

• emanresu A: Welcome to Code Golf, and nice first answer!