поменяй метод backtrackingSearch на метод решения через имитацию отжига.
вот мои файлы:
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;

public class Rectangle {
    private final String name;
    private final int height;
    private final int width;

    public Rectangle(String name, int height, int width) {
        this.name = name;
        this.height = height;
        this.width = width;
    }

    public String getName() {
        return name;
    }

    public int getHeight() {
        return height;
    }

    public int getWidth() {
        return width;
    }
}

4 файл:
package plata_kniga;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Collection;
import java.util.HashSet;
import java.util.stream.Collectors;
import plata_kniga.RectangleGrid.GridLocation;

public class RectangleConstraint extends Constraint<Rectangle, List<GridLocation>> {
    public RectangleConstraint(List<Rectangle> rectangles) {
        super(rectangles);
    }

    @Override
    public boolean satisfied(Map<Rectangle, List<GridLocation>> assignment) {
        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) {
        RectangleGrid grid = new RectangleGrid(9, 9);
        List<Rectangle> rectangles = List.of(
                new Rectangle("Rect1", 3, 2),
                new Rectangle("Rect2", 2, 3),
                new Rectangle("Rect3", 1, 4),
                new Rectangle("4", 6, 2)
        );

        Map<Rectangle, List<List<GridLocation>>> domains = new HashMap<>();
        for (Rectangle rectangle : rectangles) {
            domains.put(rectangle, grid.generateDomain(rectangle.getHeight(), rectangle.getWidth()));
        }

        CSP<Rectangle, List<GridLocation>> csp = new CSP<>(rectangles, domains);
        csp.addConstraint(new RectangleConstraint(rectangles));
        Map<Rectangle, List<GridLocation>> solution = csp.backtrackingSearch();

        if (solution == null) {
            System.out.println("No solution found!");
        } else {
            int index = 65;

            for (Map.Entry<Rectangle, List<GridLocation>> entry : solution.entrySet()) {
                grid.markRectangle(entry.getValue(), (char)index);
                index++;
            }
            System.out.println(grid);
        }
    }
}

5 файл:
package plata_kniga;

import java.util.ArrayList;
import java.util.List;

public class RectangleGrid {
    public static class GridLocation {
        public final int row, column;

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

        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + column;
            result = prime * result + row;
            return result;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (obj == null || getClass() != obj.getClass()) return false;
            GridLocation other = (GridLocation) obj;
            return column == other.column && row == other.row;
        }
    }

    private final int rows, columns;
    private char[][] grid;

    public RectangleGrid(int rows, int columns) {
        this.rows = rows;
        this.columns = columns;
        grid = new char[rows][columns];
        for (int row = 0; row < rows; row++) {
            for (int column = 0; column < columns; column++) {
                grid[row][column] = '.';
            }
        }
    }

    public void markRectangle(List<GridLocation> locations, char symbol) {
        for (GridLocation location : locations) {
            grid[location.row][location.column] = symbol;
        }
    }

    @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(int height, int width) {
        List<List<GridLocation>> domain = new ArrayList<>();
        for (int row = 0; row <= rows - height; row++) {
            for (int column = 0; column <= columns - width; column++) {
                List<GridLocation> locations = new ArrayList<>();
                for (int r = 0; r < height; r++) {
                    for (int c = 0; c < width; c++) {
                        locations.add(new GridLocation(row + r, column + c));
                    }
                }
                domain.add(locations);
            }
        }
        return domain;
    }
}