Does Using Brute-Force to solve a puzzle make it invalid

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

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby Mathimagics » Tue Oct 19, 2021 5:20 pm

Serg wrote:Did you add some logical rules for 16 x 16 Sudoku solver?

Not yet.

The current solver is simply a port of the 9x9 FSSS2 solver, with 256-bit wide bitmaps instead of 128-bit ones.

But it can easily be extended, and used to demonstrate the ideas discussed above, namely that more complex rules than singles will prove their worth on a larger grid than 9x9. The humungous solution space of 16x16, dwarfs that of 9x9 (16 is a planet, while 9 is a pea). That almost guarantees that any additional methods will speed up, rather than slow down, the solver.

Cheers
MM

PS: I too am interested in whether tdillon's solver is scalable to 16x16. I suspect it might be difficult, but he will tell us shortly.

Also, I think that creint's solver definitely is scalable, and thus we might be able to do some simple experiments.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1870
Joined: 27 May 2015
Location: Canberra

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby Serg » Tue Oct 19, 2021 5:35 pm

Hi, rjamil!
I think the difference between "backtracking" and "brute-force" Sudoku solvers is meaningful for purists only. These names for Sudoku solvers are equivalent in wide sense. But since we started discussing this topic, I should say that my unerstanding of brute-force Sudoku solving procedure differs from yours.

I think that brute-force Sudoku solving technique is selection of any combination of digits 1-9 in all empty cells, even as meaningless as ones for all empty cells. Only when all empty cells are filled (and we have some solution to check), we check if it meets the rules of sudoku. If that solution contains the same digits in some row/column/box, solution is rejected and we form another (full) solution, changing some digits in empty cells. This strategy is insanely ineffective, so noone use it in practice, but instead all use backtracking procedure.

It's a paradox, but I think all "logical" Sudoku solver (implemented in procedural programming languages) are backtracking solvers. At every step they can use maybe very sophisticated logical methods just to get another partial solution. There is no principal difference between a solver checking naked/hidden singles only and a solver checking forcing chains, exosets, etc.

Serg

[Edited] I deleted wrong statement.
Last edited by Serg on Tue Oct 19, 2021 7:46 pm, edited 1 time in total.
Serg
2018 Supporter
 
Posts: 785
Joined: 01 June 2010
Location: Russia

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby Serg » Tue Oct 19, 2021 7:42 pm

Hi, all!
After some pondering I propose such Sudoku solvers classification.

- "Backtracking" or universal Sudoku solvers. They deal with puzzles having 0, 1 or multiple solutions. The main goal of these solvers - to find all/first/first two solutions (or count all/first 2 solutions) as fast as possible. Their implementations are based on backtracking algorithm reinforced by some logical techniques for speed. These solvers are the fastest. Examples: fsss2, JCZsolver, tdoku, etc. Some people call these solvers "brute-force".

- "Human style" solvers. They deal with puzzles having unique solution only. The goal of these solvers - to find unique solution using some combination of logical techniques. If at some step no techniques can be applied, these solvers says the puzzle has no human logic solution. Such solvers differ by their applicability (i.e. by number of puzzles they can solve in human style), elegancy of solutions, etc. Before "human style" solvers usage one must check - is given puzzle valid? (i.e. has it unique solution?) by some backtracking solver.

Serg

[Edited. I corrected a typo.]
Serg
2018 Supporter
 
Posts: 785
Joined: 01 June 2010
Location: Russia

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby tdillon » Wed Oct 20, 2021 7:51 am

Serg wrote:Did you checked use of other logical solving rules (beyond naked/hidden singles and locked candidates) in your "tdoku" solver?

Hi Serg,

Tdoku also has exactly-three constraints over minirows and minicols (what I was calling triads). I think these correspond to locked triples and hidden triples (when confined to a minirow or minicol)

Tom
tdillon
 
Posts: 60
Joined: 14 June 2019

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby tdillon » Wed Oct 20, 2021 8:01 am

Mathimagics wrote:PS: I too am interested in whether tdillon's solver is scalable to 16x16. I suspect it might be difficult, but he will tell us shortly.

Hi Mathimagics,

I think it would be pretty easy to extend tdoku to the 16x16 case. In a way it's a more natural fit than 9x9 since it would fully exploit 256 bit registers. But tdoku has had a lot of micro-optimization for the 9x9 case, and it would take some effort to tune it back up again. For example, I'm not sure the special representation I have of band configurations would be worthwhile for 16x16, and it might be simpler to just represent band state with a matrix of positive triads.

Totally agree that more expensive heuristics and constraint propagation will become worthwhile for 16x16 and larger. You can also see this reflected in the relative performance gains of Minisat when compared to fsss2 and tdoku on difficult pencilmark sudoku.

Tom
tdillon
 
Posts: 60
Joined: 14 June 2019

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby rjamil » Wed Oct 20, 2021 11:56 am

Hi Serg,

Serg wrote:Hi, rjamil!
I think the difference between "backtracking" and "brute-force" Sudoku solvers is meaningful for purists only. These names for Sudoku solvers are equivalent in wide sense. But since we started discussing this topic, I should say that my unerstanding of brute-force Sudoku solving procedure differs from yours.

