WaBis

walter.bislins.ch

Datei: sudoku-01-03-2016.js

Inhalt der Datei: ./Media/sudoku-01-03-2016.js
// sudoku solver
// 2007-2013 (C) Walter Bislin, http://walter.bislins.ch/
// 2013-02-14: Redesign

function w(aText){document.write(aText);}
function wl(aText){document.writeln(aText);}
function div( a, b ) { return Math.floor( a / b ); }
function maxOf( a, b ) { return (a > b) ? a : b; }

function CUrlParameters() {
  this.Params = [];
  var url = location.href;
  var pos = url.indexOf( '?' );
  if (pos < 0) return;
  var paramListStr = url.substr( pos+1 );
  if (paramListStr == '') return;
  var paramList = paramListStr.split( '&' );
  for (paramX = 0; paramX < paramList.length; paramX++) {
    var paramStr = paramList[paramX];
    var pos = paramStr.indexOf( '=' );
    if (pos > 0) {
      var name = paramStr.substr( 0, pos ).toLowerCase();
      var value = paramStr.substr( pos+1 ).replace( /\+/g, ' ' );
      try { value = unescape( value ); } catch (err) {}
      this.Params.push( { Name: name, Value: value } );
    }
  }
}

CUrlParameters.prototype.GetParameter = function( aParamName ) {
  var lcName = aParamName.toLowerCase();
  for (var paramX = 0; paramX < this.Params.length; paramX++) {
    if (this.Params[paramX].Name == lcName) return this.Params[paramX].Value;
  }
  return '';
}

var UrlParameters = new CUrlParameters();

var CSudokuInstances = new Array();

function CSudokuFindInstance( aName ) {
  for (var i = 0; i < CSudokuInstances.length; i++) {
    if (CSudokuInstances[i].Name = aName) return CSudokuInstances[i];
  }
  return null;
}

function CSudokuHandleOnKeyDown( e ) {
  for (var i = 0; i < CSudokuInstances.length; i++) {
    CSudokuInstances[i].HandleOnKeyDown( e );
  }
}

function CSudoku( aName ) {
  // use a short name for this sudoku in aID. This gives the element names (table, cells, inputs)
  // aStatusID is a HTML-Element-ID where Status-Messages are postet
  // aMethodsID is a HTML-Element-ID where a list of used Methods is postet

  this.MaxXYChainSize = 8;
  this.MaxRemotePairsSize = 8;
  this.SolveTimeLimit = 2000;

  this.GridCreated = false;
  this.GridEnabled = false;
  this.GraphicHintsEnabled = true;
  this.TextHintsEnabled = false;
  this.TextHintLevel = 0;
  this.MethodOrder = 1;
  this.ShowAllMoves = false;
  this.SortMovesByLevel = false;
  this.StopOnSolutions = true;
  this.SlowMotion = false;
  this.LimitSolveTime = true;
  this.Name = aName;
  this.DocStatusID = aName + 'Status';
  this.DocMethodsID = aName + 'Methods';
  this.CSetBits = new Array(10);
  this.CSetBits[0] = 0;
  for (var i = 1; i < 10; i++) this.CSetBits[i] = 1 << (i-1);

  this.StartCells = this.NewCells( 0 );
  this.SolvedCells = this.NewCells( 0 );
  this.CandidateCells = this.NewCells( 0 );
  this.StatusCells = this.NewCells( '' );
  this.LastSolvedCells = this.NewCells( 0 );
  this.ColorCells = this.NewCells( 0 );
  this.NumbersCount = new Array( 10 );
  this.CandidatesCount = new Array( 10 );
  for (var i = 0; i <= 9; i++) {
    this.NumbersCount[i] = 0;
    this.CandidatesCount[i] = 0;
  }
  this.SolveStartTime = 0;
  this.RunTimeLimitExceedet = false;
  this.MarkerFilterMode = false;

  this.CandidatesAreValid = false
  this.CurrLevel = 0;
  this.MaxLevel = 0;
  this.MaxLevelName = '';
  this.MaxLevelHelp = '';
  this.SolutionCount = 0;

  this.XChainList = [];           // array of XChain
  this.XChainListValid = false;
  this.XYChainList = [];          // array of XYChain
  this.XYChainListValidSize = -1;
  this.CoverCells = this.NewCells( false );

  this.MovesFoundCandidates = this.NewCells( 0 );
  this.MovesClearedCandidates = this.NewCells( 0 );
  this.Moves = [];
  this.MovesCount = 0;
  this.CurrMove = 0;
  this.MaxMoves = 0;        // 0 = all

  // grid views (houses)
  this.Rows = new Array(9);             // array of row; row as array of cellX
  this.Cols = new Array(9);             // array of col; col as array of cellX
  this.Boxes = new Array(9);            // array of boxes; boxes as array of cellX
  this.Houses = [ this.Rows, this.Cols, this.Boxes ];
  this.HouseXofCellX = [ this.RowXofCellX, this.ColXofCellX, this.BoxXofCellX ];
  this.CellsRowX = new Array(81);       // array of rowX
  this.CellsColX = new Array(81);       // array of colX
  this.CellsBoxX = new Array(81);       // array of boxX
  this.CellsBoxCellX = new Array(81);   // array of boxCellX
  this.InitGridViews();
  this.BitCounts = Array( 512 );
  this.BitCounts[0] = 0;
  for (var i = 0, n = 1, x = 1; i < 9; i++, n *= 2) {
    for (var j = 0; j < n; j++) {
      this.BitCounts[x++] = 1 + this.BitCounts[j];
    }
  }

  // gui
  this.AppUpdateLevel = 0;  // see AppUpdateBegin, AppUpdateEnd
  this.AppHintsRequested = false;
  this.AppSaveStateRequested = false;
  this.AppUpdateStateDisplayRequested = true;
  this.AppUpdateButtonDisplayRequested = true;

  this.GuiSudokuInputCells = this.NewCells( null );
  this.GuiSudokuTableCells = this.NewCells( null );
  this.GuiGridDivCells = this.NewCells( null );
  this.GuiGridTableCells = this.NewCells( null );
  this.GuiButtonState = '';  // K = set Candidate; Z = set Number; F = Filter-Mode
  this.GuiButtonSetNumber = 0;
  this.GuiButtonFilterState = false;
  this.GuiButtonFilterNumbers = 0;
  this.GuiButtonFilterKeyPressed = false;

  this.LastInputCellValue = new Array( 81 );
  this.LastInputCellClass = new Array( 81 );
  this.LastInputCellBG    = new Array( 81 );
  this.LastGridCellBG     = new Array( 81 );
  this.LastGridCellValue  = new Array( 81 );
  for (var i = 0; i < 81; i++) {
    this.LastInputCellValue[i] = '?';
    this.LastInputCellClass[i] = '?';
    this.LastInputCellBG[i] = '?';
    this.LastGridCellBG[i] = '?';
    this.LastGridCellValue[i] = '?';
  }

  this.UndoEnabled = true;
  this.UndoBufferSolvedCells = new Array(81);
  this.UndoBufferStartCells = new Array(81);
  this.UndoBufferCandidateCells = new Array(81);
  this.UndoBufferStatusCells = new Array(81);
  this.UndoBufferLastSolvedCells = new Array(81);
  this.UndoBufferCandidatesAreValid = new Array(81);
  this.UndoBufferMaxLevel = new Array(81);
  this.UndoBufferMaxLevelName = new Array(81);
  this.UndoBufferMaxLevelHelp = new Array(81);
  this.UndoBufferMethodOrder = new Array(81);

  this.UndoFill = 0;
  this.UndoPtr = 0;

  this.Running = false;
  this.Stopped = false;
  this.StopSolving = false;
  this.StopAfterTrivialMoves = false;
  this.SearchingSolutions = false;
  this.AllSolutionsFound = false;
  this.LastSolution = this.NewCells( 0 );
  this.LastStartCells = this.NewCells( 0 );
  this.SolvedCellsStack = [];
  this.CandidateCellsStack = [];
  this.StatusCellsStack = [];
  this.StatusNumCellsStack = [];
  this.StartCellsStack = [];
  this.StackPtr = 0;
  this.StorageSolvedCells = [];
  this.StorageCandidateCells = [];
  this.StorageStartCells = [];
  this.StoragePtr = 0;
  this.TryBitCount = 0;
  this.TryCellX = 0;
  this.TryBitI = 0;
  this.Timer = null;
  this.MinFill = 17;
  CSudokuInstances[CSudokuInstances.length] = this;

  this.MethodsAndLevels1 = [
    1.0, this.FindFullHouses,
    1.0, this.FindHiddenSingles,
    1.0, this.FindNakedSingles,
    2.0, this.FindNakedPairsAndTriplets,
    2.2, this.FindLockedCandidatesBoxLine,
    2.2, this.FindLockedCandidatesLineBox,
    3.0, this.FindXWing,
    3.0, this.FindTurbotFish,
    3.5, this.FindXYWing,
    3.6, this.FindXYZWing,
    3.7, this.FindWWing,
    4.0, this.FindHiddenPairsAndTriplets,
    4.0, this.FindNakedQuadrupletsAndMore,
    5.0, this.FindBigBasicFishes,
    6.0, this.FindRemotePairs,
    6.0, this.FindXChains,
    7.0, this.FindXYChains
  ];

  this.MethodsAndLevels2 = [
    1.0, this.FindFullHouses,
    1.0, this.FindNakedSingles,
    1.0, this.FindHiddenSingles,
    2.0, this.FindNakedPairsAndTriplets,
    2.2, this.FindLockedCandidatesBoxLine,
    2.2, this.FindLockedCandidatesLineBox,
    3.0, this.FindXWing,
    3.0, this.FindTurbotFish,
    3.5, this.FindXYWing,
    3.6, this.FindXYZWing,
    3.7, this.FindWWing,
    4.0, this.FindHiddenPairsAndTriplets,
    4.0, this.FindNakedQuadrupletsAndMore,
    5.0, this.FindBigBasicFishes,
    6.0, this.FindRemotePairs,
    6.0, this.FindXChains,
    7.0, this.FindXYChains
  ];

}

CSudoku.prototype.AppUpdateBegin = function() {
  this.AppUpdateLevel++;
}

CSudoku.prototype.AppUpdateEnd = function() {
  this.AppUpdateLevel--;
  if (this.AppUpdateLevel <= 0) {
    this.AppUpdateLevel = 0;

    if (this.AppHintsRequested) {
      this.ComputeMethods();
    }
    if (this.AppSaveStateRequested) {
      this.SaveStateToCookie();
    }
    this.UpdateGui();
    this.SaveGameToCookie();

  }
}

CSudoku.prototype.AppRequestHints = function() {
  this.AppHintsRequested = true;
}

CSudoku.prototype.AppRequestSaveState = function() {
  this.AppSaveStateRequested = true;
}

CSudoku.prototype.AppRequestStateDisplayUpdate = function() {
  this.AppUpdateStateDisplayRequested = true;
}

CSudoku.prototype.AppRequestButtonDisplayUpdate = function() {
  this.AppUpdateButtonDisplayRequested = true;
}

CSudoku.prototype.StartTimer = function() {
  this.SolveStartTime = new Date().getTime();
  this.RunTimeLimitExceedet = false;
}

CSudoku.prototype.GetRunTime = function() {
  return new Date().getTime() - this.SolveStartTime;
}

CSudoku.prototype.RunTimeExceedet = function() {
  if (!this.LimitSolveTime) return false;
  if (this.GetRunTime() > this.SolveTimeLimit) {
    this.RunTimeLimitExceedet = true;
    return true;
  }
  return false;
}

CSudoku.prototype.InitGridViews = function() {
  for (var houseX = 0; houseX < 9; houseX++) {
    this.Rows[houseX] = new Array(9);
    this.Cols[houseX] = new Array(9);
    this.Boxes[houseX] = new Array(9);
  }
  var cellX = 0;
  for (var rowX = 0; rowX < 9; rowX++) {
    for (var colX = 0; colX < 9; colX++) {
      this.Rows[rowX][colX] = cellX;
      this.Cols[colX][rowX] = cellX;
      var boxX = this.BoxXofRowColX(rowX,colX);
      var boxCellX = this.BoxCellXofRowColX(rowX,colX);
      this.Boxes[boxX][boxCellX] = cellX;
      this.CellsRowX[cellX] = rowX;
      this.CellsColX[cellX] = colX;
      this.CellsBoxX[cellX] = boxX;
      this.CellsBoxCellX[cellX] = boxCellX;
      cellX++;
    }
  }
}

CSudoku.prototype.SaveStateToCookie = function() {
  function BoolToString(b) { return (b) ? '1' : '0'; }
  var states = '';
  states += BoolToString( this.GridEnabled ) + ',';
  states += BoolToString( this.GraphicHintsEnabled ) + ',';
  states += this.MethodOrder.toString() + ',';
  states += BoolToString( this.ShowAllMoves ) + ',';
  states += BoolToString( this.StopOnSolutions ) + ',';
  states += BoolToString( this.SlowMotion ) + ',';
  states += BoolToString( this.SortMovesByLevel ) + ',';
  states += BoolToString( this.LimitSolveTime );
  xSetCookie( this.Name + 'SudokuStates', states, 31 );
  this.AppSaveStateRequested = false;
}

CSudoku.prototype.LoadStateFromCookie = function() {
  var val = xGetCookie( this.Name + 'SudokuStates' );
  if (val === null) return;
  var states = val.split(',');
  this.EnableGrid( states[0] == '1' );
  this.EnableGraphicHints( states[1] == '1' );
  this.SetMethodOrder( parseInt( states[2], 10 ) );
  this.SetShowAllMoves( states[3] == '1' );
  this.SetStopOnSolutions( states[4] == '1' );
  this.SetSlowMotion( states[5] == '1' );
  this.SetSortMovesByLevel( states[6] == '1' );
  this.SetLimitSolveTime( states[7] == '1' );
}

CSudoku.prototype.SaveGameToCookie = function() {
  if (this.Running || this.SearchingSolutions) return;
  var enter = '';
  var ele = xGet( this.Name + 'SudokuStr' );
  if (ele) enter = ele.value;
  xSetCookie( this.Name + 'SudokuGame', this.GetSudokuAsString(), 31 );
  xSetCookie( this.Name + 'SudokuStartCells', this.GetStartCellsAsString(), 31 );
  xSetCookie( this.Name + 'SudokuEnter', enter, 31 );
}

CSudoku.prototype.LoadGameFromCookie = function() {
  var game = xGetCookie( this.Name + 'SudokuGame' );
  var start = xGetCookie( this.Name + 'SudokuStartCells' );
  var enter = xGetCookie( this.Name + 'SudokuEnter' );
  if (game) {
    this.InitSudokuFromString( game, start );
  }
  if (enter) {
    var ele = xGet( this.Name + 'SudokuStr' );
    ele.value = enter;
  }
}

CSudoku.prototype.SetEnterField = function( aGame ) {
  this.AppUpdateBegin();
  aGame = aGame || '';
  var ele = xGet( this.Name + 'SudokuStr' );
  ele.value = aGame;
  this.AppUpdateEnd();
}

CSudoku.prototype.ClearEnterField = function() {
  this.SetEnterField( '' );
}

CSudoku.prototype.LoadGameAndStateFromURL = function() {
  var game = UrlParameters.GetParameter('sudoku');
  if (game == '') return;
  this.InitSudokuFromString( game );
  if (game.indexOf('(') >= 0) {
    this.SaveAndExportConstellation();
  } else {
    this.SaveAndExportSudoku();
  }
  this.EnableGrid( true);
}

CSudoku.prototype.EnterSudokuFromString = function() {
  var game = '';
  var o = xGet( 'SdkSudokuStr' );
  if (o) game = o.value;
  if (game == '') return;
  this.InitSudokuFromString( game );
  if (game.indexOf('(') >= 0) {
    this.SaveAndExportConstellation();
  } else {
    this.SaveAndExportSudoku();
  }
}

CSudoku.prototype.BoxXofRowColX = function( aRowX, aColX ) {
  return div(aRowX,3) * 3 + div(aColX,3);
}

CSudoku.prototype.BoxCellXofRowColX = function( aRowX, aColX ) {
  return (aRowX % 3) * 3 + (aColX % 3);
}

CSudoku.prototype.RowXofBoxCellX = function( aBoxX, aBoxCellX ) {
  return div(aBoxX,3) * 3 + div(aBoxCellX,3);
}

CSudoku.prototype.ColXofBoxCellX = function( aBoxX, aBoxCellX ) {
  return (aBoxX % 3) * 3 + (aBoxCellX % 3);
}

CSudoku.prototype.RowXofCellX = function( aCellX ) {
  return this.CellsRowX[aCellX];
}

CSudoku.prototype.ColXofCellX = function( aCellX ) {
  return this.CellsColX[aCellX];
}

CSudoku.prototype.BoxXofCellX = function( aCellX ) {
  return this.CellsBoxX[aCellX];
}

CSudoku.prototype.BoxCellXofCellX = function( aCellX ) {
  return this.CellsBoxCellX[aCellX];
}

CSudoku.prototype.CSetContainsNum = function( aSet, aNum ) {
  // require( aNum >= 1 && aNum <= 9 );
  return (aSet & this.CSetBits[aNum]) > 0;
}

CSudoku.prototype.NextCSet = function( aCSet, aNumCSet ) {
  // require( this.CSetBitCount( aNumCSet ) == 1 );
  var nextNumCSet = 1;
  if (aNumCSet) nextNumCSet = aNumCSet << 1;
  while (nextNumCSet <= 0x100) {
    if (aCSet & nextNumCSet) return nextNumCSet;
    nextNumCSet <<= 1;
  }
  return 0;
}

CSudoku.prototype.CSetRemoveNum = function( aSet, aNum ) {
  // require( aNum >= 1 && aNum <= 9 );
  return aSet & ~this.CSetBits[aNum];
}

CSudoku.prototype.CSetAddNum = function( aSet, aNum ) {
  // require( aNum >= 1 && aNum <= 9 );
  return aSet | this.CSetBits[aNum];
}

CSudoku.prototype.IsCSetSubset = function( aSet, aSubset ) {
  return !((aSet ^ aSubset) & ~aSet);
}

CSudoku.prototype.CSetBitCount = function( aCSet ) {
  return this.BitCounts[aCSet];
}

CSudoku.prototype.CSetToString = function( aSet, aAppendixStr, bSkipLastAppendix ) {
  aAppendixStr = aAppendixStr || '';
  if (!xDef(bSkipLastAppendix)) bSkipLastAppendix = false;
  var s = '';
  for (var i = 1; i < 10; i++) {
    if (aSet & this.CSetBits[i]) {
      s += i.toString() + aAppendixStr;
    }
  }
  if (bSkipLastAppendix) {
    s = s.substr( 0, s.length-aAppendixStr.length );
  }
  return s;
}

CSudoku.prototype.ParseCSet = function( aCSetStr ) {
  var cset = 0;
  var sl = aCSetStr.length;
  for (var i = 0; i < sl; i++) {
    var numStr = aCSetStr.substr( i, 1 );
    if (this.IsNum( numStr )) cset |= this.NumToCSet( parseInt( numStr, 10 ) );
  }
  return cset;
}

CSudoku.prototype.NumToCSet = function( aNum ) {
  // require( aNum >= 0 && aNum <= 9);
  return this.CSetBits[aNum];
}

CSudoku.prototype.CSetBitToNum = function( aNumSetBit ) {
  for (var i = 1; i < 10; i++) {
    if (this.CSetBits[i] & aNumSetBit) { return i; }
  }
  return 0;
}

CSudoku.prototype.NextHint = function() {
  this.AppUpdateBegin();
  this.TextHintLevel++;
  this.AppUpdateEnd();
}

CSudoku.prototype.NewMove = function( aName, aCandidates, aSolutionX, aStatus, aHints, aLevel, aHelpPage ) {
  return {
    Name: aName,
    Candidates: aCandidates,
    SolutionX: aSolutionX,
    Status: aStatus,
    Hints: aHints,
    Level: aLevel,
    HelpPage: aHelpPage
  };
}

CSudoku.prototype.SortMoves = function() {
  // sort: solution moves befor other moves
  if (this.MovesCount < 2) return;
  if (this.SortMovesByLevel) {
    this.Moves.sort(
      function(a,b) {
        return a.Level - b.Level;
      }
    );
  } else {
    var oldMoves = this.Moves;
    this.Moves = [];
    for (var i = 0; i < this.MovesCount; i++) {
      if (oldMoves[i].SolutionX >= 0) {
        this.Moves.push( oldMoves[i] );
      }
    }
    for (var i = 0; i < this.MovesCount; i++) {
      if (oldMoves[i].SolutionX < 0) {
        this.Moves.push( oldMoves[i] );
      }
    }
  }
}

CSudoku.prototype.HasMoves = function() {
  return this.MovesCount > 0;
}

CSudoku.prototype.SelectFirstMove = function() {
  this.AppUpdateBegin();
  this.CurrMove = 0;
  this.TextHintLevel = 1;
  this.AppUpdateEnd();
}

CSudoku.prototype.SelectLastMove = function() {
  this.AppUpdateBegin();
  this.CurrMove = this.MovesCount-1;
  if (this.CurrMove < 0) this.CurrMove = 0;
  this.TextHintLevel = 1;
  this.AppUpdateEnd();
}

CSudoku.prototype.SelectNextMove = function() {
  this.AppUpdateBegin();
  if (this.CurrMove < this.MovesCount-1) this.CurrMove++;
  this.TextHintLevel = 1;
  this.AppUpdateEnd();
}

CSudoku.prototype.SelectNextMoveType = function() {
  if (this.MovesCount <= 0) return;
  this.AppUpdateBegin();
  var currMoveType = Math.floor( this.Moves[this.CurrMove].Level );
  while (this.CurrMove < this.MovesCount-1 && Math.floor( this.Moves[this.CurrMove].Level ) == currMoveType ) this.CurrMove++;
  this.TextHintLevel = 1;
  this.AppUpdateEnd();
}

CSudoku.prototype.SelectPrevMove = function() {
  this.AppUpdateBegin();
  this.CurrMove--;
  if (this.CurrMove < 0) this.CurrMove = 0;
  this.TextHintLevel = 1;
  this.AppUpdateEnd();
}

CSudoku.prototype.ClearMoves = function() {
  this.ClearCells( this.MovesFoundCandidates, 0 );
  this.ClearCells( this.MovesClearedCandidates, 0 );
  this.Moves = [];
  this.MovesCount = 0;
  this.CurrMove = 0;
  this.TextHintLevel = 0;
}

CSudoku.prototype.IsNumCSetInFoundCandidates = function( aNumCSet, aCellX ) {
  if (this.ShowAllMoves) return false;
  return (this.MovesFoundCandidates[aCellX] & aNumCSet) > 0;
}

CSudoku.prototype.IsCSetListInClearedCandidates = function( aCSetList, aListSize ) {
  if (this.ShowAllMoves) return false;
  for (var i = 0; i < aListSize; i++) {
    var cellX = aCSetList[2*i];
    var bits  = aCSetList[2*i+1];
    if (!this.IsCSetSubset( this.MovesClearedCandidates[cellX], bits )) return false;
  }
  return true;
}

CSudoku.prototype.AddNumBitToFoundCandidates = function( aNumBit, aCellX ) {
  this.MovesFoundCandidates[aCellX] |= aNumBit;
}

CSudoku.prototype.AddCSetListToClearedCandidates = function( aCSetList, aListSize ) {
  for (var i = 0; i < aListSize; i++) { this.MovesClearedCandidates[aCSetList[2*i]] |= aCSetList[2*i+1]; }
}

