Constructing a minimal Sudoku puzzle

[Deozaan]

Hi all,

I've been working on programming a Sudoku game and I've run into a problem with my code that I've been unable to solve for the past few days and realize I need some fresh eyes on the problem. This may not be the best place to ask about this, but as best as I can tell this problem requires a bit of an in-depth explanation and I don't really feel comfortable asking on other sites that may be more closely aligned with the specific area of inquiry, but where I have not really established myself as part of the community. And maybe it could be asked more succinctly, but unfortunately for anyone who reads this, I tend to be overly verbose in an effort to make sure I'm explaining myself clearly. So here goes.

First of all, I assume the reader is familiar with Sudoku puzzles and understands the basic rules. But I figure I should establish some Sudoku terminology (mostly from Peter Norvig), so we're all speaking the same language here.

Square: A place where a number goes. A Sudoku puzzle is made up of 81 squares arranged in a 9x9 grid.
Row: Nine squares arranged horizontally (9x1), in which the numbers 1 through 9 can only appear once.
Column: Nine squares arranged vertically (1x9), in which the numbers 1 through 9 can only appear once.
Box: Nine squares arranged in a 3x3 grid, in which the numbers 1 through 9 can only appear once.
Unit: Any nine squares that compose a row, column, or box. Each square is a member of exactly 3 units.
Peers: Any squares that share a unit are considered peers. Each square has exactly 20 peers.
Given: The "freebie" clues that are known at the start of the puzzle.
Minimal Puzzle: A Sudoku puzzle that has the fewest amount of givens possible, while still only having one unique solution.

And here's a crude diagram showing a minimal puzzle with some of the above terminology highlighted:

Constructing a minimal Sudoku puzzle

So what I'm trying to accomplish is making a game that can generate an infinite number of Sudoku puzzles (well, as many of the 6,670,903,752,021,072,936,960 possible puzzles as a player might want/be able to play). It turns out that generating solutions is easy. You can sort of just make it up as you go along. The part I'm having trouble with is going from the solution to the minimal puzzle.

In other words, in order to present the player with a puzzle to solve, I want to go from something like what's on the left to something like what's on the right:

Code: Text [Select]

1. 1 2 7 | 4 5 8 | 3 6 9     . . . | . . . | . 6 .
2. 5 3 9 | 6 7 2 | 1 8 4     . 3 . | . . 2 | . . .
3. 6 4 8 | 9 3 1 | 7 2 5     . . . | . 3 . | . . .
4. ------+-------+------     ------+-------+------
5. 3 1 5 | 7 8 6 | 4 9 2     . . . | 7 . 6 | . . .
6. 4 8 2 | 3 1 9 | 6 5 7     . 8 2 | . 1 . | . . .
7. 9 7 6 | 2 4 5 | 8 3 1     9 . 6 | . 4 . | . . .
8. ------+-------+------     ------+-------+------
9. 8 9 4 | 5 6 7 | 2 1 3     8 9 4 | 5 . 7 | . . 3
10. 2 6 3 | 1 9 4 | 5 7 8     . . . | 1 . . | 5 7 8
11. 7 5 1 | 8 2 3 | 9 4 6     . 5 . | . . . | . . .

I've written code that accomplishes it. In fact, the above puzzle was generated by my code. But it's far too slow, and unpredictably so, to be useful in a real-time game. Sometimes it only takes a couple of seconds to generate a puzzle, which in itself is too slow. But other times it takes up to a few minutes. And in a few cases it has taken so long that I've been too impatient to let it finish. I'm coding this in GDScript, which is a custom language created for Godot, but which is very similar to Python.

I'm storing the solution of the 9x9 grid in a special kind of one-dimensional array in GDScript called a PoolIntArray, which is passed by value instead of reference. It would look like this as a traditional array:

Code: Python [Select]

