/*
SuDoku Solver by Logic v1.0 - ChainFinder Subroutines
Copyright (C) Peter Wake 2005

This program is free software; you can redistribute it and/or
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 2
 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

The GNU General Public License can be seen at
 http://www.gnu.org/licenses/gpl.html

Or contact the author via the website link at
 http://www.sudokusolver.co.uk
*/

//
//
//  EXPLANATION OF THE CHAINFINDER ALGORITHM
//
/////////////////////////////////////////////////////////////////////////////
/*

ChainFinder is passed an array with 9 elements, ie either a row,
 column or block from the 'remaining options' SuDoku square, and
 looks for a 'chain' in the array.
 
For example in a block such as

  |   A     B     C
 -+---------------------
 1|   56    2     9
 2|   8     147   14567
 3|   17    3     17
 
The program should find the 'chain' A3,C3 which both contain
 17.
 
Another example would be

  |   A     B     C
 -+---------------------
 1|   56    2     61
 2|   8     147   14567
 3|   17    3     76

The program should find the 'chain' A3,C3,C1 which contain the
 chain 17, 76, 61.
 
The solver then knows that these cells MUST contain one or the other
 of the numbers in the chain, and together they represent ALL the
 numbers in the chain. It can therefore eliminate the numbers in the
 chain from related rows, columns and blocks.

Programming
===========
indexLink is a simple object to keep track of where a value string was
 originally indexed
 
ChainFinder is the main object. It is initialised by passing an array
of 9 string elements.

The found chain sets are stored in several ways to make them easy to
 manage:
 
foundChainSet is a stack [array] of found chains. Each chain is an array of
 indexLink objects
 
foundChainSetNumbers is a related stack of found chains set numbers.

inChain is a reference array.

So if the first chain example above would be represented by chainArray as:
  0   1   2   3   4     5       6    7   8
'56','2','9','8','147','14567','17','3','17'

Running the solver would give

foundChainSet[0]:[6->'17'],[8->'17']

foundChainSetNumbers[0]:'17'

           1    2    3    4    5    6    7    8    9
inChain:   0    null null null null null 0    null null

The code is fairly self-explanatory....
*/

function indexLink(index,cvs)
{
  this.index=index;
  this.cvs=cvs;
}
indexLink.prototype.showHTML=function()
{
  return "["+this.index+" - "+this.cvs+" ]"
}

function ChainFinder(chainArray)
{
  this.chainArray=chainArray;
  this.foundChainSet=new Array();
  this.foundChainSetNumbers=new Array();
  this.inChain=new Array();
}

ChainFinder.prototype.findChains=function()
{
  var i,linkSet;

  this.foundChainSet=null;
  this.foundChainSet=new Array();

  linkSet=new Array();
  for(i=0;i<this.chainArray.length;i++)
  {
    linkSet[i]=new indexLink(i,this.chainArray[i]);
    this.inChain[i]=null;
  }
  this.getChain(linkSet);
}

ChainFinder.prototype.debug=function(str)
{
  //document.write(str+"<br>");
}
ChainFinder.prototype.showHTML=function()
{
  var i,j,a0;
  
  a0="<table><tr><td>Index</td><td>Chain</td></tr>";
  for(i=0;i<this.foundChainSet.length;i++)
  {
    a0+="<tr><td>"+i+":</td><td>"
    for(j=0;j<this.foundChainSet[i].length;j++)
    {
      a0+="["+this.foundChainSet[i][j].index+" - "+this.foundChainSet[i][j].cvs+" ]";
    }
    a0+="</td></tr>";
  }
  a0+="</table>";
  return a0;
}

