I thought a bunch about sudoku today.
I was thinking about how to create a sudoku solving algorithim, heres the thoughts I went through. I started by thinking of sudoku in its most simple and abstract state. No grid, just 4 tiles in a single row, each can contain 1 of 4 numbers, no repeats, all tiles start out empty.
Obviously theres no way to solve this single row sudoku puzzle. Since all the tiles start out empty, we have no information to work with. All we know it that each tile could potentially be any of the 4 numbers. In other words, each tile is in a superposition of its 4 potential values. But if we arbitrarily assign a tile a value, the other tiles lose that potential value.
Thinking about suduko puzzles with superpositions in nothing new, but I choose to apply it to a single row sudoku puzzle so I could visualize all the superpositions in a grid. Each column represents a tile, and each square in the column being filled in represents a potential value that tile could hold. A solved sudoku would be one where each tile has just 1 possible value.
Since we assigned 3 to tile B, it looks like it emptied out all squares on the table in the same row and column as it. The column in this case represents how a tile with a single value, obviously doesnt have any other potential value. The row being cleared represents how no other tile can potentially be 3 now that a 3 already exists.
At this point I started expirimenting by randomly assigning tiles initial superpositions, and trying to find ways to collapse them.
In this example, tile A is the only tile with potential to be a 4, so it must be a 4. We can see this in the table too, The top row has only one tile filled in. In addition to thinking about columns as the superposition of states each tile could be, we can also think about the rows as the superpositions of the tiles each number could be assigned to. This means that if we ever see a row with just 1 filled in square, we can collapse its super position, clearing out the corosponding column (and visa versa).
Next I started thinking about grouping tiles together. At this point, its best to stop thinking of thing in terms of sudoku, and intead think purely in terms of a table (where the goal is to have each row/column have jsut 1 filled square). In this example, the first 2 tiles have the same 2 possible states.
We can imagine “grouping” these grid squares, having them act like one big square. This 2×2 group represents 2 tiles, each with 2 potential values. We dont know which tile will get which value, but we know both values will be assigned to one of the two. This means that no other tiles can hold these values, clearing out the rows of the group.
This works just like how if a grid square is the only filled square in its column, its row gets cleared out. Grouped tiles can be though of as a set of rows and colums, if all the groups colums are clear, we can clear of that groups rows. (Groups dont have to be adjacent, they can be defined by where any set of columns and rows intersect).
This only works because the rest columns of the groups were empty, what if they’re not? If we go back to the previous example, and fill in a square above the tiles we grouped, we’ll have to increase the group demensions to include this new square.
This 2×3 group represents 2 tiles, each with 3 possibilities. In other words, of 3 possible values, at least 2 of them will be in this group. We can actualy divid a large group into a smaller group, but we have to 3:2 ratio with it. If we cut off a row from the 2×3 group, we get a 2×2 group with a 2:1 ratio, meaning of 2 possible values, at least 1 of the will be in this group. We cannot use this group to clear rows because the ratio is uneven.
We can define any group as some set of rows and columns. The left side of its ratio is the number of rows, while the right side can be found by looking at all the rows not in the group. Start by taking the number of columns, and for each row that has a filled square in a column thats part of the group, subtract 1, the resulting number is the right side of the ratio. (Everything involving rows and columns also goes visa versa)
At first it doesnt seem like we can do anthing with groups with uneven ratios, since we can only use them to clear rows if the number of possible values matches the number of values guarenteed to be in that group. But we can add groups together to produce new groups with useful ratios. (I’ve upgraded to a 6×6 grid to demonstrate better)
In this example, we have a 2×2 group with a 2:1 ratio, and a 1×2 with a 2:1 ratio. Since their rows line up, we can combine them into a single 3×2 group with 2:2 ratio. Ever though the group isnt square, its ratio is even, so we can clear rows with it.
It’s not super clear how useful this group division + addition thing is, since usually the process can be done with a larger square group, but its still cool. Everything has been very far abstracted from sudoku, but the fact we can even represent sudoku in this way is cool too. Thats everthing I’ve done today, I’ma think about this more later.