11
\$\begingroup\$

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

  • Grid \$3×3\$: Fill the grid from \$1\$ to \$9\$, ensure no repeats within the grid.
  • Grid \$4×4\$: Fill the grid from \$1\$ to \$16\$, ensure no repeats within the grid.
  • Grid \$5×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.

Input:
3×3 grid:
[[12, 18, 15], # sum of row 1 2 3
 [9, 18, 18]] # sum of column 1 2 3
4×4 grid:
[[33, 21, 43, 39], # sum of row 1 2 3 4
 [24, 36, 41, 35]] # sum of column 1 2 3 4
5×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×3, 4×4, 5×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
\$\endgroup\$
2

5 Answers 5

12
\$\begingroup\$

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.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Right tool for the job! 👍 \$\endgroup\$
    – Arnauld
    Commented Jun 13 at 14:59
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Jun 14 at 17:48
  • \$\begingroup\$ "or" -> "and" ...because the remaining row/column will have the correct sum in both cases. \$\endgroup\$ Commented Jun 14 at 17:55
  • \$\begingroup\$ @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. \$\endgroup\$
    – Bubbler
    Commented Jun 17 at 6:59
  • \$\begingroup\$ Uh-huh, and for larger grids it can degrade performance. \$\endgroup\$ Commented Jun 19 at 16:00
6
\$\begingroup\$

Brachylog, 43 bytes

{hlL;Mṁ₍+ᵐ~h?∧M\+ᵐ~t?∧Mc≠{>0∧.^₂≥?∧}ᵛL∧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.

{                                           }ᵐ  Map for each input list:
 hlL                                            L is the number of sums
   L;Mṁ₍                                        M is a square matrix of size L
     M  +ᵐ~h?                                   Sums of rows of M is the first element of the input
             ∧
               M\+ᵐ~t?                          Sums of columns of M is the last element of the input
                      ∧
                        Mc≠                     All elements of M are different
                           {          }ᵛL       For each element:
                            >0                  It is strictly greater than 0
                              ∧
                                .^₂≥?∧          It is greater or equal to L²
                                         ∧
                                          M≜    Find values for elements of M that match all these
                                                constraints, M is the output
\$\endgroup\$
1
  • 3
    \$\begingroup\$ "Note that this code is not golfed." Would never have assumed that! Wow. \$\endgroup\$
    – SanguineL
    Commented Jun 13 at 13:01
5
\$\begingroup\$

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!
\$\endgroup\$
4
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Commented Jun 15 at 18:49
  • 1
    \$\begingroup\$ The code seems to consistently run in under 100ms when I changed the calls counter to 1000 on my CPU. \$\endgroup\$
    – user123147
    Commented Jun 17 at 10:15
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Commented Jun 17 at 15:16
  • 1
    \$\begingroup\$ And please comment test(grid, n1, solution); out - that was just a check for me. \$\endgroup\$ Commented Jun 17 at 15:18
5
\$\begingroup\$

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))
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Not checking the final column or row sum saves ~18% of the time (the input is guaranteed to have a solution). \$\endgroup\$ Commented Jun 15 at 16:54
  • 1
    \$\begingroup\$ Maybe you can use SolverFor('QF_FD') instead of simply Solver()? QF_FD-specific engine tends to work well on puzzle-like problems. \$\endgroup\$
    – Bubbler
    Commented Jun 17 at 7:04
  • \$\begingroup\$ @Bubbler Wow that is impressive, the time went down to ~200ms! \$\endgroup\$ Commented Jun 17 at 8:43
3
\$\begingroup\$

Nekomata + -1, 21 bytes

ᵃ#*R↕v#Š:ᵐ∑ᵈv=¿:∑ᵈ§=¿

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.

ᵃ#*R↕v#Š:ᵐ∑ᵈv=¿:∑ᵈ§=¿
ᵃ#*                     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
        :ᵐ∑ᵈv=¿         Check if the sums of each slice are equal to the first input
               :∑ᵈ§=¿   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 'ᵃ#*R↕v#Š:ᵐ∑ᵈv=¿:∑ᵈ§=¿' -1 -i '[12,18,15] [9,18,18]'
cabal run Nekomata -- -c 'ᵃ#*R↕v#Š:ᵐ∑ᵈv=¿:∑ᵈ§=¿' -1 -i '[33,21,43,39] [24,36,41,35]'
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.