The New Sudoku Players' Forum

[rjamil]

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 0
1) Apply Trial and Error Candidate 2 from Candidates 23456789 at Cell 1
2) Apply Trial and Error Candidate 3 from Candidates 3456789 at Cell 2
3) Apply Trial and Error Candidate 4 from Candidates 456789 at Cell 3
4) Apply Trial and Error Candidate 5 from Candidates 56789 at Cell 4
5) Apply Trial and Error Candidate 6 from Candidates 6789 at Cell 5
36) Found Naked triplet Candidates 789 at Unit 20 Cells 6 7 8
6) Apply Trial and Error Candidate 7 from Candidates 789 at Cell 6
7) Apply Trial and Error Candidate 8 from Candidates 89 at Cell 7
8) Apply Naked Single Candidate 9 from Candidates 9 at Cell 8
9) Apply Trial and Error Candidate 4 from Candidates 456789 at Cell 9
10) Apply Trial and Error Candidate 5 from Candidates 56789 at Cell 10
11) Apply Trial and Error Candidate 6 from Candidates 6789 at Cell 11
100) Found Hidden triplet Candidates 789 at Unit 1 Cells 12 13 14
36) Found Naked triplet Candidates 789 at Unit 2 Cells 18 19 20
100) Found Naked triplet Candidates 123 at Unit 2 Cells 21 22 23
12) Apply Trial and Error Candidate 7 from Candidates 789 at Cell 12
13) Apply Trial and Error Candidate 8 from Candidates 89 at Cell 13
14) Apply Naked Single Candidate 9 from Candidates 9 at Cell 14
15) Apply Trial and Error Candidate 1 from Candidates 123 at Cell 15
16) Apply Trial and Error Candidate 2 from Candidates 23 at Cell 16
17) Apply Naked Single Candidate 3 from Candidates 3 at Cell 17
18) Apply Trial and Error Candidate 7 from Candidates 789 at Cell 18
19) Apply Trial and Error Candidate 8 from Candidates 89 at Cell 19
20) Apply Naked Single Candidate 9 from Candidates 9 at Cell 20
21) Apply Trial and Error Candidate 1 from Candidates 123 at Cell 21
22) Apply Trial and Error Candidate 2 from Candidates 23 at Cell 22
23) Apply Naked Single Candidate 3 from Candidates 3 at Cell 23
24) Apply Trial and Error Candidate 4 from Candidates 456 at Cell 24
25) Apply Trial and Error Candidate 5 from Candidates 56 at Cell 25
26) Apply Naked Single Candidate 6 from Candidates 6 at Cell 26
27) Apply Trial and Error Candidate 2 from Candidates 235689 at Cell 27
28) Apply Trial and Error Candidate 1 from Candidates 14578 at Cell 29
29) Apply Trial and Error Candidate 4 from Candidates 4578 at Cell 32
30) Apply Trial and Error Candidate 5 from Candidates 578 at Cell 35
31) Apply Trial and Error Candidate 3 from Candidates 3679 at Cell 31
32) Apply Trial and Error Candidate 6 from Candidates 679 at Cell 28
33) Apply Hidden Single Candidate 7 from Candidates 79 at Cell 34
34) Apply Trial and Error Candidate 8 from Candidates 89 at Cell 33
35) Apply Naked Single Candidate 9 from Candidates 9 at Cell 30
36) Apply Trial and Error Candidate 1 from Candidates 167 at Cell 40
37) Apply Trial and Error Candidate 2 from Candidates 24 at Cell 44
38) Apply Trial and Error Candidate 6 from Candidates 67 at Cell 49
77) Found Naked triplet Candidates 479 at Unit 25 Cells 58 67 76
39) Apply Trial and Error Candidate 5 from Candidates 58 at Cell 39
40) Apply Trial and Error Candidate 7 from Candidates 78 at Cell 41
22) Found Naked pair Candidates 28 at Unit 5 Cells 48 50
41) Apply Trial and Error Candidate 2 from Candidates 28 at Cell 48
42) Apply Naked Single Candidate 8 from Candidates 8 at Cell 50
43) Apply Trial and Error Candidate 4 from Candidates 48 at Cell 38
44) Apply Hidden Single Candidate 8 from Candidates 389 at Cell 36
35) Found Hidden pair Candidates 14 at Unit 5 Cells 52 53
45) Apply Trial and Error Candidate 5 from Candidates 57 at Cell 47
46) Apply Hidden Single Candidate 7 from Candidates 379 at Cell 46
47) Apply Trial and Error Candidate 3 from Candidates 39 at Cell 45
48) Apply Naked Single Candidate 9 from Candidates 9 at Cell 37
49) Apply Naked Single Candidate 9 from Candidates 9 at Cell 51
50) Apply Trial and Error Candidate 3 from Candidates 36 at Cell 42
51) Apply Naked Single Candidate 6 from Candidates 6 at Cell 43
52) Apply Trial and Error Candidate 1 from Candidates 14 at Cell 52
53) Apply Naked Single Candidate 4 from Candidates 4 at Cell 53
54) Apply Trial and Error Candidate 5 from Candidates 569 at Cell 54
55) Apply Trial and Error Candidate 1 from Candidates 12 at Cell 59
56) Apply Trial and Error Candidate 3 from Candidates 34 at Cell 55
28) Found Hidden pair Candidates 49 at Unit 6 Cells 58 61
57) Apply Trial and Error Candidate 6 from Candidates 68 at Cell 57
58) Apply Naked Single Candidate 2 from Candidates 2 at Cell 60
59) Apply Trial and Error Candidate 7 from Candidates 78 at Cell 56
60) Apply Naked Single Candidate 8 from Candidates 8 at Cell 62
61) Apply Trial and Error Candidate 4 from Candidates 49 at Cell 61
62) Apply Naked Single Candidate 9 from Candidates 9 at Cell 58
63) Apply Trial and Error Candidate 6 from Candidates 69 at Cell 63
64) Apply Naked Single Candidate 5 from Candidates 5 at Cell 69
65) Apply Naked Single Candidate 2 from Candidates 2 at Cell 68
66) Apply Naked Single Candidate 8 from Candidates 8 at Cell 65
67) Apply Naked Single Candidate 3 from Candidates 3 at Cell 66
68) Apply Naked Single Candidate 9 from Candidates 9 at Cell 70
69) Apply Naked Single Candidate 9 from Candidates 9 at Cell 72
70) Apply Naked Single Candidate 2 from Candidates 2 at Cell 74
71) Apply Naked Single Candidate 8 from Candidates 8 at Cell 75
72) Apply Naked Single Candidate 5 from Candidates 5 at Cell 77
73) Apply Naked Single Candidate 6 from Candidates 6 at Cell 78
74) Apply Naked Single Candidate 3 from Candidates 3 at Cell 79
75) Apply Trial and Error Candidate 1 from Candidates 17 at Cell 71
76) Apply Naked Single Candidate 4 from Candidates 4 at Cell 64
77) Apply Hidden Single Candidate 4 from Candidates 47 at Cell 76
78) Apply Naked Single Candidate 1 from Candidates 1 at Cell 73
79) Apply Naked Single Candidate 7 from Candidates 7 at Cell 67
80) Apply Naked Single Candidate 7 from Candidates 7 at Cell 80
1) 123456789456789123789123456261934875894517362375268914537691248648372591912845637 # S1 # N0 # H4 # 15.000000

It takes following steps:

Code: Select all

1. Naked Single    = 30
2. Hidden Single   = 04
3. Trial and Error = 47
4. Naked pair      = 01
5. Hidden pair     = 02
6. Naked triplet   = 04
7. Hidden triplet  = 01
                   ====
Total steps        = 89

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

[JasonLion]

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.

[rjamil]

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.

[JasonLion]

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

[champagne]

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.

[rjamil]

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

[JasonLion]

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.

[champagne]

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.

[eleven]

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.

[rjamil]

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.

Thanks for your findings.

Added: Will you please share your counter example finding with us?

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

[champagne]

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.

[eleven]

Added: Will you please share your counter example finding with us?

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

[David P Bird]

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.

[rjamil]

Hi eleven and David,

Thanks for discussing further my point.

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

[m_b_metcalf]

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