Sudoku Programming

Programs which generate, solve, and analyze Sudoku puzzles

Sudoku Programming

Postby axiel » Wed Mar 09, 2022 9:01 pm

While not precisely software, this is a question about what many of us do to pursue our hobby, which is writing software to meet our own specific needs.

Before I ask my question, I'm not sure if my definition of a minimal puzzle is the same as shared on the forum. Please correct me if there's another term for it. In this context, I consider a minimal puzzle a puzzle that cannot have more numbers removed without creating multiple solutions.

So, I have no trouble creating minimal puzzles - my question is how to determine the 'most' minimal puzzle in a grid? For example, you have a puzzle with 25 givens and a single solution, but that same end grid can yield a puzzle with 21 givens if you choose different cells to remove.

I can do this by recursively testing all the cell removal paths, but it is painfully slow even after optimizing. Is there another better way to approach this?

Thanks!
--- He's an IT guy, but like, with superpowers
User avatar
axiel
 
Posts: 5
Joined: 09 February 2022

Re: Sudoku Programming

Postby denis_berthier » Thu Mar 10, 2022 4:38 am

axiel wrote: I'm not sure if my definition of a minimal puzzle is the same as shared on the forum. Please correct me if there's another term for it. In this context, I consider a minimal puzzle a puzzle that cannot have more numbers removed without creating multiple solutions.

Correct; To avoid ambiguities, I'd write "a puzzle with a unique solution that cannot..."

axiel wrote:So, I have no trouble creating minimal puzzles - my question is how to determine the 'most' minimal puzzle in a grid? For example, you have a puzzle with 25 givens and a single solution, but that same end grid can yield a puzzle with 21 givens if you choose different cells to remove.

There's no "most minimal" puzzle (in general).

axiel wrote:I can do this by recursively testing all the cell removal paths, but it is painfully slow even after optimizing. Is there another better way to approach this?