1. var answer := [
2.         1, 2, 7, 4, 5, 8, 3, 6, 9,
3.         5, 3, 9, 6, 7, 2, 1, 8, 4,
4.         6, 4, 8, 9, 3, 1, 7, 2, 5,
5.         3, 1, 5, 7, 8, 6, 4, 9, 2,
6.         4, 8, 2, 3, 1, 9, 6, 5, 7,
7.         9, 7, 6, 2, 4, 5, 8, 3, 1,
8.         8, 9, 4, 5, 6, 7, 2, 1, 3,
9.         2, 6, 3, 1, 9, 4, 5, 7, 8,
10.         7, 5, 1, 8, 2, 3, 9, 4, 6,
11. ]

I also have a similar array of booleans, called "givens" which indicates if a particular square is a given or not.

I then follow a method I read about in a paper called Sudoku Puzzles Generating: from Easy to Evil (link to archive, since original link is dead) which the authors refer to as "digging holes" in the puzzle, and offer this flowchart as part of their explanation:

Constructing a minimal Sudoku puzzle

I'll summarize my understanding and (attempted) implementation as follows:

• Order a list of all the squares to "dig" however you see fit. (I just shuffle an array of all the squares)
• For each square in the list, attempt to dig the known value N. This means to set the value as "unknown" or "empty" (represented internally by the number 0).
• With the newly dug square, attempt to solve the puzzle with all possible values (1-9) other than N.
• If you find a solution, it means the puzzle is no longer unique (it has multiple solutions), so the square is considered a given and must display the value N to maintain uniqueness.
• If you don't find a solution, the square can remain "dug" and you continue iterating the list to dig more holes.
• Once you've iterated the entire list, you should have dug out all squares that are not essential to maintaining the uniqueness of the puzzle, which results in a minimal puzzle.

Here's the code which I think does what I described above:

Code: Python [Select]

1. # digs a solved grid to find a minimal puzzle
2. func find_givens() -> void:
3.         # make a list of all 81 indices of the grid
4.         var dig_list := []
5.         for idx in 81:
6.                 dig_list.push_back(idx) # push_back() just adds elements to the end of an array
7.         # randomize the order of squares we "dig"
8.         dig_list.shuffle()
9.         # prepare some variables we'll be using repeatedly
10.         var nums = answer # grab a copy of the answer so we don't make changes to it
11.         var v : int # temporarily stores the "dug" value in case we need to replace it
12.         var coords := Vector2() # x,y coordinates
13.         # iterate the randomized list
14.         for i in dig_list:
15.                 # don't attempt to dig a square that is known to be a given
16.                 if given[i] == true:
17.                         # sanity check: this code should never actually be reached
18.                         continue
19.                 # store the current value of the digit
20.                 v = nums[i]
21.                 for n in range(1, 10): # iterate the numbers 1-9
22.                         # skip if this is the square's original value
23.                         if n == v:
24.                                 continue
25.                         # dig the value and try finding other solutions
26.                         nums[i] = 0
27.                         # get the (x, y) coords for this square
28.                         coords = index_to_coord(i) # convert the index (0-80) to x,y coordinates as if on a 9x9 grid
29.                         # change the value at this square to something else, if possible
30.                         if is_possible(nums, coords.y, coords.x, n):
31.                                 # N could legally be placed in this square
32.                                 nums[i] = n
33.                                 # try to find a solution to the puzzle with this new value in this square
34.                                 if solve(nums) > 0:
35.                                         # we found a solutions, which means the puzzle is no longer unique
36.                                         # so put the value back
37.                                         nums[i] = v
38.                                         # mark this square as a given
39.                                         given[i] = true
40.                                         # don't attempt further numbers for this square
41.                                         break

And here's the code for the if_possible() function, which is used to determine if a value n could legally be placed in the square located at (x,y) in a 9x9 grid. Or in other words, it makes sure that no other peer of the square (x,y) has the value n:

Code: Python [Select]

