Как составить сетку слов, похожую на кроссворд, с интервалами между непересекающимися словами? ⇐ Javascript

[Anonymous]

Я реализую сетку слов, похожую на кроссворд, где слова располагаются горизонтально и вертикально и могут пересекаться.
Моя текущая реализация помещает все ячейки в компактную прямоугольную сетку, в результате чего множество соседних ячеек принадлежат разным словам. Это делает макет плотным и визуально загроможденным.
Что я хочу вместо этого:

• Каждое слово при размещении должно оставлять место на всю его длину.
• Слова, которые не пересекаются, должны быть разделены хотя бы одной пустой ячейкой сетки со всех сторон.
• Ячейки могут соприкасаться только, если:
  
  они принадлежат одному и тому же слову (одной строке или столбцу) или
• они пересекаются в допустимой пересекающейся ячейке.

[*]Не следует отображать ячейки-заполнители — только ячейки, которые принадлежат реальным словам.

[*]Результат должен выглядеть как отдельные блоки слов, а не заполненная матрица.


Я прикрепил два изображения:
желаемый разреженный макет с правильным интервалом:


текущий компактный макет (неверно):


Вопрос:

Что такое правильный алгоритм или структуру данных для создания такого разреженного макета кроссворда с обязательными правилами размещения между непересекающимися словами?
Если возможно, меня интересуют:

• рекомендуемое представление сетки,
• логика размещения/проверки
• или ссылки на известные алгоритмы макета кроссворда, поддерживающие ограничения интервала

// For each cell the word would occupy, check all four adjacent cells
for (let i = 0; i < word.length; i++) {
let cellNo = direction === "horizontal" ? startCell + i : startCell + i * 10;
let blocksHere = getBlocksAtCellNo(cellNo);
let isIntersection =
blocksHere.length > 0 && blocksHere[0].innerHTML.toLowerCase() === word;
// Check above
if (cellNo - 10 >= 0) {
let above = getBlocksAtCellNo(cellNo - 10);
if (above.length > 0) {
// Allow only if this is a vertical word and above is part of the same word (continuation) or a valid intersection
if (!(direction === "vertical" && i > 0) && !isIntersection) return false;
}
}
// Check below
if (cellNo + 10 0) {
if (!(direction === "vertical" && i < word.length - 1) && !isIntersection)
return false;
}
}
// Check left
if (cellNo % 10 > 0) {
let left = getBlocksAtCellNo(cellNo - 1);
if (left.length > 0) {
if (!(direction === "horizontal" && i > 0) && !isIntersection)
return false;
}
}
// Check right
if (cellNo % 10 < 9) {
let right = getBlocksAtCellNo(cellNo + 1);
if (right.length > 0) {
if (
!(direction === "horizontal" && i < word.length - 1) &&
!isIntersection
)
return false;
}
}
}
// Check cell before and after the word (in the word's direction)
if (direction === "horizontal") {
// Before
if (startCell % 10 > 0) {
let beforeCell = startCell - 1;
if (getBlocksAtCellNo(beforeCell).length > 0) return false;
}
// After
let afterCell = startCell + word.length;
if (afterCell % 10 < 10 && afterCell 0) return false;
}
} else {
// Before
if (startCell - 10 >= 0) {
let beforeCell = startCell - 10;
if (getBlocksAtCellNo(beforeCell).length > 0) return false;
}
// After
let afterCell = startCell + word.length * 10;
if (afterCell 0) return false;
}
}
return true;



Подробнее здесь: https://stackoverflow.com/questions/798 ... rsecting-w