CSudoku.prototype.CreateMoves = function( aDelCandList, aCandidates, aStatus, aInfo, aHintNumCSet, aHintHouse ) {
  // returns true if no more moves are requested
  // mark cells and remove candiates
  // aDelCandList = [ <cellX>, <delCandCSet>, ... ]
  // aInfo = { Name, Help, Level }

  var delCandListSize = div( aDelCandList.length, 2 );
  if (delCandListSize <= 0) return false;

  aHintHouse = aHintHouse || '';
  var solutionCells = [];
  var nDelCand = 0;

  for (var delCandX = 0; delCandX < delCandListSize; delCandX++) {

    // remove candidate
    var cellX = aDelCandList[2*delCandX];
    var delCSet = aDelCandList[2*delCandX+1];

    var cand = aCandidates[cellX];
    var nOldBits = this.CSetBitCount( cand );
    cand = cand & ~delCSet;
    var nNewBits = this.CSetBitCount( cand );

    if (nNewBits < nOldBits) {
      aCandidates[cellX] = cand;
      nDelCand += nOldBits - nNewBits;
      var cellStatus = aStatus[cellX];
      if (cellStatus == '') cellStatus = 'r';
      cellStatus += this.CSetToString( delCSet, 'x' );
      aStatus[cellX] = cellStatus;
      if (nNewBits == 1) {
        // solution found
        solutionCells.push( cellX );
      }
    }

  }

  var nSolutions = solutionCells.length;
  if (nSolutions > 0) {

    for (var solutionX = 0; solutionX < nSolutions; solutionX++) {
      var cellX = solutionCells[solutionX];
      var solutionNumBit = aCandidates[cellX];

      if (!this.IsNumCSetInFoundCandidates( solutionNumBit, cellX )) {
        this.AddNumBitToFoundCandidates( solutionNumBit, cellX );

        // mark solution number
        cellStatus = aStatus[cellX];
        var p = cellStatus.indexOf(':') + 1;
        if (p > 1) {
          cellStatus = cellStatus.substr(0,p) + 'Y' + cellStatus.substr(p);
        } else {
          cellStatus = 'Y' + aStatus[cellX].substr(1);
        }
        cellStatus += this.CSetToString( solutionNumBit, 'O' );
        var solutionStatus = this.CopyCells( aStatus );
        solutionStatus[cellX] = cellStatus;

        this.AddMove( aInfo.Name, aCandidates, solutionStatus, cellX, aInfo.Level, aHintNumCSet, aHintHouse, nDelCand, aInfo.Help );
        if (this.MoveLimitExceeded()) return true;
      }
    }

  } else {

    if (!this.IsCSetListInClearedCandidates( aDelCandList, delCandListSize )) {

      this.AddMove( aInfo.Name, aCandidates, aStatus, -1, aInfo.Level, aHintNumCSet, aHintHouse, nDelCand, aInfo.Help );
      this.AddCSetListToClearedCandidates( aDelCandList, delCandListSize );
      if (this.MoveLimitExceeded()) return true;

    }

  }

  return false;
}

CSudoku.prototype.AddMove = function( aName, aCandidates, aStatus, aSolutionX, aLevel, aHintNums, aHintHouse, aNDelCand, aHelpPage ) {
  // aCandidates as array of NumSet
  // aStatus as array of string
  // aHintNums as CSet: numbers that are involved in the move or EmptyCSet
  // aHintHouse as string: e.g. Box X, Linie X, Spalte X, ... or ''
  // aLevel as 1-9: difficulty level of a specific step. Will be combined with this.CurrLevel.

  aHintNums = aHintNums || 0;
  aHintHouse = aHintHouse || '';
  aLevel = aLevel || 0;
  aNDelCand = aNDelCand || 0;
  aHelpPage = aHelpPage || aName;
  var moveLevel = this.CurrLevel + aLevel / 10;
  var hintText = this.MakeHintText( aCandidates, aSolutionX, aHintNums, aHintHouse, aNDelCand );
  var move = this.NewMove( aName, aCandidates, aSolutionX, aStatus, hintText, moveLevel, aHelpPage );
  this.Moves.push( move );
  this.MovesCount++;
}

CSudoku.prototype.CSetToVectorString = function( aCSet ) {
  return '(' + this.CSetToString( aCSet, ',', true ) + ')';
}

CSudoku.prototype.MakeCandidatesText = function ( aHintNums, aCount ) {
  var text;
  if (this.CSetBitCount( aHintNums ) != 1 || aCount > 1) {
    text = 'Kandidaten ';
  } else {
    text = 'Kandidat ';
  }
  if (aHintNums) text += this.CSetToVectorString( aHintNums );
  return text;
}

CSudoku.prototype.MakeBoxesText = function ( aBoxesCSet ) {
  var text;
  if (this.CSetBitCount( aBoxesCSet ) > 1) {
    text = 'Boxen ';
  } else {
    text = 'Box ';
  }
  text += this.CSetToString( aBoxesCSet, ',', true );
  return text;
}

CSudoku.prototype.MakeHintText = function( aCandidates, aSolutionX, aHintNumCSet, aHintHouse, aNDelCand ) {
  // returns an array of string: hint text list

  var textList = [];
  var hintHouseText = aHintHouse;
  if (aSolutionX >= 0) {
    if (aHintNumCSet || aHintHouse == '') {
      hintHouseText = 'Box ' + (this.BoxXofCellX(aSolutionX)+1);
    }
  }

  if (aSolutionX >= 0) {
    textList.push( 'eine Zahl in ' + hintHouseText + ' kann gesetzt werden' );
  } else {
    if (aNDelCand > 0) {
      if (aNDelCand == 1) {
        textList.push( 'ein Kandidat kann gelöscht werden' );
      } else {
        textList.push( aNDelCand + ' Kandidaten können gelöscht werden' );
      }
    } else {
      textList.push( 'Kandidaten können gelöscht werden' );
      if (!aHintNumCSet) return textList;
    }
  }

  if (aHintNumCSet) {
    var text = this.MakeCandidatesText( aHintNumCSet, 0 );
    textList.push( 'mit ' + text );
    if (aHintHouse != '') {
      textList.push( 'mit ' + text + ' in ' + aHintHouse );
    }
  }

  if (aSolutionX >= 0) {
    var text = '<b>Zahl ' + this.CSetToString( aCandidates[aSolutionX] ) + '</b>';
    textList.push( text + ' in ' + hintHouseText + ' kann gesetzt werden' );
    textList.push( text + ' in Zeile ' + (this.RowXofCellX(aSolutionX)+1) + ' Spalte ' + (this.ColXofCellX(aSolutionX)+1) );
  } else {
    var text = 'mit ' + this.MakeCandidatesText( aHintNumCSet, 0 );
    if (!aHintNumCSet) text = '';
    if (aNDelCand > 0) {
      if (text != '') text += ' &rArr; ';
      if (aNDelCand == 1) {
        text += '1 Kandidat weniger';
      } else {
        text += aNDelCand + ' Kandidaten weniger';
      }
    }
    textList.push( text );
  }

  return textList;
}

CSudoku.prototype.MoveLimitExceeded = function() {
  if (this.Running && this.MovesCount > 0) return true;
  return !(this.MaxMoves == 0 || this.MovesCount < this.MaxMoves);
}

CSudoku.prototype.CandidatesFromHouse = function( aHouse ) {
  // aHouse as this.Rows[x], Cols[x] or Boxes[x]
  var numSet = 0;
  for (var houseX = 0; houseX < 9; houseX++) { numSet |= this.CandidateCells[aHouse[houseX]]; }
  return numSet;
}

CSudoku.prototype.NewCells = function( aValue ) {
  var cells = new Array(81);
  return this.ClearCells( cells, aValue );
}

CSudoku.prototype.ClearCells = function( aCells, aValue ) {
  for (var i = 0; i < 81; i++) { aCells[i] = aValue; }
  return aCells;
}

CSudoku.prototype.CopyCells = function( aSrcCells, aDestCells ) {
  var aDestCells = aDestCells || new Array(81);
  for (var i = 0; i < 81; i++) { aDestCells[i] = aSrcCells[i]; }
  return aDestCells;
}

CSudoku.prototype.IsSameCells = function( aCells1, aCells2 ) {
  for (cellX = 0; cellX < 81; cellX++) {
    if (aCells1[cellX] != aCells2[cellX]) return false;
  }
  return true;
}

CSudoku.prototype.NewCandidates = function() {
  return this.CopyCells( this.CandidateCells );
}

CSudoku.prototype.NewStatus = function() {
  return this.NewCells( '' );
}

CSudoku.prototype.InitSudokuFromCells = function( aSolvedCells, aCandidateCells, aStartCells ) {
  this.AppUpdateBegin();
  this.SaveState();
  this.Init();
  this.CopyCells( aSolvedCells, this.SolvedCells );
  this.CopyCells( aCandidateCells, this.CandidateCells );
  this.CopyCells( aStartCells, this.StartCells );
  this.CopyCells( this.SolvedCells, this.LastSolvedCells );
  this.CandidatesAreValid = true
  this.AppRequestHints();
  this.AppUpdateEnd();
}

CSudoku.prototype.InitSudokuFromString = function( aString, aStartCellsString ) {
  // aString = '270640830640376...' 9x9 chars
  this.AppUpdateBegin();
  this.SaveState();
  this.Init();
  var s = aString.replace( /\./g, '0' );
  s = s.replace( /[^0-9()]/g, '' );
  var sl = s.length;
  this.ClearCells( this.SolvedCells, 0 );
  this.ClearCells( this.CandidateCells, 0 );
  var nSolved = 0;
  var nCand = 0;
  var cellX = 0;
  var strX = 0;
  while (strX < sl && cellX < 81) {
    var c = s.substr(strX,1);
    if (c == '(') {
      var endCSetX = s.indexOf( ')', strX );
      if (endCSetX <= 0) endCSetX = sl;
      var csetStr = s.substr( strX+1, endCSetX-strX-1 );
      this.CandidateCells[cellX] = this.ParseCSet( csetStr );
      strX = endCSetX + 1;
      nCand++;
    } else {
      this.SolvedCells[cellX] = parseInt( c, 10 );
      strX++;
      if (this.SolvedCells[cellX] > 0) nSolved++;
    }
    cellX++;
  }
  this.CandidatesAreValid = false;
  if (nCand + nSolved == 81) {
    this.CandidatesAreValid = true;
  }
  this.InitStartCells( aStartCellsString );
  this.AppRequestHints();
  this.AppUpdateEnd();
}

CSudoku.prototype.GetSudokuAsString = function() {
  // returns '210360004 510...'
  var s = '';
  for (var i = 0; i < 81; i++) {
    s += this.SolvedCells[i].toString();
    if ((((i+1) % 9) == 0) && (i < 80)) { s += ' '; }
  }
  return s;
}

CSudoku.prototype.GetConstellationAsString = function() {
  // returns '21(48)(78)364 51(68)...'
  var s = '';
  for (var i = 0; i < 81; i++) {
    if (this.SolvedCells[i] > 0) {
      s += this.SolvedCells[i].toString();
    } else {
      s += '(' + this.CSetToString( this.CandidateCells[i] ) + ')';
    }
    if ((((i+1) % 9) == 0) && (i < 80)) { s += ' '; }
  }
  return s;
}

CSudoku.prototype.GetStartCellsAsString = function() {
  var s = '';
  for (var i = 0; i < 81; i++) {
    s += this.StartCells[i].toString();
  }
  return s;
}

CSudoku.prototype.StoreSudoku = function( bSkipSameOrFull ) {
  if (!xDef(bSkipSameOrFull)) bSkipSameOrFull = false;
  if (bSkipSameOrFull) {
    if (this.GetFilledCellCount() == 81) return;
    if (this.StoragePtr > 0 &&
      this.IsSameCells( this.SolvedCells,    this.StorageSolvedCells   [this.StoragePtr-1] ) &&
      this.IsSameCells( this.CandidateCells, this.StorageCandidateCells[this.StoragePtr-1] ) &&
      this.IsSameCells( this.StartCells,     this.StorageStartCells    [this.StoragePtr-1] )
    ) {
      return;
    }
  }
  this.StorageSolvedCells   [this.StoragePtr] = this.CopyCells( this.SolvedCells );
  this.StorageCandidateCells[this.StoragePtr] = this.CopyCells( this.CandidateCells );
  this.StorageStartCells    [this.StoragePtr] = this.CopyCells( this.StartCells );
  this.StoragePtr++;
}

CSudoku.prototype.SaveAndExportSudoku = function() {
  this.AppUpdateBegin();
  this.StoreSudoku();
  var ele = xGet( this.Name + 'SudokuStr' );
  if (ele) ele.value = this.GetSudokuAsString();
  this.AppUpdateEnd();
}

CSudoku.prototype.SaveAndExportConstellation = function() {
  this.AppUpdateBegin();
  this.StoreSudoku();
  var ele = xGet( this.Name + 'SudokuStr' );
  if (ele) ele.value = this.GetConstellationAsString();
  this.AppUpdateEnd();
}

CSudoku.prototype.RecallSudoku = function() {
  if (this.StoragePtr == 0) return;
  this.StoragePtr--;
  this.InitSudokuFromCells(
    this.StorageSolvedCells   [this.StoragePtr],
    this.StorageCandidateCells[this.StoragePtr],
    this.StorageStartCells    [this.StoragePtr]
  );
  if (this.StoragePtr == 0) this.StoragePtr++; // keep always at least one sudoku ready
}

CSudoku.prototype.Init = function( bAll ) {
  if (!xDef(bAll)) bAll = true;
  if (this.Timer) clearTimeout( this.Timer );
  this.Timer = null;
  this.Running = false;
  this.Stopped = false;
  this.SearchingSolutions = false;
  this.AllSolutionsFound = false;
  this.ClearCells( this.LastSolution, 0 );
  this.ClearCells( this.LastStartCells, 0 );
  this.SolutionCount = 0;
  this.StackPtr = 0;
  this.CurrLevel = 0;
  this.MaxLevel = 0;
  this.MaxLevelName = '';
  this.MaxLevelHelp = '';
  this.CandidatesAreValid = false;
  if (bAll) {
    this.GuiButtonFilterState = false;
    this.GuiButtonState = '';
    this.AppRequestButtonDisplayUpdate();
  }
}

CSudoku.prototype.InitStartCells = function( aStartCellsString ) {
  // For each N in 1-9 in this.SolvedCells set 1 in this.StartCells, else 0.
  aStartCellsString = aStartCellsString || '';
  var sl = aStartCellsString.length;
  if (sl > 81) sl = 81;
  for (var i = 0; i < sl; i++) {
    this.StartCells[i] = (aStartCellsString.substr(i,1) != '0') ? 1 : 0;
  }
  for (var i = sl; i < 81; i++) {
    this.StartCells[i] = (this.SolvedCells[i] > 0) ? 1 : 0;
  }
  this.CopyCells( this.SolvedCells, this.LastSolvedCells );
}

CSudoku.prototype.EnableGrid = function( aFlag ) {
  if (!this.GridCreated || this.GridEnabled == aFlag) return;
  this.AppUpdateBegin();
  this.GridEnabled = aFlag;
  if (this.GridEnabled) {
    xDisplay( this.Name + 'HelpDiv', 'none' );
    xDisplay( this.Name + 'GridDiv', 'block' );
  } else {
    xDisplay( this.Name + 'GridDiv', 'none' );
    xDisplay( this.Name + 'HelpDiv', 'block' );
  }
  this.AppRequestSaveState();
  this.AppRequestStateDisplayUpdate();
  this.AppUpdateEnd();
}

CSudoku.prototype.EnableGraphicHints = function( aBool ) {
  if (this.GraphicHintsEnabled == aBool) return;
  this.AppUpdateBegin();
  this.GraphicHintsEnabled = aBool;
  this.TextHintsEnabled = !aBool;
  this.TextHintLevel = 0;
  this.AppRequestSaveState();
  this.AppRequestStateDisplayUpdate();
  this.AppUpdateEnd();
}

CSudoku.prototype.SetMethodOrder = function( aOrder ) {
  if (this.MethodOrder == aOrder) return;
  this.AppUpdateBegin();
  var hintLevel = this.TextHintLevel;
  if (hintLevel > 1) hintLevel = 1;
  this.SaveState();
  this.MethodOrder = aOrder;
  this.TextHintLevel = hintLevel;
  this.AppRequestSaveState();
  this.AppRequestStateDisplayUpdate();
  this.AppRequestHints();
  this.AppUpdateEnd();
}

CSudoku.prototype.SetShowAllMoves = function( aFlag ) {
  if (this.ShowAllMoves == aFlag) return;
  this.AppUpdateBegin();
  this.ShowAllMoves = aFlag;
  this.TextHintLevel = 0;
  this.AppRequestSaveState();
  this.AppRequestStateDisplayUpdate();
  this.AppRequestHints();
  this.AppUpdateEnd();
}

CSudoku.prototype.SetSortMovesByLevel = function( aFlag ) {
  if (this.SortMovesByLevel == aFlag) return;
  this.AppUpdateBegin();
  this.SortMovesByLevel = aFlag;
  this.TextHintLevel = 0;
  this.AppRequestSaveState();
  this.AppRequestStateDisplayUpdate();
  this.AppRequestHints();
  this.AppUpdateEnd();
}

CSudoku.prototype.SetStopOnSolutions = function( aFlag ) {
  if (this.StopOnSolutions == aFlag) return;
  this.AppUpdateBegin();
  this.StopOnSolutions = aFlag;
  this.AppRequestSaveState();
  this.AppRequestStateDisplayUpdate();
  this.AppUpdateEnd();
}

CSudoku.prototype.SetSlowMotion = function( aFlag ) {
  if (this.SlowMotion == aFlag) return;
  this.AppUpdateBegin();
  this.SlowMotion = aFlag;
  this.AppRequestSaveState();
  this.AppRequestStateDisplayUpdate();
  this.AppUpdateEnd();
}

CSudoku.prototype.SetLimitSolveTime = function( aFlag ) {
  if (this.LimitSolveTime == aFlag) return;
  this.AppUpdateBegin();
  this.LimitSolveTime = aFlag;
  this.AppRequestSaveState();
  this.AppRequestStateDisplayUpdate();
  this.AppRequestHints();
  this.AppUpdateEnd();
}

CSudoku.prototype.CanUndo = function() {
  return (this.UndoFill > 0);
}

CSudoku.prototype.ResetUndo = function() {
  this.UndoFill = 0;
  this.UndoPtr = 0;
}

CSudoku.prototype.Undo = function() {
  if (!this.CanUndo()) return;
  this.AppUpdateBegin();
  this.Init( false );
  this.UndoPtr--;
  if (this.UndoPtr < 0) this.UndoPtr = 80;
  this.UndoFill--;
  var x = this.UndoPtr;
  this.CopyCells( this.UndoBufferSolvedCells[x], this.SolvedCells );
  this.CopyCells( this.UndoBufferStartCells[x], this.StartCells );
  this.CopyCells( this.UndoBufferCandidateCells[x], this.CandidateCells );
  this.CopyCells( this.UndoBufferStatusCells[x], this.StatusCells );
  this.CopyCells( this.UndoBufferLastSolvedCells[x], this.LastSolvedCells );
  this.CandidatesAreValid = this.UndoBufferCandidatesAreValid[x];
  this.MaxLevel = this.UndoBufferMaxLevel[x];
  this.MaxLevelName = this.UndoBufferMaxLevelName[x];
  this.MaxLevelHelp = this.UndoBufferMaxLevelHelp[x];
  this.MethodOrder = this.UndoBufferMethodOrder[x];
  this.AppRequestHints();
  this.AppUpdateEnd();
}

CSudoku.prototype.SaveState = function() {
  if (!this.UndoEnabled || this.Running || this.SearchingSolutions) return;
  if (this.GetFilledCellCount() == 0) return;
  var x = this.UndoPtr;
  this.UndoBufferSolvedCells[x] = this.CopyCells( this.SolvedCells );
  this.UndoBufferStartCells[x] = this.CopyCells( this.StartCells );
  this.UndoBufferCandidateCells[x] = this.CopyCells( this.CandidateCells );
  this.UndoBufferStatusCells[x] = this.CopyCells( this.StatusCells );
  this.UndoBufferLastSolvedCells[x] = this.CopyCells( this.LastSolvedCells );
  this.UndoBufferCandidatesAreValid[x] = this.CandidatesAreValid;
  this.UndoBufferMaxLevel[x] = this.MaxLevel;
  this.UndoBufferMaxLevelName[x] = this.MaxLevelName;
  this.UndoBufferMaxLevelHelp[x] = this.MaxLevelHelp;
  this.UndoBufferMethodOrder[x] = this.MethodOrder;
  this.UndoPtr++;
  if (this.UndoPtr > 80) this.UndoPtr = 0;
  this.UndoFill++;
  if (this.UndoFill > 81) this.UndoFill = 81;
  this.CopyCells( this.SolvedCells, this.LastSolvedCells );
}

CSudoku.prototype.OutDebug = function( aText ) {
  //xInnerHTML( 'debug', aText );
}

CSudoku.prototype.OutStatus = function( aText ) {
  xInnerHTML( this.DocStatusID, aText );
}

CSudoku.prototype.OutMethods = function( aText ) {
  xInnerHTML( this.DocMethodsID, aText );
}

CSudoku.prototype.OutGridNums = function( aCellX, aNewInputCellBG ) {
  var newGridCellBG = aNewInputCellBG;
  if (newGridCellBG == '#ddd') newGridCellBG = '#fff';
  if (this.GuiButtonFilterState) {
    if (this.GuiButtonFilterNumbers) {
      if (this.CandidateCells[aCellX] && !(this.CandidateCells[aCellX] & ~this.GuiButtonFilterNumbers)) {
        var cols = new Array( '#fb6', '#afa', '#bbf', '#faf', '#aff' );
        newGridCellBG = cols[this.ColorCells[aCellX] % 5];
      } else if (this.IsCSetSubset( this.CandidateCells[aCellX], this.GuiButtonFilterNumbers )) {
        var cols = new Array( '#ff8', '#afa', '#bbf', '#faf', '#aff' );
        newGridCellBG = cols[this.ColorCells[aCellX] % 5];
      }
    } else {
      var cols = new Array( '#fff', '#afa', '#bbf', '#faf', '#aff' );
      newGridCellBG = cols[this.ColorCells[aCellX] % 5];
    }
  }
  var newGridCellValue = this.FormatGridNums( aCellX );
  if (this.LastGridCellBG[aCellX] != newGridCellBG) {
    xStyle( this.GuiGridTableCells[aCellX], 'backgroundColor', newGridCellBG );
    this.LastGridCellBG[aCellX] = newGridCellBG;
  }
  if (this.LastGridCellValue[aCellX] != newGridCellValue) {
    xInnerHTML( this.GuiGridDivCells[aCellX], newGridCellValue );
    this.LastGridCellValue[aCellX] = newGridCellValue;
  }
}

CSudoku.prototype.Color = function( aCode ) {
  switch (aCode) {
    case 'r':
      return '#f00';
      break;
    case 'g':
      return '#0a0';
      break;
    case 'b':
      return '#00f';
      break;
    case 'c':
      return '#0af';
      break;
    case 'm':
      return '#f0f';
      break;
    case 'x':
      return '#f00';
      break;
    case 'O':
      return '#000';
      break;
    default:
      return '#000';
  }
}

