The New Sudoku Players' Forum

[tarek]

I believed *every* puzzle could be progressed to a solution.

That is absolutely right. Any puzzle with a unique solution can be solved using T&E.

after a trial you search for the error, Now, the depth of search will also decide if you can reach that contradiction, if you use single elimination only (hidden/naked) that should do the trick most of the time. In the few cases where you need techniques higher than that to establish elimination & therfore a contradiction, you'll be stuck if u use single eliminations only.

What you used there is an advanced technique following T&E, you will crack EVERY puzzle that way.

[bennys]

I am not sure at all, actually I think that for any 'reasonable' set of technics there will be a puzzle that we will not be able to solve that way.
To find that puzzle however that is another issue.

[tarek]

would you please post the sequence of eliminations for puzzle #2?

I made a mistake there, What I was intending to say is that #77 was AN exception not the ONLY exception.

Puzzle #2 Also required 1 deep Guess. which came at this stage.

Code: Select all

*-----------------------------------------------------------------------------------*
| 7        126      8       | 459      4569     4569    | 3        1456     125     |
| 49       36       3469    | 2        3456     1       | 4679     4578     578     |
| 5        1236     123469  | 78       346      78      | 2469     146      129     |
|---------------------------+---------------------------+---------------------------|
| 189      4        1579    | 3579     59       3579    | 178      2        6       |
| 3        1267     1269    | 479      8        24679   | 147      1457     157     |
| 268      5678     2567    | 1        2456     2467    | 478      9        3       |
|---------------------------+---------------------------+---------------------------|
| 128      9        1357    | 6        125      2358    | 127      1378     4       |
| 12468    12368    12346   | 3489     7        23489   | 5        1368     1289    |
| 12468    3578     1234567 | 34589    1249     234589  | 12679    13678    12789   |
*-----------------------------------------------------------------------------------*
5 in r4c5 would lead to a contradiction (Complex Guess)


regrads,

tarek

[gsf]

AFAIK there are only two known puzzles that do not fall to the above method. So if, after each guess, you allow more advanced techniques than naked singles and hidden singles ... I doubt a puzzle exists that would not be thusly solved.

this method is closely related to a tree search with a 1 level forward check
as you noted, differences in the constraints applied by the search and
forward check may result in different backtrack behavior
also the amount and type of iteration applied in the forward check would
also affect the search

most efficient for 9x9 and higher order sudoku and QWH seems to be to
use the 2 simplest constraints (force by candidate and force by row/col/box count)
and to iterate the forward check as long as holes are eliminated, i.e.,
redo the forward check if any cell is solved during the check but
don't redo if there is only candidate elimination

{ 2 3 77 84 } from top1465 cause my solver to guess but these are the
only ones out of a ~250M survey

[ronk]

{ 2 3 77 84 } from top1465 cause my solver to guess but these are the only ones out of a ~250M survey

If you mean all others are solved with only "logical" techniques, that's phenomenal IMO.

What three (or more) advanced techniques does your solver use that mainly accounts for that performance?

[gsf]

{ 2 3 77 84 } from top1465 cause my solver to guess but these are the only ones out of a ~250M survey

If you mean all others are solved with only "logical" techniques, that's phenomenal IMO.

What three (or more) advanced techniques does your solver use that mainly accounts for that performance?

yes, all others are solved without guessing, but its not via a human-solver-friendly method

from the paragraph before the quote

use the 2 simplest constraints (force by candidate and force by row/col/box count)
and iterate the forward check as long as holes are eliminated

the "2 simple constraints" are the logical part subjected to the brute force
forward check that loops through all candidates in all unsolved cells

the cited puzzles kick in a backtrack search that re-applies the forward check

solver speed is ~1800/sec/Ghz for the top1465 and ~6400/sec/Ghz on a ~225M random catalog

[ronk]

from the paragraph before the quote

use the 2 simplest constraints (force by candidate and force by row/col/box count)
and iterate the forward check as long as holes are eliminated

the "2 simple constraints" are the logical part subjected to the brute force
forward check that loops through all candidates in all unsolved cells

You're talking a languague I'm not familiar with, so I feel like I'm in a foreign country without a translator.