1. # returns true if no peers have the value n
2. func is_possible(grid, y : int, x : int, n : int) -> bool:
3.         for i in 9:
4.                 # check if n already exists in current row (9x1)
5.                 if grid[coord_to_index(y, i)] == n:
6.                         return false
7.                 # check if n already exists in current column (1x9)
8.                 if grid[coord_to_index(i, x)] == n:
9.                         return false
10.         # integer math here means (5 / 3) * 3 is the same as 1 * 3
11.         var x0 : int = (x / 3) * 3
12.         var y0 : int = (y / 3) * 3
13.         # check if n already exists in current box (3x3)
14.         for i in 3:
15.                 for j in 3:
16.                         if grid[coord_to_index(y0 + i, x0 + j)] == n:
17.                                 return false
18.         # as far as we know, n is a legal value for this square
19.         return true

And finally, the code used to attempt to find a solution to the puzzle. I think this is where my trouble lies. This function basically just brute-forces the grid, attempting every possible value in every unknown square, looking for a solution, with backtracking when it reaches a dead-end. Initially I had it naively starting at element 0 of the array and looping through them in order, but this is obviously very inefficient and leads to a lot of duplicated efforts due to backtracking. It seemed to work, and generated minimal puzzles which usually had about 24-26 givens. But as mentioned previously, it was pretty slow.

So then I attempted to sort the list of squares to solve by the number of possible values that were legal to place there, starting with those which had the least possible solutions. This increases chances of success, but even in the event of a failure (dead-end) it cuts out a huge number of the possible solutions we'd have to check.

Oh, and since it's recursive, I have it keep track of and return how many solutions it has found so that it can immediately jump all the way back down the stack once a solution has been found.

Code: Python [Select]

1. func solve(grid, solutions := 0) -> int:
2.         # this is a dictionary whose key will be the (x,y) coordinate
3.         # and the value will be the number of possibilities for that coordinate
4.         var possibilities = {}
5.         # loop through every element in the grid
6.         for i in grid.size():
7.                 # get the (x,y) coordinates for this index
8.                 var coord = index_to_coord(i)
9.                 # start with the assumption that each square has 0 possibilities (i.e., the square's value is known)
10.                 possibilities[coord] = 0
11.                 # if it's not zero, then it's considered "solved" already
12.                 if not grid[i] == 0:
13.                         continue
14.                 # check how many values are possible here
15.                 for n in range(1, 10): # iterate the numbers 1-9
16.                         if is_possible(grid, coord.y, coord.x, n):
17.                                 possibilities[coord] += 1
18.         # sorted_list is an array whose elements will contain the index of the squares grid,
19.         # sorted by the number of possibilities
20.         var sorted_list := []
21.         for n in range(1, 10): # iterate the numbers 1-9
22.                 # loop through each element in possibilities
23.                 for coord in possibilities.keys(): # remember that each key is an (x,y) coordinate
24.                         if possibilities[coord] == n:
25.                                 # add this square to the sorted list of squares to solve
26.                                 sorted_list.push_back(coord_to_index(coord.y, coord.x))
27.         # now iterate through the sorted list and try solving
28.         for i in sorted_list:
29.                 var coord = index_to_coord(i)
30.                 if grid[i] == 0:
31.                         for n in range(1, 10): # iterate the numbers 1-9
32.                                 if is_possible(grid, coord.y, coord.x, n):
33.                                         grid[i] = n
34.                                         solutions += solve(grid, solutions)
35.                                         if solutions > 0:
36.                                                 return solutions
37.                                         else:
38.                                                 grid[i] = 0
39.                         # none were possible, we've reached a dead end
40.                         return solutions
41.         # if we got this far then we've solved it!
42.         solutions += 1
43.         return solutions

And again, this seems to work... kind of. I mean, it is (usually) noticeably faster than when I was naively brute-forcing without sorting. But (1) it's still too slow, taking at least a couple of seconds to complete, and (2) the "minimal" puzzles its generating can't actually be minimal. Doing it the naïve way, I was getting minimal puzzles with about 24-26 givens on average, the puzzles this is generating consistently have almost twice as many, usually in the 44-46 range. But it has been proven that the least amount of givens a unique puzzle could have is as low as 17 and the highest amount of givens a minimal unique puzzle can have is 39. So something is definitely wrong. Here's an example:

