## How to rate and solve empty Sudoku grid?

Everything about Sudoku that doesn't fit in one of the other sections

### How to rate and solve empty Sudoku grid?

Hi all,

I know that this post contain some kind of a stupid question. But, as I read and understand that, an empty Sudoku grid is also considered to be a valid Sudoku grid (provided that to exclude minimum 17 clues and unique solution constraint).

Also, I am not interested in speed for a moment (but considered added information, if one supplied). However, interested to know about steps taken to find first solution only.

Here I am sharing my solver empty Sudoku grid solution step wise, which only search through Naked/Hidden Singles/Tuples, Box-Line/Pointing and Claiming Intersection Removals, Basic Fish (i.e., X-Wing, Sword Fish and Jelly Fish) and Trial-and-Error strategies. I am not interested/planning to implement rating in my Solver near future.

My Bitwise Sudoku Solver program solves empty Sudoku grid, without backtracking, as follows:
Code: Select all
`0) Apply Trial and Error Candidate 1 from Candidates 123456789 at Cell 01) Apply Trial and Error Candidate 2 from Candidates 23456789 at Cell 12) Apply Trial and Error Candidate 3 from Candidates 3456789 at Cell 23) Apply Trial and Error Candidate 4 from Candidates 456789 at Cell 34) Apply Trial and Error Candidate 5 from Candidates 56789 at Cell 45) Apply Trial and Error Candidate 6 from Candidates 6789 at Cell 536) Found Naked triplet Candidates 789 at Unit 20 Cells 6 7 86) Apply Trial and Error Candidate 7 from Candidates 789 at Cell 67) Apply Trial and Error Candidate 8 from Candidates 89 at Cell 78) Apply Naked Single Candidate 9 from Candidates 9 at Cell 89) Apply Trial and Error Candidate 4 from Candidates 456789 at Cell 910) Apply Trial and Error Candidate 5 from Candidates 56789 at Cell 1011) Apply Trial and Error Candidate 6 from Candidates 6789 at Cell 11100) Found Hidden triplet Candidates 789 at Unit 1 Cells 12 13 1436) Found Naked triplet Candidates 789 at Unit 2 Cells 18 19 20100) Found Naked triplet Candidates 123 at Unit 2 Cells 21 22 2312) Apply Trial and Error Candidate 7 from Candidates 789 at Cell 1213) Apply Trial and Error Candidate 8 from Candidates 89 at Cell 1314) Apply Naked Single Candidate 9 from Candidates 9 at Cell 1415) Apply Trial and Error Candidate 1 from Candidates 123 at Cell 1516) Apply Trial and Error Candidate 2 from Candidates 23 at Cell 1617) Apply Naked Single Candidate 3 from Candidates 3 at Cell 1718) Apply Trial and Error Candidate 7 from Candidates 789 at Cell 1819) Apply Trial and Error Candidate 8 from Candidates 89 at Cell 1920) Apply Naked Single Candidate 9 from Candidates 9 at Cell 2021) Apply Trial and Error Candidate 1 from Candidates 123 at Cell 2122) Apply Trial and Error Candidate 2 from Candidates 23 at Cell 2223) Apply Naked Single Candidate 3 from Candidates 3 at Cell 2324) Apply Trial and Error Candidate 4 from Candidates 456 at Cell 2425) Apply Trial and Error Candidate 5 from Candidates 56 at Cell 2526) Apply Naked Single Candidate 6 from Candidates 6 at Cell 2627) Apply Trial and Error Candidate 2 from Candidates 235689 at Cell 2728) Apply Trial and Error Candidate 1 from Candidates 14578 at Cell 2929) Apply Trial and Error Candidate 4 from Candidates 4578 at Cell 3230) Apply Trial and Error Candidate 5 from Candidates 578 at Cell 3531) Apply Trial and Error Candidate 3 from Candidates 3679 at Cell 3132) Apply Trial and Error Candidate 6 from Candidates 679 at Cell 2833) Apply Hidden Single Candidate 7 from Candidates 79 at Cell 3434) Apply Trial and Error Candidate 8 from Candidates 89 at Cell 3335) Apply Naked Single Candidate 9 from Candidates 9 at Cell 3036) Apply Trial and Error Candidate 1 from Candidates 167 at Cell 4037) Apply Trial and Error Candidate 2 from Candidates 24 at Cell 4438) Apply Trial and Error Candidate 6 from Candidates 67 at Cell 4977) Found Naked triplet Candidates 479 at Unit 25 Cells 58 67 7639) Apply Trial and Error Candidate 5 from Candidates 58 at Cell 3940) Apply Trial and Error Candidate 7 from Candidates 78 at Cell 4122) Found Naked pair Candidates 28 at Unit 5 Cells 48 5041) Apply Trial and Error Candidate 2 from Candidates 28 at Cell 4842) Apply Naked Single Candidate 8 from Candidates 8 at Cell 5043) Apply Trial and Error Candidate 4 from Candidates 48 at Cell 3844) Apply Hidden Single Candidate 8 from Candidates 389 at Cell 3635) Found Hidden pair Candidates 14 at Unit 5 Cells 52 5345) Apply Trial and Error Candidate 5 from Candidates 57 at Cell 4746) Apply Hidden Single Candidate 7 from Candidates 379 at Cell 4647) Apply Trial and Error Candidate 3 from Candidates 39 at Cell 4548) Apply Naked Single Candidate 9 from Candidates 9 at Cell 3749) Apply Naked Single Candidate 9 from Candidates 9 at Cell 5150) Apply Trial and Error Candidate 3 from Candidates 36 at Cell 4251) Apply Naked Single Candidate 6 from Candidates 6 at Cell 4352) Apply Trial and Error Candidate 1 from Candidates 14 at Cell 5253) Apply Naked Single Candidate 4 from Candidates 4 at Cell 5354) Apply Trial and Error Candidate 5 from Candidates 569 at Cell 5455) Apply Trial and Error Candidate 1 from Candidates 12 at Cell 5956) Apply Trial and Error Candidate 3 from Candidates 34 at Cell 5528) Found Hidden pair Candidates 49 at Unit 6 Cells 58 6157) Apply Trial and Error Candidate 6 from Candidates 68 at Cell 5758) Apply Naked Single Candidate 2 from Candidates 2 at Cell 6059) Apply Trial and Error Candidate 7 from Candidates 78 at Cell 5660) Apply Naked Single Candidate 8 from Candidates 8 at Cell 6261) Apply Trial and Error Candidate 4 from Candidates 49 at Cell 6162) Apply Naked Single Candidate 9 from Candidates 9 at Cell 5863) Apply Trial and Error Candidate 6 from Candidates 69 at Cell 6364) Apply Naked Single Candidate 5 from Candidates 5 at Cell 6965) Apply Naked Single Candidate 2 from Candidates 2 at Cell 6866) Apply Naked Single Candidate 8 from Candidates 8 at Cell 6567) Apply Naked Single Candidate 3 from Candidates 3 at Cell 6668) Apply Naked Single Candidate 9 from Candidates 9 at Cell 7069) Apply Naked Single Candidate 9 from Candidates 9 at Cell 7270) Apply Naked Single Candidate 2 from Candidates 2 at Cell 7471) Apply Naked Single Candidate 8 from Candidates 8 at Cell 7572) Apply Naked Single Candidate 5 from Candidates 5 at Cell 7773) Apply Naked Single Candidate 6 from Candidates 6 at Cell 7874) Apply Naked Single Candidate 3 from Candidates 3 at Cell 7975) Apply Trial and Error Candidate 1 from Candidates 17 at Cell 7176) Apply Naked Single Candidate 4 from Candidates 4 at Cell 6477) Apply Hidden Single Candidate 4 from Candidates 47 at Cell 7678) Apply Naked Single Candidate 1 from Candidates 1 at Cell 7379) Apply Naked Single Candidate 7 from Candidates 7 at Cell 6780) Apply Naked Single Candidate 7 from Candidates 7 at Cell 801) 123456789456789123789123456261934875894517362375268914537691248648372591912845637 # S1 # N0 # H4 # 15.000000`

