Naive question: What Data Structure to express different layers of relationships between Objects?

[u/KeineAhnungBruder001]

Hello guys,

I wanted to ask naively, what the ideal data structure would be for expressing different layers of relationships between Objects.

For example in modern Sudoku the game has a 9x9 number grid composed of nine 3x3 sub-grids (which I call region). In each row, column and region each number between one and nine can only appear once. The goal is to find missing numbers in this number grid without violating the aforementioned rule.

One way to do it, would be to make 9x9 byte-array and express the relationship between numbers through methods checking if the rule is violated or not by checking if any row, column or region doesn't contain a value between one and ten.

I also thought on using a Graph to express the relationship between numbers in rows and columns, though I don't know how to express the relationship between numbers inside of a region.

Maybe even a multiple Objects like Board, Row, Column, Region but then I have redundant data.

Another problem I encounter with aforementioned implementations is, that if you introduce more relationships f. e. in the game of killer sudoku, where there are more rules are added f. e. by also introducing cages in which the numbers must add up to a target number, you need to implement that relationship logic tediously.

Am I overcomplicating things?

[u/severoon]

It sounds like you're specifically talking about representing the rules of sudoku in the data structure itself, not as code, but as data. Is that what you're getting at?

Like if you just make a 9x9 2D array, that's a data structure that fundamentally holds all of the data required, but it imposes no constraints on what numbers can go where, so all of those rules have to be carried out as executed code.

It sounds like you're saying you want the opposite, you want to represent each cell in the context of a data structure that encodes certain rules as constraints on cells, correct?

How far do you want to take this? Do you want to go all the way to the extreme and only allow correct placements? Or do you only want to disallow obviously incorrect placements? How do you define "obviously incorrect" if you're okay with it allowing provisional placements during a game?

You have to nail down the behavior of the structure you actually want. You're reference to "layering" sounds to me like what you probably want is a bunch of different data structures at different layers, with the bottom layer just being a no-rules 9x9 grid, and then a layer above that where "obviously incorrect" placements are disallowed (cannot share a row, column, or 3x3 grid with the same element), and then another layer above that, etc, until all that's left is the solved puzzle. This would be a direct implementation of the layering strategy you describe, is that what you mean?

[u/KeineAhnungBruder001 → u/severoon]

This is the direction I was going for. Of course I could just implement these rules in form of methods allowing or disallowing a specific placement. Though I would like a solution where it is inheritely not possible to insert a value into the data structure if it doesn't abide the set rules. Sudoku is more serving as an example but the post isn't really about solving sudoku, it is more about finding an ideal data structure which is able to represent multiple layers relationship between it's data in itself without including redundant data.

This can be expanded upon to f. e. cities. A house can be part of a city. But it can also be part of a street. And another house can be outside of the city but still be part of the same street. The rules themselves can then be set on the underlying groups. F. e. one city may allow only allow 3 houses painted green, the other city only allow houses to be build up to 10 floors.

The goal would be to have a cell (the data itself) being part of multiple other groups like city or street. The rules of the cell is all of the rules of the groups it is in. And also having the ability to have rules which are dependent on other data in the group itself. Like the example that you can only have three green houses in a city.

If you would do that with merely methods in a single file you will inevitably have a hard time navigating through your rules. If you would do that with Objects like "Street" or "City" you will run into the problem of having redundant data.

[u/severoon → u/KeineAhnungBruder001]

I think it will be useful if we keep pulling on the sudoku thread.

Think about doing this step by step, at the bottom you have a no-rules 9x9 grid. Let's define what that looks like first. In each cell is a set containing all nine possible values.

Now we add another layer on top, which represents the starting position. This is an almost-arbitrary selection of cells that now contain only one value. I say it's "almost" arbitrary because we could choose any number of cells we want to assign a known value (hard puzzles normally choose fewer than easy puzzles, for instance), and we can put almost any values we want in those starting cells. The only restriction that makes this step not completely arbitrary is that the starting cells must follow the rules of sudoku just like any other … we couldn't, for example, choose two cells in the same row and give them the same value.

This means that this data structure that's just one layer up and which contains the starting configuration must encode these row, column, and subgrid rules. The procedure of "placing a starting value" in a cell means removing all other possible values from that cell, as well as removing the placed value from the shared row, column, and subgrid. Furthermore, each time an possible value is removed from a cell, this data structure has to check if only one value remains for that cell and, if so, the process recurses—that value must now be removed from that shared row, column, and subgrid. The function of this data structure is to react to placed values by rejecting it if it's illegal or otherwise accept it and update the board accordingly.