Code: Text [Select]

1. . . . | . 5 9 | . 3 4
2. 2 1 . | . . 6 | . 5 7
3. 9 . . | 3 . 7 | . 6 .
4. ------+-------+------
5. . 9 . | . . 3 | 8 4 2
6. 5 . 8 | 7 . 2 | 3 . 9
7. . . 2 | 1 9 . | . . .
8. ------+-------+------
9. . 2 . | 8 7 1 | 4 . .
10. 1 . 7 | 9 . . | 5 . 6
11. . 3 9 | 6 2 . | 7 8 .

Oh, and for completeness, here is the code for a couple of helper functions that are used in a few places in the code above:

Code: Python [Select]

1. # returns an index for an 81-element array based on x,y coordinates of a 9x9 grid
2. func coord_to_index(y : int, x : int) -> int:
3.         return (y * 9) + x
4.  
5.  
6. # returns the x,y coordinates of a square on a 9x9 grid based on 81-element array index
7. func index_to_coord(i : int) -> Vector2:
8.         var coord := Vector2()
9.         coord.x = i % 9
10.         # integer division
11.         coord.y = i / 9
12.         return coord

I tried adding tons of comments everywhere to make sure it was clear what the code was (supposed to be) doing. If anyone here takes the time to read this, parse/understand the code, and offer helpful suggestions/solutions, I'd appreciate it. Mostly I think I just needed a break from the coding and thought that maybe the process of writing this all out would be a form of Rubber Duck debugging.

I know I'm doing something wrong because I'm not getting minimal puzzles anymore. So help figuring out why that's happening would be much appreciated. But perhaps a more helpful response would explain what else I'm doing wrong that is making this so slow. My understanding is that most minimal puzzles should be solved/generated in milliseconds at most, and that it should be fairly rare to come across a puzzle that takes a few seconds and even rarer to come across one that takes minutes or longer. I've tried benchmarking my code by generating 100 puzzles and averaging the time it takes to do each step, and I can't even do that because while it "only" takes a few seconds at best for each puzzle, it often takes up to a few minutes. But the clincher is that in every attempt at generating 100 puzzles in a row there's (at least) one that takes so long that I've never had the patience to find out exactly how long it would take to complete. I can't remember for sure, but I think I've left it running on a single puzzle for over an hour before aborting the process and trying to adjust the code to speed it up.

What am I doing wrong? And where? Please don't say "everything/everywhere"

[mouser]

"Unit: Any nine squares that compose a row, column, or box. Each square has exactly 3 units." <-- do you mean each square is a MEMBER of exactly 3 units.

[mouser]

I'm not very familiar with Sodoku solving/generating, but I'll give the paper a look and try to comment.

But maybe a quick PRELIMINARY thought experiment is worth doing to clarify what you are seeing.

As I understand the basic gist of the algorithm is that you incrementally blank out squares, and check to make sure (by running a solver) that there is still only a unique solution to the puzzle with the square blanked out.  If there are multiple solutions with that square blanked out, you must force it to be a given, and try looking for another square to blank out (dig a hole).

So, this algorithm guarantees that the puzzle, with its givens and its holes (blanks) is UNIQUELY SOLVABLE.

But it doesn't really guarantee that the puzzle is MINIMAL.  I don't think it claims to, does it?

It's not doing a brute force search for all POSSIBLE ways to dig holes.. It is in fact going through an ORDERED list of possible squares to dig, checking them one at a time, and when it finds one it can dig (leave blank), it makes it blank going forward.

This does not guarantee a minimal set of givens.  Depending on what holes (blanks) you decide on early, you may be forced into having more or less holes in the rest of the puzzle.

You could use it to find minimal puzzles if you ran it once for every possible sequence of potential holes, and kept the one that resulted in the fewest givens.

---

Does that make sense? Or am I missing something?