It takes following steps:
Code: Select all
`1. Naked Single    = 302. Hidden Single   = 043. Trial and Error = 474. Naked pair      = 015. Hidden pair     = 026. Naked triplet   = 047. Hidden triplet  = 01                   ====Total steps        = 89`

R. Jamil
------------------------------------------------------------
Place the word "only" anywhere on the sentence:
"She told him that she loved him."
rjamil

Posts: 105
Joined: 15 October 2014
Location: Karachi, Pakistan

### Re: How to rate and solve empty Sudoku grid?

It is impossible to talk about rating a puzzle without defining what rating system you want to use. There are a huge number of rating systems, none of which are preferred over the others. Thus you need to make a choice about which one you want to use and tell us that before we can talk about rating.

In a somewhat similar way, there are many ways to solve puzzles. Unless you specify some additional criteria, your approach seems as good as any.

By the by, having a minimum of 17 clues is not a primary constraint on having a valid puzzle. Instead, it is implied by the constraint of having a single solution.

JasonLion
2017 Supporter

Posts: 600
Joined: 25 October 2007
Location: Silver Spring, MD, USA

### Re: How to rate and solve empty Sudoku grid?

Hi,

I need to share that how Sudoku solver will generate first solution for empty grid? Also, how many and what are the steps taken to solve it?
I see most of the Sudoku solver available online as well as software/program won't solve the empty grid at all.