Many removal paths are equivalent (the result of a path doesn't depend on the order of removals). Apart from this, most of the generation time is spent in the solver; which must therefore be fast.
If you want a very classical example of a generator, see the suexg-td, here: https://github.com/denis-berthier/Controlled-bias_Sudoku_generator_and_collection/tree/master/PROGRAMS(not my program, so don't ask me to explain the cryptic style of C programming).
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: Sudoku Programming

Postby dobrichev » Thu Mar 10, 2022 6:45 am

Hi axiel,

axiel wrote:I consider a minimal puzzle a puzzle that cannot have more numbers removed without creating multiple solutions.

Right.

axiel wrote:Is there another better way to approach this?

Read at least the Wikipedia articles, please. Then we can discuss details on the different approaches and known results.
dobrichev
2016 Supporter
 
Posts: 1844
Joined: 24 May 2010

Re: Sudoku Programming

Postby champagne » Thu Mar 10, 2022 7:04 am

axiel wrote:While not precisely software, this is a question about what many of us do to pursue our hobby, which is writing software to meet our own specific needs.

Before I ask my question, I'm not sure if my definition of a minimal puzzle is the same as shared on the forum. Please correct me if there's another term for it. In this context, I consider a minimal puzzle a puzzle that cannot have more numbers removed without creating multiple solutions.

So, I have no trouble creating minimal puzzles - my question is how to determine the 'most' minimal puzzle in a grid? For example, you have a puzzle with 25 givens and a single solution, but that same end grid can yield a puzzle with 21 givens if you choose different cells to remove.

I can do this by recursively testing all the cell removal paths, but it is painfully slow even after optimizing. Is there another better way to approach this?

Thanks!

Hi axiel,

Nothing to add to the concept of "minimal puzzle".
And yes, this is an exponential process.
No better known code to get the minimal than to kill one by one the clues and to see if the rest is still a valid puzzle . (Not 100% true, if you know that you are in the very low number of clues for the minimal, you have another possibility)

In most cases, you want just to know if the puzzle is minimal, than the process in not too long.
If the gap increases, then you must have a process avoiding redundancy (and a good "brute force" solver). Even in C or C++, with more than five steps, the run time is already in seconds or in minutes depending on your code and the number of clues at start.

EDIT : I had not seen mladen's post when I wrote this, but he has surely with "GridChecker" one of the freely available answers to such a question.
EDIT2: if you are expecting a significant reduction in the number of clues in the minimal puzzle , You have ways through the unavoidable sets of the solution grid to speed up the recursive process, but this is another story.
champagne
2017 Supporter
 
Posts: 7334
Joined: 02 August 2007
Location: France Brittany

Re: Sudoku Programming

Postby axiel » Thu Mar 10, 2022 10:10 pm

Hi dobrichev,

Thanks for the reply!

dobrichev wrote:Read at least the Wikipedia articles, please. Then we can discuss details on the different approaches and known results.


I have read (several times) a lot of the Wikipedia articles - assuming you mean those here: Sudoku solving algorithms (Including Mathematics of Sudoku and a few others)

I'll be the first to admit I'm still new to the whole area of programming sudoku problems and to this forum, which has a whole host of information I haven't yet had time to investigate. Most of what I'm doing now uses an exact cover solver and recursive backtracking to generate unique puzzle grids. I did find your post Gridchecker thanks to @champagne's mention of Gridchecker - this looks to be an excellent place to start digging a little deeper, and may even be the answer to my original question.

I will get it compiled on my system and see where it leads me. I will follow up in that thread if I have any questions.

If you have any other suggested resources/reading, I'd be glad to take a look - I do like to solve things myself - and I can understand, seeing that you've been around for quite some time and don't want to waste time spoon-feeding another newbie ;)


Thanks!
--- He's an IT guy, but like, with superpowers
User avatar
axiel
 
Posts: 5
Joined: 09 February 2022

Re: Sudoku Programming

Postby axiel » Thu Mar 10, 2022 10:23 pm

Hi Denis,

denis_berthier wrote:Many removal paths are equivalent (the result of a path doesn't depend on the order of removals). Apart from this, most of the generation time is spent in the solver; which must therefore be fast.
If you want a very classical example of a generator, see the suexg-td, here: https://github.com/denis-berthier/Controlled-bias_Sudoku_generator_and_collection/tree/master/PROGRAMS(not my program, so don't ask me to explain the cryptic style of C programming).


I'll dig in there and see what I can find. I now realize that I purchased a book you published a few years ago - The Hidden Logic of Sudoku (Second Edition). It only arrived a few days ago, and I haven't had much more that a cursory look through, but looking forward to it. I also see that it seems you've posted your other published books in your GitHub, which is appreciated - but I'm a book nerd, and will always prefer a physical copy if I can get it :)

Thanks!
--- He's an IT guy, but like, with superpowers
User avatar
axiel
 
Posts: 5
Joined: 09 February 2022

Re: Sudoku Programming

Postby axiel » Thu Mar 10, 2022 10:38 pm

Hi Champagne,

champagne wrote:EDIT : I had not seen mladen's post when I wrote this, but he has surely with "GridChecker" one of the freely available answers to such a question.
EDIT2: if you are expecting a significant reduction in the number of clues in the minimal puzzle , You have ways through the unavoidable sets of the solution grid to speed up the recursive process, but this is another story.


Thanks for the lead on GridChecker! This should keep me occupied for some time.

One of the reasons I love Sudoku is the logic behind solving them. So puzzling out a logical solution to creating them also attracts my attention - I don't know if finding the 'most' minimal puzzle in a grid even matters, but it's got my attention now, and I'll follow the path to where it may lead me.

Thanks!
--- He's an IT guy, but like, with superpowers
User avatar
axiel
 
Posts: 5
Joined: 09 February 2022

Re: Sudoku Programming

Postby dobrichev » Fri Mar 11, 2022 8:08 am

Hi axiel,

Sudoku solving algorithms in Wikipedia is a low quality article that can only confuse you.

You can read There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem by Gary McGuire and others.
Try to understand Unavoidable Sets (UA) concept. You may skip details for reduction of the number of grids for investigation, parallelism, etc.
Authors provide an excellent algorithm (and code) for determining the short-sized UA. I have implemented it in gridchecker, if you find there it is more readable.

From your initial post I am unsure whether you are interested in minimal puzzles which givens are subset of a non-minimal puzzle, or you want minimal puzzles for particular solution grid regardless of the givens in your initial puzzle.
For the first case, you can apply McGuire's algorithm with additional constraint that givens shouldn't be in a blacklisted cells which you compose form the non-givens of your initial puzzle. The blacklisted cells also reduce the sizes of UA, sometimes to 1 which in fact forces a particular cell as a given.

The effectivness of McGuire's algorithm decreases with the size of the searched puzzles. Gridchecker has code with some experimental "improvements" for searchin puzzles of larger sizes. This complicates the code, likely unnecessary in some parts, making it difficult to understand.

Gridchecker also has code for reduction of givens that is useful for larger puzzles. At its limit, the top-down approach takes forever when started from a full solution grid, but generates some high-clue minimal puzzles in a reasonable time.

Gridchecker still keeps the initial implementation for determining the small sized puzzles within a fixed solution grid - the one before McGuire's improvements. It was effective for its time, but was overperformed in several orders of magnitude later. It attempts to determine a "dense" area of givens in the solution grid and exploits this knowledge for earlier cancellation of impossible clue placement paths. Likely this code is only in historical interest and its benefits are difficult/impossible to incorporate in other alogorithms.

For low-clue determination of a grid, see this topic by Mathimagics.

For exhaustive 17-clue puzzles search, there is an ongoing project lead by champagne.

Enjoy,
M.
dobrichev
2016 Supporter
 
Posts: 1844
Joined: 24 May 2010

Re: Sudoku Programming

Postby gulshan212 » Mon Feb 06, 2023 11:30 am

Hello this is Gulshan Negi
Well, there are several algorithms you can use to generate puzzles based on the constraints you have defined. For example, you can use a depth-first search, a breadth-first search, or a random algorithm to generate potential puzzles. Apart from this, there are several ways to do this but the above-mentioned way is the finest and simplest way to do so.
Thanks
gulshan212
 
Posts: 12
Joined: 27 January 2023
Location: Haldwani, Uttarakhand


Return to Software