// 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 += ' ⇒ '; 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 += " " } if (j < 2) { s += " "; } 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 += " " } if (j < 2) { s += " "; } 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+')"> </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) + ' ⇒ <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) + ' ⇒ <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 += ' ⇒ ' + hints[hintX]; if (hintX < lastHintX) text += ' ⇒ <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 += ' ⇒ ' + 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);