Nishio vs AICs. When is it considered cheating?

Post the puzzle or solving technique that's causing you trouble and someone will help

Re: Nishio vs AICs. When is it considered cheating?

Postby champagne » Thu Dec 21, 2017 8:14 pm

JasonLion wrote:There are several definitions of Nisho, I don't know which one SE is using. I am assuming the Sudopedia definition, which explicitly includes guessing.

Hi Jason,

No reason to fight on such a topic.

Just for information, I am not supporting SE, just describing what is done.

The basic process in SE(for high ratings) in the so-called "dynamic expansion". Starting from a "true" candidate, the PM is tagged as "true" or "false" using only basic rules :

only one occurrence of a candidate in a row, column, box
last possible candidate is "true" in row, column, box,cell.

Expansion stops at the first contradiction.

This can easily be expressed at the end as an AIC network including all locked sets in rows, columns boxes and cells.

In the so-called "nishio" step, we are in digit mode, so forget the cell constraint.

SE expand in parallel the 2 occurrences of a bi-value in "dynamic mode" limited to the studied digit.
This is equivalent to 2 AIC's networks linked by a strong link.

Nothing different from most of the complex AIC's seen here and there
champagne
2017 Supporter
 
Posts: 6039
Joined: 02 August 2007
Location: France Brittany

Re: Nishio vs AICs. When is it considered cheating?

Postby coloin » Fri Dec 22, 2017 12:04 am

So when you are doing "trial and error" what logic do you use to pick the first "trial" - it might be 2 or 3 possibilities perhaps. how is that different from a guess ? :roll: :D
coloin
 
Posts: 1695
Joined: 05 May 2005

Re: Nishio vs AICs. When is it considered cheating?

Postby StrmCkr » Fri Dec 22, 2017 12:24 am

just to chime in, seeing how we are now entering the age old debate of trial and error.
... searching can be classed as trial and error, as you find many that do nothing and some that does something...

to me anything that would be a guess is placing a digit and following its path. if the path proves a contradiction perform the elimination... otherwise keep following it until the puzzle is solved.

however,

if the network path found shows the same insertion as false without the insertion then we have a bi directional chain that proves the guess is false with out the insertion.
ie
tiral and error shows a network and the network proves the elimination.. then it is no longer trial and error just another way of "searching" for a network.

if you skip the 2nd half of testing the network path is when you are really "guessing" problem with this arises in muti-solution puzzles.
when multiple guesses are correct. { if you did a network check then you wont be removing potential solutions}
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 759
Joined: 05 September 2006

Re: Nishio vs AICs. When is it considered cheating?

Postby coloin » Fri Dec 22, 2017 12:45 am

Its a good debate !

Ah i see
so trial and error is ok .... but trial and success isnt
or another way
its acceptable to guess a wrong number but not a right number

maybe the end justifies the means :D

but yes a guess and success - that might solve a multi-solution puzzle ... thats bad .... but you have made a very good point
coloin
 
Posts: 1695
Joined: 05 May 2005

Re: Nishio vs AICs. When is it considered cheating?

Postby eleven » Fri Dec 22, 2017 10:51 am

StrmCkr wrote:to me anything that would be a guess is placing a digit and following its path. if the path proves a contradiction perform the elimination... otherwise keep following it until the puzzle is solved.

however,

if the network path found shows the same insertion as false without the insertion then we have a bi directional chain that proves the guess is false with out the insertion.
ie
tiral and error shows a network and the network proves the elimination.. then it is no longer trial and error just another way of "searching" for a network. }

Sigh, NO again.
Code: Select all
+-------------------+-------------------+-------------------+
|*49    7     6     | 8     5     3     |*49    2     1     |
| 2     5     3     | 19    14    49    | 7     6     8     |
|*49+18 489   1489  | 27    6     27    |*49    3     5     |
+-------------------+-------------------+-------------------+
| 14    6     14    | 3     9     8     | 2     5     7     |
| 789   89    789   | 12    12    5     | 3     4     6     |
| 5     3     2     | 4     7     6     | 8     1     9     |
+-------------------+-------------------+-------------------+
| 3478  1     478   | 6     348-2 47-2  | 5     9    #23    |
| 379   29    5     | 279  #23    1     | 6     8     4     |
| 6     2489  489   | 5    @2348  249   | 1     7    @23    |
+-------------------+-------------------+-------------------+

Take this example.

If you see the 2 cells with candidates 23 and find the strong link for 3 in the last row, you have found a w-wing pattern, which allows you to eliminate 2 in r7c56.