As far as rating is concern, How one's solver rate empty grid, no matter on what rating system they prefer?
This will help to identify that an empty Sudoku grid is easy to solve with very complex strategy solver as compared to simple strategy solver.

R. Jamil
---------------------------------------------------------------------------------------------
An English professor wrote the words: "A woman without her man is nothing"
on the chalkboard and asked his students to punctuate it correctly.
All of the males in the class wrote: "A woman, without her man, is nothing."
All the females in the class wrote: "A woman: without her, man is nothing."
Punctuation is powerful.
rjamil

Posts: 105
Joined: 15 October 2014
Location: Karachi, Pakistan

### Re: How to rate and solve empty Sudoku grid?

I must be missing something, because nothing you are saying makes any sense to me.

The only two criteria for solved grids I can remember anyone talking about are how quickly you can produce them, and if the creation process is biased or not. Nearly all approaches are biased, i.e. they are more likely to produce some grids and less likely to produce others

JasonLion
2017 Supporter

Posts: 600
Joined: 25 October 2007
Location: Silver Spring, MD, USA

### Re: How to rate and solve empty Sudoku grid?

rjamil wrote:Hi,

I need to share that how Sudoku solver will generate first solution for empty grid? Also, how many and what are the steps taken to solve it?
I see most of the Sudoku solver available online as well as software/program won't solve the empty grid at all.

As far as rating is concern, How one's solver rate empty grid, no matter on what rating system they prefer?
This will help to identify that an empty Sudoku grid is easy to solve with very complex strategy solver as compared to simple strategy solver.

R. Jamil

I fully agree with jasonlion, it is nearly impossible to understand where you want to go.

The number of valid solution grids ( in the minimal lexical form) is well known for long and the program to generate them is not so hard to write.

But using the words "solving" or "rating" referring to that catalog starting from an empty grid has no sense.

The word "solving" is commonly used for a sudoku grid (having one and only one solution). It describes a logical sequence showing how that solution can be established. It is commonly understood that "solving" excludes any guess. Guesses are at the opposite a basic way to verify that a given grid is a sudoku.

The qualifier "rating" tries to give a measurement of the difficulty to find such a solution.

But, as already mentioned, The "rating" has multiple definitions.
champagne
2017 Supporter

Posts: 5445
Joined: 02 August 2007
Location: France Brittany

