Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

NEWS:
(My) Nishio defintion

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
rubylips

Joined: 07 Apr 2005
Posts: 62
:
Location: London

Items
PostPosted: Thu Apr 14, 2005 11:29 pm    Post subject: (My) Nishio defintion Reply with quote

Wayne Gould coined the term 'Nishio' to describe a technique - dismissed by some as trial-and-error - originally devised by the Sudoku puzzle compiler Nishio-san. Since I don't have access to the official explanation, I've pieced together a plausible definition from the available snippets of information.

The following article has been copied across from the old Google Sudoku Programmers group.

Quote:
Definition:

Given a value and a candidate cell, the Nishio rule considers whether
the placement of the given value within the given cell would allow the
remaining instances of that value to be placed. The remaining
placements have be trivial, i.e. each value has to be placed in a row,
column or box where there exists just a single candidate cell - where
no trivial placement exists, the candidate move cannot be rejected.
When the remaining values cannot be placed, the initial candidate move
is eliminated.

Comments:

Some people regard the rule as controversial because it relies upon
reductio ad absurdum - however, the rule cannot be classified as
trial-and-error because it always leaves the grid in a valid state. The
rule is slow to apply (because in most implementations it analyses each
available candidate move), so it should be applied after other
available rules. Nishio is more general than X-Wings (which doesn't
rely upon reductio ad absurdum), which is to say that any move
eliminated by X-Wings will be eliminated by Nishio, but X-Wings is
much, much faster and should be applied before Nishio. I have found
experimentally that, even for larger grids, the introduction of Nishio
slows the solution process, i.e. even when Nishio uncovers the value
for a cell, it would have probably been quicker to guess! Nevertheless,
Nishio is a powerful rule that performs eliminations that other rules
miss. Moreover, it often reveals patterns of eliminated moves that hint
at the existence of faster, less general rules such as X-Wings.


Here's a pseudo-code implementation:

Code:
An algorithm to test whether it's possible to eliminate the possible move (r,c):=v by the Nishio method.

Create an array with the dimensions of the grid and fill each element
with one of three values:
DEFINITE if the corresponding grid cell is occupied by v.
POSSIBLE if the corresponding grid cell could be occupied by v.
NULL if the corresponding grid cell could not be occupied by v.


The array is assumed to be in a good state, by which we mean:
i. Each DEFINITE element will have only NULL values in the other
elements in its row, cell and box.
ii. Each row, column and box will have at least one DEFINITE or
POSSIBLE element.


Set CANDIDATE to (r,c). [Element (r,c) will have been set to POSSIBLE
by our initial hypothesis].


while(CANDIDATE is set){

    Change the status of CANDIDATE to DEFINITE.
    Set the remaining POSSIBLE elements from the row, column and box of CANDIDATE to NULL.
    Unset CANDIDATE.

    For each row, column and box {
        Count the number of DEFINITE and POSSIBLE elements.
        Stop the count and move on to the next row, column or box if:
        i. A DEFINITE element has been found, or
        ii. Two or more POSSIBLE elements have been found.

        If no POSSIBLE element has been found, reject the original
hypothesis.

        One POSSIBLE element has been found.
        If CANDIDATE is unset, set it to the cell corresponding to the
POSSIBLE element.
    }
}

There's no reason to reject the original hypothesis if we reach here.


Here are some puzzles that feature the Nishio pattern:

Quote:
Puzzle 1:

Code:
 . . 6 * . . . * . . .
 . 9 . * . . . * . 2 1
 . 5 . * . 3 8 * . . .
**********************
 3 . . * . . . * 7 . .
 . . . * 9 . 5 * . . .
 . . 1 * . . . * . . 6
**********************
 . . . * 2 4 . * . 9 .
 7 8 . * . . . * . 4 .
 . . . * . . . * 3 . .


Puzzle 2:

Code:
 . 2 . * . . . * 4 . .
 . . . * . . . * . 8 .
 . . . * 9 1 . * . 5 .
**********************
 9 . . * . . . * 6 . .
 7 . . * 5 . 6 * . . 3
 . . 1 * . . . * . . 7
**********************
 . 5 . * . 7 3 * . . .
 . 4 . * . . . * . . .
 . . 8 * . . . * . 2 .


Puzzle 3:

Code:
 1 . . * . . . * 7 . .
 . 2 . * . . . * 5 . .
 6 . . * 3 8 . * . . .