CSudoku.prototype.BgColor = function( aCode ) {
  switch (aCode) {
    case 'r':
      return '#fcc';
      break;
    case 'R':
      return '#f44';
      break;
    case 'g':
      return '#dfd';
      break;
    case 'G':
      return '#9e9';
      break;
    case 'b':
      return '#ddf';
      break;
    case 'B':
      return '#aaf';
      break;
    case 'c':
      return '#dff';
      break;
    case 'C':
      return '#9ff';
      break;
    case 'm':
      return '#fdf';
      break;
    case 'M':
      return '#e8e';
      break;
    case 'o':
      return '#fdc';
      break;
    case 'O':
      return '#fc7';
      break;
    case 'y':
      return '#ffa';
      break;
    case 'Y':
      return '#ff5';
      break;
    default:
      return '#ddd';
  }
}

CSudoku.prototype.FormatGridNums = function( aCellX ) {
  var s = '';
  var n = 1;
  var solutionNum = this.SolvedCells[aCellX];
  if (solutionNum == 0) {
    if (this.GuiButtonFilterState) {
      for (var i = 0; i < 3; i++) {
        for (var j = 0; j < 3; j++) {
          var sn = n.toString();
          if (this.CSetContainsNum( this.CandidateCells[aCellX], n )) {
            if (this.CSetContainsNum( this.GuiButtonFilterNumbers, n )) {
              s += '<span style="background-color:#d60; color:#fff;">' + sn + '</span>';
            } else {
              s += sn;
            }
          } else {
            s += "&nbsp;"
          }
          if (j < 2) { s += "&nbsp;"; }
          n++;
        }
        if (i < 2) { s += "<br>"; }
      }
    } else {
      var status = this.StatusCells[aCellX];
      if (this.GraphicHintsEnabled && status == '') {
        if (this.MovesCount > 0) {
          status = this.Moves[this.CurrMove].Status[aCellX];
          var p = status.indexOf(':');
          if (p > 0) status = status.substr(p+1);
        }
      }
      for (var i = 0; i < 3; i++) {
        for (var j = 0; j < 3; j++) {
          var sn = n.toString();
          var p = status.indexOf(sn);
          if (p >= 0) {
            var bgColor = this.Color( status.substr(p+1,1) );
            s += '<span style="background-color:' + bgColor + '; color:#fff;">' + sn + '</span>';
          } else if (this.CSetContainsNum( this.CandidateCells[aCellX], n )) {
            s += sn;
          } else {
            s += "&nbsp;"
          }
          if (j < 2) { s += "&nbsp;"; }
          n++;
        }
        if (i < 2) { s += "<br>"; }
      }
    }
  } else { // if (solutionNum > 0)
    if (this.LastSolvedCells[aCellX] != solutionNum) {
      s = '<span class="solution updated">' + solutionNum.toString() + '</span>';
    } else {
      s = '<span class="solution">' + solutionNum.toString() + '</span>';
    }
  }
  return s;
}

CSudoku.prototype.InitSudoku = function() {
  this.AppUpdateBegin();
  this.SaveState();
  this.Init();
  this.ClearCells( this.SolvedCells, 0 );
  this.PrepareMethods( true );
  this.InitStartCells();
  this.LoadGameFromCookie();
  this.LoadStateFromCookie();
  this.LoadGameAndStateFromURL();
  this.AppRequestHints();
  this.AppUpdateEnd();
}

CSudoku.prototype.ClearSudoku = function() {
  this.AppUpdateBegin();
  this.SaveState();
  this.Init();
  this.ClearCells( this.SolvedCells, 0 );
  this.PrepareMethods( true );
  this.InitStartCells();
  this.AppRequestHints();
  this.AppUpdateEnd();
}

CSudoku.prototype.MakeSudokuGui = function() {
  wl('<table id="'+this.Name+'" class="SudokuTable">');
  var cellX = 0;
  for (var i = 0; i < 9; i++) {
    wl('<tr>');
    for (var j = 0; j < 9; j++) {
      var cellCss = "cell";
      if ((i % 3) == 0) cellCss += "U";
      if ((j % 3) == 0) cellCss += "L";
      var cellID = this.Name + cellX;
      wl('<td id="T'+cellID+'" class="'+cellCss+'"><input type="text" id="I'+cellID+'" maxlength="1" size="1" onfocus="CSudokuShowFieldInfos(\''+this.Name+'\','+cellX+',\'I'+cellID+'\')" onchange="CSudokuHandleInput(\''+this.Name+'\','+cellX+')" onkeyup="CSudokuHandleInput(\''+this.Name+'\','+cellX+')"></td>');
      cellX++;
    }
    wl('</tr>');
  }
  wl('</table>');
  for (var cellX = 0; cellX < 81; cellX++) {
    var cellID = this.Name + cellX;
    this.GuiSudokuTableCells[cellX] = xGet("T"+cellID);
    this.GuiSudokuInputCells[cellX] = xGet("I"+cellID);
  }
}

CSudoku.prototype.MakeGridGui = function() {
  wl('<table id="'+this.Name+'Grid" class="SudokuTable">');
  var cellX = 0;
  for (var i = 0; i < 9; i++) {
    wl('<tr>');
    for (var j = 0; j < 9; j++) {
      var cellCss = "cell";
      if ((i % 3) == 0) cellCss += "U";
      if ((j % 3) == 0) cellCss += "L";
      var cellID = this.Name + cellX;
      wl('<td id="TG'+cellID+'" class="'+cellCss+'"><div id="G'+cellID+'" class="GridCell" onclick="OnGridClick('+cellX+')">&nbsp;</div></td>');
      cellX++;
    }
    wl('</tr>');
  }
  wl('</table>');
  for (var cellX = 0; cellX < 81; cellX++) {
    var cellID = this.Name + cellX;
    this.GuiGridTableCells[cellX] = xGet("TG"+cellID);
    this.GuiGridDivCells[cellX] = xGet("G"+cellID);
  }
  this.GridCreated = true;
}

CSudoku.prototype.OnGuiBtnClick = function( aButton ) {
  // aButton as string of length 1
  this.AppUpdateBegin();
  var modifier = false;
  if (isNaN(aButton) && aButton.length > 1) {
    if (aButton.substr(0,1) == '*') {
      modifier = true;
      aButton = aButton.substr(1);
    }
  }
  if (!isNaN(aButton)) {
    // number button clicked
    var num = parseInt( aButton, 10 );
    if (this.GuiButtonState == 'K' || this.GuiButtonState == 'Z') {
      if (this.GuiButtonSetNumber == num || num == 0) {
        this.GuiButtonSetNumber = 0;
      } else {
        this.GuiButtonSetNumber = num;
      }
    } else if (this.GuiButtonState == 'F') {
      if (this.MarkerFilterMode) {
        for (var cellX = 0; cellX < 81; cellX++) {
          if (num == 0) {
            this.ClearCells( this.ColorCells, 0 );
          } else {
            if (this.CSetBitCount( this.CandidateCells[cellX] ) == num) this.ColorCells[cellX]++;
          }
        }
      } else if (num == 0) {
        this.GuiButtonFilterNumbers = 0;
      } else {
        var numCSet = this.NumToCSet( num );
        if (modifier || this.GuiButtonFilterKeyPressed) {
          if (this.GuiButtonFilterNumbers == numCSet) {
            this.GuiButtonFilterNumbers ^= numCSet;
          } else {
            this.GuiButtonFilterNumbers = numCSet;
          }
        } else {
          this.GuiButtonFilterNumbers ^= numCSet;
        }
        if (this.CSetContainsNum( this.GuiButtonFilterNumbers, num )) {
          this.GuiButtonSetNumber = num;
        }
      }
    } else {
      this.GuiButtonSetNumber = num;
      this.GuiButtonState = 'Z';
    }
    this.GuiButtonFilterKeyPressed = false;
  } else if (aButton == 'K') {
    if (this.GuiButtonState == 'K') {
      if (this.GuiButtonFilterState) {
        this.GuiButtonState = 'F';
      } else {
        this.GuiButtonState = '';
      }
    } else {
      this.GuiButtonState = 'K';
    }
    this.GuiButtonFilterKeyPressed = false;
  } else if (aButton == 'Z') {
    if (this.GuiButtonState == 'Z') {
      if (this.GuiButtonFilterState) {
        this.GuiButtonState = 'F';
      } else {
        this.GuiButtonState = '';
      }
    } else {
      this.GuiButtonState = 'Z';
    }
    this.GuiButtonFilterKeyPressed = false;
  } else if (aButton == 'F') {
    this.GuiButtonFilterKeyPressed = false;
    if (this.GuiButtonState == 'F') {
      this.GuiButtonState = '';
      this.GuiButtonFilterState = false;
      this.ClearCells( this.ColorCells, 0 );
    } else {
      this.GuiButtonState = 'F';
      this.GuiButtonFilterState = true;
      this.GuiButtonFilterKeyPressed = true;
    }
  } else if (aButton == 'C') {
    this.GuiButtonFilterKeyPressed = false;
    this.ClearCells( this.ColorCells, 0 );
    if (this.GuiButtonState == 'Z' || this.GuiButtonState == 'K') {
      this.GuiButtonFilterState = false;
    }
  }
  this.AppRequestButtonDisplayUpdate();
  this.AppUpdateEnd();
}

CSudoku.prototype.IsEventInInputElement = function( ev ) {
  var ele = ev.target;
  while (ele) {
    if (((ele.tagName == 'INPUT') && (ele.type == 'text')) || (ele.tagName == 'TEXTAREA')) return true;
    ele = ele.parentNode;
  }
  return false;
}

CSudoku.prototype.HandleOnKeyDown = function( ev ) {
  if (this.IsEventInInputElement(ev)) return;
  var done = false;
  var markerMode = false;
  if (!ev.ctrlKey && !ev.altKey && !ev.shiftKey) {
    if (ev.keyCode >= 48 && ev.keyCode <= 57) {
      this.OnGuiBtnClick( ev.keyCode - 48 );
      done = true;
    }
    if (ev.keyCode >= 96 && ev.keyCode <= 105) {
      this.OnGuiBtnClick( '*' + (ev.keyCode-96) );
      done = true;
    }
    if (ev.keyCode == 190 || ev.keyCode == 110) { // decimal point
      this.MarkerFilterMode = true;
      markerMode = true;
      done = true;
    }
    if (ev.keyCode == 90 || ev.keyCode == 111) { // Z or slash on keypad
      this.OnGuiBtnClick( 'Z' );
      done = true;
    }
    if (ev.keyCode == 70 || ev.keyCode == 109) {
      this.OnGuiBtnClick( 'F' );
      done = true;
    }
    if (ev.keyCode == 75 || ev.keyCode == 106) { // K or * on keypad
      this.OnGuiBtnClick( 'K' );
      done = true;
    }
    if (ev.keyCode == 67) {
      this.OnGuiBtnClick( 'C' );
      done = true;
    }
    // Sudoku Functions
    if (ev.keyCode == 80) { // P
      this.NextHint();
      done = true;
    }
    if (ev.keyCode == 83) { // S
      this.SolveStep();
      done = true;
    }
    if (ev.keyCode == 36) { // Home
      this.SelectFirstMove();
      done = true;
    }
    if (ev.keyCode == 35) { // End
      this.SelectLastMove();
      done = true;
    }
    if (ev.keyCode == 37) { // Cursor left
      this.SelectPrevMove();
      done = true;
    }
    if (ev.keyCode == 39) { // Cursor right
      this.SelectNextMove();
      done = true;
    }
    if (ev.keyCode == 76) { // L
      this.Solve( false );
      done = true;
    }
    if (ev.keyCode == 84) { // T
      this.Solve( true );
      done = true;
    }
    if (ev.keyCode == 85) { // U
      this.Undo();
      done = true;
    }
    if (ev.keyCode == 71) { // G
      this.EnableGraphicHints( !this.GraphicHintsEnabled );
      done = true;
    }
    if (ev.keyCode == 65) { // A
      this.SetShowAllMoves( !this.ShowAllMoves );
      done = true;
    }
    if (ev.keyCode == 77) { // M
      this.SetSortMovesByLevel( !this.SortMovesByLevel );
      done = true;
    }
    if (ev.keyCode == 78) { // N
      this.SetMethodOrder( (this.MethodOrder == 1) ? 2 : 1 );
      done = true;
    }
    if (ev.keyCode == 88) { // X
      this.EnableGrid( !this.GridEnabled );
      done = true;
    }
  }
  if (!ev.ctrlKey && !ev.altKey && ev.shiftKey) {
    if (ev.keyCode == 39) { // Cursor right
      this.SelectNextMoveType();
      done = true;
    }
    if (ev.keyCode == 37) { // Cursor left
      this.SelectFirstMove();
      done = true;
    }
  }
  if (done) {
    ev.PreventDefault();
    ev.StopPropagation();
  }
  if (!markerMode) {
    this.MarkerFilterMode = false;
  }
}

CSudoku.prototype.UpdateGuiState = function() {

  var ele = xGet( this.Name + 'EnableGridCB' );
  if (ele) ele.checked = this.GridEnabled;

  var ele = xGet( this.Name + 'GraphicHintsCB' );
  if (ele) ele.checked = this.GraphicHintsEnabled;
  xDisplay( this.Name + 'NextHintBtn', this.TextHintsEnabled ? '' : 'none' );

  var ele = xGet( this.Name + 'PreferNakedSinglesCB' );
  if (ele) ele.checked = (this.MethodOrder == 2);

  var ele = xGet( this.Name + 'ShowAllMovesCB' );
  if (ele) ele.checked = (this.ShowAllMoves);

  var ele = xGet( this.Name + 'SortMovesByLevelCB' );
  if (ele) ele.checked = (this.SortMovesByLevel);

  var ele = xGet( this.Name + 'StopOnSolutionsCB' );
  if (ele) ele.checked = (this.StopOnSolutions);

  var ele = xGet( this.Name + 'SlowMotionCB' );
  if (ele) ele.checked = (this.SlowMotion);

  var ele = xGet( this.Name + 'LimitSolveTimeCB' );
  if (ele) ele.checked = (this.LimitSolveTime);

  this.AppUpdateStateDisplayRequested = false;
}

CSudoku.prototype.UpdateGuiButtons = function() {
  xRemoveClass( this.Name+'GuiBtn'+'K', 'lbtnActive' );
  xRemoveClass( this.Name+'GuiBtn'+'Z', 'lbtnActive' );
  xRemoveClass( this.Name+'GuiBtn'+'F', 'lbtnActive' );
  for (var i = 1; i <= 9; i++) xRemoveClass( this.Name+'GuiBtn'+i, 'lbtnActive' );
  if (this.GuiButtonState != '') {
    xAddClass( this.Name+'GuiBtn'+this.GuiButtonState, 'lbtnActive' );
  }
  if (this.GuiButtonState == 'K' || this.GuiButtonState == 'Z') {
    if (this.GuiButtonSetNumber > 0) xAddClass( this.Name+'GuiBtn'+this.GuiButtonSetNumber, 'lbtnActive' );
  }
  if (this.GuiButtonState == 'F') {
    for (var i = 1; i <= 9; i++) {
      if (this.CSetContainsNum( this.GuiButtonFilterNumbers, i )) {
        xAddClass( this.Name+'GuiBtn'+i, 'lbtnActive' );
      }
    }
  }
  this.AppUpdateButtonDisplayRequested = false;
}

CSudoku.prototype.OnGridClick = function( aCellXStr ) {
  this.AppUpdateBegin();
  if (this.GuiButtonState == 'Z') {
    var numStr = '';
    if (this.GuiButtonSetNumber > 0) {
      numStr = this.GuiButtonSetNumber.toString();
    }
    var cellX = parseInt( aCellXStr, 10 );
    this.GuiSudokuInputCells[cellX].value = numStr;
    this.HandleFieldInput( cellX );
    this.ShowFieldInfos( cellX );
  }
  if (this.GuiButtonState == 'K') {
    if (this.GuiButtonSetNumber > 0) {
      var cellX = parseInt( aCellXStr, 10 );
      this.SaveState();
      this.CandidateCells[cellX] ^= this.NumToCSet( this.GuiButtonSetNumber );
      this.AppRequestHints();
    }
  }
  if (this.GuiButtonState == 'F') {
    var cellX = parseInt( aCellXStr, 10 );
    this.ColorCells[cellX]++;
  }
  this.AppUpdateEnd();
}

CSudoku.prototype.ShowFieldInfos = function( aCellX ) {
  if (this.SolvedCells[aCellX] == 0 && !this.CandidateCells[aCellX]) {
    this.OutStatus( 'Keine Werte für diese Zelle möglich!' );
  } else {
    var sCandidates = this.CSetToString( this.CandidateCells[aCellX] );
    var s = '';
    if (sCandidates.length == 1) {
      s = 'Erlaubte Zahl in der Zelle: ';
    } else {
      s = 'Erlaubte Zahlen in der Zelle: ';
    }
    if (this.SolvedCells[aCellX] > 0 && !this.CandidateCells[aCellX]) {
      var s = ''
      if (this.NumbersCount[0] == 1) {
        s += 'Es fehlt noch 1 Zahl.';
      } else {
        s += 'Es fehlen noch ' + this.NumbersCount[0] + ' Zahlen.';
      }
      if (this.RunTimeLimitExceedet) {
        s = 'Suchzeit überschritten; Lösungssuche abgebrochen.';
      } else {
        s += ' Warte auf deine Eingaben...';
      }
    }
    if (sCandidates.length == 9) {
      s += 'alle';
    } else {
      s += sCandidates;
    }
    if (!this.IsSolved()) this.OutStatus( s );
  }
}

CSudoku.prototype.HandleFieldInput = function( aCellX ) {
  this.AppUpdateBegin();
  this.SaveState();
  if (!this.CheckGui()) {
    this.AppUpdateEnd();
    return;
  }
  this.AppRequestHints();
  this.AppUpdateEnd();
}

CSudoku.prototype.ResetCellBackgrounds = function() {
  for (var i = 0; i < 81; i++) {
    xStyle( this.GuiSudokuTableCells[i], 'backgroundColor', '#fff' );
    this.LastInputCellBG[i] = '#fff';
  }
}

CSudoku.prototype.UpdateGui = function() {

  if (this.AppUpdateStateDisplayRequested) this.UpdateGuiState();
  if (this.AppUpdateButtonDisplayRequested) this.UpdateGuiButtons();

  var stat = this.GetStatus();
  var sbg = '#ddd';
  if (this.GraphicHintsEnabled && (stat != 'solved' || this.SearchingSolutions)) {
    sbg = '#fff';
  }
  for (var i = 0; i < 81; i++) {
    var newInputCellBG = '#fff';
    if (this.StartCells[i] > 0) {
      // background of cell is sbg if i is a start cell
      newInputCellBG = sbg;
    }
    var newGridCellBG = newInputCellBG;
    if (this.StartCells[i] == 2) {
      // background of cell if cell is a gess
      newInputCellBG = '#fdc';
    }
    if (this.SearchingSolutions) {
      if (this.TryCellX == i) {
        newInputCellBG = '#fc8';
      }
    }
    var enumValue = '';
    if (this.GraphicHintsEnabled && this.StatusCells[i] == '') {
      if (this.MovesCount > 0) {
        var status = this.Moves[this.CurrMove].Status[i];
        if (status != '') {
          // status has format: '<enum>:<bgColor><num1><numColor1><num2><numColor2>...'
          // <bgColor> one of chars: rRgGbBmMcCoOyY for red, green, blue, magenta, cyan, orange, yellow; small char means brighter
          // <numX> as char: 1-9
          // <numColorX> one of chars: rgbxO for red, green, blue, red, black; background color of <numX>
          var p = status.indexOf(':');
          if (p > 0) {
            if (!this.SearchingSolutions) {
              enumValue = status.substr(0,p);
            }
            status = status.substr(p+1);
          }
          if (this.SearchingSolutions) {
            newGridCellBG = this.BgColor( status.substr(0,1) );
          } else {
            newInputCellBG = this.BgColor( status.substr(0,1) );
            newGridCellBG = newInputCellBG;
          }
        }
      }
    }
    var invalidInput = false;
    if (this.StatusCells[i] == 'NaN') {
      // invalid input
      newInputCellBG = '#faa';
      invalidInput = true;
    }
    if (this.StatusCells[i] == 'Multi') {
      // one value more than once in same house
      newInputCellBG = '#faa';
      invalidInput = true;
    }
    if (this.SolvedCells[i] == 0 && !this.CandidateCells[i]) {
      // no solution left for this cell
      newInputCellBG = 'red';
    }

    var newInputCellValue = '';
    var newInputCellClass = '';
    if (this.SolvedCells[i] > 0) {
      newInputCellValue = this.SolvedCells[i].toString();
    } else if (enumValue != '') {
      newInputCellValue = '(' + enumValue +')';
      newInputCellClass = 'enum';
    } else if (invalidInput) {
      newInputCellValue = '?';
    }

    // update input cell
    var inputCell = this.GuiSudokuInputCells[i];
    if (newInputCellBG != this.LastInputCellBG[i]) {
      xStyle( this.GuiSudokuTableCells[i], 'backgroundColor', newInputCellBG );
      this.LastInputCellBG[i] = newInputCellBG;
    }
    if ((newInputCellValue != this.LastInputCellValue[i]) || invalidInput) {
      inputCell.value = newInputCellValue;
      this.LastInputCellValue[i] = newInputCellValue;
    }
    if (newInputCellClass != this.LastInputCellClass[i]) {
      if (newInputCellClass != '') {
        xAddClass( inputCell, 'enum' );
      } else {
        xRemoveClass( inputCell, 'enum' );
      }
      this.LastInputCellClass[i] = newInputCellClass;
    }

    if (this.GridCreated && this.GridEnabled) {
      this.OutGridNums( i, newGridCellBG );
    }
  }

  if (this.AllSolutionsFound) {
    if (this.SolutionCount == 0) {
      this.OutStatus( 'Es konnte keine Lösung gefunden werden.' );
    } else if (this.SolutionCount == 1) {
      this.OutStatus( 'Genau eine Lösung mit Raten gefunden.' );
    } else {
      this.OutStatus( this.SolutionCount.toString() + ' Lösungen mit raten gefunden.' );
    }
    var helpLink = this.MakeHelpLink( this.MaxLevelName, this.MaxLevelHelp );
    this.OutMethods( '<b>Raten</b>; Höchster verwendeter Level: ' + this.MaxLevel.toFixed(1) + ' &rArr; <b>' + helpLink + '</b>' );
  } else if (this.SearchingSolutions) {
    var text = '';
    if ((stat == 'solved' && this.SolutionCount > 0) || this.SlowMotion) {
      var guessNums = this.TryStateToString();
      if (guessNums.length == 1) {
        text = 'Rate-Zahl';
      } else {
        text = 'Rate-Zahlen';
      }
      text = '<b>' + text + ':</b> ' + guessNums + '; ';
    }
    if (stat == 'solved' && this.SolutionCount > 0) {
      this.OutMethods( text + 'Lösung ' + this.SolutionCount + ', Anzahl geratene Zellen: ' + this.StackPtr );
    } else {
      if (this.SlowMotion) {
        this.OutMethods( text + ' ' + this.MakeMethodTextForCurrentMove() + ' ...' );
      }
    }
    if (this.Running && !this.Stopped) {
      this.OutStatus('Suche nach Lösungen...');
    } else {
      if (stat == 'solved') {
        this.OutStatus('Klicke auf <b>Lösen</b> um weitere Lösungen zu suchen.');
      } else if (stat == 'no solution') {
        this.OutStatus('Klicke auf <b>Lösen</b> um mögliche Lösungen durch Raten zu finden.');
      } else {
        this.OutStatus('Lösungs-Suche angehalten');
      }
    }
  } else {
    this.OutMethods( this.MakeMethodTextForCurrentMove() );
    if (stat == 'solved') {
      this.OutStatus( 'Das Sudoku ist gelöst!' );
      if (this.MaxLevel == 0) {
        this.OutMethods( 'Von Hand gelöst' );
      } else {
        var helpLink = this.MakeHelpLink( this.MaxLevelName, this.MaxLevelHelp );
        this.OutMethods('Höchster verwendeter Level: ' + this.MaxLevel.toFixed(1) + ' &rArr; <b>' + helpLink + '</b>' );
      }
    } else if (stat == 'empty') {
      this.OutStatus( 'Gib Zahlen in die leeren Zellen ein!' );
    } else if (stat == 'few') {
      this.OutStatus( 'Bitte mindestens ' + this.MinFill + ' Zahlen eingeben!' );
    } else if (stat == 'no solution') {
      this.OutStatus( 'Klicke auf <b>Lösen</b> um Lösungen zu raten.' );
    } else if (stat == 'invalid') {
      this.OutStatus( 'Das Sudoku ist ungültig und nicht lösbar!' );
    } else {
      var text = '';
      if (this.NumbersCount[0] == 1) {
        text += 'Es fehlt noch 1 Zahl.';
      } else {
        text += 'Es fehlen noch ' + this.NumbersCount[0] + ' Zahlen.';
      }
      if (this.Running) {
        text += ' Löse das Sudoku...';
      } else {
        if (this.RunTimeLimitExceedet) {
          text = 'Suchzeit überschritten; Lösungssuche abgebrochen.';
        } else {
          text += ' Warte auf deine Eingaben...';
        }
      }
      this.OutStatus( text );
    }
  }
}

