I am working on a project that solves sudokus. It is part of my university module and while I have been planning my approach to it I wanted to try using a priority queue to decide which cell to work on in the sudoku next.
What should I store in the priority queue?
I was thinking I could store the cell (e.g grid[x][y]), however, this is the tricky part. I work out a priority for a cell at a certain location by the number of possible combinations that can go into the cell. But I have no way to store how many combinations each cell has so I was thinking of using a map data type to store the grid location as the key and the possible combinations as the value. Then I was gonna use a priority queue of these values and these values would point me to the grid location.
I am not that experienced with Java or data structures, but I really liked thinking of this approach. Any help will be really appreciated!
Since you haven't posted code, I cannot comment on if this is the best approach. But the answer to your question is yes.
Let me first summarize what (I understand) you want to achieve: You have a couple of objects (the grid cells or their coordinates). You also have a map that assigns a priority to each of these objects. You now want to establish a priority queue that orders the objects based on the priority in the map.
This is possible by feeding a custom Comparator to the priority queue. The comparator takes to objects (in our case, two grid cells) and returns which of the two is smaller (or in the concept of priority queues, which comes first). Our special comparator will need access to the Map with the number of combinations. Once it has this access, comparing two GridCells is pretty easy. Here is the comaprator:
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);
}
}
To use this comparator, we need to use the constructor overload of PriorityQueue that takes a Comparator. This overload also takes the initial capacity, which we can set to the number of cells we want to add:
PriorityQueue<GridCell> prio = new PriorityQueue<GridCell>(cells.size(), new GridCellComparer(combinations));
The rest works as with any other priority queue. You add grid cells and so on. Here is a complete example. The first part of the code generates a few grid cells and sets a number of combinations for them. The int n inside the grid cell is only used to identify them when printing them.
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);
}
}
When you run this code, you will see the following output:
4
2
3
0
1
These are the GridCell ids ordered from high number of combinations to low.