### Re: How to rate and solve empty Sudoku grid?

Hi,

I just want to know how many steps needed to solve empty grid. As I checked with my solver, it took 89 steps to fill 81 cells. Also, strategies used to complete empty grid are basic strategies. Is there any advance strategy required to minimize trial and error steps. Although, trial and error steps never required backtracking.

Well, if advance technique will minimize steps or replace trial and error steps then there must be some rating involve.

Maybe, I am unable to explain my point clearly for which am really sorry.

R. Jamil
rjamil

Posts: 105
Joined: 15 October 2014
Location: Karachi, Pakistan

### Re: How to rate and solve empty Sudoku grid?

The usual concern is creating the grid very quickly. One common approach starts by filling in a fair number of clues in some mixture of deterministically and randomly and then using a very quick brute force solver to fill in the rest of the grid. Neither of these steps has anything to do with any of the more common rating procedures. In a typical top down puzzle creation approach, you create a random grid, then create a puzzle from that grid, and only then do you apply a rating procedure/filter.

JasonLion
2017 Supporter

Posts: 600
Joined: 25 October 2007
Location: Silver Spring, MD, USA

### Re: How to rate and solve empty Sudoku grid?

rjamil wrote:Hi,

I just want to know how many steps needed to solve empty grid. As I checked with my solver, it took 89 steps to fill 81 cells. ...

R. Jamil

Again, your wording is highly confusing
"solve" means usually "find the final value of a sudoku" (one and one only solution) known by the given clues .

jasonlion tried to answer to the question "how can you find a sudoku" or, if you prefer, how to generate clues leading to a sudoku starting from an empty grid.

To find all 81 valid grid, the process is normally different. gsf prepared years ago the list of 401 minlex possible values for the first band.
This is the usual start and then you generate all possible values for the remaining 54 cells. (trying to see as soon as possible if the next steps are hopeless)

but having no idea of what you want to do, both answers can be out of the scope.
champagne
2017 Supporter

Posts: 5445
Joined: 02 August 2007
Location: France Brittany

### Re: How to rate and solve empty Sudoku grid?

rjamil wrote:I just want to know how many steps needed to solve empty grid. As I checked with my solver, it took 89 steps to fill 81 cells. Also, strategies used to complete empty grid are basic strategies. Is there any advance strategy required to minimize trial and error steps. Although, trial and error steps never required backtracking.

Well, if advance technique will minimize steps or replace trial and error steps then there must be some rating involve.

So you want to know, if with more advanced techniques you could find a solution to the empty grid in less than 89 steps, where for each step you
- apply a technique, if available or just pick a remaining candidate from a cell
(where it is not defined which cell and candidate you choose here)

I don't think, that more advanced techniques than locked candidates and subsets could help you, because i believe that, as long as you apply these simple techniques before each guess ("trial and error"), any candidate you choose will lead to a solution - so there is nothing to find for more advanced techniques.
However i don't have a proof for that.
[Added:] Ah no, that's not true, i just found a counter example.

So you will have to define more about, how cells or candidates have to be chosen. Randomly ? Then the number of steps probably will vary. Fixed ? Then take any solution grid and choose one number after the other -> 81 steps.
eleven

Posts: 1386
Joined: 10 February 2008

### Re: How to rate and solve empty Sudoku grid?

Hi eleven,

You got my point.

As I have coded for basic techniques and basic fishes only. After applying these two types of techniques, applying trial-and-error and backtracking.

What I have in my mind is that, the order of technique to implement should have some meaning. And it should be either to fill empty grid in less steps or even replace/minimize at least trial-and-error steps.

R. Jamil
--------------------------------------------------------------
There are seldom, if ever, any hopeless situations,
but there are many people who lose hope in the face of some situations.
rjamil

Posts: 105
Joined: 15 October 2014
Location: Karachi, Pakistan

### Re: How to rate and solve empty Sudoku grid?