I just think it's important to understand that the algorithm doesn't seem to be promising to generate minimal puzzles.

[mouser]

Maybe im missing something since it seems like it would break everything if it was missing, or maybe you didn't show all the code, but in find_givens() function, line 21 starts a loop checking if there are solutions with the alternative digits.

In the loop you force the test value, and check if there is a solution..
And at the end of the loop if you DID find other solutions, you force the value back and then set it as a given square.

BUT what you dont do is at the end of that if you DONT find any solutions, is FORCE that value to a hole (value 0).. so in the code you show above it will be left as bad value (the last value you checked in the loop), rather than marked as a hole.
Did you just forget to show that code or am i missing something?

[wraith808]

Here is one in Python that does the same thing you're trying to do (I think)

https://www.101compu...generator-algorithm/

Not sure if that helps...

[Deozaan]

"Unit: Any nine squares that compose a row, column, or box. Each square has exactly 3 units." <-- do you mean each square is a MEMBER of exactly 3 units.

-mouser (July 28, 2021, 11:23 AM)

Yes, that's a better way of phrasing it. I'll edit the post to reflect that.

As I understand the basic gist of the algorithm is that you incrementally blank out squares, and check to make sure (by running a solver) that there is still only a unique solution to the puzzle with the square blanked out.  If there are multiple solutions with that square blanked out, you must force it to be a given, and try looking for another square to blank out (dig a hole).

So, this algorithm guarantees that the puzzle, with its givens and its holes (blanks) is UNIQUELY SOLVABLE.

But it doesn't really guarantee that the puzzle is MINIMAL.  I don't think it claims to, does it?

It's not doing a brute force search for all POSSIBLE ways to dig holes.. It is in fact going through an ORDERED list of possible squares to dig, checking them one at a time, and when it finds one it can dig (leave blank), it makes it blank going forward.

This does not guarantee a minimal set of givens.  Depending on what holes (blanks) you decide on early, you may be forced into having more or less holes in the rest of the puzzle.

You could use it to find minimal puzzles if you ran it once for every possible sequence of potential holes, and kept the one that resulted in the fewest givens.

---

Does that make sense? Or am I missing something?

I just think it's important to understand that the algorithm doesn't seem to be promising to generate minimal puzzles.

-mouser (July 28, 2021, 12:00 PM)

I was operating under the idea that, of all the number of clues given at the start of the puzzle, if removing any one of them results in multiple solutions, then that puzzle is a minimal puzzle. But you make a convincing case that there is a distinction between a truly minimal puzzle and the conception I had of it, and there could possibly be (and almost certainly is) a different arrangement/number of givens that would result in the same unique solution using the digging holes method.

And now that I realize this, I'm interested in what it would take to attain your definition of a truly minimal puzzle. But at the same time, I think the definition I've been using until now is good enough for my purposes with this project.

For reference, I got the idea of a minimal puzzle from a paper by Andrew C. Stuart (PDF link), and there may have been something lost in my paraphrasing of his definition:

The fifth criterion is that the puzzle should be minimal. That is all the numbers have been removed so that the bare minimum of clues remain make a single solution puzzle. Interestingly mathematicians have worked out that 39 numbers is the most number of clues that a minimal puzzle can have.

[...]

Given a filled board I then start subtracting numbers to make the puzzle. To maintain symmetry either two or four numbers that are diagonally opposite each other must be removed at the same time. For the first twenty or so subtractions four numbers can be removed. Beyond that the chance of four numbers leaving a single solution puzzle get slimmer so two at a time are subtracted. A low target of 20 clues is set and by 30 the remaining numbers are tested individually to see if they can be removed safely. After each subtraction the puzzle is tested to see if it retains a single solution. If this fails the numbers are restored and a different quad, pair or single subtraction is tried.

-https://www.sudokuwiki.org/Sudoku_Creation_and_Grading.pdf

So that's the "original" source of the term "minimal puzzle" that I'm aware of. And it doesn't seem to contradict my interpretation of it.