I can only guess that ...

1. Your "force by candidate" is my "naked singles" and "hidden singles",
2. Your "force by row/col/box count" is my "locked candidates", but the word "count" doesn't make sense for that,
3. Your "brute force forward check" is my "guess", and
4. Your "holes are eliminated" are my "candidate placements" or "cell fills"

Confused, Ron

[gsf]

You're talking a languague I'm not familiar with, so I feel like I'm in a foreign country without a translator.

sorry for the mixed terminology
I included refs to some ancient ai work along with QWH (quasigroup with holes == latin square completion)

1. Your "force by candidate" is my "naked singles" and "hidden singles" -- a cell with only one candidate value
2. Your "force by row/col/box count" is my "locked candidates", but the word "count" doesn't make sense for that -- only one cell in a row/col/box permits placement of the candidate -- I implement this by counters updated with each placement
3. Your "brute force forward check" is my "guess" -- no, a 1 level forward check is a loop through all unsolved cells and all candidates in those cells -- a non-human procedure, but not a guess
4. Your "holes are eliminated" are my "candidate placements" or "cell fills" -- yes, hole is a QWH crossover

the guess (and backtrack) happens when the forward check makes no progress
make no progress can be combinations of:

1. no candidate value changes
2. no cell placement changes

the forward check can be iterated when progress is made before making a guess and backtracking
I use no cell placement changes because the other tends to get picked off immediately on the next backtrack level

[ronk]

Your "brute force forward check" is my "guess"

no, a 1 level forward check is a loop through all unsolved cells and all candidates in those cells -- a non-human procedure, but not a guess

How then does the forward check advance the puzzle to a solution?

[gsf]

How then does the forward check advance the puzzle to a solution?

via three functions:

1. move() assigns a value to a cell and iteratively propagates the constraints to all the other cells
2. forward_check() for each unsolved cell it calls move() for each candidate value on a copy of the grid; if only one of the candidates succeeds then the cell is assigned that value; otherwise the union of all changed values for the assignments for this cell are used to update the candidate lists for the other unsolved cells (which may result in more assignments) -- frisch mentions this for his ocaml solver
3. backtrack() when forward check fails to progress a "good" cell and candidate value are chosen and assigned via move() using standard DFS backtrack logic; a "good" cell is one which has the minmax # unsolved cells for all cells examined by forward_check()
   

[ronk]

How then does the forward check advance the puzzle to a solution?

via three functions: ..................................

Thanks for the comprehensive reply, Ron

[evert]

A constrained puzzle is solvable by constraint propagation (no trial
and error.)
A magic cell set is the smallest set of solution cells with the
smallest number of candidate values that produces a constrained puzzle.

Its not what I am looking for .look at the example in my previous post where I show that using the method that I am talking about it can be solved
And that is because I allow removing candidates.

Does allow removing candidates make the difference? So what Bennys looks for is different from a 2-constraint?

[udosuk]

So, to repropose what bennys asked, but to restrict the techniques used to just naked singles and hidden singles, is there such a puzzle state, that:

1. No more moves of naked singles and hidden singles are available.

2. For each of the undetermined cells, one by one we assign all possible candidates, and then try to apply the naked singles and hidden singles techniques, but all of these assignments lead to the puzzle being stuck (neither leading to the final solution nor to a contradiction).

Is there any puzzle state like this?

Or, equivalently, is a program using naked singles + hidden singles + 1-level T&E able to solve all valid puzzles?

[Typos corrected]

[ronk]

duplicate deleted

[ronk]

does a program using naked singles + hidden singles + 1-level T&E able to solve all valid puzzles?

No. Puzzle #77 of the top1465 (below) requires more than singles. Also #2 and #3 from the same set, six of Ocean's "diagonal symmetry" puzzles and eighteen of Ocean's "X" puzzles.

Code: Select all

 7..|...|4..
 .2.|.7.|.8.
 ..3|..8|..9
 ---+---+---
 ...|5..|3..
 .6.|.2.|.9.
 ..1|..7|..6
 ---+---+---
 ...|3..|9..
 .3.|.4.|.6.
 ..9|..1|.35