ChainFinder.prototype.isChain=function(linkedSet,link)
{
  var i,j,ct,cArr,cv;

/*
 Note that this doesn't take care of situation where linkedSet,link contains
 e.g. [12,12,34],34
 but this should not be proposed by the getChain function
*/

  cArr=new Array();
  for(i=1;i<=9;i++)
  {
    cArr[i]=0;
  }

  ct=link.cvs.length;
  for(i=0;i<linkedSet.length;i++)
  {
    if(linkedSet[i].cvs.length!=ct) return false;
  }
  for(i=0;i<linkedSet.length;i++)
  {
    for(j=0;j<linkedSet[i].cvs.length;j++)
    {
      cv=linkedSet[i].cvs.charCodeAt(j)-48;
      cArr[cv]++;
    }
  }
  for(j=0;j<link.cvs.length;j++)
  {
    cv=link.cvs.charCodeAt(j)-48;
    cArr[cv]++;
  }
  for(i=1;i<=9;i++)
  {
    if(cArr[i]!=0 && cArr[i]!=ct) return false;
  }
  return true;
}
ChainFinder.prototype.areLinked=function(linkA,linkB)
{
  var i,c;
  
  if(linkA.cvs.length!=linkB.cvs.length) return false;
  return linkA.cvs.anyMatch(linkB.cvs);
}
ChainFinder.prototype.chainElements=function(chain)
{
  var a0,c,i,j;
  a0="";

  for(i=0;i<chain.length;i++)
  {
    for(j=0;j<chain[i].cvs.length;j++)
    {
      c=chain[i].cvs.charAt(j)
      if(a0.indexOf(c)<0) a0+=c;
    }
  }
  return a0;
}
ChainFinder.prototype.saveChain=function(chain)
{
  var i,copyChain;
  
  copyChain=new Array();
  for(i=0;i<chain.length;i++)
  {
    copyChain[i]=new indexLink(chain[i].index,chain[i].cvs)
    this.inChain[chain[i].index]=this.foundChainSet.length;
  }
  this.foundChainSet.push(copyChain);
  this.foundChainSetNumbers.push(this.chainElements(copyChain));

}

ChainFinder.prototype.getChain=function(remainingLinks,link,linkedSet,unLinkedSet)
{
  var i,testLink;
  
  this.debug("<br>Getting chain length "+remainingLinks.length);
  this.debug(remainingLinks.showHTML());

  if(link==null || linkedSet==null || unLinkedSet==null)
  {
    while(remainingLinks.length>0)
    {
      //pull the first link off the list
      link=remainingLinks.shift();
      this.getChain(remainingLinks,link,new Array(),new Array());
    }
  }
  else
  {
    this.debug(link.showHTML());
    this.debug(linkedSet.showHTML());
    this.debug(unLinkedSet.showHTML());
  }

  if(link.cvs.length==1) return; //link length 1 is already solved
  while(remainingLinks.length>0)
  {
    testLink=remainingLinks.shift();
    if(this.areLinked(link, testLink))
    {
      this.debug(link.showHTML()+" and "+testLink.showHTML()+" are linked.");
      linkedSet.push(link);
      link=testLink;
      if(this.isChain(linkedSet,link))
      {
        this.debug("Found set "+linkedSet.showHTML());
        linkedSet.push(link);
        this.saveChain(linkedSet);
        //put the remainingLinks on the unLinkedSet stack so that they get checked
        //and break out of this loop
        while(remainingLinks.length>0)
        {
          unLinkedSet.push(remainingLinks.shift());
        }
        break;
      }
      else //linked, but still not a chain.. so keep moving along the linked set
      {
        this.debug("Not a chain though - recursing..");
        //put back all the unLinkedSet elements that have the same length
        for(i=0;i<unLinkedSet.length;i++)
        {
          if(unLinkedSet[i].cvs.length==link.cvs.length)
          {
            spliceArr=unLinkedSet.splice(i,1);
            if(spliceArr[0]) {spliceItem=spliceArr[0];} else {spliceItem=spliceArr;}
            remainingLinks.push(spliceItem);
          }
        }

        this.getChain(remainingLinks,testLink,linkedSet,unLinkedSet);
        link=linkedSet.pop();
      }
    }
    else //not linked
    {
      unLinkedSet.push(testLink);
    }
  }
  if(unLinkedSet!=null && unLinkedSet.length>0) this.getChain(unLinkedSet)
}