History of AIC's

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

History of AIC's

Postby RSW » Wed Jun 22, 2022 11:06 pm

I'm curious as to whether AIC's were developed specifically for solving Sudoku puzzles, or whether they previously existed and were used for other logic problems. I haven't been able to find any information related to them except for their application in Sudoku solving. Does anyone have any information about the history of AIC's?
RSW
 
Posts: 401
Joined: 01 December 2018
Location: Western Canada

Re: History of AIC's

Postby denis_berthier » Thu Jun 23, 2022 3:31 am

.
AFAIK, AICs are a re-branding of the previously existing nice loops (with a few changes, mainly notational). Both emerged in the Sudoku world.
denis_berthier
2010 Supporter
 
Posts: 3536
Joined: 19 June 2007
Location: Paris

Re: History of AIC's

Postby jco » Mon Aug 08, 2022 2:42 am

I just came across this by accident.
In that thread, Myth Jellies (Myth Jellies » Fri Apr 27, 2007 8:34 am) mentions the origins of AICs in
a large quoted paragraph. The originator seems to be Myth Jellies.

Edit: I am aware of Steve K.'s "forbidding chains" (I studied them here). In the thread Alternating Inference Chains Steve K. mentions that
Upon studying your notes on AIC, it is obvious to me that what I have been calling "forbidding chains", and what is called here AIC are precisely the same idea.
JCO
jco
 
Posts: 499
Joined: 09 June 2020

Re: History of AIC's

Postby denis_berthier » Mon Aug 08, 2022 3:39 am

jco,
thanks for this reference I wasn't aware of.
It clearly establishes that:
- AICs are a different view of NLs;
- the main difference is, AICs are based on links between candidates, while NLs were based on links between cells.

This is the opportunity for me to recall that in my approach, and in the nrc-notation that best expresses it, both views are totally fused:
- by definition, a chain is a continuous sequence of candidates (with additional conditions, of course);
- a chain can always be represented as csp1{llc1 rlc1} - csp2{llc2 rlc2} ...
where, in Sudoku, the cpsi's are 2D-cells - i.e. not only the classical rc-cells but also rn-, cn- or bn- cells - i.e. cells of my extended sudoku board.
Neither the NLs nor the AICs can deal with chains in such a uniform way.
Basically, this amounts to considering bivalue and bilocal relations as being one and only one concept - an idea totally absent in AICs and the corresponding notation.

Another major difference is, NLs and AICs were expressed in terms of inferences (weak and strong links) whereas my chains are expressed as purely logical patterns observable on a grid without any inferencing: basically, for two candidates, observe a (direct contradiction) link or the presence in a same 2D-cell.
denis_berthier
2010 Supporter
 
Posts: 3536
Joined: 19 June 2007
Location: Paris

Re: History of AIC's

Postby denis_berthier » Mon Aug 08, 2022 3:50 am

jco wrote:IEdit: I am aware of Steve K.'s "forbidding chains" (I studied them here). In the thread Alternating Inference Chains Steve K. mentions that
Upon studying your notes on AIC, it is obvious to me that what I have been calling "forbidding chains", and what is called here AIC are precisely the same idea.

This should be made clear: the AIC post dates back to Jan. 2006. The first mention we have of "forbidding chains" dates back to Jan. 2007 (one year later).
denis_berthier
2010 Supporter
 
Posts: 3536
Joined: 19 June 2007
Location: Paris

Re: History of AIC's

Postby jco » Mon Aug 08, 2022 11:57 am

Perhaps I should have mentioned also the link of the originator of forbidding chains. Steve K. learned forbidding chains from Bruno Greco and developed it further. Steve K. of course mentions this explicitlyand points to that link. Bruno Greco material dates back to 2005.
Since I fancy myself as an independent type of thinker, I did not accept easily the teachings of gb - Bruno Greco - who previously frequented sudoku.com.au tough puzzles with sage solving advice. Eventually, I adopted most of his viewpoints on solving sudoku puzzles. I still think of gb as the teacher, and I the student. gb was a frequent poster at this site from its inception through about February of 2006.

IMHO Alternating Inference Chains and Forbidding Chains are independent developments.
JCO
jco
 
Posts: 499
Joined: 09 June 2020

Re: History of AIC's

Postby denis_berthier » Mon Aug 08, 2022 12:19 pm

OK.
Great job of finding old references.
denis_berthier
2010 Supporter
 
Posts: 3536
Joined: 19 June 2007
Location: Paris

Re: History of AIC's

Postby RSW » Mon Aug 08, 2022 11:55 pm

Thank you jco, for finding these early references. I guess we can conclude that AIC's were not imported from some other field of logic, which is what I had been wondering.

I had thought that the basic principle of being able to telescope a chain of propositions (a,b,c...):
a = b - c = d - e = f
down to simply:
a = f
is beautifully elegant, and that the principle had perhaps been used in some other field.
RSW
 
Posts: 401
Joined: 01 December 2018
Location: Western Canada

Re: History of AIC's

Postby denis_berthier » Tue Aug 09, 2022 3:30 am

RSW wrote:I guess we can conclude that AIC's were not imported from some other field of logic.

I had thought that the basic principle of being able to telescope a chain of propositions (a,b,c...):
a = b - c = d - e = f
down to simply:
a = f
is beautifully elegant, and that the principle had perhaps been used in some other field.

As this is totally trivial, I can't see how this could even be named a principle. Fortunately for AICs, there's more to them than just collapsing...
BTW, this in particular isn't an invention of AICs: NLs and xy-chains did the same thing much before AICs.

xy-chains - the most basic chains and the only chains I had heard of when I started Sudoku - were the source of inspiration for all my developments. I'm quite sure they predated any other type of chains - but I have no references.
I'm curious to know how they originated. Has anyone old references for them, like jco has found for AICs?
denis_berthier
2010 Supporter
 
Posts: 3536
Joined: 19 June 2007
Location: Paris


Return to General