CSudoku.prototype.MakeHelpLink = function( aHelpName, aHelpPage ) {
  var helpURI = encodeURIComponent( 'Sudoku: ' + aHelpPage ).replace( /%20/g, '+' );
  var helpLink = '<a href="' + ASP_PAGE + '?page=' + helpURI + '" title="Hilfe zu: ' + aHelpPage + '">' + aHelpName + '</a>';
  return helpLink;
}

CSudoku.prototype.MakeMethodTextForCurrentMove = function() {
  var text = 'Keine ' + this.MakeHelpLink( 'programmierten Methoden', 'Programmierte Methoden' ) + ' anwendbar auf diese Konstellation.';
  var hintLevel = this.TextHintLevel;
  if (this.MovesCount > 0) {
    var x = this.CurrMove;
    var hints = this.Moves[x].Hints;
    var lastHintX = hints.length - 1;
    var helpLink = this.MakeHelpLink( this.Moves[x].Name, this.Moves[x].HelpPage );
    if (!this.SearchingSolutions && this.TextHintsEnabled) {
      if (hintLevel == 0) {
        if (this.MovesCount == 1) {
          text = '1 Zug';
        } else {
          text = this.MovesCount + ' Züge';
        }
        text += ' gefunden für diese Konstellation. Klicke auf <b>Tipp</b> für mehr Hinweise.';
      } else {
        var hintX = hintLevel - 2;
        if (hintX > lastHintX) hintX = lastHintX;
        text = '';
        if (this.MovesCount > 1) text = (x+1) + '/' + this.MovesCount + ': ';
        text += '<b>' + helpLink + '</b>';
        if (lastHintX < 0 || hintX == lastHintX) text += ' [Level: ' + this.Moves[x].Level.toFixed(1) + ']';
        if (lastHintX >= 0) {
          if (hintX >= 0) text += ' &rArr; ' + hints[hintX];
          if (hintX < lastHintX) text += ' &rArr; <b>Tipp</b>';
        }
      }
    } else { // if (this.SearchingSolutions || !this.TextHintsEnabled)
      text = '';
      if (this.MovesCount > 1) text = (x+1) + '/' + this.MovesCount + ': ';
      text += '<b>' + helpLink + '</b>';
      if (!this.SearchingSolutions) {
        text += ' [Level: ' + this.Moves[x].Level.toFixed(1) + ']';
        if (lastHintX >= 0) text += ' &rArr; ' + hints[lastHintX];
      }
    }
  }
  return text;
}

CSudoku.prototype.IsNum = function( aString ) {
  var s = '0123456789';
  return (aString.length == 1) && (s.indexOf(aString) >= 0);
}

CSudoku.prototype.ReadGui = function() {
  var ok = true;
  var oldSolvedCells = Array(81);
  this.CopyCells( this.SolvedCells, oldSolvedCells );
  this.ClearCells( this.StatusCells, '' );
  for (var i = 0; i < 81; i++) {
    var v = this.GuiSudokuInputCells[i].value;
    if (v.indexOf('(') == 0) v = '';
    if (v != '') {
      if (this.IsNum(v)) {
        this.SolvedCells[i] = parseInt( v, 10 );
      } else {
        this.StatusCells[i] = 'NaN';
        this.SolvedCells[i] = 0;
        ok = false;
      }
    } else {
      this.SolvedCells[i] = 0;
    }
    if (this.SolvedCells[i] != oldSolvedCells[i]) {
      if (this.SolvedCells[i] == 0) {
        // number from cell deleted
        this.CandidatesAreValid = false;
      } else {
        if (this.CSetContainsNum( this.CandidateCells[i], this.SolvedCells[i] )) {
          // valid number entered
          this.CandidateCells[i] = 0;
          this.RemoveCandidatesForCell( i );
        } else {
          // invalid number entered
          this.CandidatesAreValid = false;
        }
      }
    }
  }
  return ok;
}

CSudoku.prototype.CheckGui = function() {
  if (!this.ReadGui()) {
    this.AppUpdateBegin();
    this.OutStatus( 'Fehler: Ungültige Zeichen in den markierten Zellen!' );
    this.AppUpdateEnd();
    return false;
  }
  if (!this.IsValid()) {
    this.AppUpdateBegin();
    this.OutStatus( 'Fehler: Einige Zahlen kommen mehrfach vor!' );
    this.CandidatesAreValid = false;
    this.AppUpdateEnd();
    return false;
  }
  return true;
}

CSudoku.prototype.ComputeMethods = function() {
  this.AppHintsRequested = false;
  this.PrepareMethods( false );
  this.FindAllMethods();
  this.SortMoves();
}

CSudoku.prototype.FindAllMethods = function( ) {
  // returns true if searching is stopped before end

  var methodsAndLevels;
  if (this.MethodOrder == 1) {
    methodsAndLevels = this.MethodsAndLevels1;
  } else {
    methodsAndLevels = this.MethodsAndLevels2;
  }

  this.CurrLevel = 0;
  var fill = this.GetFilledCellCount();
  if (fill == 81 || fill < this.MinFill) {
    return true;
  }

  this.StartTimer();
  var nMethods = div( methodsAndLevels.length, 2 );
  for (var methodX = 0; methodX < nMethods; methodX++) {

    this.CurrLevel = methodsAndLevels[methodX*2];

    var method = methodsAndLevels[methodX*2+1];

    if (method.call( this )) {
      return true;
    }

    if (methodX == 2 && this.StopAfterTrivialMoves) this.StopSolving = true;

    if (this.RunTimeExceedet()) return true;
  }

  return false;
}

CSudoku.prototype.PrepareMethods = function( bClearCandidates ) {
  this.ClearCells( this.StatusCells, '' );
  this.ClearMoves();
  if (bClearCandidates || !this.CandidatesAreValid) {
    this.FindBasicCandidates();
  }
  this.XChainList = [];
  this.XYChainList = [];
  this.XChainListValid = false;
  this.XYChainListValidSize = -1;
  this.CandidatesAreValid = true;
  this.CountNumbers();
  this.CountCandidates();
}

CSudoku.prototype.CountNumbers = function() {
  for (var num = 0; num <= 9; num++) this.NumbersCount[num] = 0;
  var solvedCells = this.SolvedCells;
  for (cellX = 0; cellX < 81; cellX++) this.NumbersCount[solvedCells[cellX]]++;
}

CSudoku.prototype.CountCandidates = function() {
  for (var num = 0; num <= 9; num++) this.CandidatesCount[num] = 0;
  var candidateCells = this.CandidateCells;
  var candCounts = this.CandidatesCount;
  for (num = 1; num <= 9; num++) {
    var numCSet = this.NumToCSet( num );
    for (cellX = 0; cellX < 81; cellX++) {
      if (candidateCells[cellX] & numCSet) candCounts[num]++;
    }
  }
}

CSudoku.prototype.FindBasicCandidates = function() {
  // remove candidates for all solved cells
  for (var cellX = 0; cellX < 81; cellX++) {
    if (this.SolvedCells[cellX] == 0) {
      this.CandidateCells[cellX] = 0x1FF;
    } else {
      this.CandidateCells[cellX] = 0;
    }
  }
  for (var cellX = 0; cellX < 81; cellX++) {
    if (this.SolvedCells[cellX] > 0) {
      this.RemoveCandidatesForCell( cellX );
    }
  }
}

CSudoku.prototype.RemoveCandidatesForCell = function( aCellX ) {
  // For Number in aCellX remove it from CandidateCells of same houses (row, col and box).
  // require this.SolvedCells[aCellX] > 0

  var num = this.SolvedCells[aCellX];
  this.CandidateCells[aCellX] = 0;

  var house = this.Rows[this.RowXofCellX(aCellX)];
  this.RemoveNumFromHouseCandidates( num, house, aCellX );

  var house = this.Cols[this.ColXofCellX(aCellX)];
  this.RemoveNumFromHouseCandidates( num, house, aCellX );

  var house = this.Boxes[this.BoxXofCellX(aCellX)];
  this.RemoveNumFromHouseCandidates( num, house, aCellX );
}

CSudoku.prototype.RemoveNumFromHouseCandidates = function( aNum, aHouse, aRefCellX ) {
  // aHouse as this.Rows[x], Cols[x] or Boxes[x]
  for (var houseX = 0; houseX < 9; houseX++) {
    var cellX = aHouse[houseX];
    if (cellX != aRefCellX) {
      if (this.SolvedCells[cellX] == 0) {
        this.CandidateCells[cellX] = this.CSetRemoveNum( this.CandidateCells[cellX], aNum );
      }
    }
  }
}

CSudoku.prototype.FindFullHouses = function() {
  // Mark cells in rows, cols and boxes which are the only empty ones:
  // returns true if no more moves are requested
  if (this.FindFullHouse(this.Boxes)) return true;
  if (this.FindFullHouse(this.Rows )) return true;
  if (this.FindFullHouse(this.Cols )) return true;
  return false;
}

CSudoku.prototype.FindFullHouse = function( aGridView ) {
  // aGridView as this.Rows, Cols or Boxes
  // returns true if no more moves are requested
  var targetCellX, cellX;
  for (var viewX = 0; viewX < 9; viewX++) {
    var house = aGridView[viewX];
    var n = 0;
    for (var houseX = 0; houseX < 9 && n <= 1; houseX++) {
      cellX = house[houseX];
      if (this.SolvedCells[cellX] == 0) {
        n++;
        targetCellX = cellX;
      }
    }
    if (n == 1) {
      var solutionNumBit = this.CandidateCells[targetCellX];
      if (!this.IsNumCSetInFoundCandidates( solutionNumBit, targetCellX )) {
        this.AddNumBitToFoundCandidates( solutionNumBit, targetCellX );
        var candidates = this.NewCandidates();
        var status = this.NewStatus();
        for (var houseX = 0; houseX < 9; houseX++) {
          status[house[houseX]] = 'g';
        }
        status[targetCellX] = 'Y' + this.CSetToString( solutionNumBit ) + 'O';

        this.AddMove( 'Full House', candidates, status, targetCellX, 1 );
        if (this.MoveLimitExceeded()) return true;
      }
    }
  }
  return false;
}

CSudoku.prototype.FindNakedSingles = function() {
  // returns true if no more moves are requested
  for (var cellX = 0; cellX < 81; cellX++) {
    if (this.CSetBitCount(this.CandidateCells[cellX]) == 1) {
      var solutionNumBit = this.CandidateCells[cellX];
      if (!this.IsNumCSetInFoundCandidates( solutionNumBit, cellX )) {
        this.AddNumBitToFoundCandidates( solutionNumBit, cellX );

        var candidates = this.NewCandidates();
        var status = this.NewStatus();

        var house = this.Boxes[this.BoxXofCellX(cellX)];
        this.MarkHouse( status, house, 'g' );
        var nPerHouse = this.NSolvedCellsInHouse( house );

        var house = this.Rows[this.RowXofCellX(cellX)];
        this.MarkHouse( status, house, 'g' );
        nPerHouse = maxOf( nPerHouse, this.NSolvedCellsInHouse( house ) );

        var house = this.Cols[this.ColXofCellX(cellX)];
        this.MarkHouse( status, house, 'g' );
        nPerHouse = maxOf( nPerHouse, this.NSolvedCellsInHouse( house ) );

        status[cellX] = 'Y' + this.CSetToString( candidates[cellX] ) + 'O';

        this.AddMove( 'Naked Single', candidates, status, cellX, 9-nPerHouse );
        if (this.MoveLimitExceeded()) return true;
      }
    }
  }
  return false;
}

CSudoku.prototype.MarkHouse = function( aStatusCells, aHouse, aMark ) {
  for (var houseX = 0; houseX < 9; houseX++) {
    aStatusCells[aHouse[houseX]] = aMark;
  }
}

CSudoku.prototype.FindHiddenSingles = function() {
  // für jedes fehlende N in Zeile, Spalte oder Box wird bestimmt,
  // ob es mehr als eine Position einnehmen kann. Wenn nicht, haben wir eine Lösung gefunden.
  // returns true if no more moves are requested

  // check Boxes
  for (var boxX = 0; boxX < 9; boxX++) {
    var box = this.Boxes[boxX];
    var numSet = this.CandidatesFromHouse( box );
    for (var num = 1; num <= 9; num++) {
      if (this.CSetContainsNum(numSet,num)) {
        var targetCellX = 0;
        var n = 0;
        for (var boxCellX = 0; boxCellX < 9 && n <= 1; boxCellX++) {
          if (this.CSetContainsNum(this.CandidateCells[box[boxCellX]],num)) {
            n++;
            targetCellX = box[boxCellX];
          }
        }
        if (n == 1) {
          var solutionNumBit = this.NumToCSet( num );
          if ((this.CSetBitCount(this.CandidateCells[targetCellX]) > 1) && !this.IsNumCSetInFoundCandidates( solutionNumBit, targetCellX )) {
            this.AddNumBitToFoundCandidates( solutionNumBit, targetCellX );

            var candidates = this.NewCandidates();
            var status = this.NewStatus();

            candidates[targetCellX] = solutionNumBit;
            status[targetCellX] = 'Y' + num.toString() + 'O';

            // Zeilen und Spalten markieren
            var boxStartRowX = this.RowXofBoxCellX( boxX, 0 );
            var boxStartColX = this.ColXofBoxCellX( boxX, 0 );
            var targetRowX = this.RowXofCellX( targetCellX );
            var targetColX = this.ColXofCellX( targetCellX );
            var diffLevel = 0;
            diffLevel += this.MarkHiddenSinglesNums( status, num, this.Rows, boxStartRowX, boxStartColX, targetRowX );
            diffLevel += this.MarkHiddenSinglesNums( status, num, this.Cols, boxStartColX, boxStartRowX, targetColX );
            diffLevel += this.MarkHiddenSinglesNumSets( status, num, this.Rows, boxStartRowX, boxStartColX, targetRowX );
            diffLevel += this.MarkHiddenSinglesNumSets( status, num, this.Cols, boxStartColX, boxStartRowX, targetColX );
            if (diffLevel < 0) diffLevel = 0;
            if (diffLevel > 9) diffLevel = 9;

            this.AddMove( 'Hidden Single', candidates, status, targetCellX, diffLevel );
            if (this.MoveLimitExceeded()) return true;
          }
        }
      }
    }
  }

  // apply method B to rows and cols
  if (this.FindHiddenSinglesInRowCol( this.Rows, this.Cols )) {
    return true;
  }
  if (this.FindHiddenSinglesInRowCol( this.Cols, this.Rows )) {
    return true;
  }
  return false;
}

CSudoku.prototype.FindHiddenSinglesInRowCol = function( aOuterGridView, aInnerGridView ) {
  // aOuterGridView as this.Rows or this.Cols
  // aInnerGridView as this.Cols or this.Rows
  for (var viewX = 0; viewX < 9; viewX++) {
    var house = aOuterGridView[viewX];
    var numSet = this.CandidatesFromHouse( house );
    for (var num = 1; num <= 9; num++) {
      if (this.CSetContainsNum(numSet,num)) {
        var targetCellX = 0;
        var n = 0;
        for (var houseX = 0; houseX < 9 && n <= 1; houseX++) {
          if (this.CSetContainsNum(this.CandidateCells[house[houseX]],num)) {
            n++;
            targetCellX = house[houseX];
          }
        }
        if (n == 1) {
          var solutionNumBit = this.NumToCSet( num );
          if ((this.CSetBitCount(this.CandidateCells[targetCellX]) > 1) && !this.IsNumCSetInFoundCandidates( solutionNumBit, targetCellX )) {

            var candidates = this.NewCandidates();
            var status = this.NewStatus();

            candidates[targetCellX] = solutionNumBit;
            var diffLevel = this.MarkHiddenSinglesRowCol( status, num, house, aInnerGridView, targetCellX );
            status[targetCellX] = 'Y' + num.toString() + 'O';
            if (diffLevel > 9) diffLevel = 9;

            var houseHint = (aOuterGridView == this.Rows) ? 'Zeile ' : 'Spalte ';
            houseHint += (viewX+1);

            this.AddNumBitToFoundCandidates( solutionNumBit, targetCellX );
            this.AddMove( 'Hidden Single', candidates, status, targetCellX, diffLevel, 0, houseHint );
            if (this.MoveLimitExceeded()) return true;
          }
        }
      }
    }
  }
  return false;
}

CSudoku.prototype.MarkHiddenSinglesNums = function( aStatusCells, aNum, aGridView, aViewStartX, aHouseStartX, aTargetViewX ) {
  // aGridView as this.Rows or Cols
  var nMarked = 0;
  var viewEndX = aViewStartX + 2;
  var houseEndX = aHouseStartX + 2;
  for (var viewX = aViewStartX; viewX <= viewEndX; viewX++) {
    if (viewX != aTargetViewX) {
      // Check wether in this row/col (aGridView) of current box candites can be found
      var house = aGridView[viewX];
      var found = false;
      for (var houseX = aHouseStartX; houseX <= houseEndX && !found; houseX++) {
        found = !!this.CandidateCells[house[houseX]];
      }
      if (found) {
        // Check wether num exists in SolvedCells of this row/col:
        found = false;
        for (var houseX = 0; houseX < 9 && !found; houseX++) {
          found = (this.SolvedCells[house[houseX]] == aNum);
        }
        if (found) {
          // Mark row/col:
          for (var houseX = 0; houseX < 9; houseX++) {
            var cellX = house[houseX];
            if (this.SolvedCells[cellX] == aNum) {
              if (aStatusCells[cellX] == '') nMarked++;
              aStatusCells[cellX] = 'B' + aNum.toString() + 'b';
            } else {
              aStatusCells[cellX] = 'b';
            }
          }
        }
      }
    }
  }
  return nMarked;
}

CSudoku.prototype.MarkHiddenSinglesNumSets = function( aStatusCells, aNum, aGridView, aViewStartX, aHouseStartX, aTargetViewX ) {
  // aGridView as this.Rows or Cols
  // for not yet marked cells in aStatusCells induced from solutions of aNum find candidates for aNum and mark them
  var nMarked = 0;
  var viewEndX = aViewStartX + 2;
  var houseEndX = aHouseStartX + 2;
  for (var viewX = aViewStartX; viewX <= viewEndX; viewX++) {
    if (viewX != aTargetViewX) {
      // Check wether in this row/col (aGridView) of current box candites can be found
      var house = aGridView[viewX];
      var found = false;
      for (var houseX = aHouseStartX; houseX <= houseEndX && !found; houseX++) {
        var cellX = house[houseX];
        found = (aStatusCells[cellX] == '' && this.CandidateCells[cellX]);
      }
      if (found) {
        // Check wether num exists in CandidateCells of this row/col and mark them:
        for (var houseX = 0; houseX < 9; houseX++) {
          var cellX = house[houseX];
          if (this.CSetContainsNum(this.CandidateCells[cellX],aNum)) {
            if (aStatusCells[cellX] == '') nMarked++;
            aStatusCells[cellX] = 'B' + aNum.toString() + 'b';
          } else {
            aStatusCells[cellX] = 'b';
          }
        }
      }
    }
  }
  return nMarked;
}

CSudoku.prototype.MarkHiddenSinglesRowCol = function( aStatusCells, aNum, aOuterHouse, aInnerGridView, aTargetCellX ) {
  // aOuterHouse as this.Rows[rowX] or this.Cols[colX]
  // aInnerGridView as this.Cols or this.Rows
  // returns number of marked cells.

  var tmpStatus = this.NewCells( '' );
  var nMarked = 0;
  // find solution cells that induced aNum and set marks in tmpStatus for this
  for (var outerX = 0; outerX < 9; outerX++) {
    var outerCellX = aOuterHouse[outerX];
    aStatusCells[outerCellX] = 'b';
    if (outerCellX != aTargetCellX && this.SolvedCells[outerCellX] == 0) {
      // find and mark num in inner range
      var innerHouse = aInnerGridView[outerX];
      for (var innerX = 0; innerX < 9; innerX++) {
        var cellX = innerHouse[innerX];
        if (this.SolvedCells[cellX] == aNum) {
          if (aStatusCells[cellX] == '') nMarked++;
          aStatusCells[cellX] = 'B';
          tmpStatus[outerCellX] = 'b';
        }
      }
      // find and mark num in box
      var marked = false;
      var box = this.Boxes[this.BoxXofCellX(outerCellX)];
      for (var boxCellX = 0; boxCellX < 9 && !marked; boxCellX++) {
        var cellX = box[boxCellX];
        if (this.SolvedCells[cellX] == aNum) {
          if (aStatusCells[cellX] == '') nMarked++;
          aStatusCells[cellX] = 'B';
          marked = true;
        }
      }
      if (marked) {
        // mark box cells
        for (var boxCellX = 0; boxCellX < 9; boxCellX++) {
          var cellX = box[boxCellX];
          tmpStatus[cellX] = 'b';
        }
      }
    }
  }
  // for each not yet marked cell in tmpStatus of same row/col as aOuterHouse
  // find cells in this.CandidateCells that may have induced aNum and mark them in aStatusCells
  for (var outerX = 0; outerX < 9; outerX++) {
    var outerCellX = aOuterHouse[outerX];
    if (outerCellX != aTargetCellX && this.SolvedCells[outerCellX] == 0 && tmpStatus[outerCellX] == '') {
      // find and mark num in inner range
      var innerHouse = aInnerGridView[outerX];
      for (var innerX = 0; innerX < 9; innerX++) {
        var cellX = innerHouse[innerX];
        if (this.CSetContainsNum(this.CandidateCells[cellX],aNum)) {
          if (aStatusCells[cellX] == '') nMarked++;
          aStatusCells[cellX] = 'B' + aNum.toString() + 'b';
          tmpStatus[outerCellX] = 'b';
        }
      }
    }
  }
  for (var outerX = 0; outerX < 9; outerX++) {
    var outerCellX = aOuterHouse[outerX];
    if (outerCellX != aTargetCellX && this.SolvedCells[outerCellX] == 0 && tmpStatus[outerCellX] == '') {
      // find and mark num in box
      var box = this.Boxes[this.BoxXofCellX(outerCellX)];
      for (var boxCellX = 0; boxCellX < 9; boxCellX++) {
        var cellX = box[boxCellX];
        if (this.CSetContainsNum(this.CandidateCells[cellX],aNum)) {
          if (aStatusCells[cellX] == '') nMarked++;
          aStatusCells[cellX] = 'B' + aNum.toString() + 'b';
          tmpStatus[cellX] = 'b';
        }
      }
    }
  }
  return nMarked;
}

