another measure for inferior puzzles

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

another measure for inferior puzzles

Postby ab » Mon Jun 09, 2008 6:54 pm

With puzzles that can be solved by singles we can measure the number of steps needed to solve the puzzle. See the inferior thread for details:
http://forum.enjoysudoku.com/viewtopic.php?t=3609&postdays=0&postorder=asc&start=0

Also people talk about the number of narrow steps, which is another good measure of a singles' puzzle's difficulty. However with these puzzles we could measure the number of paths through the puzzle, or certainly get an upper limit on it. It's the product of the factorials of the number of clues that can be placed on each step. I calculated this for Tarek's 39 step puzzle and was surprised to find that it was 127401984. Maybe that's why noone has mentioned this as another measure for these puzzles before, it obviously quickly gets very large. It might be a useful way of ranking puzzles with the same number of steps.
ab
 
Posts: 451
Joined: 06 September 2005

Postby ab » Mon Jun 09, 2008 10:47 pm

thinking about it this is probably not an upper limit on the number of paths through the puzzle:!:
ab
 
Posts: 451
Joined: 06 September 2005

Postby Pat » Tue Jun 10, 2008 12:27 pm

ab wrote:people talk about the number of narrow steps,
which is another good measure of a singles' puzzle's difficulty.

However with these puzzles we could measure the number of paths through the puzzle---


the puzzle may become tough if there is a critical "single" -- if i happen to miss this one then i'm stuck ( or must use some non-"single" instead )
User avatar
Pat
 
Posts: 4056
Joined: 18 July 2005

Postby tarek » Tue Jun 10, 2008 12:29 pm

Hi ab,

it is an interesting point regarding the paths because this will bring us back to how people solve puzzles.

the narrow start path is the safest in regards to qualifying the solving path.

singles as you know can be divided into:

a.hidden singles.
a1. only in box
a2. only in column
a3. only in row
b.naked singles.


A narrow start path "1,1,1,...." is the most difficult puzzle.

if you decide to do the steps check by choosing to take out some of the above division out of the equation without a change in the number of steps & still solving it .... then you can prdict the solving path better.

if a batch breadth 1st solving tachnique with a2a2a3 & b being the heirarchy results in a similar steps to the combined hidden+naked singles step count .... then that would make yuo predict the solving path even better.

The narrow path is still the best predictor IMO.

tarek
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby Pat » Tue Jun 10, 2008 1:30 pm

    i'm trying to say that a particular "single" can be critical
    even where the step contains more than 1 "single"
      in this situation, narrowness will not detect criticality
User avatar
Pat
 
Posts: 4056
Joined: 18 July 2005

Postby tarek » Tue Jun 10, 2008 4:12 pm

Pat wrote:
    i'm trying to say that a particular "single" can be critical
    even where the step contains more than 1 "single"
      in this situation, narrowness will not detect criticality

A narrow step of 1 single is critical.
if the step has more than one single then there must be some way in telling if it is critical or not.

An attempt at a definition of critical single:

Code: Select all
Critical single:
an available single which if un-placed would render the rest of the puzzle unsolvable using singles only


tarek
[EDIT: Added "Rest of the" to the definition]
Last edited by tarek on Wed Jun 11, 2008 4:03 am, edited 1 time in total.
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby daj95376 » Tue Jun 10, 2008 6:27 pm

Inferior Puzzles are solved using Singles only -- through Steps. Each step involves the concurrent application of all Singles present. I propose the use of evaluated Steps.

If there is only one Single present for a Step, then it's certainly critical to advancing the solution. This leaves the question of deciding criticality when there are multiple Singles present.

If there are multiple Singles present and a Single doesn't create any new Singles, then I would classify this Single as non-critical and remove it from the Singles performed at this Step. This evaluation would be performed on every Single present at this Step. It would indicate if a lone Single is a critical choice at a given Step.

The total number of these evaluated Steps would be more indicative of what it takes to solve the puzzle with Singles. It's not perfect, but it's doable with a reasonable amount of effort.

===== ===== ===== ===== ===== ===== =====

A more complex way to evaluate the criticality of a Single is to temporarily lock it so that it's not allowed to be performed. You proceed solving the puzzle until you can't proceed any further using Singles. The number of candidates remaining would be an indication of the criticality of the original Single. This would be a more complex process of analyzing the criticality of each Single present at a Step.

In this approach, all Singles would be performed in a traditional Step after every Single is analyzed.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby Pat » Sun Jun 15, 2008 8:52 am

daj95376 wrote:
A more complex way to evaluate the criticality of a Single is to temporarily lock it so that it's not allowed to be performed. You proceed solving the puzzle until you can't proceed any further using Singles. The number of candidates remaining would be an indication of the criticality of the original Single. This would be a more complex process of analyzing the criticality of each Single present at a Step.

In this approach, all Singles would be performed in a traditional Step after every Single is analyzed.


i was only thinking of criticality in the absolute sense
( as in tarek's definition )
when this cell is locked-out,
the rest of the puzzle cannot be completed by "singles".
User avatar
Pat
 
Posts: 4056
Joined: 18 July 2005


Return to General