Question

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

Postby tarek » Mon Jan 09, 2006 2:35 am

ronk wrote: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.
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Postby bennys » Mon Jan 09, 2006 4:07 am

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.
bennys
 
Posts: 156
Joined: 28 September 2005

Postby tarek » Mon Jan 09, 2006 4:23 am

ronk wrote: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
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Postby gsf » Mon Jan 09, 2006 4:47 am

ronk wrote: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
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ronk » Mon Jan 09, 2006 12:12 pm

gsf wrote:{ 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?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby gsf » Tue Jan 10, 2006 8:48 am

ronk wrote:
gsf wrote:{ 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
gsf wrote: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
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ronk » Tue Jan 10, 2006 10:57 am

gsf wrote:from the paragraph before the quote
gsf wrote: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.:D

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
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby gsf » Tue Jan 10, 2006 2:51 pm

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

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
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ronk » Tue Jan 10, 2006 3:09 pm

gsf wrote:
ronk wrote: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?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby gsf » Tue Jan 10, 2006 11:52 pm

ronk wrote: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()
Last edited by gsf on Tue Jan 10, 2006 10:14 pm, edited 1 time in total.
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ronk » Wed Jan 11, 2006 1:23 am

gsf wrote:
ronk wrote:How then does the forward check advance the puzzle to a solution?

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

Thanks for the comprehensive reply, Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby evert » Tue Jan 17, 2006 9:37 pm

gsf on Sudoku Programmers forum wrote: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.

bennys wrote: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?
evert
 
Posts: 186
Joined: 26 August 2005

Postby udosuk » Wed Sep 13, 2006 12:55 pm

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]
Last edited by udosuk on Wed Sep 13, 2006 3:10 pm, edited 2 times in total.
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby ronk » Wed Sep 13, 2006 1:11 pm

duplicate deleted
Last edited by ronk on Wed Sep 13, 2006 11:00 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ronk » Wed Sep 13, 2006 1:11 pm

udosuk wrote: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
Last edited by ronk on Wed Sep 13, 2006 5:39 pm, edited 4 times in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext

Return to General