Maybe im missing something since it seems like it would break everything if it was missing, or maybe you didn't show all the code, but in find_givens() function, line 21 starts a loop checking if there are solutions with the alternative digits.

In the loop you force the test value, and check if there is a solution..
And at the end of the loop if you DID find other solutions, you force the value back and then set it as a given square.

BUT what you dont do is at the end of that if you DONT find any solutions, is FORCE that value to a hole (value 0).. so in the code you show above it will be left as bad value (the last value you checked in the loop), rather than marked as a hole.
Did you just forget to show that code or am i missing something?

-mouser (July 28, 2021, 12:12 PM)

You're right. You're missing something that I failed to mention.

For the sake of simplicity, I lied a little in my description of the problem, because I failed to understand the ramifications of the differences I swept under the rug. I'm not actually using a true array to store the squares. I'm using a special array type in GDScript called a PoolIntArray, which is optimized for memory usage and is passed by value instead of reference. I thought both of these characteristics were important for improving the speed of the algorithm, but didn't really see it worth mentioning this special type. (I've updated the original post to include this detail)

But because it's passed by value instead of reference, there's no need to backtrack the changes because the PoolIntArray from the level above is unchanged. What that means is that I actually don't even need to force the value back to its original value when a solution is found. I just need to mark it as given in the "given" array (which is a true array).

Forcing it back to its original value is an artifact in the code from when I originally wrote the functions using a two-dimensional array to store the grid. I thought it was so slow because not only did I have to duplicate the array each time I tried to solve it recursively, I had to do a deep copy to ensure the nested arrays didn't get set to bad values. So when I went to change the code to use a normal array I found the PoolIntArray and thought that it was killing two birds with one stone: No more deep copying, and memory usage optimization! I managed to remove the code to re-dig the hole when no solution was found, but accidentally left in the code that re-sets the square to the original value when a solution is found.

Here is one in Python that does the same thing you're trying to do (I think)

https://www.101compu...generator-algorithm/

Not sure if that helps...

-wraith808 (July 28, 2021, 01:05 PM)

Thanks. I'll take a look at that.

[mouser]

Your solve() function looks a little problematic to me.

First, just as a matter of clarity -- you are returning an int variable "solutions" which seems like its suggesting the number of solutions found, but this isnt quite right is it.. You really just want to return a bool of true if a solution was found, or false if not.  The recursive calls must eventually end in a true or a false, which gets propagated back up to be returned.  You never want to find more than 1 solution, and your algorithm explicitly stops searching once it finds one solution.  Having it look like its adding up solution counts makes it harder to understand.  This makes lines like 40 particularly confusing since you really should be saying "return false" -- there is no way to get there with a solutions>0.