Serg

First of all, many thanks for your valuable response.

I think, there are two types of problems that need to be solve by two different type of Brute-Force (exhaustive) algorithms, i.e., deterministic and randomized algorithms. See here and here and here.

Based on my above mentioned assumption, your definition also seems to be right.

R. Jamil
Image
rjamil
 
Posts: 669
Joined: 15 October 2014
Location: Karachi, Pakistan

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby RSW » Thu Oct 21, 2021 8:04 am

Mathimagics wrote:FSSS is a simple backtracking solver with naked single + hidden single checking as the fundamental search-tree pruning method.

It gets its speed advantage by a highly efficient representation of the current puzzle state, using bitmaps. This is designed in such a way as to make the testing for hidden singles more efficient.

This is good to know.
When I set up my own brute force solver, I never considered doing it without some kind of singles checking. It was trivial to include naked singles, but hidden singles were more complicated due to the data structure that I chose. I'm also using bit mapping, but would need to include a second set of bit maps to handle hidden singles. In most cases, just the naked singles eliminations were sufficient for my needs. But rare puzzles would be horrendously slow to solve this way. So, I added one hidden singles scan at the beginning, and then reverted to just naked singles for the rest of the solution. This sped things up considerably, but there are still occasional puzzles where this isn't sufficient. So, I'll probably add a second set of bit patterns to handle the hidden singles at each level.

@rjamil
Great animation!
RSW
 
Posts: 263
Joined: 01 December 2018
Location: Western Canada

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby m_b_metcalf » Thu Oct 21, 2021 8:20 am

RSW wrote:@rjamil
Great animation!

Indeed, but if I stare at the cells r5c3 or r6c2 I sometimes see the value 7 flash by, but that value cannot be in the pencil marks for those cells. So why are they shown?

Thanks,

Mike
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 13094
Joined: 15 May 2006
Location: Berlin

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby Mathimagics » Thu Oct 21, 2021 9:06 am

User avatar
Mathimagics
2017 Supporter
 
Posts: 1870
Joined: 27 May 2015
Location: Canberra

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby RSW » Thu Oct 21, 2021 9:35 am


Now I'm totally disillusioned. :(
RSW
 
Posts: 263
Joined: 01 December 2018
Location: Western Canada

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby m_b_metcalf » Thu Oct 21, 2021 10:17 am



MM, Thanks. I'll clearly have to pose my simple-minded question elsewhere!

Mike
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 13094
Joined: 15 May 2006
Location: Berlin

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby Mathimagics » Thu Oct 21, 2021 8:46 pm

Mike, my apologies, I did fail to answer your question.

There are no pencilmarks in this simplified solver. It is a backtracking solver reduced to its purest/simplest form.

For each unsolved cell (left to right) the solver the tests all possible candidates 1 to 9. The current cell's candidate value is shown in blue. If this value contradicts the Sudoku rules, the cell is cleared and the solver returns (backtracks), and moves on to the next value.

So, for example, you will occasionally see a red 7 appear in box 4, but since this always results in a contradiction (since box 4 already has a 7), it immediately disappears as the search procedure backtracks.

Cheers
MM
Last edited by Mathimagics on Sat Oct 23, 2021 2:07 am, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1870
Joined: 27 May 2015
Location: Canberra

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby m_b_metcalf » Fri Oct 22, 2021 7:59 pm

Mathimagics wrote:There are no pencilmarks in this simplified solver. It is a backtracking solver reduced to its purest/simplest form.


MM, Thanks. I just didn't realise that this simplest form was of any practical use. I have a number of backtracking solvers. They all involve:

1. Set up a list of pencil marks (valid candidate values).
2. Solve as far as possible for singles.
3. 'Condition' the puzzle by rearranging its row/columns/bands so as to have the highest density of givens in its top left corner and the lowest in the bottom right.

Thus, the statement "A brute force algorithm visits the empty cells in some order, filling in digits sequentially, or backtracking when the number is found to be not valid." becomes for me

"My brute force algorithm visits the empty cells in an optimized order, filling in valid candidates sequentially, or backtracking when the number is found to be not valid."

Regards,

Mike
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 13094
Joined: 15 May 2006
Location: Berlin

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby Mathimagics » Fri Oct 22, 2021 9:07 pm

The method of visiting (unsolved) cells in an optimal order is what I called the NCS (next cell selection) strategy in this old thread, the rather flippantly titled Guess Theory.

There I make a general point that a depth-first search solver will inevitably encounter some pathological cases where its NCS is sub-optimal. This is not usually an issue for 9x9 solvers, but becomes a serious issue for 16x16.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1870
Joined: 27 May 2015
Location: Canberra

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby rjamil » Fri Oct 22, 2021 9:28 pm

Hi Mike,

m_b_metcalf wrote:1. Set up a list of pencil marks (valid candidate values).

Well, by setting up a list of valid candidate values at initial puzzle state and/or after each step, instead of all 1 to 9 values, will violate brute-force definition and should be called T&E / guessing algorithm.

R. Jamil
rjamil
 
Posts: 669
Joined: 15 October 2014
Location: Karachi, Pakistan

PreviousNext

Return to General