Сетка чисел и целевых сумм для каждой проблемы строки и столбца ⇐ Javascript

[Anonymous]

У меня есть сетка в паре с «целевыми суммами» для каждой строки и столбца. Вот пример: < /p>
06 03 21 19
19 2 4 8 9
09 8 7 6 3
11 4 8 1 7
10 2 3 7 7
< /code>
Цель состоит в том, чтобы определить, какие ячейки удалить, чтобы убедиться, что все целевые суммы выполняются: < /p>
06 03 21 19
19 2 . 8 9
09 . . 6 3
11 4 . . 7
10 . 3 7 .
< /code>
Гарантируется, что всегда будет решение для этой проблемы. Сумма и удалите их: < /p>
import { readFile } from "fs/promises";

const file = await readFile("input.txt", "utf8").then((contents) => contents.split("\n"));

const dimension = Number(file[0]);

const colTargets = file[1].trim().split(" ").map(Number);
const rowTargets: number[] = [];

const matrix: number[][] = [];

for (let i = 0; i < dimension; i++) {
const [target, ...rest] = file[2 + i].split(/\s+/).filter(Boolean).map(Number);

rowTargets = target;

matrix.push(rest);
}

function matchTarget(target: number, list: number[]) {
// do not sort since we need the indices
const candidates = list.slice(); // .sort((a, b) => b - a);
const combinations: number[][] = [];

const tracker: number[] = [];

function recurse(target: number, start: number) {
// right on the target
if (target === 0) return combinations.push(tracker.slice());

// overshot the target
if (target matchTarget(target, matrix));
const colCandidates = colTargets.map((target, i) =>
matchTarget(
target,
matrix.map((row) => row),
),
);

for (let y = 0; y < dimension; y++) {
for (let x = 0; x < dimension; x++) {
const rowUses = rowCandidates[y].flat().filter((n) => n === x).length;
const colUses = colCandidates[x].flat().filter((n) => n === y).length;

if (rowUses + colUses === 0) matrix[y][x] = 0;
}
}
< /code>
Однако я не уверен, как продолжить и хотел бы увидеть более эффективный метод. Какой алгоритм решить эту проблему?


Подробнее здесь: https://stackoverflow.com/questions/794 ... mn-problem