(My) Nishio defintion

rubylips · Posted: Thu Apr 14, 2005 11:29 pm Post subject: (My) Nishio defintion

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.

IJ · Posted: Mon Apr 18, 2005 4:58 pm Post subject:

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")

rubylips · Posted: Mon Apr 18, 2005 6:34 pm Post subject:

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.

rallveird · Posted: Wed Jun 15, 2005 7:19 pm Post subject:

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]

Merri · Posted: Thu Aug 18, 2005 3:40 pm Post subject: Re: (My) Nishio defintion

dukuso · Posted: Fri Aug 19, 2005 3:24 am Post subject:

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.

Merri · Posted: Fri Aug 19, 2005 11:15 am Post subject:

dukuso · Posted: Sat Aug 20, 2005 5:37 am Post subject:

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.