CSudoku.prototype.FindLockedCandidatesBoxLine = function() {
  // suche in jeder Box eine Zeile oder Spalte, in der eine bestimmte Zahl exklusiv vorkommt.
  // Diese Zahl kann dann in der entsprechenden Zeile/Spalte der anderen Blöcke gestrichen werden.
  // returns true if no more moves are requested

  for (var boxX = 0; boxX < 9; boxX++) {

    var box = this.Boxes[boxX];
    var boxCSet = this.CandidatesFromHouse( box );
    if (boxCSet) {

      var boxStartRowX = this.RowXofBoxCellX( boxX, 0 );
      var boxStartColX = this.ColXofBoxCellX( boxX, 0 );

      // search box in row order
      if (this.FindLockedCandidatesBoxRowCol( box, boxCSet, this.Rows, boxStartRowX, boxStartColX )) {
        return true;
      }

      // search box in col order
      if (this.FindLockedCandidatesBoxRowCol( box, boxCSet, this.Cols, boxStartColX, boxStartRowX )) {
        return true;
      }

    }
  }
  return false;
}

CSudoku.prototype.FindLockedCandidatesBoxRowCol = function( aBox, aBoxNumSet, aGridView, aBoxStartOuterX, aBoxStartInnerX ) {
  // aBox as this.Boxes[i]
  // aGridView as this.Rows or this.Cols
  // returns true if no more moves are requested

  // collect all candidates of each aBox-row/col seperately
  var boxNums = new Array( 0, 0, 0 );
  var boxEndOuterX = aBoxStartOuterX + 2;
  var boxEndInnerX = aBoxStartInnerX + 2;
  for (var outerX = aBoxStartOuterX, i = 0; outerX <= boxEndOuterX; outerX++, i++) {
    var house = aGridView[outerX];
    for (var innerX = aBoxStartInnerX; innerX <= boxEndInnerX; innerX++) {
      boxNums[i] |= this.CandidateCells[house[innerX]];
    }
  }

  for (var num = 1; num <= 9; num++) {
    if (this.CSetContainsNum( aBoxNumSet, num )) {

      // if num is only in one row/col (boxNums), then a candidate is found for LockedCandidatesBoxLine
      var n = 0;
      var x = 0;
      for (var i = 0; i < 3 && n <= 1; i++) {
        if (this.CSetContainsNum( boxNums[i], num )) {
          n++;
          x = i;
        }
      }

      if (n == 1) {
        // num is only in aBox-row/col[x]

        // check wether num can be removed from other cells of row/col (aGridView):
        var outerX = aBoxStartOuterX + x;
        var house = aGridView[outerX];
        var nInLine = 0;
        var nInBox = 0;
        for (var innerX = 0; innerX < 9; innerX++) {
          if (innerX < aBoxStartInnerX || innerX > boxEndInnerX) {
            if (this.CSetContainsNum( this.CandidateCells[house[innerX]], num )) {
              nInLine++;
            }
          } else {
            if (this.CSetContainsNum( this.CandidateCells[house[innerX]], num )) {
              nInBox++;
            }
          }
        }

        var minInBox = 2;
        // Note: Hidden or Naked Singles are handled already, so minInBox can be 2
        //if (this.ShowAllMoves) minInBox = 1;
        if (nInLine > 0 && nInBox >= minInBox) {

          var candidates = this.NewCandidates();
          var status = this.NewStatus();

          // premark house (row/col)
          this.MarkHouse( status, house, 'm' );
          // mark box
          var hintBoxCellX = -1;
          for (var boxCellX = 0; boxCellX < 9; boxCellX++) {
            // mark box:
            var cellX = aBox[boxCellX];
            if (this.CSetContainsNum( candidates[cellX], num )) {
              status[cellX] = 'c' + num.toString() + 'g';
            } else {
              status[cellX] = 'c';
            }
            hintBoxCellX = cellX;
          }

          // mark cells
          var delCandList = [];
          var numCSet = this.NumToCSet( num );

          for (var innerX = 0; innerX < 9; innerX++) {
            if (innerX < aBoxStartInnerX || innerX > boxEndInnerX) {
              var cellX = house[innerX];
              if (this.CSetContainsNum( candidates[cellX], num )) {
                delCandList.push( cellX );
                delCandList.push( numCSet );
              }
            }
          }

          if (delCandList.length > 0) {
            var infos = { Name: 'Locked Candidates Box-Line', Level: 1, Help: 'Locked Candidates' };
            var hintHouse = 'Box ' + (this.BoxXofCellX(hintBoxCellX)+1);
            if (this.CreateMoves( delCandList, candidates, status, infos, numCSet, hintHouse )) {
              return true;
            }
          }

        }
      } // end if IsLockedCandidateBoxLine
    } // end if (this.CSetContainsNum( aBoxNumSet, num ))
  } // next num
  return false;
}

CSudoku.prototype.FindLockedCandidatesLineBox = function() {
  // Suche für jede Box Zeilen/Spalten in benachbarten Boxen nach Zahlen ab,
  // die dort nicht vorkommen. Diese müssen in der Zeile/Spalte der aktuellen
  // Box stehen! Daher können sie aus den anderen Zellen der aktuellen Box
  // gestrichen werden.
  // returns true if no more moves are requested

  for (var boxX = 0; boxX < 9; boxX++) {

    var box = this.Boxes[boxX];
    var boxStartRowX = this.RowXofBoxCellX( boxX, 0 );
    var boxStartColX = this.ColXofBoxCellX( boxX, 0 );

    // search box in row order
    if (this.FindLockedCandidatesLineBoxRowCol( box, this.Rows, boxStartRowX, boxStartColX )) {
      return true;
    }

    // search box in col order
    if (this.FindLockedCandidatesLineBoxRowCol( box, this.Cols, boxStartColX, boxStartRowX )) {
      return true;
    }

  }
  return false;
}

CSudoku.prototype.FindLockedCandidatesLineBoxRowCol = function( aBox, aGridView, aBoxStartOuterX, aBoxStartInnerX ) {
  // aBox as this.Boxes[i]
  // aGridView as this.Rows or this.Cols
  // returns true if no more moves are requested

  var boxEndOuterX = aBoxStartOuterX + 2;
  var boxEndInnerX = aBoxStartInnerX + 2;

  for (var outerX = aBoxStartOuterX; outerX <= boxEndOuterX; outerX++) {
    var boxCSet = 0;
    var outCSet = 0;
    var outerHouse = aGridView[outerX];
    for (var innerX = 0; innerX < 9; innerX++) {
      var numCSet = this.CandidateCells[outerHouse[innerX]];
      if (numCSet) {
        if (innerX < aBoxStartInnerX || innerX > boxEndInnerX) {
          outCSet |= numCSet;
        } else {
          boxCSet |= numCSet;
        }
      }
    }
    if (boxCSet) {

      for (var num = 1; num <= 9; num++) {
        if (this.CSetContainsNum( boxCSet, num ) && !this.CSetContainsNum( outCSet, num )) {

          // search for changes in box
          var nInBox = 0;
          var nInLine = 0;
          for (var outerXX = aBoxStartOuterX; outerXX <= boxEndOuterX; outerXX++) {
            var house = aGridView[outerXX];
            for (var innerX = aBoxStartInnerX; innerX <= boxEndInnerX; innerX++) {
              var cellX = house[innerX];
              if (outerXX != outerX) {
                if (this.CSetContainsNum( this.CandidateCells[cellX], num )) {
                  nInBox++;
                }
              } else {
                if (this.CSetContainsNum( this.CandidateCells[cellX], num )) {
                  nInLine++;
                }
              }
            }
          }

          var minInLine = 2;
          // Note: Hidden or Naked Singles are handled already, so minInBox can be 2
          //if (this.ShowAllMoves) minInLine = 1;
          if (nInBox > 0 && nInLine >= minInLine) {

            var candidates = this.NewCandidates();
            var status = this.NewStatus();

            // mark house (row/col)
            for (var innerX = 0; innerX < 9; innerX++) {
              var cellX = outerHouse[innerX];
              if (this.CSetContainsNum( candidates[cellX], num )) {
                status[cellX] = 'c' + num.toString() + 'g';
              } else {
                status[cellX] = 'c';
              }
            }

            // remove num from box-rows/cols other than outerX and mark box
            var delCandList = [];
            var numCSet = this.NumToCSet( num );

            for (var outerXX = aBoxStartOuterX; outerXX <= boxEndOuterX; outerXX++) {
              if (outerXX != outerX) {
                var house = aGridView[outerXX];
                for (var innerX = aBoxStartInnerX; innerX <= boxEndInnerX; innerX++) {
                  var cellX = house[innerX];
                  status[cellX] = 'm';
                  if (this.CSetContainsNum( this.CandidateCells[cellX], num )) {
                    delCandList.push( cellX );
                    delCandList.push( numCSet );
                  }
                }
              }
            }

            if (delCandList.length > 0) {
              var infos = { Name: 'Locked Candidates Line-Box', Level: 2, Help: 'Locked Candidates' };
              var hintHouse = (aGridView == this.Rows) ? 'Zeile ' : 'Spalte ';
              hintHouse += (outerX+1);
              if (this.CreateMoves( delCandList, candidates, status, infos, numCSet, hintHouse )) {
                return true;
              }
            }

          } // end if (nInBox > 0 && nInLine >= minInLine)
        }
      } // next num
    } // end if (boxCSet != 0)
  } // next outerX
  return false;
}

CSudoku.prototype.FindNakedPairsAndTriplets = function( ) {
  return this.FindNakedTuplets( 2, 3 );
}

CSudoku.prototype.FindNakedQuadrupletsAndMore = function( ) {
  return this.FindNakedTuplets( 4 );
}

CSudoku.prototype.FindNakedTuplets = function( aStartNTuplet, aEndNTuplet ) {
  // returns true if no more moves are requested

  aStartNTuplet = aStartNTuplet || 2;
  aEndNTuplet = aEndNTuplet || 7;

  for (var nTuplet = aStartNTuplet; nTuplet <= aEndNTuplet; nTuplet++) {
    if (this.FindNTuples( nTuplet, false )) {
      return true;
    }
  }

  return false;
}

CSudoku.prototype.FindHiddenPairsAndTriplets = function( ) {
  return this.FindHiddenTuplets( 2, 3 );
}

CSudoku.prototype.FindHiddenTuplets = function( aStartNTuplet, aEndNTuplet ) {
  // returns true if no more moves are requested

  aStartNTuplet = aStartNTuplet || 2;
  aEndNTuplet = aEndNTuplet || 7;

  for (var nTuplet = aStartNTuplet; nTuplet <= aEndNTuplet; nTuplet++) {
    if (this.FindNTuples( nTuplet, true )) {
      return true;
    }
  }

  return false;
}

CSudoku.prototype.FindNTuples = function( aNTuplet, bHiddenTuples ) {
  // returns true if no more moves are requested

  // blocks
  for (var rangeX = 0; rangeX < 9; rangeX++) {
    if (this.FindNTupletInHouse( aNTuplet, bHiddenTuples, this.Boxes[rangeX], 'Box '+(rangeX+1) )) {
      return true;
    }
  }

  // rows
  for (var rangeX = 0; rangeX < 9; rangeX++) {
    if (this.FindNTupletInHouse( aNTuplet, bHiddenTuples, this.Rows[rangeX], 'Zeile '+(rangeX+1) )) {
      return true;
    }
  }

  // cols
  for (var rangeX = 0; rangeX < 9; rangeX++) {
    if (this.FindNTupletInHouse( aNTuplet, bHiddenTuples, this.Cols[rangeX], 'Spalte '+(rangeX+1) )) {
      return true;
    }
  }

  return false;
}

CSudoku.prototype.TupletNames = Array( 'Pair', 'Triple', 'Quadruple', '-Tuple' );

CSudoku.prototype.MakeTupletName = function( aNTuplet, bHiddenTuplets ) {
  var name = '';
  if (bHiddenTuplets) {
    name = 'Hidden ';
  } else {
    name = 'Naked ';
  }
  if (aNTuplet >= 2 && aNTuplet <= 4) {
    name += CSudoku.prototype.TupletNames[aNTuplet-2];
  } else {
    name += aNTuplet.toString() + CSudoku.prototype.TupletNames[3];
  }
  return name;
}

CSudoku.prototype.FindNTupletInHouse = function( aNTuplet, bHiddenTuplets, aHouse, aHouseName ) {
  // aHouse as this.Boxes[i], this.Rows[i] or this.Cols[i]
  // returns true if no more moves are requested

  var tupletNumber = aNTuplet;
  var helpPage = '';
  if (bHiddenTuplets) {
    var nCandCells = 0;
    for (var houseX = 0; houseX < 9; houseX++) {
      if (this.CandidateCells[aHouse[houseX]]) nCandCells++;
    }
    tupletNumber = nCandCells - aNTuplet;
    if (tupletNumber < 2) return false;
    helpPage = 'Hidden Subsets';
  } else {
    helpPage = 'Naked Subsets';
  }

  var ixVec = new Array(9);
  var cellVec = new Array(9);
  var candVec = new Array(9);
  var bitcVec = new Array(9);
  var statVec = new Array(9);

  var vecSize = 0;
  var nToBigSet = 0;
  for (var houseX = 0; houseX < 9; houseX++) {
    var cellX = aHouse[houseX];
    var numCSet = this.CandidateCells[cellX];
    if (numCSet) {
      var bitc = this.CSetBitCount(numCSet);
      cellVec[vecSize] = cellX;
      candVec[vecSize] = numCSet;
      bitcVec[vecSize] = bitc;
      statVec[vecSize] = false;
      if (bitc > tupletNumber) nToBigSet++;
      vecSize++;
    }
  }
  if ((vecSize <= tupletNumber) || (nToBigSet > vecSize-tupletNumber)) return false;

  for (var tup = 0; tup < tupletNumber; tup++) { ixVec[tup] = tup; }

  do {
    var currCSet = this.CommonIxVecSet( tupletNumber, ixVec, candVec, bitcVec );
    if (currCSet) {
      var currSetBitc = this.CSetBitCount(currCSet);
      if (currSetBitc == tupletNumber) {
        var nSubSets = this.FindIxVecSubSets( currCSet, currSetBitc, vecSize, candVec, bitcVec, statVec );
        if ((nSubSets == tupletNumber) && (vecSize-tupletNumber > 1)) {

          var candidates = this.NewCandidates();
          var status = this.NewStatus();
          var delCandList = []; // [ cellX, bits, cellX, bits, ... ]
          var hintNums = 0;
          var minSubsetCountInCell = 9;

          this.MarkHouse( status, aHouse, 'o' );

          // Zahlen in currCSet aus anderen Zellen entfernen (siehe statVec)
          for (var i = 0; i < vecSize; i++) {
            if (statVec[i]) {
              if (!bHiddenTuplets) {
                // mark duplets
                var dupletNumsToMark = candVec[i] & currCSet;
                status[cellVec[i]] += this.CSetToString( dupletNumsToMark, 'g' );
                hintNums |= dupletNumsToMark;
              }
            } else {
              var candBits = candVec[i];
              var newNums = candBits & ~currCSet;
              var cellX = cellVec[i];
              if (newNums != candBits) {
                // mark removed numbers
                var removedNumsToMark = candBits & ~newNums;
                delCandList.push( cellX );
                delCandList.push( removedNumsToMark );
              }
              // mark hidden tuplets
              if (bHiddenTuplets) {
                status[cellX] += this.CSetToString( newNums, 'g' );
                hintNums |= newNums;
                var newNumsCount = this.CSetBitCount( newNums );
                if (newNumsCount < minSubsetCountInCell) minSubsetCountInCell = newNumsCount;
              }
            }
          }

          if ((delCandList.length > 0) && (minSubsetCountInCell > 1)) {
            var infos = {
              Name: this.MakeTupletName( aNTuplet, bHiddenTuplets ),
              Level: tupletNumber-1,
              Help: helpPage
            };
            if (this.CreateMoves( delCandList, candidates, status, infos, hintNums, aHouseName )) {
              return true;
            }
          }

        }
      }
    }
  } while (this.IncrIxVec( ixVec, tupletNumber, vecSize ));
  return false;
}

CSudoku.prototype.FindIxVecSubSets = function( aCurrSet, aCurrSetBitc, aVecSize, aCandVec, aBitcVec, aStatVecRet ) {
  var nSubSets = 0;
  for (var i = 0; i < aVecSize; i++) {
    var bitCount = aBitcVec[i];
    if ((bitCount > 1) && (bitCount <= aCurrSetBitc)) {
      if (this.IsCSetSubset( aCurrSet, aCandVec[i] )) {
        aStatVecRet[i] = true;
        nSubSets++;
      } else {
        aStatVecRet[i] = false;
      }
    }
  }
  return nSubSets;
}

CSudoku.prototype.CommonIxVecSet = function( aNTuplet, aIxVec, aCandVec, aBitcVec ) {
  var commonSet = 0;
  for (var tup = 0; tup < aNTuplet; tup++) {
    var i = aIxVec[tup];
    if (aBitcVec[i] > aNTuplet) return 0;
    commonSet |= aCandVec[i];
  }
  return commonSet;
}

CSudoku.prototype.IncrIxVec = function( aIxVecRet, aNTuplet, aVecSize ) {
  if (aNTuplet <= 0) return false;
  var i = aNTuplet-1;
  aIxVecRet[i]++;
  if (aIxVecRet[i] < aVecSize) return true;
  if (!this.IncrIxVec( aIxVecRet, i, aVecSize-1 )) return false;
  aIxVecRet[i] = aIxVecRet[i-1] + 1;
  return true;
}

CSudoku.prototype.FindXWing = function( ) {
  return this.FindBasicFishes( 2, 2 );
}

CSudoku.prototype.FindBigBasicFishes = function( ) {
  return this.FindBasicFishes( 3 );
}

CSudoku.prototype.FindBasicFishes = function( aStartFishSize, aEndFishSize ) {
  // returns true if no more moves are requested

  aStartFishSize = aStartFishSize || 2;
  aEndFishSize = aEndFishSize || 7;

  for (var fishSize = aStartFishSize; fishSize <= aEndFishSize; fishSize++) {
    if (this.FindFishesOfSize( fishSize )) {
      return true;
    }
  }

  return false;
}

CSudoku.prototype.FindFishesOfSize = function( aFishSize ) {
  // returns true if no more moves are requested

  // rows
  if (this.FindFishesInGridView( aFishSize, this.Rows, this.Cols )) {
    return true;
  }

  // cols
  if (this.FindFishesInGridView( aFishSize, this.Cols, this.Rows )) {
    return true;
  }

  return false;
}

CSudoku.prototype.FishNames = Array( 'X-Wing', 'Swordfish', 'Jellyfish', 'Squirmbag', 'Whale', 'Leviathan' );

CSudoku.prototype.GetFishInfos = function( aFishSize ) {
  var name = '';
  var help = 'Basic Fish';
  if (aFishSize == 2) {
    help = 'X-Wing';
  }
  if (aFishSize >= 2 && aFishSize <= 7) {
    name += CSudoku.prototype.FishNames[aFishSize-2] + ' (' + aFishSize.toString() + '-Base Fish)';
  } else {
    name += aFishSize.toString() + '-Base-Fish';
  }
  var level = aFishSize - 1;
  return { Name: name, Help: help, Level: level };
}

CSudoku.prototype.FindFishesInGridView = function( aFishSize, aPrimaryGridView, aSecondaryGridView ) {
  // aPrimaryGridView, aSecondaryGridView as this.Rows/Cols
  // returns true if no more moves are requested

  for (var num = 1; num <= 9; num++) {
    if (this.NumbersCount[num] < 9) {
      if (this.FindFishesInGridViewForNum( num, aFishSize, aPrimaryGridView, aSecondaryGridView )) {
        return true;
      }
    }
  }
  return false;
}

CSudoku.prototype.FindFishesInGridViewForNum = function( aNum, aFishSize, aPrimaryGridView, aSecondaryGridView ) {
  // aPrimaryGridView, aSecondaryGridView as this.Rows/Cols
  // returns true if no more moves are requested

  // prepare internal vectors
  var numCSet = this.NumToCSet( aNum );
  var ixVec = [];
  var primXVec = [];
  var secMaskVec = [];
  var vecSize = 0;
  for (var primX = 0; primX < 9; primX++) {
    var house = aPrimaryGridView[primX];
    var mask = 0;
    var numCount = 0;
    for (var secX = 0; secX < 9 && numCount <= aFishSize; secX++) {
      var cellX = house[secX];
      if (this.CandidateCells[cellX] & numCSet) {
        mask |= this.NumToCSet( secX+1 );
        numCount++;
      }
    }
    if (numCount >= 2 && numCount <= aFishSize) {
      primXVec.push( primX );
      secMaskVec.push( mask );
      vecSize++;
    }
  }
  if (vecSize < aFishSize) return false;
  for (var i = 0; i < aFishSize; i++) { ixVec.push( i ); }

  do {
    var commonSecMask = 0;
    var primMask = 0;
    for (var i = 0; i < aFishSize; i++) {
      var vecX = ixVec[i];
      commonSecMask |= secMaskVec[vecX];
      primMask |= this.NumToCSet(primXVec[vecX]+1);
    }
    if (this.CSetBitCount( commonSecMask ) == aFishSize) {
      // fish found

      // check if candidates can be removed
      var nRemoves = 0;
      var nMinCandPerHouse = 9;
      for (var secX = 0; secX < 9; secX++) {
        if (this.CSetContainsNum( commonSecMask, secX+1 )) {
          var house = aSecondaryGridView[secX];
          var nCand = 0;
          for (var primX = 0; primX < 9; primX++) {
            // skip cells of fish houses
            var cellX = house[primX];
            if (this.CandidateCells[cellX] & numCSet) {
              nCand++;
              if (!this.CSetContainsNum( primMask, primX+1 )) nRemoves++;
            }
          }
          nMinCandPerHouse = (nCand < nMinCandPerHouse) ? nCand : nMinCandPerHouse;
        }
      }

      // remove candidates and mark cells
      if (nRemoves > 0 && nMinCandPerHouse > 1) {

        var candidates = this.NewCandidates();
        var status = this.NewStatus();
        var delCandList = []; // [ cellX, bits, cellX, bits, ... ]

        // mark primary houses (rows/cols)
        for (var primX = 0; primX < 9; primX++) {
          if (this.CSetContainsNum( primMask, primX+1 )) {
            this.MarkHouse( status, aPrimaryGridView[primX], 'g' );
          }
        }

        for (var secX = 0; secX < 9; secX++) {
          if (this.CSetContainsNum( commonSecMask, secX+1 )) {
            var house = aSecondaryGridView[secX];
            for (var primX = 0; primX < 9; primX++) {
              var cellX = house[primX];
              if (this.CSetContainsNum( primMask, primX+1 )) {

                // for fish cells do...
                status[cellX] = 'c';
                if (candidates[cellX] & numCSet) {
                  status[cellX] += aNum.toString() + 'g';
                }

              } else {

                // remove candidates from secondary view
                status[cellX] = 'b';
                if (candidates[cellX] & numCSet) {
                  delCandList.push( cellX );
                  delCandList.push( numCSet );
                }

              }
            }
          }
        }

        if (delCandList.length > 0) {
          var hintHouse = (aPrimaryGridView == this.Rows) ? 'Zeilen ' : 'Spalten ';
          hintHouse += this.CSetToVectorString( primMask );
          var infos = this.GetFishInfos( aFishSize );
          if (this.CreateMoves( delCandList, candidates, status, infos, numCSet, hintHouse )) {
            return true;
          }
        }

      }
    }
  } while (this.IncrIxVec( ixVec, aFishSize, vecSize ));

  return false;
}