If you try to set r7c6=2, and find a contradiction
r7c6=2 => r7c9=3 => r9c9<>3 => r9c5=3 => r8c5=2
you can eliminate 2 from r7c6. You have proven, that it cannot be there.

If you try to set r7c9<>2, which implies r7c9=3, and find
r7c9<>2 => r7c9=3 => r9c9<>3 => r9c5=3 => r8c5=2,
you can eliminate 2 from r7c56. You have proven, that they cannot be there.

If you try the link (2=3)r7c9 and - by assumimg r7c9 is 3 - find
(2=3)r7c9-r9c9=r9c5-(3=2)r8c5 (which says 2 in r7c9 or in r8c5)
you can eliminate 2 from r7c56. You have proven, that they cannot be there.

If you see the unique rectangle 49 in r13c17, you can eliminate 4 and 9 in r3c1. It is proven, that they cannot be there, if the puzzle is unique (which is a requirement for normal puzzles).

If you try 2 in r7c9, and it helps you to solve the puzzle, this is a guess, because you have not proven, that it must be there. To be accurate, it would be proven to be correct, if you find a valid solution for a unique puzzle then. But you have not proven the move, when you made it.
eleven
 
Posts: 1741
Joined: 10 February 2008

Re: Nishio vs AICs. When is it considered cheating?

Postby SpAce » Fri Dec 22, 2017 3:37 pm

eleven wrote:If you try 2 in r7c9, and it helps you to solve the puzzle, this is a guess, because you have not proven, that it must be there. To be accurate, it would be proven to be correct, if you find a valid solution for a unique puzzle then. But you have not proven the move, when you made it.


Could this also be seen the other way around? If the moves in your solve path prove that the solution is unique then you haven't truly guessed (or at least you have proved your guesses). Of course this isn't a very practical definition because that would exclude uniqueness strategies. But in principle?
SpAce
 
Posts: 218
Joined: 22 May 2017

Re: Nishio vs AICs. When is it considered cheating?

Postby eleven » Fri Dec 22, 2017 3:59 pm

I don't quite understand.
If you use correct (proven) non-uniqueness based moves and solve the puzzle, you also have shown the uniqueness of the puzzle.
If you use unproven moves or uniqueness moves in a non-unique puzzle or make a mistake, you may be lucky to arrive at a solution - which can be unique or not.
eleven
 
Posts: 1741
Joined: 10 February 2008

Re: Nishio vs AICs. When is it considered cheating?

Postby SpAce » Fri Dec 22, 2017 5:28 pm

eleven wrote:I don't quite understand.


I'm not sure I do either :D It has a taste of circular reasoning, I admit. Let's see if I can rephrase what I was really after.

If you use correct (proven) non-uniqueness based moves and solve the puzzle, you also have shown the uniqueness of the puzzle.


Exactly. If you have recorded such a set of moves that is known to prove the uniqueness of the solution, then we know you haven't just guessed.

If you use unproven moves or uniqueness moves in a non-unique puzzle or make a mistake, you may be lucky to arrive at a solution - which can be unique or not.


Exactly.
SpAce
 
Posts: 218
Joined: 22 May 2017

Re: Nishio vs AICs. When is it considered cheating?

Postby StrmCkr » Fri Dec 22, 2017 6:50 pm

Sigh, NO again.
i guess i worded that way to confusing.
moreover your entire posts actually agrees with me,
and you further extended it to include assumptive uniqueness techniques
which has no proof of elimination just the assumptive that no solution can be found in a particular arrangement of digits in specific cells when a solution is already known to be unique with no proof of why.
which i also agree with. examples are scattered over this forum where 3 solution puzzle using a UR move set reduces it down to zero. {instead of the assumed 1}

the try you did miss in your examples was how you developed the network in the first place.

it can be found two ways, collectively trying every connection until it proves a contradiction. { yes even educated built network paths{strong weak links etc} are still being "tried" one after another until one proves something. }

or by trying cells with a digit {which happens to be the elimination cell of a network}, and noting the network.
can the network in the placement chain directly prove the contradiction without placement? if yes, then you have built your self a chain of some sort that proves the initial placement as an elimination ie false placement.

a clear example:
Inverted w-wing: (7) r2c1 = (7-3) r2c3 = r2c6 - r3c5 = (3-7) r9c5 = r6c5 => -7 r6c1;
found backwards by links from placing 7 @ r6c1.

