The New Sudoku Players' Forum

[JasonLion]

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?

As before, that depends on what you are trying to do. If you are concerned with the speed of the code, you are indeed headed in the wrong direction. For standard 9x9 Sudoku, using anything more complex than locked candidates will only slow the whole process down. The largest speedups can be achieved by judicious choice of initial guess placement and optimizing the basic techniques so they are as fast as possible. David P Bird's approach gest a lot of placements without any chance of conflict, which minimizes the the chances of backtracking, while m_b_metcalf's approach allows you to simplify the basic techniques so they take as little time as possible.

Another way to say this is that your count of "steps" is not a good proxy for time taken. Thousands of very simple steps can be taken in the amount of time consumed by a single step using a more advanced technique.

On the other hand, if you are setting yourself a puzzle of how to minimize steps as you have defined them, then there are several questions you could ask next. It would be very useful to quantify how many steps are added by backtracking on average, and then compare that to how many steps can be saved on average by using each individual advanced technique.

[rjamil]

Hi Jason,

The largest speedups can be achieved by judicious choice of initial guess placement and optimizing the basic techniques so they are as fast as possible. David P Bird's approach gest a lot of placements without any chance of conflict, which minimizes the the chances of backtracking, while m_b_metcalf's approach allows you to simplify the basic techniques so they take as little time as possible.

Another way to say this is that your count of "steps" is not a good proxy for time taken. Thousands of very simple steps can be taken in the amount of time consumed by a single step using a more advanced technique.

On the other hand, if you are setting yourself a puzzle of how to minimize steps as you have defined them, then there are several questions you could ask next. It would be very useful to quantify how many steps are added by backtracking on average, and then compare that to how many steps can be saved on average by using each individual advanced technique.

Well, I think I reached my limit to optimize the code for speed (no matter how many lines of code required). Now, I do really agree with you that, my concern is to further speedup by either re-ordering the techniques or skipping some at some level. (But what techniques and what level are questionable.)

Now, for empty or partially filled Sudoku grid, is it ok to check just naked and hidden singles; and guesses till reached minimum Sudoku clues (i.e., 17), or just guesses, and then applying basic and/or advance techniques as well?

R. Jamil
---------------------------------------------------------
"A good speech should be like a woman's skirt;
long enough to cover the subject and short enough to create interest."
~ Winston S. Churchill

[rjamil]

Hi again,

Let me re-phrase my question with added support links to reconsider my point.

What I want to ask/share here is based on first zhouyondong_2012's ZSolver program progress. As per Sun Feb 12, 2012 9:03 pm post, CGame structure type defined Guess board size is G[33], but, in reply of Afmob reported crashes on Wed Mar 14, 2012 9:00 pm post:

After bugfix: I hope it is the last version. it doesn't affect speed. just G[33] to G[50] and CompF should be initialized to -1

And, JasonLion put together a small archive with the next to last version of zhouyundong_2012's solver on Thu Apr 04, 2013 8:52 pm post, in which guess board size increased from G[50] to G[60].

Now, keeping above fact in view, let me quote my question here again from one of my above post in this thread dated Tue Nov 17, 2015 11:24 am:

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?

How many maximum guess [i.e., trial and error] steps are required to solve either empty or some very hard, unsolvable through any/all known techniques Sudoku puzzle? 50 or 60?

R. Jamil

[JasonLion]

Your question is not well defined. ZSolve does not use "any/all known techniques", or anything even remotely close to that. It isn't even possible to define what "any/all known techniques" is. There are too many edge cases that are debatable, for example the "what is brute force and should brute force techniques be included" debate.

It is possible to set an upper bound of 64 guesses by considering the approach of not using any solving techniques and guessing every cell. No valid Sudoku puzzle can have fewer than 17 clues, leaving 64 cells to be guessed. I assume that adding solving techniques can't possibly increase that number. It is also presumably possible, with more work, to answer your question for well defined lists of solving techniques. But is is not possible to answer your question as stated.

Also, the ZSolve number is empirical. We run ZSolve on various puzzles and keep increasing the stack depth until it stops crashing. There isn't any proof of what the upper limit really is, just an empirical result that it is above 50 and quite unlikely to be above 60 (as nothing that crashes a stack of 60 elements has ever be observed). Intermediate values (between 50 and 60) were never tested.

[dobrichev]

This is an interesting question.
First, don't confuse total number of guesses during the solving process, with maximal guess depth required to solve the (empty) puzzle.
Considering the maximal depth and presence of the elementary techniques that clear the pencilmarks for the candidates that are in direct contradiction with all already set (given or guessed) cells, then the latest cell of any house will be solved without guessing, for example

Code: Select all

... ... ..X
... ... ..X
..X ..X ...

... ... ..X
... ... ..X
..X ..X ...

... ... ..X
... ... ..X
XX. XX. XX.


This gives maximal guess depth of 81 - 16 = 65 even if iterating over all solutions of an empty puzzle.

What is the best guessing strategy for empty puzzle that guarantees minimal guessing depth, and what is the actual depth?

[rjamil]

Hi,

Many thanks dobrichev for the clarification regarding total number of guesses during the solving process and maximal guess depth required to solve the (empty) puzzle.

What is the best guessing strategy for empty puzzle that guarantees minimal guessing depth, and what is the actual depth?

As per my findings, naked/hidden singles and with or without other techniques, total 47 guesses are required to solve empty Sudoku puzzle without backtracking means equal to 47 guess depth. (Am I right?)

Note: I have commented all techniques except naked single and guess-backtracking in my solver (i.e., this time excluding hidden single as well). The outcome shows as follows:

Code: Select all

... ... ..X
... ..X ..X
..X ..X ..X

.X. X.. .X.
... ... .X.
.XX ..X X.X

... ..X XXX
.XX XXX XXX
XXX XXX XXX

And the steps required to solve empty Sudoku puzzle in logical order are (as per attached file):
Naked Single = 36
Guess depth = 45

R. Jamil

[rjamil]

Hi,

I found interesting this site discussing about whether the blank Sudoku grid is diabolic or not. Also discussing about how to solve blank Sudoku puzzle without backtracking.

R. Jamil

[StrmCkr]

am i reading this thread correctly?

you want to start with a blank grid
1: fill in a number
2: apply solving techniques to reduce potential clue count
and repeat steps 1 and 2 until a a grid is fully solved? without back tracking or near minimal back tracking?

my solver had this programmed into it for a long time as its primary generator, the problem I found with this feature is that every time i added a new solving technique my generators "building a puzzle" time skyrocketed exponentially
as the remove excess clues function ended up taking more and more time to run through.

even then it would hit snags where inserting a clue would result in a zero solution grid, as some placements would "chain reduce" further then my "logic " could identify as potential errors
and id have to backtrack to undue that placement.

most of the grids it generated ended up being "none" minimal and id have to have a 2ndary function remove superfluous clues ensuring the puzzle was minimal.