// ------------------------------------------

CSudoku.prototype.FindTurbotFish = function( ) {
  // returns true if no more moves are requested
  return this.FindXChainsOfSize( 4, 4 );
}

CSudoku.prototype.FindXChains = function( ) {
  // returns true if no more moves are requested
  return this.FindXChainsOfSize( 6 );
}

CSudoku.prototype.FindXChainsOfSize = function( aMinSize, aMaxSize ) {
  // returns true if no more moves are requested

  aMinSize = aMinSize || 4;
  aMaxSize = aMaxSize || 0;
  aMinSize = div( aMinSize+1, 2 ) * 2;
  aMaxSize = div( aMaxSize+1, 2 ) * 2;
  if (aMinSize < 4) aMinSize = 4;
  if (aMaxSize > 0 && aMaxSize < aMinSize) aMaxSize = aMinSize;

  this.CreateXChainList();

  var maxChainSize = this.GetMaxXChainSize();
  if (aMaxSize > 0 && aMaxSize < maxChainSize) maxChainSize = aMaxSize;

  for (var chainSize = aMinSize; chainSize <= maxChainSize; chainSize += 2) {

    var chainListSize = this.XChainList.length;
    for (var chainListX = 0; chainListX < chainListSize; chainListX++) {

      var chainListElement = this.XChainList[chainListX];
      var chain = chainListElement.XChain;

      if (chain.length == chainSize) {

        var numBit = chainListElement.Num;
        var chainType = chainListElement.ChainType;

        var candidates = this.NewCandidates();
        var status = this.NewStatus();

        // mark chain to exclude marked cells from following search of delete candidates
        for (var chainX = 0; chainX < chainSize; chainX++) {
          var node = chain[chainX];
          var firstOrLast = ((chainX == 0 || chainX == chainSize-1) && (chainType != 1));
          var cellStatus = (chainX+1) + ':';
          if (chainX % 2 == 0) {
            if (firstOrLast) {
              if (chainType == 2) {
                cellStatus = '1:';
              } else {
                cellStatus += 'G' + this.CSetToString( numBit, 'g' );
              }
            } else {
              cellStatus += 'g' + this.CSetToString( numBit, 'g' );
            }
          } else {
            if (firstOrLast) {
              if (chainType == 2) {
                cellStatus = '1:';
              } else {
                cellStatus += 'B' + this.CSetToString( numBit, 'b' );
              }
            } else {
              cellStatus += 'b' + this.CSetToString( numBit, 'b' );
            }
          }
          status[node.CellX] = cellStatus;
        }

        var delCandList = []; // [ <cellX>, <delCandCSet>, ... ]

        if (chainType == 1) {

          // X-Chain Nice Loops: check for cells that see any pairs of chain with common candidate
          for (var cellX = 0; cellX < 81; cellX++) {
            if ((status[cellX] == '') && (candidates[cellX] & numBit)) {
              var seesNOdd = 0;
              var seesNEven = 0;
              for (var chainX = 0; chainX < chainSize; chainX++) {
                var node = chain[chainX];
                var nodeCellX = node.CellX;
                if (this.IsSameHouse( cellX, nodeCellX )) {
                  seesNOdd += (chainX % 2);
                  seesNEven += ((chainX+1) % 2);
                }
              }
              if ((seesNOdd * seesNEven) != 0) {
                // cellX sees both an even and an odd node
                delCandList.push( cellX );
                delCandList.push( numBit );
              }
            }
          }

        } else if (chainType == 2) {

          // X-Chain Dicont. Loop: candidate numBit in start cell = end cell is solution,
          // -> delete other candidates from this cell
          var firstCellX = chain[0].CellX;
          var otherNumBits = candidates[firstCellX] & ~numBit;
          if (otherNumBits) {
            delCandList.push( firstCellX );
            delCandList.push( otherNumBits );
          }

        } else {

          // X-Chain: check for cells that see start and end of chain
          var firstCellX = chain[0].CellX;
          var lastCellX = chain[chainSize-1].CellX;

          for (var cellX = 0; cellX < 81; cellX++) {
            if ((status[cellX] == '') && (candidates[cellX] & numBit)) {
              if (this.IsSameHouse( cellX, firstCellX ) && this.IsSameHouse( cellX, lastCellX )) {
                delCandList.push( cellX );
                delCandList.push( numBit );
              }
            }
          }

        }

        if (delCandList.length > 0) {

          var infos = this.GetXChainInfos( chain, chainType );

          if (infos.Help == 'Skyscraper') {
            this.MarkSkyscraper( numBit, chain, status );
          } else if (infos.Help == '2-String Kite') {
            this.MarkKite( numBit, chain, status );
          } else if (infos.Help == 'Turbot Fish') {
            this.MarkTurbotFish( numBit, chain, status );
          }

          if (this.CreateMoves( delCandList, candidates, status, infos, numBit )) {
            return true;
          }
        }

      } // end if (chain.length == chainSize)
    } // next chainListX
  } // next chainSize
  return false;
}

CSudoku.prototype.XChainLoopIsXWing = function( aXChain ) {
  // Requires aXChain.length == 4
  var rowMask = 0;
  var colMask = 0;
  for (var chainX = 0; chainX < 4; chainX++) {
    var cellX = aXChain[chainX].CellX;
    var rowX = this.RowXofCellX( cellX );
    var colX = this.ColXofCellX( cellX );
    rowMask |= this.NumToCSet( rowX+1 );
    colMask |= this.NumToCSet( colX+1 );
  }
  return (this.CSetBitCount(rowMask) == 2 && this.CSetBitCount(colMask) == 2);
}

CSudoku.prototype.GetXChainInfos = function( aXChain, aChainType ) {
  // returns { Name, Help, Level }
  var name = '';
  var help = '';
  var chainSize = aXChain.length;
  var level = chainSize - 5;

  if (chainSize == 4) {

    if (aChainType == 1) {

      name = 'X-Chain Nice Loop ' + chainSize;
      help = 'X-Chain Nice Loop';
      if (this.XChainLoopIsXWing( aXChain )) {
        name += ' (X-Wing)';
        level = 1;
      } else {
        level = 3;
      }

    } else {

      name = 'X-Chain ' + chainSize;
      var dirHash = '';
      for (var i = 0; i < 3; i++) {
        dirHash += aXChain[i].Dir;
      }
      if (dirHash.indexOf('2') == -1) {
        name = 'Skyscraper (' + name + ')';
        help = 'Skyscraper';
        level = 2;
      } else if (dirHash == '021' || dirHash == '120') {
        name = '2-String Kite (' + name + ')';
        help = '2-String Kite';
        level = 4;
      } else if (dirHash == '012' || dirHash == '102' || dirHash == '201' || dirHash == '210' ) {
        name = 'Turbot Fish (' + name + ')';
        help = 'Turbot Fish';
        level = 5;
      } else {
        level = 5;
      }

    }

  } else {

    if (aChainType == 1) {

      name = 'X-Chain Nice Loop ' + chainSize;
      help = 'X-Chain Nice Loop';
      level++;

    } else if (aChainType == 2) {

      name = 'X-Chain Discont. Loop ' + (chainSize-1);
      help = 'X-Chain Discontinuous Loop';
      level++;

    } else {

      name = 'X-Chain ' + chainSize;
      help = 'X-Chain';

    }
  }

  if (level > 9) level = 9;
  return { Name: name, Help: help, Level: level };
}

CSudoku.prototype.CompXChainLevel = function( aXChain, aChainType ) {
  // returns Level : int
  var level = aXChain.length - 5;
  if (aXChain.length == 4) {
    if (aChainType == 1) {
      if (this.XChainLoopIsXWing( aXChain )) {
        level = 1;
      } else {
        level = 3;
      }
    } else {
      var dirHash = '';
      for (var i = 0; i < 3; i++) {
        dirHash += aXChain[i].Dir;
      }
      if (dirHash.indexOf('2') == -1) {
        level = 2;
      } else if (dirHash == '021' || dirHash == '120') {
        level = 4;
      } else {
        level = 5;
      }
    }
  } else {
    if (aChainType != 0) {
      level++;
    }
  }
  if (level > 9) level = 9;
  return level;
}

CSudoku.prototype.MarkSkyscraper = function( aNumCSet, aChain, aStatus ) {
  var cellX1 = aChain[0].CellX;
  var cellX2 = aChain[1].CellX;
  var cellX3 = aChain[2].CellX;
  var cellX4 = aChain[3].CellX;
  if (this.IsSameRow( cellX2, cellX3 )) {
    var rowX = this.RowXofCellX( cellX2 );
    this.MarkHouse( aStatus, this.Rows[rowX], 'c' );
    var colX = this.ColXofCellX( cellX1 );
    this.MarkHouse( aStatus, this.Cols[colX], 'g' );
    var colX = this.ColXofCellX( cellX4 );
    this.MarkHouse( aStatus, this.Cols[colX], 'b' );
  } else {
    var colX = this.ColXofCellX( cellX2 );
    this.MarkHouse( aStatus, this.Cols[colX], 'c' );
    var rowX = this.RowXofCellX( cellX1 );
    this.MarkHouse( aStatus, this.Rows[rowX], 'g' );
    var rowX = this.RowXofCellX( cellX4 );
    this.MarkHouse( aStatus, this.Rows[rowX], 'b' );
  }
  aStatus[cellX1] = '1:G' + this.CSetToString( aNumCSet, 'g' );
  aStatus[cellX2] = '2:c' + this.CSetToString( aNumCSet, 'b' );
  aStatus[cellX3] = '3:c' + this.CSetToString( aNumCSet, 'g' );
  aStatus[cellX4] = '4:B' + this.CSetToString( aNumCSet, 'b' );
}

CSudoku.prototype.MarkKite = function( aNumCSet, aChain, aStatus ) {
  var cellX1 = aChain[0].CellX;
  var cellX2 = aChain[1].CellX;
  var cellX3 = aChain[2].CellX;
  var cellX4 = aChain[3].CellX;
  if (this.IsSameRow( cellX3, cellX4 )) {
    var rowX = this.RowXofCellX( cellX4 );
    this.MarkHouse( aStatus, this.Rows[rowX], 'b' );
    var colX = this.ColXofCellX( cellX1 );
    this.MarkHouse( aStatus, this.Cols[colX], 'g' );
    var cellX = this.Rows[rowX][colX];
    aStatus[cellX] = 'c';
  } else {
    var colX = this.ColXofCellX( cellX4 );
    this.MarkHouse( aStatus, this.Cols[colX], 'b' );
    var rowX = this.RowXofCellX( cellX1 );
    this.MarkHouse( aStatus, this.Rows[rowX], 'g' );
    var cellX = this.Rows[rowX][colX];
    aStatus[cellX] = 'c';
  }
  aStatus[cellX1] = '1:G' + this.CSetToString( aNumCSet, 'g' );
  aStatus[cellX2] = '2:' + aStatus[cellX2] + this.CSetToString( aNumCSet, 'b' );
  aStatus[cellX3] = '3:' + aStatus[cellX3] + this.CSetToString( aNumCSet, 'g' );
  aStatus[cellX4] = '4:B' + this.CSetToString( aNumCSet, 'b' );
}

CSudoku.prototype.MarkTurbotFish = function( aNumCSet, aChain, aStatus ) {
  var cellX1 = aChain[0].CellX;
  var cellX2 = aChain[1].CellX;
  var cellX3 = aChain[2].CellX;
  var cellX4 = aChain[3].CellX;
  if (this.IsSameBox( cellX1, cellX2 )) {
    var boxX = this.BoxXofCellX( cellX1 );
    this.MarkHouse( aStatus, this.Boxes[boxX], 'g' );
    if (this.IsSameRow( cellX3, cellX4 )) {
      var rowX = this.RowXofCellX( cellX4 );
      this.MarkHouse( aStatus, this.Rows[rowX], 'b' );
      var colX = this.ColXofCellX( cellX3 );
      this.MarkHouse( aStatus, this.Cols[colX], 'c' );
    } else {
      var colX = this.ColXofCellX( cellX4 );
      this.MarkHouse( aStatus, this.Cols[colX], 'b' );
      var rowX = this.RowXofCellX( cellX3 );
      this.MarkHouse( aStatus, this.Rows[rowX], 'c' );
    }
  } else {
    var boxX = this.BoxXofCellX( cellX4 );
    this.MarkHouse( aStatus, this.Boxes[boxX], 'b' );
    if (this.IsSameRow( cellX1, cellX2 )) {
      var rowX = this.RowXofCellX( cellX1 );
      this.MarkHouse( aStatus, this.Rows[rowX], 'g' );
      var colX = this.ColXofCellX( cellX2 );
      this.MarkHouse( aStatus, this.Cols[colX], 'c' );
    } else {
      var colX = this.ColXofCellX( cellX1 );
      this.MarkHouse( aStatus, this.Cols[colX], 'g' );
      var rowX = this.RowXofCellX( cellX2 );
      this.MarkHouse( aStatus, this.Rows[rowX], 'c' );
    }
  }
  aStatus[cellX1] = '1:G' + this.CSetToString( aNumCSet, 'g' );
  aStatus[cellX2] = '2:c' + this.CSetToString( aNumCSet, 'b' );
  aStatus[cellX3] = '3:c' + this.CSetToString( aNumCSet, 'g' );
  aStatus[cellX4] = '4:B' + this.CSetToString( aNumCSet, 'b' );
}

CSudoku.prototype.CreateXChainList = function() {
  if (this.XChainListValid) return;

  for (var num = 1; num <= 9; num++) {
    if (this.CandidatesCount[num] > 4) {
      var numCSet = this.NumToCSet( num );
      var chain = [];

      while (this.NextXChain( num, numCSet, chain )) {
        this.AddXChainToList( chain, numCSet );
      }
    }
  }
  this.XChainListValid = true;
}

CSudoku.prototype.AddXChainToList = function( aXChain, aNumCSet ) {
  // If a chain with same start and endpoint and same size and same aNumCSet is already in the list, then aXChain is not added,
  // but if aXChain is smaller for the same enpoints or Level is less than the entry in the list is replaced by aXChain.
  // Note: aXChain is copied!
  // XChainList: array of { ChainType: <0,1,2>, Num: <CSet>, XChain: array of ChainNodes: { CellX, Dir, DirX, LinkNum } }
  // ChainType = 0 -> open chain; 1 -> nice loop; 2 -> dicontinuous loop

  if (aXChain.length < 4) return; // skip too small chains

  var startCellX = aXChain[0].CellX;
  var endCellX = aXChain[aXChain.length-1].CellX;
  var chainType = 0;
  if (this.IsSameHouse( startCellX, endCellX )) {
    if (startCellX == endCellX) {
      chainType = 2;
    } else {
      chainType = 1;
    }
  }

  var level = this.CompXChainLevel( aXChain, chainType );

  if (chainType == 1) {

    // find loop chain with same size and same cells and same aNumCSet
    var xChainListSize = this.XChainList.length;
    for (var chainListX = 0; chainListX < xChainListSize; chainListX++) {
      var le = this.XChainList[chainListX];
      var leChain = le.XChain;
      var leChainNumCSet = le.Num;
      var leChainType = le.ChainType;
      if ((leChainType == 1) && (leChainNumCSet == aNumCSet) && this.IsSameChainLoop( leChain, aXChain )) {
        // discard chain
        return false;
      }
    }

    // if no such X-Chain loop is in this.XChainList, append a copy of aXChain
    this.XChainList.push( { ChainType: chainType, Num: aNumCSet , XChain: this.CopyChain(aXChain) } );
    return true;

  } else {

    // find chain with same endpoints
    var chainListSize = this.XChainList.length;
    for (var chainListX = 0; chainListX < chainListSize; chainListX++) {
      var le = this.XChainList[chainListX];
      var leChain = le.XChain;
      var leChainNumCSet = le.Num;
      var leChainType = le.ChainType;
      var leStartCellX = leChain[0].CellX;
      var leEndCellX = leChain[leChain.length-1].CellX;
      if ((leChainType != 1) && (leChainNumCSet == aNumCSet) && ((startCellX == leStartCellX && endCellX == leEndCellX) || (startCellX == leEndCellX && endCellX == leStartCellX))) {

        // chain with same endpoints found at chainListX. Check which is shorter
        if ((aXChain.length < leChain.length) || ((aXChain.length == leChain.length) && (level < this.CompXChainLevel(leChain,leChainType)))) {
          // replace chain at chainListX with a copy of aXChain
          this.XChainList[chainListX] = { ChainType: chainType, Num: aNumCSet, XChain: this.CopyChain(aXChain) };
        }
        // else discard aXChain
        return false;
      }
    }

    // if no similar xChain is in this.XChainList, append a copy of aXChain
    this.XChainList.push( { ChainType: chainType, Num: aNumCSet, XChain: this.CopyChain(aXChain) } );
    return true;

  }
}

CSudoku.prototype.NewChainNode = function( aCellX, aLinkNum, aDir, aDirX ) {
  aLinkNum = aLinkNum | 0;
  aDir = aDir | 0;
  aDirX = aDirX | -1;
  return {
    CellX:    aCellX,
    LinkNum:  aLinkNum,
    Dir:      aDir,
    DirX:     aDirX,
    CellMask: 0,
    RowMask:  0,
    ColMask:  0,
    BoxMask:  0
  };
}

CSudoku.prototype.MakeChainNodeMasks = function( aCurrNode, aPrevNode ) {
  if (aPrevNode) {
    var cellX = aCurrNode.CellX;
    aCurrNode.CellMask = this.CandidateCells[cellX] | aPrevNode.CellMask;
    aCurrNode.RowMask = this.NumToCSet( this.RowXofCellX( cellX ) + 1 ) | aPrevNode.RowMask;
    aCurrNode.ColMask = this.NumToCSet( this.ColXofCellX( cellX ) + 1 ) | aPrevNode.ColMask;
    aCurrNode.BoxMask = this.NumToCSet( this.BoxXofCellX( cellX ) + 1 ) | aPrevNode.BoxMask;
  } else {
    var cellX = aCurrNode.CellX;
    aCurrNode.CellMask = this.CandidateCells[cellX];
    aCurrNode.RowMask = this.NumToCSet( this.RowXofCellX( cellX ) + 1 );
    aCurrNode.ColMask = this.NumToCSet( this.ColXofCellX( cellX ) + 1 );
    aCurrNode.BoxMask = this.NumToCSet( this.BoxXofCellX( cellX ) + 1 );
  }
}

CSudoku.prototype.CopyChainNode = function( aNode ) {
  return {
    CellX:    aNode.CellX,
    LinkNum:  aNode.LinkNum,
    Dir:      aNode.Dir,
    DirX:     aNode.DirX,
    CellMask: aNode.CellMask,
    RowMask:  aNode.RowMask,
    ColMask:  aNode.ColMask,
    BoxMask:  aNode.BoxMask
  };
}

CSudoku.prototype.CopyChain = function( aChain ) {
  // Works for XChains and XYChains
  var newChain = [];
  var chainSize = aChain.length;
  for (var i = 0; i < chainSize; i++) {
    newChain.push( this.CopyChainNode( aChain[i] ) );
  }
  // copy summerized statistics of last node into first node
  if (chainSize > 1) {
    var firstNode = newChain[0];
    var lastNode = newChain[chainSize-1];
    firstNode.CellMask = lastNode.CellMask;
    firstNode.RowMask = lastNode.RowMask;
    firstNode.ColMask = lastNode.ColMask;
    firstNode.BoxMask = lastNode.BoxMask;
  }
  return newChain;
}

CSudoku.prototype.IsSameChainLoop = function( aChain1, aChain2 ) {
  // works for XChains and XYChains!
  // requires that aChain1 and aChain2 are chain loops, e.g. start and end point are in same house.
  var chainSize = aChain1.length;
  if (chainSize != aChain2.length) return false;

  // check statistics: if at least one CSet does not match, then aChain1 is not same loop as Chain2
  var n1 = aChain1[chainSize-1];
  var n2 = aChain2[chainSize-1];
  if (n1.CellMask != n2.CellMask || n1.RowMask != n2.RowMask || n1.ColMask != n2.ColMask) return false;

  // further check wether chains are in same direction or counter directional
  var startX1 = 0;
  var startX2 = this.FindChainNode( aChain2, aChain1[0].CellX );
  if (startX2 == -1) return false;
  var nextX1 = startX1 + 1;
  var nextX2 = (startX2 + 1) % chainSize;

  var dir = 1;
  if (aChain1[nextX1].CellX != aChain2[nextX2].CellX) {
    // counter directional
    dir = -1;
    startX2 += chainSize;
  }
  // check wether all nodes have same CellX
  for (startX1 = 0; startX1 < chainSize; startX1++) {
    if (aChain1[startX1].CellX != aChain2[startX2 % chainSize].CellX) return false;
    startX2 += dir;
  }
  return true;
}

CSudoku.prototype.SetCoverCells = function( aChain ) {
  this.ClearCells( this.CoverCells, false );
  var chainSize = aChain.length;
  var grid = this.CoverCells;
  for (var chainX = 0; chainX < chainSize; chainX++) {
    grid[aChain[chainX].CellX] = true;
  }
}

CSudoku.prototype.IsSameCoverCells = function( aChain ) {
  var chainSize = aChain.length;
  var grid = this.CoverCells;
  for (var chainX = 0; chainX < chainSize; chainX++) {
    if (!grid[aChain[chainX].CellX]) return false;
  }
  return true
}

CSudoku.prototype.FindChainNode = function( aChain, aCellX ) {
  // Works for XChains and XYChains
  var chainSize = aChain.length;
  for (var chainX = 0; chainX < chainSize; chainX++) {
    if (aChain[chainX].CellX == aCellX) return chainX;
  }
  return -1;
}

CSudoku.prototype.IsCellInChain = function( aChain, aCellX, bIgnoreFirstCell ) {
  // Works for XChains and XYChains
  var offset = bIgnoreFirstCell ? 1 : 0;
  return this.FindChainNode( aChain, aCellX  ) >= offset;
}

CSudoku.prototype.GetMaxXChainSize = function() {
  var chainListSize = this.XChainList.length;
  var maxXChainSize = 0;
  for (var chainListX = 0; chainListX < chainListSize; chainListX++) {
    var chainSize = this.XChainList[chainListX].XChain.length;
    if (chainSize > maxXChainSize) maxXChainSize = chainSize;
  }
  return maxXChainSize;
}