And now looking more into the loop, the idea is to recursively fill in one value, and then call solve on the new grid with the filled in value, each recursive call filling in one additional square of the grid.
(you are doing some optimization on what ORDER you try to fill in squares based on looking at ones with least options first -- maybe document the reasoning and approach more; that's not important).

So the idea of this recursion is that it should return FALSE if you ever call solve() with a grid where there is a hole (blank square) that CANNOT be filled in.  That false will return to the caller who will continue looping checking for a different value to put into the square before it recursively checks for another solution.  That looks right to me.

And then you need it to return TRUE when it has SOLVED the grid COMPLETELY.

But looking at the code, i see what MIGHT be a problem.

Your last lines of solve say "       

[Select]

# if we got this far then we've solved it!        solutions += 1         return solutions

"

But let's look how we can get down there.
One way is if there are no more holes -- that's what we want.  When there are no holes, return TRUE, we found a solution.
But also i think you can get there if your PRELIMINARY sorting operations identifying possibilities creates a situation where some illegal spot has no good options.  this should NOT be returning a true case(!)

I think the better solution would be to set some flag line at line 14: flagFoundHole = true;

then somewhere before line 18 you could just say

[Select]

If (!flagFoundHole) {
// no holes found, so this represents a solution!
return true;
}

[mouser]

You know the famous Knuth programming quote: "premature optimization is the root of all evil" (which I don't agree with -- I think code duplication gets that spot).

My first strategy for trying to understand code like this would be to remove wherever possible all the clever optimization stuff.  Like the lines 2-26 in solve serve only the purpose of reordering the indices to check to get faster results; i'd try to get rid of that kind of thing until i knew it all worked well first.

After it all works then worry about speeding it up.

[mouser]

I know I just said to avoid premature optimization, but in terms of speed, I think your original code with ONE grid passed by reference and resetting values that don't lead to success actually seems like it would be a lot faster and memory friendly than the alternative...  Because you are doing a depth first search it seems like that would work just fine.

Something to consider after you get it all working

[Deozaan]

After it all works then worry about speeding it up.

-mouser (July 28, 2021, 01:49 PM)

That's where I am (I think).

I had it working (I think). But it was too slow to be useable in a real-time game. So now I'm trying to speed it up. And breaking it in the process.

And that's also why some of the code doesn't make much sense. Originally, I was counting solutions. The solve() function was flexible and could be used to find just one solution, two solutions (quitting after it realized the puzzle wasn't unique), or all solutions. Then I realized I didn't really care about finding all solutions. And then I realized I could tweak my other code so that it only needed to find a single solution to know whether or not it was unique. So the solution count stayed in there even though it didn't need to count anymore. Oops! My bad.

But looking at the code, i see what MIGHT be a problem.

Your last lines of solve say "       

[Select]

# if we got this far then we've solved it!        solutions += 1         return solutions

"

But let's look how we can get down there.
One way is if there are no more holes -- that's what we want.  When there are no holes, return TRUE, we found a solution.
But also i think you can get there if your PRELIMINARY sorting operations identifying possibilities creates a situation where some illegal spot has no good options.  this should NOT be returning a true case(!)

-mouser (July 28, 2021, 01:45 PM)

I think you're onto something. I was writing up a response about how I didn't see how that was possible, but in the process of explaining my viewpoint there was a momentary flash of neurons connecting in such a way as to realize that you may be right. But then those neurons went on break or something, because I don't think I fully comprehend it yet. So I'm not fully convinced that you're right (or in what way you're right). But now my confidence that my initial viewpoint was right is very low.

[Deozaan]

You know the famous Knuth programming quote: "premature optimization is the root of all evil" (which I don't agree with -- I think code duplication gets that spot).

-mouser (July 28, 2021, 01:49 PM)

Well, speaking of code duplication, I think that brings up another adage that applies very well to this situation: "Don't try to reinvent the wheel."

I kind of wanted to understand how to generate a Sudoku puzzle, so I could use that knowledge to accomplish something else that was related to doing so. But I realize now--after banging my head against the wall for several days trying to solve something that has already been solved by people who are much smarter than I am--that "the how" of doing it is ancillary to the actual goal of making a Sudoku game in a game engine. So I think I'm going to revisit some of the references I found during my research on "the how" which also included example code in the explanations, such as Peter Norvig's article on Solving Every Sudoku Puzzle and just copy/convert it line for line until I get something that works. (And of course, I'm definitely going to be using the link from wraith808 as a jumping off point as well, so thanks for that.)

Thanks for taking the time to give detailed and helpful replies. Now I have some direction and hope that there's light at the end of the tunnel.

[wraith808]

I think code duplication gets that spot

-mouser (July 28, 2021, 01:49 PM)

I'm working on making some legacy code async, and am cringing as I duplicate whole sections of code because whatever stupid idiot made the original thing put a lot of processing in the ctor! And as it is a nuget package used elsewhere in the company by other teams, I have to leave those old methods in.

[mouser]

I should clarify my use of the term "code duplication".

Don't Repeat Yourself (DRY) is what I believe is the most important principle in coding.

I'm not arguing against one person recreating the code someone else has made.  That's fine, that's programming.

What's evil is when you have two places in your code where you are essentially repeating yourself, such that if you wanted to improve one version you'd have to remember to also always reproduce your changes in the other branch..

[wraith808]

What's evil is when you have two places in your code where you are essentially repeating yourself, such that if you wanted to improve one version you'd have to remember to also always reproduce your changes in the other branch..

-mouser (July 28, 2021, 05:31 PM)

Yup. That's what I'm talking about above.

[Deozaan]

And speaking again of code duplication, I've converted the code from https://www.101compu...generator-algorithm/ into GDScript. It contains two, ~70-line functions which are virtually identical, with only something like 3 lines different between them.

It works, but it still takes about 3 seconds on average to generate a puzzle. And they tend to be easier puzzles (with more givens) because it just tries to get rid of one number at a time until it finds multiple solutions, does that a few times, then stops attempting even if there are other numbers that could be removed while maintaining a unique solution.

So then I modified their "digging" function to try every square in a randomized order, and it takes significantly longer to generate a puzzle, with only a few fewer givens.

I benchmarked the difference between "Hey, I tried a bit, what do you expect of me?" and "I must attempt to remove every single number I can!" by generating 10 puzzles of each, and the difference is staggering. As stated, the "lazy" way took about 3 seconds on average to generate a puzzle, 0.1 seconds for the fastest and 12 seconds for the slowest. But the "stickler" way took about 12 minutes on average, 26 seconds for the fastest one and and a whopping 18 minutes for the slowest one.

I'm starting to think that most Sudoku software doesn't actually generate minimal puzzles on the fly every time you start a new puzzle, because I'm having a hard time imagining being able to do so reliably in 0.1 seconds or less.

Either that or I need to get closer to the metal with C++ or something. 😬

[4wd]

Javascript version that runs in your browser: jsSudoku

It's generating puzzles almost immediately on my computer at any of the 5 difficulty levels.

[Deozaan]

Javascript version that runs in your browser: jsSudoku

It's generating puzzles almost immediately on my computer at any of the 5 difficulty levels.

-4wd (July 29, 2021, 07:32 AM)

After looking through the source code for a few minutes, it appears to be generating the solution using an idea that occurred to me as a possibility sometime in the past couple of days.

It starts with a single, pre-generated solution, then applies random transformations to it fifteen times, which basically shuffles it in ways that maintain the legality of number placement. (In my own code, I was generating a random solution, then transforming it 100 times. This usually only took tens of milliseconds at most, but sometimes generating a random solution took hundreds of milliseconds. Meanwhile, transforming is always super quick to do, taking only up to a few milliseconds at most, but often finishing under 1ms.) So they skipped the slowest part of solution generation by starting with a solved puzzle and just transforming it.

Then, to create a puzzle out of the solution, it randomly removes a certain number of digits based on the difficulty level. That is to say:

• Trivial removes 22 digits, resulting in 59 givens.
• Easy removes 32 digits, resulting in 49 givens.
• Medium removes 42 digits, resulting in 39 givens.
• Hard removes 52 digits, resulting in 29 givens.
• Ultra removes 58 digits, resulting in 23 givens.

Like the python code wraith808 linked to, the result is obviously not necessarily a minimal puzzle. And in fact, all but Hard and Ultra difficulty result in puzzles that have so many givens that professional Sudoku puzzle creators would throw them out.

I also insist that the average number of clues hangs around 27 and is never more than 30. Nikoli, the inventor of the modern version of Sudoku states as part of his definition that the number of clues should not exceed 32.

[...]

Over a large run I get a set of puzzles where the number of clues is a bell-curve centered on 27.

-https://www.sudokuwiki.org/Sudoku_Creation_and_Grading.pdf

But in the case of Ultra difficulty, which results in a puzzle with only 23 givens, it may be good enough considering the speed at which it does it. Many of the puzzles I've been generating the slow way have up to a few more givens than that.

So maybe I just need to drop the self-imposed requirement of having a minimal puzzle, since it seems there do exist other methods of generating a puzzle that is good enough in a much faster time.