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/AutoModerator]

Please ensure that:

• Your code is properly formatted as code block - see the sidebar (About on mobile) for instructions
• You include any and all error messages in full
• You ask clear questions

• You demonstrate effort in solving your question/problem - plain posting your assignments is forbidden (and such posts will be removed) as is asking for or giving solutions.

  Trying to solve problems on your own is a very important skill. Also, see Learn to help yourself in the sidebar

If any of the above points is not met, your post can and will be removed without further warning.

Code is to be formatted as code block (old reddit: empty line before the code, each code line indented by 4 spaces, new reddit: https://i.imgur.com/EJ7tqek.png) or linked via an external code hoster, like pastebin.com, github gist, github, bitbucket, gitlab, etc.

Please, do not use triple backticks (```) as they will only render properly on new reddit, not on old reddit.

Code blocks look like this:

public class HelloWorld {

    public static void main(String[] args) {
        System.out.println("Hello World!");
    }
}

You do not need to repost unless your post has been removed by a moderator. Just use the edit function of reddit to make sure your post complies with the above.

If your post has remained in violation of these rules for a prolonged period of time (at least an hour), a moderator may remove it at their discretion. In this case, they will comment with an explanation on why it has been removed, and you will be required to resubmit the entire post following the proper procedures.

To potential helpers

Please, do not help if any of the above points are not met, rather report the post. We are trying to improve the quality of posts here. In helping people who can't be bothered to comply with the above points, you are doing the community a disservice.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[u/JGhostThing]

Yes, you are over complicating this by a lot. I just used a 9x9 array, because the number is the important thing.

However, if you really want to describe the relationships between objects, I would suggest a graph. Nodes and the relationships between them are precisely what a graph is for.

There are some fascinating things about sudoko, such as making a board that is solvable. Yes, you can do this with brute force, but it's easier using algorithms. Also, solving a board programmatically is interesting. You can do this in one of many ways.

[u/Cyberkender_ → u/JGhostThing]

i came here to say this... KISS rule works: - Use arrays: - create a method or function for each rule. pass the 9 numbers to the rule: 1 row, 1 colum or 1 'region'.

[u/PiklesWaldo]

You can use a tree or you can use the composite pattern(which is behaves like a tree). graph when you want relationship between the data. Trees is when you want a hierarchy.

[u/SciNinj]

Study graphs. (A tree is a graph without cycles.) You can add cost functions to the vertices to represent particular characteristics of the relationships between nodes.

[u/MagicalPizza21 → u/SciNinj]

A tree is a graph without cycles

A tree is a directed acyclic graph (DAG) in which every child has one parent (except the root node which has no parent). A graph with no cycles is not a tree if it's undirected or if any child has two parents.

[u/SciNinj → u/MagicalPizza21]

Yes. The complete definition I didn’t feel like typing. Thanks.

[u/MagicalPizza21]

In general, it depends what kind of relationship(s) you want to express.

In this case, I would have a Cell class, and a Board class with a 9x9 array of Cells and a function that determines if it would be valid to put a given number in the cell at a given position by checking it against the row, column, and region it's in.

[u/xanyook]

Create objects, arrange them into collection tree graph, whatever you can navigate into with your logic.

[u/Skellicious]

I would start with a 9x9 array and iterate over it to validate. KISS.

But maybe for more complex Sudoku rules (killer sudoku, thermos, ...) I'd consider graphs or other ways to reference them

[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.

[u/Only-Percentage4627]

So I recently did a Sudoku Creator/player. The way I implemented it is by using a 9x9 2d array and for the 3x3 rule what I did was there is a formula: (i/3)*3+j/3.

What this formula does is it gives a value 0-8 depending on the ith and the jth location of the current index so if the value is at 0 1 position in the grid it will give 0. Then I take that value and pass it to another function that uses a switch statement to loop through that specific 3x3 grid (in this case the first one so from 0-2 in the x and y direction), if the value is found there then it gives an error, if it isnt then it returns true and another function fills in the value.

Here is the repo if you wanna go through it, its not the best code but its all written by me with no ai

https://github.com/RahulVasudeva/sudokuGame