**********************
 . 7 8 * . . . * . . .
 . . . * 6 . 9 * . . .
 . . . * . . . * 1 4 .
**********************
 . . . * . 2 5 * . . 9
 . . 3 * . . . * . 6 .
 . . 4 * . . . * . . 2


Puzzle 4:

Code:
 . 7 . * . . 3 * 2 . .
 . . 5 * 6 9 . * . . .
 . . . * . . . * . . .
**********************
 . . . * . 8 . * 7 . 3
 . . 4 * . . . * 8 . .
 9 . 1 * . 2 . * . . .
**********************
 . . . * . . . * . . .
 . . . * . 5 8 * 4 . .
 . . 6 * 4 . . * . 1 .
Back to top
View user's profile Send private message Visit poster's website
IJ

Joined: 15 Apr 2005
Posts: 16
:

Items
PostPosted: Mon Apr 18, 2005 4:58 pm    Post subject: Reply with quote

Well, I guess I've let this sit for long enough...

I'd just like to re-iterate my pennysworth and say that this method is clearly T&E - the argument that because it leaves a grid in a valid state it isn't Trial and Error is, being generous, erroneous. After all, it can hardly be denied that T&E can be used to solve any puzzle, and always gets the right answer - how is this an invalid state?

The definition of T&E is self evident - you trial something and look for a resulting error. This is exactly what the process above is all about.

I don't really want to rehash these arguments, and as I've said before, this is a neat method. I just thought that we ought to have both views here. To me at least, it is unarguably in the T&E camp, and doesn't compare at all with the beatiful Swordfish identified by the same author.

I'll start another thread shortly to describe for anyone interested a pattern (now called the Jacko) that can also be used to resolve the only positively identified instance of Nishio (Wayne Gould said "That's a Nishio, that is")
Back to top
View user's profile Send private message
rubylips

Joined: 07 Apr 2005
Posts: 62
:
Location: London

Items
PostPosted: Mon Apr 18, 2005 6:34 pm    Post subject: Reply with quote

Here we go again ... Wink

I don't disagree with the sentiment that Nishio is T & E - in fact, I'm happy to concede that it is T & E - it's just that I think that there are varying degrees of T & E and that Nishio is less T & E than the Total Guess is. I see a hierarchy of patterns:

X-Wings < Swordfish < Nishio < Total Guess

Whereas anyone from the Pappocom world will regard the precise point at which the justification of a move depends upon T & E as critical, anyone from a more general world who has already implemented the Total Guess (almost certainly necessary in order to solve all conceivable Sudoku puzzles) simply won't care - the fact that Nishio leads to a more helpful logical explanation that the Total Guess will be ample justification for its use.

Consider Puzzle 1 from the Nishio examples. With Nishio enabled, my solver tells me at the critical spot:

31. The values 5 and 8 occupy the cells (9,4) and (9,5) in some order.
The move (4,2):= 6 would make it impossible to place the remaining 6s.
The value 2 is the only candidate for the cell (4,2).

(The second statement is due to Nishio).

With Nishio disabled, my solver tells me:

31. The values 5 and 8 occupy the cells (9,4) and (9,5) in some order.
The cell (9,6) is one of 2 candidates for the value 6 in Row 9.

i.e. it makes a complete guess as to the position of the 6 in Row 9 and provides no semblance of a logical justification.