CSudoku.prototype.NextXChain = function( aNum, aCSet, aXChain ) {
  // aXChain: [ Node ]
  // Node: {
  //   CellX: 0-80
  //   Dir: 0=Row, 1=Col, 2=Box
  //   DirX: 0-8
  //   LinkNum: CSet
  //   CellMask: CSet
  //   RowMask: CSet
  //   ColMask: CSet
  // }

  if (aXChain.length == 0) {
    if (!this.FirstXChainLink( aNum, aCSet, aXChain )) return false;
  }
  while (aXChain.length > 0) {
    if (this.NextXChainLinkPair( aNum, aCSet, aXChain )) return true;
    if (aXChain.length > 2) {
      aXChain.length -= 2;
    } else {
      aXChain.length = 1;
      if (!this.FirstXChainLink( aNum, aCSet, aXChain )) {
        aXChain.length = 0;
        return false;
      }
    }
  }
  return false;
}

CSudoku.prototype.FirstXChainLink = function( aNum, aCSet, aXChain ) {
  while (this.NextXChainStart( aNum, aCSet, aXChain )) {
    if (this.NextXChainLink( aNum, aCSet, aXChain, true )) return true
  }
  return false;
}

CSudoku.prototype.NextXChainLinkPair = function( aNum, aCSet, aXChain ) {
  while (this.NextXChainLink( aNum, aCSet, aXChain, false )) {
    if (this.NextXChainLink( aNum, aCSet, aXChain, true )) return true;
    aXChain.length--;
  }
  return false;
}

CSudoku.prototype.NextXChainStart = function( aNum, aCSet, aXChain ) {
  if (aXChain.length == 0) {
    // find first node
    for (var cellX = 0; cellX < 81; cellX++) {
      if (this.CandidateCells[cellX] & aCSet) {
        // init chain
        aXChain.push( this.NewChainNode( cellX ) );
        return true;
      }
    }
    return false;
  }

  var node = aXChain[0];
  node.Dir++;
  node.DirX = -1;
  if (node.Dir <= 2) return true;

  for (var cellX = node.CellX+1; cellX < 81; cellX++) {
    if (this.CandidateCells[cellX] & aCSet) {
      node.CellX = cellX;
      node.Dir = 0;
      node.DirX = -1;
      return true;
    }
  }
  aXChain = [];
  return false;
}

CSudoku.prototype.NextXChainLink = function( aNum, aCSet, aXChain, bStrong ) {

  var chainSize = aXChain.length;
  var minLeftCandidates = 3;
  if (bStrong) minLeftCandidates = 2;
  if ((this.CandidatesCount[aNum] - chainSize) < minLeftCandidates) return false;

  var currNodeX = chainSize - 1;
  if (currNodeX < 0) return false;

  // if first cell = last cell then aXChain is a discontinuous loop
  // -> further nodes must not be searched from this chain!
  if ((chainSize > 1) && (aXChain[0].CellX == aXChain[chainSize-1].CellX)) return false;

  var currNode = aXChain[currNodeX];
  var currRowX = this.RowXofCellX( currNode.CellX );
  var currColX = this.ColXofCellX( currNode.CellX );

  var lastDir = -1;
  if (currNodeX > 0) {
    var lastNode = aXChain[currNodeX - 1];
    lastDir = lastNode.Dir;
  }

  for (var dir = currNode.Dir; dir <= 2; dir++) {
    if (dir != lastDir) {
      var dirHouse = this.Houses[dir];
      var houseX = this.HouseXofCellX[dir].call( this, currNode.CellX );
      var house = dirHouse[houseX];

      if (!bStrong || this.NCandidatesInHouse( aCSet, house ) == 2) {
        for (var dirX = currNode.DirX + 1; dirX < 9; dirX++) {

          var cellX = house[dirX];
          // skip box cells in the same row or col as current node, because they are already processed in dir = 0 or 1!
          var skip = (dir == 2 && (currRowX == this.RowXofCellX( cellX ) || currColX == this.ColXofCellX( cellX )));
          var skipFirstNode = bStrong && chainSize > 4;

          if (!skip && (this.CandidateCells[cellX] & aCSet) && !this.IsCellInChain( aXChain, cellX, skipFirstNode )) {
            var newNode = this.NewChainNode( cellX );
            currNode.Dir = dir;
            currNode.DirX = dirX;
            aXChain.push( newNode );
            return true;
          }
        }
      }
      currNode.DirX = -1;
    }
  }
  return false;
}

//---------------------------------------------------------

CSudoku.prototype.FindXYZWing = function ( ) {
  // returns true if no more moves are requested

  var pivotList = [];
  var pincer1List = [];
  var pincer2List = [];

  // search for XYZ Wings and save them in lists above
  for (var pivotCellX = 0; pivotCellX < 81; pivotCellX++) {
    var pivot = this.CandidateCells[pivotCellX];
    if (this.CSetBitCount( pivot ) == 3) {

      var rowX = this.RowXofCellX( pivotCellX );
      var colX = this.ColXofCellX( pivotCellX );
      var boxX = this.BoxXofCellX( pivotCellX );
      var pincerList = [];
      this.FindPincerInHouse( this.Rows[rowX], pincerList, pivotCellX, pivot );
      this.FindPincerInHouse( this.Cols[colX], pincerList, pivotCellX, pivot );
      this.FindPincerInHouse( this.Boxes[boxX], pincerList, pivotCellX, pivot );

      var pincerListSize = pincerList.length;
      if (pincerListSize >= 2) {
        for (var pincerX1 = 0; pincerX1 < pincerListSize-1; pincerX1++) {
          var pincer1CellX = pincerList[pincerX1];
          var pincer1 = this.CandidateCells[pincer1CellX];
          for (var pincerX2 = pincerX1+1; pincerX2 < pincerListSize; pincerX2++) {
            var pincer2CellX = pincerList[pincerX2];
            var pincer2 = this.CandidateCells[pincer2CellX];
            var commonPincerNumBit = pincer1 & pincer2;
            if (this.CSetBitCount( commonPincerNumBit ) == 1 && !this.IsSameHouse( pincer1CellX, pincer2CellX )) {
              if (this.IsSameBox( pivotCellX, pincer1CellX ) || this.IsSameBox( pivotCellX, pincer2CellX )) {
                // XYZ Wing found
                pivotList.push( pivotCellX );
                pincer1List.push( pincer1CellX );
                pincer2List.push( pincer2CellX );
              }
            }
          }
        }
      }
    }
  }

  // handle XYZ Wings
  var wingListSize = pivotList.length;
  for (wingX = 0; wingX < wingListSize; wingX++) {

    var pivotCellX = pivotList[wingX];
    var pincer1CellX = pincer1List[wingX];
    var pincer2CellX = pincer2List[wingX];
    var pivot = this.CandidateCells[pivotCellX];
    var pincer1 = this.CandidateCells[pincer1CellX];
    var pincer2 = this.CandidateCells[pincer2CellX];
    var commonPincerNumBit = pincer1 & pincer2;
    var linkNumCSet1 = pincer1 & ~commonPincerNumBit;
    var linkNumCSet2 = pincer2 & ~commonPincerNumBit;

    var candidates = this.NewCandidates();
    var status = this.NewStatus();

    // mark pivot and pincers to exclude marked cells from search of delete candidates
    var commonNumMark = this.CSetToString( commonPincerNumBit, 'm' );
    var cellStatus = '2:c' + this.CSetToString( linkNumCSet1, 'g' ) + this.CSetToString( linkNumCSet2, 'b' ) + commonNumMark;
    status[pivotCellX] = cellStatus;
    cellStatus = '1:C' + this.CSetToString( linkNumCSet1, 'g' ) + commonNumMark;
    status[pincer1CellX] = cellStatus;
    cellStatus = '3:C' + this.CSetToString( linkNumCSet2, 'b' ) + commonNumMark;
    status[pincer2CellX] = cellStatus;

    // find candidates that can be removed
    var delCandList = []; // [ <cellX>, <delCandCSet>, ... ]

    for (var cellX = 0; cellX < 81; cellX++) {
      var cand = this.CandidateCells[cellX];
      if ((cand & commonPincerNumBit) && (status[cellX] == '') && this.IsSameHouse(cellX,pivotCellX) && this.IsSameHouse(cellX,pincer1CellX) && this.IsSameHouse(cellX,pincer2CellX)) {
        delCandList.push( cellX );
        delCandList.push( commonPincerNumBit );
      }
    }

    if (delCandList.length > 0) {
      var infos = { Name: 'XYZ-Wing', Level: 0, Help: 'XYZ-Wing' };
      var hintHouse = 'Box ' + (this.BoxXofCellX( pivotCellX ) + 1);
      if (this.CreateMoves( delCandList, candidates, status, infos, commonPincerNumBit, hintHouse )) {
        return true;
      }
    }

  } // next wingX

  return false;
}

CSudoku.prototype.FindPincerInHouse = function( aHouse, aPincerList, aPivotCellX, aPivot ) {

  function ListContains( aList, aValue ) {
    for (var i = 0; i < aList.length; i++) {
      if (aList[i] == aValue) return true;
    }
    return false;
  }

  for (var houseX = 0; houseX < 9; houseX++) {
    var cellX = aHouse[houseX];
    var pincer = this.CandidateCells[cellX];
    if (cellX != aPivotCellX && this.CSetBitCount(pincer) == 2 && this.CSetBitCount(pincer & aPivot) == 2) {
      if (!ListContains( aPincerList, cellX )) {
        aPincerList.push( cellX );
      }
    }
  }
}

//---------------------------------------------------------

CSudoku.prototype.FindWWing = function ( ) {
  // returns true if no more moves are requested

  var w1List = [];
  var w2List = [];
  var l1List = [];
  var l2List = [];
  var wNumList = [];

  // search for w-wing configurations
  for (var w1CellX = 0; w1CellX < 80; w1CellX++) {
    var w1Cand = this.CandidateCells[w1CellX];
    if (w1Cand && this.CSetBitCount(w1Cand) == 2) {
      for (var w2CellX = w1CellX+1; w2CellX < 81; w2CellX++) {
        var w2Cand = this.CandidateCells[w2CellX];
        if (w2Cand == w1Cand && !this.IsSameHouse( w1CellX, w2CellX )) {
          // wing tips found, find strong link between wing tips
          var numCSet = 0;
          while (numCSet = this.NextCSet( w1Cand, numCSet )) {
            for (var l1CellX = 0; l1CellX < 81; l1CellX++) {
              var l1Cand = this.CandidateCells[l1CellX];
              if (
                (l1CellX != w1CellX) &&
                (l1Cand & numCSet) &&
                (this.CSetBitCount( w1Cand | l1Cand ) > 2) &&
                this.IsSameHouse( l1CellX, w1CellX ) &&
                !this.IsSameHouse( l1CellX, w2CellX )
              ) {
                for (var l2CellX = 0; l2CellX < 81; l2CellX++) {
                  var l2Cand = this.CandidateCells[l2CellX];
                  if (
                    (l2CellX != w2CellX) &&
                    (l2Cand & numCSet) &&
                    (this.CSetBitCount( w1Cand | l2Cand ) > 2) &&
                    this.IsSameHouse( l2CellX, w2CellX ) &&
                    !this.IsSameHouse( l2CellX, w1CellX )
                  ) {

                    // wing link candidates found. If they are in the same house and a strongly linked, take it
                    if (this.GetStrongLinkHouse( numCSet, l1CellX, l2CellX )) {

                      w1List.push( w1CellX );
                      w2List.push( w2CellX );
                      l1List.push( l1CellX );
                      l2List.push( l2CellX );
                      wNumList.push( numCSet );

                    }

                  }
                }
              }
            }
          }
        }
      }
    }
  }

  var wingListSize = w1List.length;
  for (var wingX = 0; wingX < wingListSize; wingX++) {

    // find candidates that can deleted from W-Wing
    var w1CellX = w1List[wingX];
    var w2CellX = w2List[wingX];
    var l1CellX = l1List[wingX];
    var l2CellX = l2List[wingX];
    var linkNumCSet = wNumList[wingX];
    var wingNumCSet = this.CandidateCells[w1CellX] & ~linkNumCSet;

    var candidates = this.NewCandidates();
    var status = this.NewStatus();

    // mark cells
    var cellStatus = '1:C' + this.CSetToString( wingNumCSet, 'm' ) + this.CSetToString( linkNumCSet, 'g' );
    status[w1CellX] = cellStatus;
    cellStatus = '2:c' + this.CSetToString( linkNumCSet, 'b' );
    status[l1CellX] = cellStatus;
    cellStatus = '3:c' + this.CSetToString( linkNumCSet, 'g' );
    status[l2CellX] = cellStatus;
    cellStatus = '4:C' + this.CSetToString( linkNumCSet, 'b' ) + this.CSetToString( wingNumCSet, 'm' );
    status[w2CellX] = cellStatus;

    // find candidates that can be removed
    var delCandList = []; // [ <cellX>, <delCandCSet>, ... ]

    for (var cellX = 0; cellX < 81; cellX++) {
      var cand = this.CandidateCells[cellX];
      if ((cand & wingNumCSet) && (status[cellX] == '') && this.IsSameHouse(cellX,w1CellX) && this.IsSameHouse(cellX,w2CellX)) {
        delCandList.push( cellX );
        delCandList.push( wingNumCSet );
      }
    }

    if (delCandList.length > 0) {
      var infos = { Name: 'W-Wing', Level: 0, Help: 'W-Wing' };
      if (this.CreateMoves( delCandList, candidates, status, infos, wingNumCSet )) {
        return true;
      }
    }

  } // next wingX

  return false;
}

//---------------------------------------------------------

CSudoku.prototype.FindXYWing = function( ) {
  return this.FindXYChainsOrRemotePairs( false, 3, 3 );
}

CSudoku.prototype.FindXYChains = function( ) {
  return this.FindXYChainsOrRemotePairs( false, 4 );
}

CSudoku.prototype.FindRemotePairs = function( ) {
  return this.FindXYChainsOrRemotePairs( true, 4 );
}

CSudoku.prototype.FindXYChainsOrRemotePairs = function( bRemotePairs, aMinSize, aMaxSize ) {

  aMinSize = aMinSize || 3;
  aMaxSize = aMaxSize || 0;

  this.CreateXYChainList( aMaxSize );

  var maxChainSize = this.GetMaxXYChainSize();
  if (aMaxSize > 0 && aMaxSize < maxChainSize) maxChainSize = aMaxSize;

  for (var chainSize = aMinSize; chainSize <= maxChainSize; chainSize++) {
    var chainListSize = this.XYChainList.length;
    for (var chainListX = 0; chainListX < chainListSize; chainListX++) {
      var chainListElement = this.XYChainList[chainListX];
      var chain = chainListElement.XYChain;
      var isLoop = chainListElement.IsLoop;
      var isRemotePairs = chainListElement.IsRemotePairs;
      if (chain.length == chainSize && isRemotePairs == bRemotePairs) {

        var candidates = this.NewCandidates();
        var status = this.NewStatus();

        // mark chain to exclude marked cells from following search of delete candidates
        for (var chainX = 0; chainX < chainSize; chainX++) {
          var cellX = chain[chainX].CellX;
          var cellStatus = (chainX+1) + ':';
          if (isRemotePairs) {
            var firstOrLast = (chainX == 0 || chainX == chainSize-1);
            var color = ((chainX % 2) == 0) ? 'g' : 'b';
            if (firstOrLast) color = color.toUpperCase();
            cellStatus += color;
          } else {
            var firstOrLast = (!isLoop && (chainX == 0 || chainX == chainSize-1));
            if (firstOrLast) {
              cellStatus += 'C';
            } else {
              cellStatus += 'c';
            }
          }
          var nextColor = 'g';
          var prevColor = 'b';
          if (!isLoop && !isRemotePairs) {
            if (chainX == 0) prevColor = 'm';
            if (chainX == chainSize-1) nextColor = 'm';
          }
          var linkNumBit = chain[chainX].LinkNum;
          var otherNumBit = candidates[cellX] & ~linkNumBit;
          cellStatus += this.CSetToString( linkNumBit, prevColor ) + this.CSetToString( otherNumBit, nextColor );
          status[cellX] = cellStatus;
        }

        var delCandList = []; // [ <cellX>, <delCandCSet>, ... ]
        var hintCSet = 0;

        if (isRemotePairs) {

          // check for cells that see opposit colored cells of chain and remove both candidates
          var pairNums = candidates[chain[0].CellX];
          hintCSet = pairNums;
          for (var cellX = 0; cellX < 81; cellX++) {
            if ((status[cellX] == '') && (candidates[cellX] & pairNums)) {
              var seesEven = false;
              var seesOdd  = false;
              for (var chainX = 0; chainX < chainSize && !(seesEven && seesOdd); chainX++) {
                if (this.IsSameHouse( cellX, chain[chainX].CellX )) {
                  seesEven = seesEven || ((chainX % 2) == 0);
                  seesOdd  = seesOdd  || ((chainX % 2) == 1);
                }
              }
              if (seesEven && seesOdd) {
                var delCandCSet = candidates[cellX] & pairNums;
                delCandList.push( cellX );
                delCandList.push( delCandCSet );
              }
            }
          }

        } else if (isLoop) {

          // check for cells that see any pairs of chain with common candidate
          for (var cellX = 0; cellX < 81; cellX++) {
            if (status[cellX] == '') {
              var cand = candidates[cellX];
              var seesLinkNumCSet = 0;
              var seesOtherNumCSet = 0;
              for (var chainX = 0; chainX < chainSize; chainX++) {
                var node = chain[chainX];
                var nodeCellX = node.CellX;
                if (this.IsSameHouse( cellX, nodeCellX )) {
                  var linkNumBit = node.LinkNum;
                  var otherNumBit = candidates[nodeCellX] & ~linkNumBit;
                  seesLinkNumCSet |= linkNumBit;
                  seesOtherNumCSet |= otherNumBit;
                }
              }
              var delCandCSet = cand & seesLinkNumCSet & seesOtherNumCSet;
              if (delCandCSet) {
                delCandList.push( cellX );
                delCandList.push( delCandCSet );
              }
            }
          }

        } else {

          // check for cells that see start and end of chain with common candidate
          var firstCellX = chain[0].CellX;
          var lastCellX = chain[chainSize-1].CellX;
          var linkNumBit = chain[0].LinkNum;
          hintCSet = linkNumBit;

          for (var cellX = 0; cellX < 81; cellX++) {
            if ((status[cellX] == '') && (candidates[cellX] & linkNumBit)) {
              if (this.IsSameHouse( cellX, firstCellX ) && this.IsSameHouse( cellX, lastCellX )) {
                delCandList.push( cellX );
                delCandList.push( linkNumBit );
              }
            }
          }

        }

        // mark cells and remove candiates
        if (delCandList.length > 0) {
          var info = this.GetXYChainInfos( chain, isLoop, isRemotePairs );
          if (this.CreateMoves( delCandList, candidates, status, info, hintCSet )) {
            return true;
          }
        }

      } // end if (chain.length == chainSize && isRemotePairs == bRemotePairs)
    } // next chainListX
  } // next chainSize

  return false;
}

CSudoku.prototype.GetXYChainInfos = function( aXYChain, bIsLoop, bIsRemotePairs ) {
  // returns { Name, Help, Level }
  var name = '';
  var help = '';
  var level = (aXYChain.length - 4) * 2 + 1;
  if (bIsRemotePairs) {
    level = aXYChain.length - 4;
    name = 'Remote Pairs ' + aXYChain.length;
    help = 'Remote Pairs';
  } else if (bIsLoop) {
    name = 'XY-Chain Loop ' + aXYChain.length;
    help = 'XY-Chain Loop';
    level++;
  } else {
    if (aXYChain.length == 3) {
      name = 'XY-Wing';
      help = 'XY-Wing';
      level = 0;
    } else {
      var last = aXYChain.length-1;
      var nums = 0;
      var endNums = this.CandidateCells[aXYChain[0].CellX] | this.CandidateCells[aXYChain[last].CellX];
      for (var chainX = 1; chainX < last; chainX++) nums |= this.CandidateCells[aXYChain[chainX].CellX];
      if (this.CSetBitCount( nums ) == 2 && this.CSetBitCount( endNums ) == 3) {
        name = 'XY-Wing Chain ' + aXYChain.length;
        help = 'XY-Wing Chain';
      } else {
        name = 'XY-Chain ' + aXYChain.length;
        help = 'XY-Chain';
      }
    }
  }
  if (level < 1) level = 1;
  if (level > 9) level = 9;
  return { Name: name, Help: help, Level: level };
}

CSudoku.prototype.CreateXYChainList = function( aSizeLimit ) {
  if (aSizeLimit == 0) aSizeLimit = 81;
  if (this.XYChainListValidSize >= aSizeLimit) return;

  var oldMaxXYChainSize = this.MaxXYChainSize;
  var oldMaxRemotePairsSize = this.MaxRemotePairsSize;
  if (aSizeLimit < this.MaxXYChainSize) this.MaxXYChainSize = aSizeLimit;
  if (aSizeLimit < this.MaxRemotePairsSize) this.MaxRemotePairsSize = aSizeLimit;

  var chain = [];
  while (!this.RunTimeExceedet() && this.NextXYChain( chain )) {

    this.AddXYChainToList( chain );

  }

  this.MaxXYChainSize = oldMaxXYChainSize;
  this.MaxRemotePairsSize = oldMaxRemotePairsSize;

  this.XYChainListValidSize = aSizeLimit;
}

CSudoku.prototype.IsXYChainRemotePairs = function( aXYChain ) {
  return (aXYChain.length >= 4 && this.CSetBitCount( aXYChain[aXYChain.length-1].CellMask ) == 2);
}

CSudoku.prototype.AddXYChainToList = function( aXYChain ) {
  // Lists of length 2 or less are rejected.
  // Lists with all elements in same house are rejected.
  // If a Chain with same Endpoints is already in List, the shorter one replaces the longer one.
  // Note: aXChain is copied!
  // XYChainList: array of { IsLoop: <bool>, IsRemotePairs: <bool>, XYChain: array of ChainNode: { CellX, LinkNum, Dir, DirX } }

  var chainSize = aXYChain.length;
  if (chainSize <= 2) return false;
  if (this.AllXYChainNodesInSameHouse( aXYChain )) return false;

  var startCellX = aXYChain[0].CellX;
  var endCellX = aXYChain[chainSize-1].CellX;

  // check for remote pairs
  var isRemotePairs = this.IsXYChainRemotePairs( aXYChain );
  if (isRemotePairs && chainSize <= 3) return false;

  var isLoop = this.IsSameHouse( startCellX, endCellX );
  // reject remote pairs with start and end cell in same house, because they are handled with simpler methods
  if (isRemotePairs && isLoop) return false;

  if (isLoop || isRemotePairs) {

    // find loop or remote pairs chain with same size and same cells
    this.SetCoverCells( aXYChain );
    var xyChainListSize = this.XYChainList.length;
    for (var chainListX = 0; chainListX < xyChainListSize; chainListX++) {
      var leChain = this.XYChainList[chainListX].XYChain;
      var leIsLoop = this.XYChainList[chainListX].IsLoop;
      var leIsRemotePairs = this.XYChainList[chainListX].IsRemotePairs;
      var leChainSize = leChain.length;
      if ((leIsLoop || leIsRemotePairs) && (chainSize == leChainSize) && this.IsSameCoverCells(leChain) ) {
        // discard chain
        return false;
      }
    }

    // if no such chain loop is in this.XYChainList, append a copy of aXYChain
    this.XYChainList.push( { IsLoop: isLoop, IsRemotePairs: isRemotePairs, XYChain: this.CopyChain(aXYChain) } );
    return true;

  } else {

    // find not looped chain with same endpoints
    var xyChainListSize = this.XYChainList.length;
    for (var chainListX = 0; chainListX < xyChainListSize; chainListX++) {
      var leChain = this.XYChainList[chainListX].XYChain;
      var leIsLoop = this.XYChainList[chainListX].IsLoop;
      var leStartCellX = leChain[0].CellX;
      var leEndCellX = leChain[leChain.length-1].CellX;
      if (!leIsLoop && (startCellX == leStartCellX && endCellX == leEndCellX) || (startCellX == leEndCellX && endCellX == leStartCellX)) {

        // chain with same endpoints found at chainListX. Check which is shorter
        if (aXYChain.length < leChain.length) {
          // replace chain at chainListX with a copy of aXYChain
          this.XYChainList[chainListX] = { IsLoop: isLoop, IsRemotePairs: isRemotePairs, XYChain: this.CopyChain( aXYChain ) };
          return true;
        }
        // else discard aXYChain
        return false;
      }
    }

    // if no similar chain is in this.XYChainList, append a copy of aXYChain
    this.XYChainList.push( { IsLoop: false, IsRemotePairs: isRemotePairs, XYChain: this.CopyChain(aXYChain) } );
    return true;

  }
}