{that's the point i was trying to get at.}

from that you can also, skip recording networks and just go ham.
try digits and remove that digit choice when contradictions occur
try digits and solve them no contradiction occurs.

that's the two sides of what is "trial" and "error"

so yeah..... lets try to get this topic back on to the original discussion and save countless rehashing of the same thing that spans probably 400+ threads over the last 15 years.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 759
Joined: 05 September 2006

Re: Nishio vs AICs. When is it considered cheating?

Postby David P Bird » Fri Dec 22, 2017 10:02 pm

I no longer consider any method amounts to 'cheating' just that some, such as forcing chains, are more acceptable than others, such as kraken nodes.

Just as professional gamblers can make a living out of using their experience to weigh up if the bookies' odds favour them or not, so an experienced Sudoku player will be able to shortlist the most productive looking assumptions to test first. In comparison, without the aid of an artificial intelligence approach, a computer would use a brute force and methodically test every option in turn.

The problem is that when assumptive solutions are posted on the forum, readers have no way of knowing how many fruitless assumptions were tested before the successful ones were found. But the same thing can be said about players who use non assumptive methods who can also follow many insignificant chains before finding a telling one. However, for two players with equal experience, the one that uses non-assumptive methods has a better chance of making some progress, however small, for every line of investigation he follows.

Of the disparaging descriptors used for the less popular methods 'Brute Force', 'Trial and Error', 'Assumptive' and 'Bifurcative', the first three are all subjective as it is easy to find some aspect of every method to criticise on one or other of these grounds. The 'Bifurcative' group is simpler. There are several types but I use a catch-all test for all of them. It is based on the number of cases (ie Boolean terms) are live at any point in reaching a deduction. As a chain is constructed, the relationship between the two end nodes of a chain is being evaluated - the intermediate ones are history. Therefore, there must always be two live terms. When any sort of branch is followed, or the state of some intermediate term is remembered, there is an extra live term and the method becomes bifurcative. The inclusion of Boolean pattern nodes in a chain does not affect this as they have the same status as the other Boolean nodes.

ALS and Fish pattern nodes are true or false according to how many truths the cell set holds and so are simple. (As an aside, it was after considering this point that I realised that similar 'split-node' group Booleans could be similarly defined for peers of a term that are in different houses.)

However, some other pattern nodes can only be proved by using cases. They therefore present a backdoor method of introducing a bifurcative method into a solution. However, I agree with the consensus view that Boolean pattern nodes are acceptable for 'recognisable patterns'. The term implies firstly that the pattern occurs frequently enough to be given a name, and secondly it can be recognised without needing to track implication chains. (JExocets were spawned from a wider Exocet specification precisely to meet these conditions, but they do stretch the concept of a recognisable pattern as wide as it can go as they take quite of bit of checking to confirm the pattern exists.)

So an under my re-appraisal I am prepared to accept assumptive chains provided they pass my bifurcation test and this would also apply to the different Nishio methods that have been defined. However, in general I'm far from sure how many would pass the test because I don't use them.

In another thread, Gordon Fick also requested clarification whether on SK Loops and Multi-Sector Locked Sets were assumptive. SK Loops are MSLS patterns that are easy to recognise if a player knows what to look for. No assumptions are needed in the proof of MSLSs but the big question is how they are found. Some can be spotted by checking for two distinct sub-sets if givens that appear in parallel rows and columns, and some others are worth exploring for when the bivalue cells are peers to orthogonal sets of cells that either contain all or most of the digits they hold or none of them. Therefore, there can be good reasons for checking for them. However when the digit distributions are more jumbled and they are found by a brute force computer search the picture is different. The problem is telling these cases apart as some players have savant-like skills in picking out hidden digit patterns (Steve Kurzhals, who discovered SK Loops, was one of them).

I apologise for being slow in posting this but I had man-flu in the run up to the festivities and have been playing catch up with my preparations.

Season's Greetings to All

David PB
David P Bird
2010 Supporter
 
Posts: 1001
Joined: 16 September 2008
Location: Middle England

Re: Nishio vs AICs. When is it considered cheating?

Postby SpAce » Sat Dec 23, 2017 12:53 am

David has good points. A couple of thoughts on what I subjectively count as "trial and error", "brute force" and "assumptive" (with my limited experience), though I'm not making any judgments on what is good or bad. For example, discontinuous nice loop proofs can be considered assumptive trial-and-error techniques, if you first pick a candidate and then look for a loop to eliminate or place it. I don't see how it's any different from simple Nishios which can be replaced with discontinuous loops anyway. They're both also a form of brute force, if the tested candidate is picked randomly (or systematically). If some intelligence is used in picking the candidate, then it's not brute force but it's still t&e.

In other words, whenever you start with what you're trying to prove, it's t&e, and if the target is chosen randomly then it's also a form of brute force. If, on the other hand, a pattern is found first and the eliminations follow from that, then it's not t&e (though searching for the pattern may be). AICs count as such unassumptive patterns in my book -- but only if they're found first and independently of their eliminations. I'm not saying it's necessarily better, however. Using only unassumptive methods may not be a very strategic approach, because there's no guarantee that the unassumed eliminations actually advance the puzzle. Strategically chosen assumptive trials may have a better chance at that. Like I said, I'm not making any judgments. Both approaches have their merits. Even brute force may have its place if nothing else helps, but few probably enjoy it much.

I'll try to explain my point with an example. Since the original poster mentioned SudokuWiki and its approach to Nishio, I took the example from there:
http://www.sudokuwiki.org/Nishio_Forcing_Chains.

Code: Select all
+-----------------+------------------+--------------+
|  38   389  4    |  2    179  17    | 68  158 56   |
|  26   268  7    |  45   45   16    | 3   18  9    |
|  1    69   5    |  3    69   8     | 2   7   4    |
+-----------------+------------------+--------------+
|  9    4    26   |  16   267  1267  | 5   3   8    |
|  368  1    368  |  9    368  5     | 4   2   7    |
|  7    5    238  |  48   2348 23    | 9   6   1    |
+-----------------+------------------+--------------+
|  4  cF2+6- 1    |  7    256  9     | 68  58  3    |
|  5    38   9    | B168 B1268 123   | 7   4  C26   |
|bE2368  7  b368  |aA58-6 2358 4     | 1   9  D256  |
+-----------------+------------------+--------------+


Stuart's Nishio starts with 6@r9c4 and forms two branches that connect and prove a contradiction at r7c2:

1 (a-c): r9c4=6 => r9c13<>6 => r7c2=6
2 (A-F): r9c4=6 => r8c45<>6 => r8c9=6 => r9c9=2 => r9c1<>2 => r7c2=2 => r7c2<>6
=> contradiction => r9c4 <> 6

That's a logical proof, all right, but the real question is why someone would choose such a useless looking candidate to test. It looks like a totally random or systematic choice, i.e. brute force. Of course it makes even less sense to use Nishio here, when a grouped discontinuous loop is easily available (as Leren seems to have pointed out in the comments, and even Stuart's own solver sees it that way):

