Переделай на расстановку прямоугольников внутри поля
1 файл:
package plata_kniga;

import java.util.List;
import java.util.Map;
// V — тип переменной, D — тип домена.
public abstract class Constraint<V, D> {
    // Переменные, для которых существует ограничение
    protected List<V> variables;
    public Constraint(List<V> variables) {
        this.variables = variables;
    }
    // Необходимо переопределить в подклассах
    public abstract boolean satisfied(Map<V, D> assignment);
}

2 файл:
package plata_kniga;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class CSP<V, D> {
    private List<V> variables;
    private Map<V, List<D>> domains;
    private Map<V, List<Constraint<V, D>>> constraints = new HashMap<>();
    public CSP(List<V> variables, Map<V, List<D>> domains) {
        this.variables = variables;
        this.domains = domains;
        for (V variable : variables) {
            constraints.put(variable, new ArrayList<>());
            if (!domains.containsKey(variable)) {
                throw new IllegalArgumentException("Every variable should have a domain assigned to it.");
            }
        }
    }
    public void addConstraint(Constraint<V, D> constraint) {
        for (V variable : constraint.variables) {
            if (!variables.contains(variable)) {
                throw new IllegalArgumentException("Variable in constraint not in CSP");
            }
            constraints.get(variable).add(constraint);
        }
    }
    // Проверяем, соответствует ли присваивание значения,
    // проверяя все ограничения для данной переменной
    public boolean consistent(V variable, Map<V, D> assignment) {
        for (Constraint<V, D> constraint : constraints.get(variable)) {
            if (!constraint.satisfied(assignment)) {
                return false;
            }
        }
        return true;
    }
    public Map<V, D> backtrackingSearch(Map<V, D> assignment) {
        // присваивание завершено, если существует присваивание
        // для каждой переменной (базовый случай)
        if (assignment.size() == variables.size()) {
            return assignment;
        }
        // получить все переменные из CSP, но не из присваивания
        V unassigned = variables.stream().filter(v ->
                !assignment.containsKey(v)).findFirst().get();
        // получить все возможные значения области определения
        // для первой переменной без присваивания
        for (D value : domains.get(unassigned)) {
            // мелкая копия присваивания, которую мы можем изменить
            Map<V, D> localAssignment = new HashMap<>(assignment);
            localAssignment.put(unassigned, value);
            // если нет противоречий, продолжаем рекурсию
            if (consistent(unassigned, localAssignment)) {
                Map<V, D> result = backtrackingSearch(localAssignment);
                // если результат не найден, заканчиваем возвраты
                if (result != null) {
                    return result;
                }
            }

        }
        return null;
    }
    // вспомогательный класс функции backtrackingSearch
    public Map<V, D> backtrackingSearch() {
        return backtrackingSearch(new HashMap<>());
    }
}

3 файл:
package plata_kniga;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class WordGrid {
    public static class GridLocation {
        public final int row, column;

        public GridLocation(int row, int column) {
            this.row = row;
            this.column = column;
        }

        // автоматическое создание Eclipse
        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + column;
            result = prime * result + row;
            return result;
        }

        // автоматическое создание Eclipse
        @Override
        public boolean equals(Object obj) {
            if (this == obj) {
                return true;
            }
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            GridLocation other = (GridLocation) obj;
            if (column != other.column) {
                return false;
            }
            if (row != other.row) {
                return false;
            }
            return true;
        }
    }

    private final char ALPHABET_LENGTH = 26;
    private final char FIRST_LETTER = 'A';
    private final int rows, columns;
    private char[][] grid;

    public WordGrid(int rows, int columns) {
        this.rows = rows;
        this.columns = columns;
        grid = new char[rows][columns];
        // инициализируем сетку случайными буквами
        Random random = new Random();
        for (int row = 0; row < rows; row++) {
            for (int column = 0; column < columns; column++) {
                char randomLetter = (char) (random.nextInt(ALPHABET_LENGTH)
                        + FIRST_LETTER);
                grid[row][column] = randomLetter;
            }
        }
    }

    public void mark(String word, List<GridLocation> locations) {
        for (int i = 0; i < word.length(); i++) {
            GridLocation location = locations.get(i);
            grid[location.row][location.column] = word.charAt(i);
        }
    }

    // получаем красивую печатную версию сетки
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (char[] rowArray : grid) {
            sb.append(rowArray);
            sb.append(System.lineSeparator());
        }
        return sb.toString();
    }

    public List<List<GridLocation>> generateDomain(String word) {
        List<List<GridLocation>> domain = new ArrayList<>();
        int length = word.length();
        for (int row = 0; row < rows; row++) {
            for (int column = 0; column < columns; column++) {
                if (column + length <= columns) {
                    // слева направо
                    fillRight(domain, row, column, length);
                }
                if (row + length <= rows) {
                    // сверху вниз
                    fillDown(domain, row, column, length);
                }
            }
        }
        return domain;
    }

    private void fillRight(List<List<GridLocation>> domain,
                           int row, int column, int length) {
        List<GridLocation> locations = new ArrayList<>();
        for (int c = column; c < (column + length); c++) {
            locations.add(new GridLocation(row, c));
        }
        domain.add(locations);
    }

    private void fillDown(List<List<GridLocation>> domain, int row,
                          int column, int length) {
        List<GridLocation> locations = new ArrayList<>();
        for (int r = row; r < (row + length); r++) {
            locations.add(new GridLocation(r, column));
        }
        domain.add(locations);
    }
}

4 файл:
package plata_kniga;

import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Random;
import java.util.Set;
import java.util.stream.Collectors;
import plata_kniga.WordGrid.GridLocation;

public class WordSearchConstraint extends Constraint<String, List<GridLocation>> {
    public WordSearchConstraint(List<String> words) {
        super(words);
    }
    @Override
    public boolean satisfied(Map<String, List<GridLocation>> assignment) {
        // объединение всех GridLocations в один огромный список
        List<GridLocation> allLocations = assignment.values().stream()
                .flatMap(Collection::stream).collect(Collectors.toList());
        // наличие дубликатов положений сетки означает наличие совпадения
        Set<GridLocation> allLocationsSet = new HashSet<>(allLocations);
        // если какие-либо повторяющиеся местоположения сетки найдены,
        // значит, есть перекрытие
        return allLocations.size() == allLocationsSet.size();
    }
    public static void main(String[] args) {
        WordGrid grid = new WordGrid(9, 9);
        List<String> words = List.of("MATTHEW", "JOE", "MARY", "SARAH", "SALLY");
        // генерация доменов для всех слов
        Map<String, List<List<GridLocation>>> domains = new HashMap<>();
        for (String word : words) {
            domains.put(word, grid.generateDomain(word));
        }
        CSP<String, List<GridLocation>> csp = new CSP<>(words, domains);
        csp.addConstraint(new WordSearchConstraint(words));
        Map<String, List<GridLocation>> solution = csp.backtrackingSearch();
        if (solution == null) {
            System.out.println("No solution found!");
        } else {
            Random random = new Random();
            for (Entry<String, List<GridLocation>> item : solution.entrySet()) {
                String word = item.getKey();
                List<GridLocation> locations = item.getValue();
                // в половине случаев случайным выбором — задом наперед
                if (random.nextBoolean()) {
                    Collections.reverse(locations);
                }
                grid.mark(word, locations);
            }
            System.out.println(grid);
        }
    }
}