CSudoku.prototype.GetMaxXYChainSize = function() {
  var chainListSize = this.XYChainList.length;
  var maxSize = 0;
  for (var chainListX = 0; chainListX < chainListSize; chainListX++) {
    var chainSize = this.XYChainList[chainListX].XYChain.length;
    if (chainSize > maxSize) maxSize = chainSize;
  }
  return maxSize;
}

CSudoku.prototype.AllXYChainNodesInSameHouse = function( aXYChain ) {
  // require aXYChain.length > 2
  var node = aXYChain[aXYChain.length-1];
  return (this.CSetBitCount(node.RowMask) == 1 || this.CSetBitCount(node.ColMask) == 1 || this.CSetBitCount(node.BoxMask) == 1);
}

CSudoku.prototype.NextXYChain = function( aXYChain ) {
  // aXYChain: [ Node ]
  // Node: {
  //   CellX: 0-80
  //   Dir: 0=Row, 1=Col, 2=Box
  //   DirX: 0-8
  //   LinkNum: CSet
  // }

  if (aXYChain.length == 0) {
    if (!this.FirstXYChainNode( aXYChain )) return false;
  }

  while (aXYChain.length > 0) {

    if (this.NextXYChainEndNode( aXYChain )) return true;

    var chainSize = aXYChain.length;
    if (chainSize > 1) {

      var firstNode = aXYChain[0];
      if (firstNode.LoopNode == aXYChain[chainSize-1]) firstNode.LoopNode = null;
      aXYChain.length--;

    } else {

      if (!this.FirstXYChainNode( aXYChain )) {
        aXYChain.length = 0;
        return false;
      }

    }
  }

  return false;
}

CSudoku.prototype.FirstXYChainNode = function( aXYChain ) {

  if (aXYChain.length == 0) {
    // find first cell
    for (var cellX = 0; cellX < 81; cellX++) {
      if (this.CSetBitCount( this.CandidateCells[cellX] ) == 2) {
        // init chain, try first candidate
        var linkNum = this.NextCSet( this.CandidateCells[cellX], 0 );
        var node = this.NewChainNode( cellX, linkNum );
        this.MakeChainNodeMasks( node );
        node.LoopNode = null;
        aXYChain.push( node );
        return true;
      }
    }
    return false;
  }

  var node = aXYChain[0];
  // try next candidate in same cell
  var cellX = node.CellX;
  var linkNum = this.NextCSet( this.CandidateCells[cellX], node.LinkNum );
  if (linkNum) {
    node.Dir = 0;
    node.DirX = -1;
    node.LinkNum = linkNum;
    node.LoopNode = null;
    return true;
  }

  // find next cell
  for (var cellX = node.CellX+1; cellX < 81; cellX++) {
    if (this.CSetBitCount( this.CandidateCells[cellX] ) == 2) {
      var linkNum = this.NextCSet( this.CandidateCells[cellX], 0 );
      node.CellX = cellX;
      node.LinkNum = linkNum;
      node.Dir = 0;
      node.DirX = -1;
      node.LoopNode = null;
      this.MakeChainNodeMasks( node );
      return true;
    }
  }

  // no more cell with candidate pair found
  aXYChain = [];
  return false;
}

CSudoku.prototype.NextXYChainEndNode = function( aXYChain ) {

  if (this.IsXYChainRemotePairs( aXYChain )) {
    if (aXYChain.length >= this.MaxRemotePairsSize) return false;
  } else {
    if (aXYChain.length >= this.MaxXYChainSize) return false;
  }

  var firstNode = aXYChain[0];
  var firstCellX = firstNode.CellX;
  var firstCand = this.CandidateCells[firstCellX];
  var firstLinkNum = firstNode.LinkNum;

  while (this.NextXYChainNode( aXYChain )) {

    var chainSize = aXYChain.length;
    var lastNode = aXYChain[chainSize-1];
    var lastCellX = lastNode.CellX;
    var lastCand = this.CandidateCells[lastCellX];
    var lastFreeNum = lastCand & ~lastNode.LinkNum;

    if (chainSize > 2 && lastFreeNum == firstLinkNum ) {

      var isLoop = this.IsSameHouse( firstCellX, lastCellX );
      if (isLoop) {

        // Only return smallest loop starting from firstNode. Other loops are found from other start cells on.
        if (!firstNode.LoopNode) {
          firstNode.LoopNode = lastNode;
          return true;
        }
        // else continue searching next node

      } else {

        return true;

      }
    }

    if (this.IsXYChainRemotePairs( aXYChain )) {
      if (aXYChain.length >= this.MaxRemotePairsSize) return false;
    } else {
      if (aXYChain.length >= this.MaxXYChainSize) return false;
    }

  }

  return false;
}

CSudoku.prototype.NextXYChainNode = function( aXYChain ) {

  var currNodeX = aXYChain.length - 1;
  if (currNodeX < 0) return false;

  var currNode = aXYChain[currNodeX];
  var currCellX = currNode.CellX;
  var currRowX = this.RowXofCellX( currCellX );
  var currColX = this.ColXofCellX( currCellX );
  var currCand = this.CandidateCells[ currCellX ];
  var currFreeNum = currCand & ~currNode.LinkNum;

  for (var dir = currNode.Dir; dir <= 2; dir++) {
    var dirHouse = this.Houses[dir];
    var houseX = this.HouseXofCellX[dir].call( this, currNode.CellX );
    var house = dirHouse[houseX];

    for (var dirX = currNode.DirX + 1; dirX < 9; dirX++) {

      var cellX = house[dirX];
      var newCand = this.CandidateCells[cellX];
      if (newCand && cellX != currCellX) {
        // skip box cells in the same row or col as current node, because they are already processed in dir = 0 or 1!
        var skip = (dir == 2 && (currRowX == this.RowXofCellX( cellX ) || currColX == this.ColXofCellX( cellX )));

        if (!skip && (this.CSetBitCount(newCand) == 2) && (newCand & currFreeNum)) {
          if (!this.IsCellInChain( aXYChain, cellX, false )) {
            var newNode = this.NewChainNode( cellX, currFreeNum );
            this.MakeChainNodeMasks( newNode, currNode );
            currNode.Dir = dir;
            currNode.DirX = dirX;
            aXYChain.push( newNode );
            return true;
          }
        }
      }
    }
    currNode.DirX = -1;
  }
  return false;
}

//---------------------------------------------------------

CSudoku.prototype.HasDummyCells = function() {
  for (var i = 0; i < 81; i++) {
    if (!this.CandidateCells[i] && this.SolvedCells[i] == 0) return true
  }
  return false;
}

CSudoku.prototype.IsValid = function() {
  // überprüft auf doppelte Zahlen in Zeile, Kolonne und Box
  // markiert Fehler in StatusCells mit 'Multi'
  var ok = true;
  for (var cellX = 0; cellX < 81; cellX++) {
    if (this.SolvedCells[cellX] > 0) {
      // test in row
      var house = this.Rows[this.RowXofCellX( cellX )];
      if (this.MarkDoublettesInHouse( house, cellX )) { ok = false; }
      // test in col
      house = this.Cols[this.ColXofCellX( cellX )];
      if (this.MarkDoublettesInHouse( house, cellX )) { ok = false; }
      // test in boxes
      house = this.Boxes[this.BoxXofCellX( cellX )];
      if (this.MarkDoublettesInHouse( house, cellX )) { ok = false; }
    }
  }
  return ok;
}

CSudoku.prototype.MarkDoublettesInHouse = function( aHouse, aRefCellX ) {
  // aHouse as this.Rows[i], Cols[i], Boxes[i]
  // returns true if doublettes are found
  var found = false;
  var num = this.SolvedCells[aRefCellX];
  for (var houseX = 0; houseX < 9; houseX++) {
    if (aHouse[houseX] != aRefCellX && this.SolvedCells[aHouse[houseX]] == num) {
      this.StatusCells[aRefCellX] = 'Multi';
      this.StatusCells[aHouse[houseX]] = 'Multi';
      found = true;
    }
  }
  return found;
}

CSudoku.prototype.HasUniqueCells = function() {
  for (var i = 0; i < 81; i++) {
    if (this.CSetBitCount(this.CandidateCells[i]) == 1) return true
  }
  return false;
}

CSudoku.prototype.UniqueCellCount = function() {
  var n = 0;
  for (var i = 0; i < 81; i++) {
    if (this.CSetBitCount(this.CandidateCells[i]) == 1) n++;
  }
  return n;
}

CSudoku.prototype.GetFilledCellCount = function() {
  var n = 0;
  for (var i = 0; i < 81; i++) { if (this.SolvedCells[i] > 0) n++; }
  return n;
}

CSudoku.prototype.NSolvedCellsInHouse = function( aHouse ) {
  var n = 0;
  for (var houseX = 0; houseX < 9; houseX++) {
    if (this.SolvedCells[aHouse[houseX]] > 0) n++;
  }
  return n;
}

CSudoku.prototype.NCandidatesInHouse = function( aNumCSet, aHouse ) {
  var count = 0;
  for (var cellX = 0; cellX < 9; cellX++) {
    if (this.CandidateCells[aHouse[cellX]] & aNumCSet) count++;
  }
  return count;
}

CSudoku.prototype.IsSameHouse = function( aCellX1, aCellX2 ) {
  return (this.IsSameRow(aCellX1,aCellX2) || this.IsSameCol(aCellX1,aCellX2) || this.IsSameBox(aCellX1,aCellX2));
}

CSudoku.prototype.IsSameRow = function( aCellX1, aCellX2 ) {
  return (this.RowXofCellX( aCellX1 ) == this.RowXofCellX( aCellX2 ));
}

CSudoku.prototype.IsSameCol = function( aCellX1, aCellX2 ) {
  return (this.ColXofCellX( aCellX1 ) == this.ColXofCellX( aCellX2 ));
}

CSudoku.prototype.IsSameBox = function( aCellX1, aCellX2 ) {
  return (this.BoxXofCellX( aCellX1 ) == this.BoxXofCellX( aCellX2 ));
}

CSudoku.prototype.GetCandidatesInHouse = function( aCandidateCSet, aHouse ) {
  // returns array of cellX of found candidates
  var c = [];
  for (var houseX = 0; houseX < 9; houseX++) {
    var cellX = aHouse[houseX];
    if (this.CandidateCells[cellX] & aCandidateCSet) c.push( cellX );
  }
  return c;
}

CSudoku.prototype.GetStrongLinkHouse = function( aNumCSet, aCell1X, aCell2X ) {
  // returns House in which the cells aCell1X and aCell2X lie and containes aNumCSet as the only common candidate
  // returns null if aCell1X and aCell2X are not in same house.
  // return only the first house (order row, col, box) when cells lie in more than one house
  if (this.IsSameRow( aCell1X, aCell2X )) {
    var rowX = this.RowXofCellX( aCell1X );
    var house = this.Rows[rowX];
    if (this.NCandidatesInHouse( aNumCSet, house ) == 2) {
      return house;
    }
  }
  if (this.IsSameCol( aCell1X, aCell2X )) {
    var colX = this.ColXofCellX( aCell1X );
    var house = this.Cols[colX];
    if (this.NCandidatesInHouse( aNumCSet, house ) == 2) {
      return house;
    }
  }
  if (this.IsSameBox( aCell1X, aCell2X )) {
    var boxX = this.BoxXofCellX( aCell1X );
    var house = this.Boxes[boxX];
    if (this.NCandidatesInHouse( aNumCSet, house ) == 2) {
      return house;
    }
  }
  return null;
}

CSudoku.prototype.SolveStep = function() {
  if (!this.HasMoves()) return;

  this.AppUpdateBegin();
  this.SaveState();
  var currMove = this.CurrMove;
  var cellX = this.Moves[currMove].SolutionX;
  var thisLevel = this.Moves[currMove].Level;
  if (thisLevel > this.MaxLevel) {
    this.MaxLevel = thisLevel;
    this.MaxLevelName = this.Moves[currMove].Name;
    this.MaxLevelHelp = this.Moves[currMove].HelpPage;
  }

  if (cellX >= 0) {
    // copy current solution from move list to sudoku
    this.SolvedCells[cellX] = this.CSetBitToNum( this.Moves[currMove].Candidates[cellX] );
    this.CopyCells( this.Moves[currMove].Candidates, this.CandidateCells );
    this.CandidateCells[cellX] = 0;
    this.RemoveCandidatesForCell( cellX );
    this.ClearCells( this.StatusCells, '' );
    this.AppRequestHints();
    this.AppUpdateEnd();
    return;
  }
  // no solution: copy candidates from current move to sudoku
  this.CopyCells( this.Moves[currMove].Candidates, this.CandidateCells );
  this.ClearCells( this.StatusCells, '' );
  this.AppRequestHints();
  this.AppUpdateEnd();
}

CSudoku.prototype.Solve = function( bStopAfterTrivialMoves ) {
  this.AppUpdateBegin();
  if (!xDef(bStopAfterTrivialMoves)) bStopAfterTrivialMoves = false;
  this.StoreSudoku( true );
  var stat = this.GetStatus();
  if (stat == 'no solution') {
    this.OutMethods( '<b>Raten:</b> ...' );
  }
  if (this.SearchingSolutions || stat == 'no solution') {
    this.FindSolutions();
  } else {
    this.StopSolving = false;
    this.StopAfterTrivialMoves = bStopAfterTrivialMoves;
    this.DoSolve();
  }
  this.AppUpdateEnd();
}

CSudoku.prototype.DoSolve = function() {
  // toggle auto SolveStep
  var me = this;

  function NextStep() {
    if (me.Timer) clearTimeout( me.Timer );
    me.Timer = null;
    if (!me.Running) {
      return;
    }
    me.AppUpdateBegin();
    var status = me.GetStatus();
    if (status == '' && !me.StopSolving) {
      me.SolveStep();
      me.Timer = setTimeout( NextStep, me.SlowMotion ? 1000 : 1 );
    } else {
      me.Running = false;
      me.StopSolving = false;
      me.StopAfterTrivialMoves = false;
      if (status == '') {
        me.AppRequestHints();
      }
    }
    me.AppUpdateEnd();
  }

  if (this.Running) {
    clearTimeout( this.Timer );
    this.Timer = null;
    this.Running = false;
    if (this.GetStatus() == '') {
      this.AppRequestHints();
    }
  } else {
    this.SaveState();
    this.Running = true;
    NextStep();
  }
}

CSudoku.prototype.DisplayLastSolution = function() {
  if (this.SolutionCount == 0) return;
  this.CopyCells( this.LastSolution, this.SolvedCells );
  this.CopyCells( this.LastStartCells, this.StartCells );
  this.ClearCells( this.CandidateCells, 0 );
  this.ClearCells( this.StatusCells, '' );
  this.ClearMoves();
}

CSudoku.prototype.FindSolutionsNextStep = function() {
  var sStatus, oldStatus
  if (this.AllSolutionsFound) return false;
  sStatus = this.GetStatus();
  oldStatus = this.PrevStatus;
  this.PrevStatus = sStatus;
  if (!this.SearchingSolutions) {
    if (sStatus == 'solved' || sStatus == 'invalid') {
      this.AllSolutionsFound = true;
      this.DisplayLastSolution();
      return false;
    }
    if (sStatus != 'no solution') {
      this.SolveStep();
      return true;
    }
    // assert sStatus == 'no solution'
  }
  this.SearchingSolutions = true;
  if (sStatus == 'solved' || sStatus == 'invalid') {
    if (sStatus == 'solved' && oldStatus != sStatus) this.AddSolution();
    if (sStatus == 'solved' && this.StopOnSolutions && !this.Stopped) {
      this.Stopped = true;
      return false;
    }
    this.Stopped = false;
    if (this.FindNextTry()) return true;
    this.AllSolutionsFound = true;
    this.DisplayLastSolution();
    this.SearchingSolutions = false;
    return false;
  }
  if (sStatus == 'no solution') {
    if (this.InitTry()) return true;
    this.AllSolutionsFound = true;
    this.DisplayLastSolution();
    this.SearchingSolutions = false;
    return false;
  }
  this.SolveStep();
  return true;
}

CSudoku.prototype.AddSolution = function() {
  this.CopyCells( this.SolvedCells, this.LastSolution );
  this.CopyCells( this.StartCells, this.LastStartCells );
  this.SolutionCount++;
}

CSudoku.prototype.InitTry = function() {
  for (var bitCount = 2; bitCount <= 9; bitCount++) {
    for (var cellX = 0; cellX < 81; cellX++) {
      var cand = this.CandidateCells[cellX];
      if (cand && (this.CSetBitCount(cand) == bitCount)) {
        // save state
        this.PushTryState();
        // init try loop vars
        this.TryBitCount = bitCount;
        this.TryCellX = cellX;
        this.TryBitI = 0;
        // try first num
        for (var num = 1; num <= 9; num++) {
          if (this.CSetContainsNum( cand, num )) {
            this.SolvedCells[cellX] = num;
            this.CandidateCells[cellX] = 0;
            this.StartCells[cellX] = 2;
            this.CandidatesAreValid = false
            this.AppRequestHints();
            return true;
          }
        }
      }
    }
  }
  return false;
}

CSudoku.prototype.FindNextTry = function() {
  if (this.StackPtr == 0) return false;
  do {
    var sp = this.StackPtr-1;
    this.CopyCells( this.SolvedCellsStack[sp], this.SolvedCells );
    this.CopyCells( this.CandidateCellsStack[sp], this.CandidateCells );
    this.CopyCells( this.StartCellsStack[sp], this.StartCells );
    this.CandidatesAreValid = false
    // try next
    var bitCount = this.TryBitCount;
    var cellX = this.TryCellX;
    var bitI = this.TryBitI + 1;
    if (bitI < bitCount) {
      var cand = this.CandidateCells[cellX];
      var i = bitI;
      for (var num = 1; num <= 9; num++) {
        if (this.CSetContainsNum( cand, num )) {
          if (i == 0) {
            this.TryBitI = bitI;
            // try this num
            this.SolvedCells[cellX] = num;
            this.CandidateCells[cellX] = 0;
            this.CandidatesAreValid = false
            this.StartCells[cellX] = 2;
            this.AppRequestHints();
            return true;
          } else {
            i--;
          }
        }
      }
    }
    this.PopTryState();
  } while (this.StackPtr > 0);
  this.AppRequestHints();
  return false;
}

CSudoku.prototype.PushTryState = function() {
  var sp = this.StackPtr;
  this.SolvedCellsStack[sp] = this.NewCells( 0 );
  this.CandidateCellsStack[sp] = this.NewCells( 0 );
  this.StartCellsStack[sp] = this.NewCells( 0 );
  this.CopyCells( this.SolvedCells, this.SolvedCellsStack[sp] );
  this.CopyCells( this.CandidateCells, this.CandidateCellsStack[sp] );
  this.CopyCells( this.StartCells, this.StartCellsStack[sp] );
  var s = new Array( 3 );
  s[0] = this.TryBitCount;
  s[1] = this.TryCellX;
  s[2] = this.TryBitI;
  this.StatusCellsStack[sp] = s;
  this.StackPtr++;
}

CSudoku.prototype.PopTryState = function() {
  if (this.StackPtr <= 0) return;
  this.StackPtr--;
  var sp = this.StackPtr;
  this.CopyCells( this.SolvedCellsStack[sp], this.SolvedCells );
  this.CopyCells( this.CandidateCellsStack[sp], this.CandidateCells );
  this.CopyCells( this.StartCellsStack[sp], this.StartCells );
  this.CandidatesAreValid = false
  var s = this.StatusCellsStack[sp];
  this.TryBitCount = s[0];
  this.TryCellX = s[1];
  this.TryBitI = s[2];
}

CSudoku.prototype.TryStateToString = function() {
  var s = '';
  for (var sp = 1; sp < this.StackPtr; sp++) {
    s += this.SolvedCells[this.StatusCellsStack[sp][1]].toString();
  }
  s += this.SolvedCells[this.TryCellX].toString();
  return s;
}

CSudoku.prototype.FindSolutions = function() {
  // toggle auto SolveStep
  var me = this;

  function NextStep() {
    if (me.Timer) clearTimeout(me.Timer);
    me.Timer = null;
    if (!me.Running) {
      return;
    }
    me.AppUpdateBegin();
    if (me.FindSolutionsNextStep()) {
      me.Timer = setTimeout( NextStep, me.SlowMotion ? 1000 : 1 );
    } else {
      me.Running = false;
    }
    me.AppUpdateEnd();
  }

  if (this.Running) {
    clearTimeout( this.Timer );
    this.Timer = null;
    this.Running = false;
  } else {
    if (!this.SearchingSolutions) this.SaveState();
    this.Running = true;
    NextStep();
  }
}

CSudoku.prototype.GetStatus = function() {
  // returns: '', 'empty', 'few', 'solved', 'no solution', 'invalid'
  // Damit diese Funktion funktioniert, muss zuvor Analyze() ausgeführt worden sein.
  if (!this.IsValid() || this.HasDummyCells()) return 'invalid';
  var filled = this.GetFilledCellCount();
  if (filled == 0) return 'empty';
  if (filled < this.MinFill) return 'few';
  if (filled == 81) return 'solved';
  if (!this.HasMoves()) return 'no solution';
  return '';
}

CSudoku.prototype.IsSolved = function() {
  return (this.GetFilledCellCount() == 81);
}

function CSudokuShowFieldInfos( aName, aCellX, aInputId ) {
  var sdk = CSudokuFindInstance(aName);
  if (sdk) sdk.ShowFieldInfos( aCellX );
  var inp = xGet( aInputId );
  if (inp) inp.select();
}

function CSudokuHandleInput( aName, aCellX ) {
  var sdk = CSudokuFindInstance(aName);
  if (sdk) {
    sdk.HandleFieldInput( aCellX );
    sdk.ShowFieldInfos( aCellX );
  }
}

function InitSudokuHandlers() {
  oBody = xGet('body');
  // install key handler on document
  var oHtmlList = xGetByTag("html");
  if (oHtmlList.length > 0) {xAddEvent(oHtmlList[0],'keydown',CSudokuHandleOnKeyDown); }
}

xOnLoad(InitSudokuHandlers);

Weitere Infos zur Seite
Erzeugt Mittwoch, 2. März 2016
von wabis
Zum Seitenanfang
Geändert Mittwoch, 2. März 2016
von wabis