If I correctly understood eleven's point, nothing object, building progressively a bunch of given to have some logical rules forcing some of the cells.

Is that anything to do with a final rating? I am sure that the response is no.

If we consider efficiency, the best known process in the grid building is limited to basic rules. (locked mini rows at maximum) in the brute force I use.
champagne
2017 Supporter

Posts: 5445
Joined: 02 August 2007
Location: France Brittany

### Re: How to rate and solve empty Sudoku grid?

I did not keep it, because the idea, that applying locked candidates & subsets would prevent you from backtracking, when starting with an empty grid, was simply nonsense (though it probably is true in the big majority of cases).
If the order of guessing numbers is free, you can start with guessing each possible sudoku (unique or not). If it is one, where only an advanced technique (in my case an x-wing) could eliminate a candidate, and your next choose is this candidate, you would have to backtrack.

But i still don't think, that for random guessing (starting with an empty grid) advanced techniques would reduce the number of steps (on average) significantly. The reason is, that on average there are rare sudokus, where only advanced techniques can make progress.

OT: nice aphorisms
eleven

Posts: 1386
Joined: 10 February 2008

### Re: How to rate and solve empty Sudoku grid?

I've had limited experience in this area but my method is to start by picking 3 boxes in a diagonal. In two of them enter the digits 1-9 in any order you choose and in the third box enter digits in just two diagonal cells. Only then is it necessary start making the simple eliminations the placements produce. From this point on various tactics are possible based on the cells or digits that have the most restricted options. A simple one is to choose a digit at a time and pick one of the cells it can occupy in the boxes where it is missing.
David P Bird
2010 Supporter

Posts: 935
Joined: 16 September 2008
Location: Middle England

### Re: How to rate and solve empty Sudoku grid?

Hi eleven and David,

Thanks for discussing further my point.

eleven wrote:If the order of guessing numbers is free, you can start with guessing each possible sudoku (unique or not). If it is one, where only an advanced technique (in my case an x-wing) could eliminate a candidate, and your next choose is this candidate, you would have to backtrack.

I developed a solver that uses X-Wing technique too. But due to either order of techniques applied or the order of trial-and-error (guessing) prevent it to fill empty Sudoku grid for providing first solution.

My idea/question is to implement the techniques/methods in order to reduce the guess work and backtracking. And for that, first reduce the same from empty Sudoku grid, no matter how guess minimize, either by re-ordering the techniques or order of unsolved cell position picking technique (as in David solver case). The number of logical steps is inverse proportional to guess work. (As singleton and guess directly fill the cell position as compared to logical steps, which only reduce the chance of backtracking from next step.)

I tested again empty Sudoku grid for first solution with my solver by Naked/Hidden singles and guess-backtracking routine only (and commented rest of the techniques). It took only 81 steps to complete, including 47 trial-and-error steps. With added techniques, took same 47 trial-and-error steps but total 89 steps.

So, the only positive point to include any logical technique is to reduce the backtracking chances.

Am I going some wrong direction?

R. Jamil
Attachments
rjmty1.txt
With techniques
rjmty.txt
Without techniques
rjamil

Posts: 105
Joined: 15 October 2014
Location: Karachi, Pakistan

### Re: How to rate and solve empty Sudoku grid?

FWIW, and for the record, I generate a solution grid by starting with an empty grid and filling its first row with nine digits in a random order, obtained using a PRNG. I then add subsequent rows of randomly arranged digits, sorting their order as necessary to avoid clashes with digits already in place on previous rows or already in the current box. If this cannot be done, a fresh set of random numbers is used. For the third and sixth rows, an additional check is required that the box constraint is also fulfilled. Also, a deadlock condition can arise in row six when the three digits missing from an almost-completed box have already been assigned to a single column above the box. If this occurs, the program restarts. This program can generate not only standard 9x9 grids, but also larger sizes up to 49x49.

Regards,

Mike Metcalf

m_b_metcalf
2017 Supporter

Posts: 7938
Joined: 15 May 2006
Location: Berlin

Next