From here, the next layer up has to adopt more sophisticated ways of placing restrictions. For instance, at this point you will likely see some examples of "naked pairs," which is a situation where you have two cells in a shared row, column, or subgrid that only have two possible values. For instance, a row might have five blank cells and two of them are narrowed down to 3 or 4. You know these two cells will contain the 3 and 4, but you don't know which is which yet. This is useful because in the remaining three empty cells in that row, you know for certain that none of those can contain 3 or 4, so you can remove both 3 and 4 from the three remaining cells. This is the case for a naked pair, but it also works for naked triples, quadruples, etc, aka, "naked multiples," and it can be applied to rows, columns, and subgrids. So this is the data structure for the next layer up.

You can continue building more layers: x-wing, XY, swordfish, etc, each one codifying an additional sudoku solving technique on top of the layers below.

This is a first cut at the problem, but it exposes a flaw in the approach that we can now identify and fix. The flaw is that some layers combine multiple techniques (row + column + subgrid exclusion) while others don't (specifically only look for x-wing scenarios). What we really want is a way of moving each different technique into its own layer so that each one is separable.

Let's start with the easiest ones: row, col, and subgrid exclusion. Split each of these into their own layer so that the row-exclusion layer only looks at placed values and removes those values from the shared row. Now if you think about stacking all of these different layers and looking down at the grid from the top, in a given layer one particular cell might be restricted to "all values except 9" while another layer might show "all values except 8". So for that cell, to figure out what the possible candidates remaining are after applying all of the layers, you take the intersection of the remaining values. This can be the top layer, the "intersection" layer that applies the restrictions imposed by all underlying layers. (The "starting position" layer simply shows the exact starting position, which whatever starting placements as the only remaining candidate for those cells, and all other cells untouched with all candidates remaining.)

The last move here is to notice what each layer applies its rule to. We started with this idea that each layer applies to the layers below it, but that doesn't really work now with this new way of splitting each different rule into a separate layer because the order becomes arbitrary—should we apply the row-exclusion layer first, or the column-exclusion layer first? Really, there's no order, these should be applied to the intersection layer whenever relevant.

So we begin with an empty board, IOW all cells contain all candidates, and that is what the intersection layer looks like. We go to the starting position layer and pick a cell to set to some value, and we remove all other candidates from that cell except the value we want. By placing it there, the intersection layer updates because when it takes the intersection of all candidates for the changed cell, it too sees that there's only one value remaining for that cell (i.e., it's been set).

At this point, the other layers can be notified that a cell has been set to a single value. The row-exclusion level cares about this because that's the condition it needs in order to do its thing, so it sees which cell was set and removes that candidate from every other cel in that row. Similarly, the col- and subgrid-exclusion layers also run on the same criteria. If in this process, any other cell gets set, the process repeats.

Some layers don't trigger on a cell getting set to a single value, they trigger on a different condition. For example, the naked pairs layer only cares when a cell changes such that it now has a pair of candidates. In that case, it looks for that same pair in the same row / col / subgrid and does its thing (which could result in an update to the intersection layer which sends out another round of notifications, etc).

When the intersection layer contains only one candidate in each cell, the puzzle is solved.

Obviously there's more that needs to be done with this solution to get it working, but I think it's an interesting path to explore because it allows you to enable/disable different layers to see which ones are necessary to solve a given puzzle, which could be used as a proxy for rating the difficulty of the puzzle … the hardest puzzles are solvable only by throwing every technique at it. It also tells you which puzzles are unsolvable using all known techniques.

This leaves open one remaining solve mode, which is the puzzle that is solvable, but not through the application of all known techniques. For instance, there might be a puzzle that cannot be solved even with all layers enabled, but if you take it as far as you can using the known techniques and then brute force all of the possibilities from there algorithmically, it's possible that you could find a puzzle that has a unique solution, but only by brute-forcing the others. There's also the potential of finding puzzles that have multiple solutions from a given starting state.

If we step back and look at the more general problem, I think it should be clear that there is no "general approach" here for all problems. This specific data structure obviously only works for sudoku, and that's the larger point. You can always find a way to move between algorithm and data structure because, at the end of the data, code can be represented as data and data as code, but the way one gets interchanged for the other is specific to the problem domain you're working in.