Блог

Я работаю над проектом, который решает судоку. Это часть моего университетского модуля, и пока я планировал свой подход к нему, я хотел попробовать использовать приоритетную очередь, чтобы решить, с какой ячейкой работать в судоку дальше.

Что я должен хранить в очереди приоритетов?

Я думал, что мог бы сохранить ячейку (например, grid [x] [y]), однако это сложная часть. Я определяю приоритет для ячейки в определенном местоположении по количеству возможных комбинаций, которые могут входить в ячейку. Но у меня нет способа сохранить количество комбинаций в каждой ячейке, поэтому я подумал об использовании типа данных карты для хранения местоположения сетки в качестве ключа и возможных комбинаций в качестве значения. Тогда я собирался использовать приоритетную очередь этих значений, и эти значения укажут мне местоположение сетки.

Я не очень разбираюсь в Java или структурах данных, но мне очень понравилось думать об этом подходе. Любая помощь будет очень признательна!

Поскольку вы не опубликовали код, я не могу прокомментировать, является ли это лучшим подходом. Но ответ на ваш вопрос — да.

Позвольте мне сначала кратко изложить, чего (я понимаю) вы хотите достичь: У вас есть пара объектов (ячейки сетки или их координаты). У вас также есть карта, которая присваивает приоритет каждому из этих объектов. Теперь вы хотите установить приоритетную очередь, которая упорядочивает объекты на основе приоритета на карте.

Это возможно путем подачи пользовательского Comparator в очередь приоритетов. Компаратор обращается к объектам (в нашем случае к двум ячейкам сетки) и возвращает, какая из двух меньше (или в концепции приоритетных очередей, которая идет первой). Нашему специальному компаратору потребуется доступ к Map с количеством комбинаций. Как только у него будет этот доступ, сравнить два GridCell s довольно просто. Вот сопоставитель:

 class GridCellComparer implements Comparator<GridCell> {
    
    // reference to the map with the number of combinations for each grid cell
    Map<GridCell, Integer> combinations;
    
    public GridCellComparer(Map<GridCell, Integer> combinations) {
        this.combinations = combinations;
    }
    
    // calculate which grid cell comes first
    public int compare(GridCell c1, GridCell c2) {
        return combinations.get(c2) - combinations.get(c1);
    }
}
  

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

 PriorityQueue<GridCell> prio = new PriorityQueue<GridCell>(cells.size(), new GridCellComparer(combinations));
  

Остальное работает как с любой другой приоритетной очередью. Вы добавляете ячейки сетки и так далее. Вот полный пример. Первая часть кода генерирует несколько ячеек сетки и задает для них ряд комбинаций. Ячейка int n внутри сетки используется только для их идентификации при их печати.

 import java.util.Map;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Comparator;

public class Example {

     public static void main(String []args){
        
        // map with the number of combinations for each cell
        Map<GridCell, Integer> combinations = new HashMap<GridCell, Integer>();
        
        // list of grid cells
        List<GridCell> cells = new ArrayList<GridCell>();
        for(int i = 0; i < 5;   i)
            cells.add(new GridCell(i));
        
        // add number of combinations for each grid cell
        combinations.put(cells.get(0), 2);
        combinations.put(cells.get(1), 0);
        combinations.put(cells.get(2), 6);
        combinations.put(cells.get(3), 4);
        combinations.put(cells.get(4), 10);
        
        // instantiate the priority queue
        PriorityQueue<GridCell> prio = new PriorityQueue<GridCell>(cells.size(), new GridCellComparer(combinations));
        prio.addAll(cells);
        
        // retrieve the grid cells in the order imposed by the number of combinations
        while(!prio.isEmpty()) {
            GridCell topCell = prio.poll();
            System.out.println(topCell);
        }
     }
}

class GridCell{
    
    // number to identify the cell
    private int n;
    
    public GridCell(int n) { this.n = n; }
    
    public String toString(){
        return Integer.toString(n);
    }
}

class GridCellComparer implements Comparator<GridCell> {
    
    // reference to the map with the number of combinations for each grid cell
    Map<GridCell, Integer> combinations;
    
    public GridCellComparer(Map<GridCell, Integer> combinations) {
        this.combinations = combinations;
    }
    
    // calculate which grid cell comes first
    public int compare(GridCell c1, GridCell c2) {
        return combinations.get(c2) - combinations.get(c1);
    }
}
  

Когда вы запустите этот код, вы увидите следующий вывод:

 4
2
3
0
1
  

Это идентификаторы ячеек сетки, упорядоченные от большого количества комбинаций до низкого.