A further benefit of Nishio over the Total Guess is that in some sense it highlights the candidate moves that are 'easiest' to eliminate. Someone who wished to identify a new pattern would be well advised to seek puzzles with no apparent 'purely logical' solution yet which are solved by Nishio. A new pattern (that doesn't rely on T & E) might lurk within the eliminated moves. Remember that X-Wings and Swordfish are special cases of Nishio.

In summary, I don't disagree with the opinion that Nishio is less valid than X-Wings of Swordfish or even that it's T&E - it's just that I think it's more desirable than the Total Guess.
Back to top
View user's profile Send private message Visit poster's website
rallveird

Joined: 13 Jun 2005
Posts: 31
:

Items
PostPosted: Wed Jun 15, 2005 7:19 pm    Post subject: Reply with quote

I've been trying to understand the Nishio and I really can't see that it's not a Total Guess function with optimalisation code in it.

When you make a recursive routine you sometimes add optimalisation code in it to remove obvious trees that are not the best. Eg, in the Shortest Path problem you usually add contraints as "if the sum of the graf is greater than the smallest solution graf we don't investigate the rest of that tree".

Total Guess is not Total Guess.
A total guess check of sudokus can be implemented in many ways.

The first obvious is start at (1,1) and check all the empty cells recursively for every numbers. This is a basic recursive check and will need to check all possible permutations to find the solution (and to check that's not more than 1 solution). If the board starts with 30 cells, you need to do 9^51 permutations, which is quite a lot.

But this method is overkill. An obvious optimalisation is to only check the legal numbers for a cell. This has some overhead finding the legal numbers but will greatly reduce the permutations. Actually with 30 starting cells you'll probably have less than 10.000 permutations on all possible boards.

But this method is overkill too. A better way is to not start at (1,1) but rather find the cell with least possible numbers, then check recursively from there over all the cells. This method will probably reduce the permutations to less than 500 for 30 starting cells.

(And then we can start checking which of the least possible number cell to check first to get even less permutation. But when you're down to 500 permutation that check will probably cost you more to do than just try the permutations)

As you see, some optimalisation of the standard Total Guess greatly enhance the solving process. But it's still a Total Guess strategy. Where does it say that a Total Guess needs to start at (1,1) and check all possible solutions?

Nishio is Total Guess
I've been thinking about a T & E function which will do this:

Take the solution grid and try to remove a number from a cell with more than 2 numbers in it. Will this result to an empty cell in the solution grid? If yes, we know then that number isn't a solution for that cell. We do this recursively over all the cells in the solution grid, trying to remove all the possibly numbers.

Isn't this just a optimalisation of the Total Guess? What I do is trying a number and testing if it's possible as a solution. It's the same as when I in Total Guess try a number and checking if that's a possible solution. The difference is in a normal Total Guess I check the legality when I've populated all the cells, but here I can check for legality much earlier in the process. Hey, stop. Wasn't this exactly what you did in the optimalisations of Total Guess when you checked for legal numbers to check? Yes.

My point is. All types of "trying a number" is a Total Guess, with different optimalisations. Nishio is trying a number, therefore it's a Total Guess function with some clever optimalisation.

Nishio gives us more info than Total Guess
No, that's wrong. It's perfectly possible to code a Total Guess where the optimalisation code tells you what the next move should be. This is what Nishio is. Take my function above. When you have tested a number and found out that removing that cell ([5,5]=4) will remove all numbers from another cell ([6,7]) you can say "Cell [5,5] can't be 4 since cell [6,7] will have no solutions."

Actually, when using the optimalisation for Total Guess where you only check legal numbers you could say "[5,5]=4 is not possible since [5,4] is 4". (that's what you do when you populate the solution grid)

Conclution
Nishio is an optimalisation of Total Guess. Using a Nishio optimalisation you can remove possible numbers to check for a cell.[/url]
Back to top
View user's profile Send private message
Merri

Joined: 02 Aug 2005
Posts: 44
:

Items
PostPosted: Thu Aug 18, 2005 3:40 pm    Post subject: Re: (My) Nishio defintion Reply with quote

rubylips wrote:
The rule is slow to apply (because in most implementations it analyses each available candidate move), so it should be applied after other available rules. Nishio is more general than X-Wings (which doesn't rely upon reductio ad absurdum), which is to say that any move eliminated by X-Wings will be eliminated by Nishio, but X-Wings is much, much faster and should be applied before Nishio. I have found experimentally that, even for larger grids, the introduction of Nishio slows the solution process, i.e. even when Nishio uncovers the value for a cell, it would have probably been quicker to guess! Nevertheless, Nishio is a powerful rule that performs eliminations that other rules miss. Moreover, it often reveals patterns of eliminated moves that hint at the existence of faster, less general rules such as X-Wings.


I have to disagree about the speed of Nishio. I were well able to make Nishio work rather fast. However, the speed gain it gave me was minimal. A lot depends on the amount of optimization. Nishio should also be combined with the most basic logic, known as naked single or sole candidate: this logic should be ran to its completion before Nishio does its final checking for validity.

Details of my computer speed optimized logic:

- look for naked singles until none can be found; try other logics:
-- look for hidden singles; return to naked singles if success
--- look for naked subset; return to naked singles if success
---- if still unsolved, exit
- if solved, return True; otherwise look for cell with least candidates
- start backtracking from the given cell; return True if success
-- make a copy of all optimization arrays
-- select one of the candidates of the cell, apply it to the cell
-- look for naked singles until none can be found; try Nishio
--- if Nishio succeeds, look for naked singles until none can be found
---- check for validity
----- look for hidden singles; return to naked singles if success
------ look for naked subset; return to naked singles if success
-- if valid but not solved, look for another cell with least candidates; backtrack
-- if valid and solved, return True and end all backtracking
-- if failed Nishio or if unvalid, reset all optimization arrays
-- unmark candidate value, prepare to try another one

This far I haven't found a faster algorithm, ie. all other programs I've tried have been slower.
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 454
:
Location: germany

Items
PostPosted: Fri Aug 19, 2005 3:24 am    Post subject: Reply with quote

hi Merri, thanks for posting this !

>Details of my computer speed optimized logic:
>- look for naked singles until none can be found; try other logics:

OK, I looked up the terms. Found them with google at "sadman".
"Copyrighted" , well.

>-- look for hidden singles; return to naked singles if success

Exact-cover method won't distinguish naked and hidden singles.
They are just "constraints". 81 "naked" constraints and 243 "hidden"
constraints, if you want. How much goes your speed down when
stop distinguishing them ?

>--- look for naked subset; return to naked singles if success

again, how much speed increase gives this ?
When you use a placement which you could have excluded by
"naked pairs" in backtracking, then it will lead immediately to a
contradiction. Naked triples etc. should also be no problem.

>---- if still unsolved, exit
>- if solved, return True; otherwise look for cell with least candidates

ignoring the other constraints ?
Suppose least candidates for a cell would be 3, but e.g.
symbol 7 has only possible 2 places in row 8. That would
be 2 candidates for constraint r8s7 and preferrable to your 3.
Did you test it ? Was it too slow to detect these ?

>- start backtracking from the given cell; return True if success
>-- make a copy of all optimization arrays

? what optimization arrays do you use ?
Isn't it faster to undo the changes which you will make instead
of storing the whole array ?

>-- select one of the candidates of the cell, apply it to the cell
>-- look for naked singles until none can be found; try Nishio

no looking for hidden singles here ?
"Nishio" involves looking for 9 symbols times 81 cells, whether that
placement can lead to a completion of that symbol.
I assume this is the bipartite matching problem mentioned in
the Eppstein-paper.

>--- if Nishio succeeds, look for naked singles until none can be found

again no hidden singles

>---- check for validity

? that's what this is all about and motivates the previous steps.
What's new here ?

>----- look for hidden singles; return to naked singles if success

ahh, here they are. They were hidden behind validity-checking. But why ?

>------ look for naked subset; return to naked singles if success
>-- if valid but not solved, look for another cell with least candidates; backtrack
>-- if valid and solved, return True and end all backtracking
>-- if failed Nishio or if unvalid, reset all optimization arrays
>-- unmark candidate value, prepare to try another one

this is not quite clear, but I got the idea.

>This far I haven't found a faster algorithm, ie. all other programs
>I've tried have been slower.

what all have you tried ? I assume you tried a lot, else you wouldn't
have written this.

Have you tried to vary the method depending on the number of cells placed ?
I assuming filling the last clues requires a different strategy than
filling the first clues.


When you are looking for singles, where do you start ?
Always at the first cell ?
Isn't it better to search for all singles at once
and store them ?
Or start looking for those singles with the same
row,column,symbol as the last placement ?
Or even somehow restrict it to those ? - by looking
for which possible new singles a placement can create

have you tried anything for larger sudokus ?


cheers, Guenter.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Merri

Joined: 02 Aug 2005
Posts: 44
:

Items
PostPosted: Fri Aug 19, 2005 11:15 am    Post subject: Reply with quote

dukuso wrote:
Exact-cover method won't distinguish naked and hidden singles.
They are just "constraints". 81 "naked" constraints and 243 "hidden"
constraints, if you want. How much goes your speed down when
stop distinguishing them ?

I have to look for them separately, because both are found with completely different code. My code would require a complete rewrite to completely different direction if I didn't distinguish them... really, I can't think of a method that would find both of them quickly. Atleast with the way I've done my program (still can't tell the details about that due to the contest; one week to go).

dukuso wrote:
again, how much speed increase gives this ?
When you use a placement which you could have excluded by
"naked pairs" in backtracking, then it will lead immediately to a
contradiction. Naked triples etc. should also be no problem.


It drops down the need for backtracking by lessening the number of possibles.

dukuso wrote:
ignoring the other constraints ?
Suppose least candidates for a cell would be 3, but e.g.
symbol 7 has only possible 2 places in row 8. That would
be 2 candidates for constraint r8s7 and preferrable to your 3.
Did you test it ? Was it too slow to detect these ?


It would require looping through the whole sudoku board atleast three times where as looking for the least candidates takes only one loop. It would also be pretty hard to optimize, atleast with the way I've done it.

dukuso wrote:
what optimization arrays do you use ?
Isn't it faster to undo the changes which you will make instead
of storing the whole array ?

It is slow to store all the changes done.

dukuso wrote:
no looking for hidden singles here ?
"Nishio" involves looking for 9 symbols times 81 cells, whether that
placement can lead to a completion of that symbol.
I assume this is the bipartite matching problem mentioned in
the Eppstein-paper.

It can be highly optimized. However, I've now left out Nishio as I figured out I actually made other optimizations as well which helped nicely. Nishio actually caused a few ms of slowdown. So, not fast enough even after optimizations. Also, my Nishio only looked for the changed value... I never picked up any place where it said to look for all nine "symbols".

Detecting hidden singles caused a slowdown by 1/7.

dukuso wrote:
? that's what this is all about and motivates the previous steps.
What's new here ?


Well, as can be read above, my Nishio wasn't complete and thus validation was required. At the moment of writing this, I haven't tested whether removing the validation speeds things up and gives valid answers.

dukuso wrote:
ahh, here they are. They were hidden behind validity-checking. But why ?

Because most often, with my algorithm, invalid backtracked board is caused by looking for naked singles.

dukuso wrote:
what all have you tried ? I assume you tried a lot, else you wouldn't
have written this.


Actually, only one program has included same kind of timing. All the others store logs etc. which naturally slow down the execution. Since the program was pretty bad, I removed it after doing some tests (couldn't find it anymore). Doing a complete test was bothersome as it loaded only one sudoku at a time.

dukuso wrote:
Have you tried to vary the method depending on the number of cells placed ?
I assuming filling the last clues requires a different strategy than
filling the first clues.


I've thought about it, but the last clues are automatically filled with the fastest possible logic (hidden singles). All other logics are used only to return as quickly as possible to detecting hidden singles, which is very fast.

dukuso wrote:
When you are looking for singles, where do you start ?
Always at the first cell ?
Isn't it better to search for all singles at once
and store them ?
Or start looking for those singles with the same
row,column,symbol as the last placement ?
Or even somehow restrict it to those ? - by looking
for which possible new singles a placement can create
have you tried anything for larger sudokus ?


Naked singles are easy to find while you're marking out the possibles with any method. So, I'm not actually looking for naked singles, they are known for sure. All other logics require looking for certain rules. I haven't tried this with a larger sudoku, I'd have to do a lot of recode.

So, my algorithm as such isn't very flexible, but that can be expected from any highly optimized code. My starting point for the whole thing was to do the things as fast as possible from computer point of view.


Edit After trying a complete Nishio (now that I got it right), I can be sure it is too slow. It could be optimized more with the cost of slowing down other code than what my implementation was, but it probably wouldn't have been faster than my current algorithm. My validation code is very fast and accurate enough.
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 454
:
Location: germany

Items
PostPosted: Sat Aug 20, 2005 5:37 am    Post subject: Reply with quote

hi Merri,

thanks for your answers and efforts to explain. I understand
a bit better now, what you are doing, but it's also a bit
unfortunate that it's probably hard to include your routines
into other solvers and that it doesn't generalise to larger
boards or similar problems.

Seriously, would you recommend to someone else who is trying
to write a speed-optimized sudoku-solver to base it on
your description and algorithm and program ?
Looks complicated.


Just one other idea, which helped me a lot:
hold a table with the number of candidates for each
of the 324 constraints which is updated after each placement.
Once on such an update you meet a constraint which is reduced
to only one candidate to satisfy it, then put it on a stack
to be remembered for the next placement.
In that case no further search is necessary.
You must be doing something similar, but for my exact-cover
solver it gave an immediate and surprising 5 fold speedup.



Guenter.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron
FREE FORUM HOSTING by AtFreeForum. Terms of Service - Privacy Policy
FASHION ACCESSORIES - BLING BLING - LADIES WATCHES - KOREAN CHILDREN CLOTHING - ONLINE BARGAIN STORE - FASHION JEWELLERIES