Discontinuous Nice Loop Type 1 (Grouped): (6)r9c4 - r9c13 = (6-2)r7c2 = r9c3 - r9c9 = (2-6)r8c9 = r8c45 - (6)r9c4 => -6 r9c4

That's much simpler, but it's just a tactical difference. From a strategic point of view it's no different, as there's still the question of why that particular candidate was chosen to be tested in the first place. It's still t&e and looks like brute force, too.

To me the least t&e and brute force way of finding that elimination is if you happen to see the grouped AIC as a pattern first:

AIC Type 1 (Grouped): (6)r9c13 = (6-2)r7c2 = r9c3 - r9c9 = (2-6)r8c9 = (6)r8c45 => -6 r9c4

Now we know that there must be a 6 in one of those two end nodes and we can eliminate any 6 that sees them both. That is an unassumptive pattern-based elimination. Neither the discontinuous loop or the Nishio is, even though they provide the same proof using essentially the same chain.
SpAce
 
Posts: 218
Joined: 22 May 2017

Re: Nishio vs AICs. When is it considered cheating?

Postby StrmCkr » Sat Dec 23, 2017 2:30 am

i'm not sure what prompted the name change on scanraid
happened some where around the time he re-branded his website as sudokuwiki after the real wiki page died out and lost its registry.

p.s part of the original wiki is restored on these forums.

scanraid used to have Nisho listed way down near the bottom with bomens bingo under trial and error techniques.
it was purely trial and error lots of nested guessing to form a contradiction sub-net, not exactly sure what it is now to earn the re-branding....
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 759
Joined: 05 September 2006

Re: Nishio vs AICs. When is it considered cheating?

Postby SpAce » Sat Dec 23, 2017 6:18 am

StrmCkr wrote:i'm not sure what prompted the name change on scanraid
happened some where around the time he re-branded his website as sudokuwiki after the real wiki page died out and lost its registry.


Is there some bad blood?

scanraid used to have Nisho listed way down near the bottom with bomens bingo under trial and error techniques.
it was purely trial and error lots of nested guessing to form a contradiction sub-net, not exactly sure what it is now to earn the re-branding....


Well, to me the current implementation seems completely useless based on the description (which also happens to contradict itself). First it defines the technique as: "Two chains emanate from the candidate in different directions and try to join up later on another candidate." That's only one type, however, as it next shows several other contradiction types as well (which makes more sense, of course). Hard to say how it actually works, as there's just one example, of the first type only (that I showed), and I haven't tested it otherwise. In any case it seems useless if it only spawns two branches (which don't branch themselves), because as far as I can imagine, those cases can be covered with AICs or discontinuous loops much more intuitively. It would make more sense if it could spawn more branches as then it would have the same power as 3+ candidate cell and unit forcing chains (as their opposite end). I don't know if the implementation does that, but at least the description implies otherwise.

http://www.sudokuwiki.org/Nishio_Forcing_Chains

For the same reason the Digit Forcing Chains seem at least as useless. All of the examples there are much more simply seen and discovered as continuous or discontinuous loops, and again, I can't imagine cases where that wouldn't be true. Yet the solver finds use for digit forcing chains from time to time, even with AICs turned on, which puzzles me. I can only imagine that it must be due to a lacking AIC implementation. To me both the SudokuWiki Nishio and DFC seem like ugly brute force ways of applying the power of AICs. I can't see what they would offer to a manual solver, except a (somewhat confusing) tutorial to understanding more complex forcing chains.

http://www.sudokuwiki.org/Digit_Forcing_Chains

As far as I understand, the only forcing chains on SudokuWiki that have potential for more abilities than correctly implemented AICs (without exotic nodes) are the triple/quad cell and unit forcing chains. Even then, at least the first triple cell forcing chain example is easily replaced by an ALS AIC, but that's just a poor example. The others seem harder to crack.

http://www.sudokuwiki.org/Cell_Forcing_Chains
http://www.sudokuwiki.org/Unit_Forcing_Chains
SpAce
 
Posts: 218
Joined: 22 May 2017

Re: Nishio vs AICs. When is it considered cheating?

Postby StrmCkr » Sat Dec 23, 2017 7:08 am

bad blood?
probably not, but he is a business man given the opportunity to buy the titled Sudoku wiki website moniker would be a smart move especially when he publishes puzzles to papers.

http://sudopedia.enjoysudoku.com/Nishio.html


I do know most of his stuff was built off the players forums and documentation submitted and collaborated by a handful of contributors directly from here.
from what i last checked it still functioned like this original description.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 759
Joined: 05 September 2006

Re: Nishio vs AICs. When is it considered cheating?

Postby eleven » Sat Dec 23, 2017 2:49 pm

Remark: The other nishio contradiction types are not necessary. Just do one more step in one of the chains and you have type 1.

Let me state again, that Sudoku Explainer's Nishio and Andrew Stuart's Nishio are not the same:
Explainer: "The chains are Nishio chains: they only involve a single value (like Forcing X-Chains), but the conclusions of multiple sub-chains must be combined in some cases." (i.e. it uses single digit nets)
Andrew Stuarts Nishio consists of 2 multidigit forcing chains showing a contradiction.
What they have in common is, that they start with a single digit, setting it one time true and one time false.
In both cases i cannot see any reason, why they stop their chains somewhere in the grid (where their contradiction arises), instead of continuing, until they get a contradition in the starting cell.
But note, that both are from ancient Sudoku times around 2006. Nowadays Explainer's Nishio is covered by the grouped x-chain and fish techniques and Stuart's double chains are just AIC's written differently.


Once again let me say that AIC's ARE NO PATTERNS, but an ASSUMPTIVE TRIAL & ERROR technique.
A pattern is something, which has a structure, you can optically recognize in a grid. Examples are the patterns, which show you the hidden singles, many fish and wings, unique rectangles, deadly patterns and so forth. But no one can identify any non trivial AIC optically without following the chain. And to follow it, you have to make the assumption, that a digit is true or false, just as you do with the nishios above.

To get the AIC "(6)r9c13 = (6-2)r7c2 = r9c3 - r9c9 = (2-6)r8c9 = (6)r8c45 => -6 r9c4" SpAce had to make the assumption, that 6r7c2 is true. So it is just nonsense to claim "That is an unassumptive pattern-based elimination".

This is my last attempt to make that clear here. If people don't want to accept the truth, it makes no sense, trying to explain it. At the end you are just lying to yourselves.

Btw when David says, he uses a method to show all bifurcations, that is called "brute force" (there can be really much).
eleven
 
Posts: 1741
Joined: 10 February 2008

PreviousNext

Return to Help with puzzles and solving techniques

cron