How to use sudoku._rand_range method in Cypress

Best JavaScript code snippet using cypress

generator.js

Source:generator.js

...107            108            // If an assignment of a random chioce causes a contradictoin, give109            // up and try again110            var rand_candidate_idx = 111                    sudoku._rand_range(candidates[square].length);112            var rand_candidate = candidates[square][rand_candidate_idx];113            if(!sudoku._assign(candidates, square, rand_candidate)){114                break;115            }116            117            // Make a list of all single candidates118            var single_candidates = [];119            for(var si in SQUARES){120                var square = SQUARES[si];121                122                if(candidates[square].length == 1){123                    single_candidates.push(candidates[square]);124                }125            }126            127            // If we have at least difficulty, and the unique candidate count is128            // at least 8, return the puzzle!129            if(single_candidates.length >= difficulty && 130                    sudoku._strip_dups(single_candidates).length >= 8){131                var board = "";132                var givens_idxs = [];133                for(var i in SQUARES){134                    var square = SQUARES[i];135                    if(candidates[square].length == 1){136                        board += candidates[square];137                        givens_idxs.push(i);138                    } else {139                        board += sudoku.BLANK_CHAR;140                    }141                }142                143                // If we have more than `difficulty` givens, remove some random144                // givens until we're down to exactly `difficulty`145                var nr_givens = givens_idxs.length;146                if(nr_givens > difficulty){147                    givens_idxs = sudoku._shuffle(givens_idxs);148                    for(var i = 0; i < nr_givens - difficulty; ++i){149                        var target = parseInt(givens_idxs[i]);150                        board = board.substr(0, target) + sudoku.BLANK_CHAR + 151                            board.substr(target + 1);152                    }153                }154                155                // Double check board is solvable156                // TODO: Make a standalone board checker. Solve is expensive.157                if(sudoku.solve(board)){158                    return board;159                }160            }161        }162        163        // Give up and try a new puzzle164        return sudoku.generate(difficulty);165    };166    // Solve167    // -------------------------------------------------------------------------168    sudoku.solve = function(board, reverse){169        /* Solve a sudoku puzzle given a sudoku `board`, i.e., an 81-character 170        string of sudoku.DIGITS, 1-9, and spaces identified by '.', representing the171        squares. There must be a minimum of 17 givens. If the given board has no172        solutions, return false.173        174        Optionally set `reverse` to solve "backwards", i.e., rotate through the175        possibilities in reverse. Useful for checking if there is more than one176        solution.177        */178        179        // Assure a valid board180        var report = sudoku.validate_board(board);181        if(report !== true){182            throw report;183        }184        185        // Check number of givens is at least MIN_GIVENS186        var nr_givens = 0;187        for(var i in board){188            if(board[i] !== sudoku.BLANK_CHAR && sudoku._in(board[i], sudoku.DIGITS)){189                ++nr_givens;190            }191        }192        if(nr_givens < MIN_GIVENS){193            throw "Too few givens. Minimum givens is " + MIN_GIVENS;194        }195        // Default reverse to false196        reverse = reverse || false;197        var candidates = sudoku._get_candidates_map(board);198        var result = sudoku._search(candidates, reverse);199        200        if(result){201            var solution = "";202            for(var square in result){203                solution += result[square];204            }205            return solution;206        }207        return false;208    };209    sudoku.get_candidates = function(board){210        /* Return all possible candidatees for each square as a grid of 211        candidates, returnning `false` if a contradiction is encountered.212        213        Really just a wrapper for sudoku._get_candidates_map for programmer214        consumption.215        */216        217        // Assure a valid board218        var report = sudoku.validate_board(board);219        if(report !== true){220            throw report;221        }222        223        // Get a candidates map224        var candidates_map = sudoku._get_candidates_map(board);225        226        // If there's an error, return false227        if(!candidates_map){228            return false;229        }230        231        // Transform candidates map into grid232        var rows = [];233        var cur_row = [];234        var i = 0;235        for(var square in candidates_map){236            var candidates = candidates_map[square];237            cur_row.push(candidates);238            if(i % 9 == 8){239                rows.push(cur_row);240                cur_row = [];241            }242            ++i;243        }244        return rows;245    }246    sudoku._get_candidates_map = function(board){247        /* Get all possible candidates for each square as a map in the form248        {square: sudoku.DIGITS} using recursive constraint propagation. Return `false` 249        if a contradiction is encountered250        */251        252        // Assure a valid board253        var report = sudoku.validate_board(board);254        if(report !== true){255            throw report;256        }257        258        var candidate_map = {};259        var squares_values_map = sudoku._get_square_vals_map(board);260        261        // Start by assigning every digit as a candidate to every square262        for(var si in SQUARES){263            candidate_map[SQUARES[si]] = sudoku.DIGITS;264        }265        266        // For each non-blank square, assign its value in the candidate map and267        // propigate.268        for(var square in squares_values_map){269            var val = squares_values_map[square];270            271            if(sudoku._in(val, sudoku.DIGITS)){272                var new_candidates = sudoku._assign(candidate_map, square, val);273                274                // Fail if we can't assign val to square275                if(!new_candidates){276                    return false;277                }278            }279        }280        281        return candidate_map;282    };283    sudoku._search = function(candidates, reverse){284        /* Given a map of squares -> candiates, using depth-first search, 285        recursively try all possible values until a solution is found, or false286        if no solution exists. 287        */288        289        // Return if error in previous iteration290        if(!candidates){291            return false;292        }293        294        // Default reverse to false295        reverse = reverse || false;296        297        // If only one candidate for every square, we've a solved puzzle!298        // Return the candidates map.299        var max_nr_candidates = 0;300        var max_candidates_square = null;301        for(var si in SQUARES){302            var square = SQUARES[si];303            304            var nr_candidates = candidates[square].length;305                306            if(nr_candidates > max_nr_candidates){307                max_nr_candidates = nr_candidates;308                max_candidates_square = square;309            }310        }311        if(max_nr_candidates === 1){312            return candidates;313        }314        315        // Choose the blank square with the fewest possibilities > 1316        var min_nr_candidates = 10;317        var min_candidates_square = null;318        for(si in SQUARES){319            var square = SQUARES[si];320            321            var nr_candidates = candidates[square].length;322            323            if(nr_candidates < min_nr_candidates && nr_candidates > 1){324                min_nr_candidates = nr_candidates;325                min_candidates_square = square;326            }327        }328        329        // Recursively search through each of the candidates of the square 330        // starting with the one with fewest candidates.331        332        // Rotate through the candidates forwards333        var min_candidates = candidates[min_candidates_square];334        if(!reverse){335            for(var vi in min_candidates){336                var val = min_candidates[vi];337                338                // TODO: Implement a non-rediculous deep copy function339                var candidates_copy = JSON.parse(JSON.stringify(candidates));340                var candidates_next = sudoku._search(341                    sudoku._assign(candidates_copy, min_candidates_square, val)342                );343                344                if(candidates_next){345                    return candidates_next;346                }347            }348            349        // Rotate through the candidates backwards350        } else {351            for(var vi = min_candidates.length - 1; vi >= 0; --vi){352                var val = min_candidates[vi];353                354                // TODO: Implement a non-rediculous deep copy function355                var candidates_copy = JSON.parse(JSON.stringify(candidates));356                var candidates_next = sudoku._search(357                    sudoku._assign(candidates_copy, min_candidates_square, val), 358                    reverse359                );360                361                if(candidates_next){362                    return candidates_next;363                }364            }365        }366        367        // If we get through all combinations of the square with the fewest368        // candidates without finding an answer, there isn't one. Return false.369        return false;370    };371    sudoku._assign = function(candidates, square, val){372        /* Eliminate all values, *except* for `val`, from `candidates` at 373        `square` (candidates[square]), and propagate. Return the candidates map374        when finished. If a contradiciton is found, return false.375        376        WARNING: This will modify the contents of `candidates` directly.377        */378        // Grab a list of canidates without 'val'379        var other_vals = candidates[square].replace(val, "");380        // Loop through all other values and eliminate them from the candidates 381        // at the current square, and propigate. If at any point we get a 382        // contradiction, return false.383        for(var ovi in other_vals){384            var other_val = other_vals[ovi];385            var candidates_next =386                sudoku._eliminate(candidates, square, other_val);387            if(!candidates_next){388                //console.log("Contradiction found by _eliminate.");389                return false;390            }391        }392        return candidates;393    };394    sudoku._eliminate = function(candidates, square, val){395        /* Eliminate `val` from `candidates` at `square`, (candidates[square]),396        and propagate when values or places <= 2. Return updated candidates,397        unless a contradiction is detected, in which case, return false.398        399        WARNING: This will modify the contents of `candidates` directly.400        */401        // If `val` has already been eliminated from candidates[square], return402        // with candidates.403        if(!sudoku._in(val, candidates[square])){404            return candidates;405        }406        // Remove `val` from candidates[square]407        candidates[square] = candidates[square].replace(val, '');408           409        // If the square has only candidate left, eliminate that value from its 410        // peers411        var nr_candidates = candidates[square].length;412        if(nr_candidates === 1){413            var target_val = candidates[square];414            415            for(var pi in SQUARE_PEERS_MAP[square]){416                var peer = SQUARE_PEERS_MAP[square][pi];417                418                var candidates_new = 419                        sudoku._eliminate(candidates, peer, target_val);420                        421                if(!candidates_new){422                    return false;423                }424            }425        426        // Otherwise, if the square has no candidates, we have a contradiction.427        // Return false.428        } if(nr_candidates === 0){429            return false;430        }431        432        // If a unit is reduced to only one place for a value, then assign it433        for(var ui in SQUARE_UNITS_MAP[square]){434            var unit = SQUARE_UNITS_MAP[square][ui];435            436            var val_places = [];437            for(var si in unit){438                var unit_square = unit[si];439                if(sudoku._in(val, candidates[unit_square])){440                    val_places.push(unit_square);441                }442            }443            444            // If there's no place for this value, we have a contradition!445            // return false446            if(val_places.length === 0){447                return false;448                449            // Otherwise the value can only be in one place. Assign it there.450            } else if(val_places.length === 1){451                var candidates_new = 452                    sudoku._assign(candidates, val_places[0], val);453                454                if(!candidates_new){455                    return false;456                }457            }458        }459        460        return candidates;461    };462    463    // Square relationships464    // -------------------------------------------------------------------------465    // Squares, and their relationships with values, units, and peers.466    467    sudoku._get_square_vals_map = function(board){468        /* Return a map of squares -> values469        */470        var squares_vals_map = {};471        472        // Make sure `board` is a string of length 81473        if(board.length != SQUARES.length){474            throw "Board/squares length mismatch.";475            476        } else {477            for(var i in SQUARES){478                squares_vals_map[SQUARES[i]] = board[i];479            }480        }481        482        return squares_vals_map;483    };484    sudoku._get_square_units_map = function(squares, units){485        /* Return a map of `squares` and their associated units (row, col, box)486        */487        var square_unit_map = {};488        // For every square...489        for(var si in squares){490            var cur_square = squares[si];491            // Maintain a list of the current square's units492            var cur_square_units = [];493            // Look through the units, and see if the current square is in it,494            // and if so, add it to the list of of the square's units.495            for(var ui in units){496                var cur_unit = units[ui];497                if(cur_unit.indexOf(cur_square) !== -1){498                    cur_square_units.push(cur_unit);499                }500            }501            // Save the current square and its units to the map502            square_unit_map[cur_square] = cur_square_units;503        }504        return square_unit_map;505    };506    sudoku._get_square_peers_map = function(squares, units_map){507        /* Return a map of `squares` and their associated peers, i.e., a set of508        other squares in the square's unit.509        */510        var square_peers_map = {};511        // For every square...512        for(var si in squares){513            var cur_square = squares[si];514            var cur_square_units = units_map[cur_square];515            // Maintain list of the current square's peers516            var cur_square_peers = [];517            // Look through the current square's units map...518            for(var sui in cur_square_units){519                var cur_unit = cur_square_units[sui];520                for(var ui in cur_unit){521                    var cur_unit_square = cur_unit[ui];522                    if(cur_square_peers.indexOf(cur_unit_square) === -1 && 523                            cur_unit_square !== cur_square){524                        cur_square_peers.push(cur_unit_square);525                    }526                }527            }528            529            // Save the current square an its associated peers to the map530            square_peers_map[cur_square] = cur_square_peers;531        }532        return square_peers_map;533    };534    535    sudoku._get_all_units = function(rows, cols){536        /* Return a list of all units (rows, cols, boxes)537        */538        var units = [];539        // Rows540        for(var ri in rows){541            units.push(sudoku._cross(rows[ri], cols));542        }543        // Columns544        for(var ci in cols){545           units.push(sudoku._cross(rows, cols[ci]));546        }547        // Boxes548        var row_squares = ["ABC", "DEF", "GHI"];549        var col_squares = ["123", "456", "789"];550        for(var rsi in row_squares){551            for(var csi in col_squares){552                units.push(sudoku._cross(row_squares[rsi], col_squares[csi]));553            }554        }555        return units;556    };557    558    // Conversions559    // -------------------------------------------------------------------------560    sudoku.board_string_to_grid = function(board_string){561        /* Convert a board string to a two-dimensional array562        */563        var rows = [];564        var cur_row = [];565        for(var i in board_string){566            cur_row.push(board_string[i]);567            if(i % 9 == 8){568                rows.push(cur_row);569                cur_row = [];570            }571        }572        return rows;573    };574    575    sudoku.board_grid_to_string = function(board_grid){576        /* Convert a board grid to a string577        */578        var board_string = "";579        for(var r = 0; r < 9; ++r){580            for(var c = 0; c < 9; ++c){581                board_string += board_grid[r][c];582            }   583        }584        return board_string;585    };586    587    // Utility588    // -------------------------------------------------------------------------589    sudoku.print_board = function(board){590        /* Print a sudoku `board` to the console.591        */592        593        // Assure a valid board594        var report = sudoku.validate_board(board);595        if(report !== true){596            throw report;597        }598        599        var V_PADDING = " ";  // Insert after each square600        var H_PADDING = '\n'; // Insert after each row601        602        var V_BOX_PADDING = "  "; // Box vertical padding603        var H_BOX_PADDING = '\n'; // Box horizontal padding604        var display_string = "";605        606        for(var i in board){607            var square = board[i];608            609            // Add the square and some padding610            display_string += square + V_PADDING;611            612            // Vertical edge of a box, insert v. box padding613            if(i % 3 === 2){614                display_string += V_BOX_PADDING;615            }616            617            // End of a line, insert horiz. padding618            if(i % 9 === 8){619                display_string += H_PADDING;620            }621            622            // Horizontal edge of a box, insert h. box padding623            if(i % 27 === 26){624                display_string += H_BOX_PADDING;625            }626        }627        console.log(display_string);628    };629    sudoku.validate_board = function(board){630        /* Return if the given `board` is valid or not. If it's valid, return631        true. If it's not, return a string of the reason why it's not.632        */633        634        // Check for empty board635        if(!board){636            return "Empty board";637        }638        639        // Invalid board length640        if(board.length !== NR_SQUARES){641            return "Invalid board size. Board must be exactly " + NR_SQUARES +642                    " squares.";643        }644        645        // Check for invalid characters646        for(var i in board){647            if(!sudoku._in(board[i], sudoku.DIGITS) && board[i] !== sudoku.BLANK_CHAR){648                return "Invalid board character encountered at index " + i + 649                        ": " + board[i];650            }651        }652        653        // Otherwise, we're good. Return true.654        return true;655    };656    sudoku._cross = function(a, b){657        /* Cross product of all elements in `a` and `b`, e.g.,658        sudoku._cross("abc", "123") ->659        ["a1", "a2", "a3", "b1", "b2", "b3", "c1", "c2", "c3"]660        */661        var result = [];662        for(var ai in a){663            for(var bi in b){664                result.push(a[ai] + b[bi]);665            }666        }667        return result;668    };669    670    sudoku._in = function(v, seq){671        /* Return if a value `v` is in sequence `seq`.672        */673        return seq.indexOf(v) !== -1;674    };675    676    sudoku._first_true = function(seq){677        /* Return the first element in `seq` that is true. If no element is678        true, return false.679        */680        for(var i in seq){681            if(seq[i]){682                return seq[i];683            }684        }685        return false;686    };687    sudoku._shuffle = function(seq){688        /* Return a shuffled version of `seq`689        */690        691        // Create an array of the same size as `seq` filled with false692        var shuffled = [];693        for(var i = 0; i < seq.length; ++i){694            shuffled.push(false);695        }696        697        for(var i in seq){698            var ti = sudoku._rand_range(seq.length);699            700            while(shuffled[ti]){701                ti = (ti + 1) > (seq.length - 1) ? 0 : (ti + 1);702            }703            704            shuffled[ti] = seq[i];705        }706        707        return shuffled;708    };709    sudoku._rand_range = function(max, min){710        /* Get a random integer in the range of `min` to `max` (non inclusive).711        If `min` not defined, default to 0. If `max` not defined, throw an 712        error....

ds.js

Source:ds.js

...112113            // If an assignment of a random chioce causes a contradictoin, give114            // up and try again115            var rand_candidate_idx =116                    sudoku._rand_range(candidates[square].length);117            var rand_candidate = candidates[square][rand_candidate_idx];118            if(!sudoku._assign(candidates, square, rand_candidate)){119                break;120            }121122            // Make a list of all single candidates123            var single_candidates = [];124            for(var si in SQUARES){125                var square = SQUARES[si];126127                if(candidates[square].length == 1){128                    single_candidates.push(candidates[square]);129                }130            }131132            // If we have at least difficulty, and the unique candidate count is133            // at least 8, return the puzzle!134            if(single_candidates.length >= difficulty &&135                    sudoku._strip_dups(single_candidates).length >= 8){136                var board = "";137                var givens_idxs = [];138                for(var i in SQUARES){139                    var square = SQUARES[i];140                    if(candidates[square].length == 1){141                        board += candidates[square];142                        givens_idxs.push(i);143                    } else {144                        board += sudoku.BLANK_CHAR;145                    }146                }147148                // If we have more than `difficulty` givens, remove some random149                // givens until we're down to exactly `difficulty`150                var nr_givens = givens_idxs.length;151                if(nr_givens > difficulty){152                    givens_idxs = sudoku._shuffle(givens_idxs);153                    for(var i = 0; i < nr_givens - difficulty; ++i){154                        var target = parseInt(givens_idxs[i]);155                        board = board.substr(0, target) + sudoku.BLANK_CHAR +156                            board.substr(target + 1);157                    }158                }159160                // Double check board is solvable161                // TODO: Make a standalone board checker. Solve is expensive.162                if(sudoku.solve(board)){163                    return board;164                }165            }166        }167168        // Give up and try a new puzzle169        return sudoku.generate(difficulty);170    };171172    // Solve173    // -------------------------------------------------------------------------174    sudoku.solve = function(board, reverse){175        /* Solve a sudoku puzzle given a sudoku `board`, i.e., an 81-character176        string of sudoku.DIGITS, 1-9, and spaces identified by '.', representing the177        squares. There must be a minimum of 17 givens. If the given board has no178        solutions, return false.179180        Optionally set `reverse` to solve "backwards", i.e., rotate through the181        possibilities in reverse. Useful for checking if there is more than one182        solution.183        */184185        // Assure a valid board186        var report = sudoku.validate_board(board);187        if(report !== true){188            throw report;189        }190191        // Check number of givens is at least MIN_GIVENS192        var nr_givens = 0;193        for(var i in board){194            if(board[i] !== sudoku.BLANK_CHAR && sudoku._in(board[i], sudoku.DIGITS)){195                ++nr_givens;196            }197        }198        if(nr_givens < MIN_GIVENS){199            throw "Too few givens. Minimum givens is " + MIN_GIVENS;200        }201202        // Default reverse to false203        reverse = reverse || false;204205        var candidates = sudoku._get_candidates_map(board);206        var result = sudoku._search(candidates, reverse);207208        if(result){209            var solution = "";210            for(var square in result){211                solution += result[square];212            }213            return solution;214        }215        return false;216    };217218    sudoku.get_candidates = function(board){219        /* Return all possible candidatees for each square as a grid of220        candidates, returnning `false` if a contradiction is encountered.221222        Really just a wrapper for sudoku._get_candidates_map for programmer223        consumption.224        */225226        // Assure a valid board227        var report = sudoku.validate_board(board);228        if(report !== true){229            throw report;230        }231232        // Get a candidates map233        var candidates_map = sudoku._get_candidates_map(board);234235        // If there's an error, return false236        if(!candidates_map){237            return false;238        }239240        // Transform candidates map into grid241        var rows = [];242        var cur_row = [];243        var i = 0;244        for(var square in candidates_map){245            var candidates = candidates_map[square];246            cur_row.push(candidates);247            if(i % 9 == 8){248                rows.push(cur_row);249                cur_row = [];250            }251            ++i;252        }253        return rows;254    }255256    sudoku._get_candidates_map = function(board){257        /* Get all possible candidates for each square as a map in the form258        {square: sudoku.DIGITS} using recursive constraint propagation. Return `false`259        if a contradiction is encountered260        */261262        // Assure a valid board263        var report = sudoku.validate_board(board);264        if(report !== true){265            throw report;266        }267268        var candidate_map = {};269        var squares_values_map = sudoku._get_square_vals_map(board);270271        // Start by assigning every digit as a candidate to every square272        for(var si in SQUARES){273            candidate_map[SQUARES[si]] = sudoku.DIGITS;274        }275276        // For each non-blank square, assign its value in the candidate map and277        // propigate.278        for(var square in squares_values_map){279            var val = squares_values_map[square];280281            if(sudoku._in(val, sudoku.DIGITS)){282                var new_candidates = sudoku._assign(candidate_map, square, val);283284                // Fail if we can't assign val to square285                if(!new_candidates){286                    return false;287                }288            }289        }290291        return candidate_map;292    };293294    sudoku._search = function(candidates, reverse){295        /* Given a map of squares -> candiates, using depth-first search,296        recursively try all possible values until a solution is found, or false297        if no solution exists.298        */299300        // Return if error in previous iteration301        if(!candidates){302            return false;303        }304305        // Default reverse to false306        reverse = reverse || false;307308        // If only one candidate for every square, we've a solved puzzle!309        // Return the candidates map.310        var max_nr_candidates = 0;311        var max_candidates_square = null;312        for(var si in SQUARES){313            var square = SQUARES[si];314315            var nr_candidates = candidates[square].length;316317            if(nr_candidates > max_nr_candidates){318                max_nr_candidates = nr_candidates;319                max_candidates_square = square;320            }321        }322        if(max_nr_candidates === 1){323            return candidates;324        }325326        // Choose the blank square with the fewest possibilities > 1327        var min_nr_candidates = 10;328        var min_candidates_square = null;329        for(si in SQUARES){330            var square = SQUARES[si];331332            var nr_candidates = candidates[square].length;333334            if(nr_candidates < min_nr_candidates && nr_candidates > 1){335                min_nr_candidates = nr_candidates;336                min_candidates_square = square;337            }338        }339340        // Recursively search through each of the candidates of the square341        // starting with the one with fewest candidates.342343        // Rotate through the candidates forwards344        var min_candidates = candidates[min_candidates_square];345        if(!reverse){346            for(var vi in min_candidates){347                var val = min_candidates[vi];348349                // TODO: Implement a non-rediculous deep copy function350                var candidates_copy = JSON.parse(JSON.stringify(candidates));351                var candidates_next = sudoku._search(352                    sudoku._assign(candidates_copy, min_candidates_square, val)353                );354355                if(candidates_next){356                    return candidates_next;357                }358            }359360        // Rotate through the candidates backwards361        } else {362            for(var vi = min_candidates.length - 1; vi >= 0; --vi){363                var val = min_candidates[vi];364365                // TODO: Implement a non-rediculous deep copy function366                var candidates_copy = JSON.parse(JSON.stringify(candidates));367                var candidates_next = sudoku._search(368                    sudoku._assign(candidates_copy, min_candidates_square, val),369                    reverse370                );371372                if(candidates_next){373                    return candidates_next;374                }375            }376        }377378        // If we get through all combinations of the square with the fewest379        // candidates without finding an answer, there isn't one. Return false.380        return false;381    };382383    sudoku._assign = function(candidates, square, val){384        /* Eliminate all values, *except* for `val`, from `candidates` at385        `square` (candidates[square]), and propagate. Return the candidates map386        when finished. If a contradiciton is found, return false.387388        WARNING: This will modify the contents of `candidates` directly.389        */390391        // Grab a list of canidates without 'val'392        var other_vals = candidates[square].replace(val, "");393394        // Loop through all other values and eliminate them from the candidates395        // at the current square, and propigate. If at any point we get a396        // contradiction, return false.397        for(var ovi in other_vals){398            var other_val = other_vals[ovi];399400            var candidates_next =401                sudoku._eliminate(candidates, square, other_val);402403            if(!candidates_next){404                //console.log("Contradiction found by _eliminate.");405                return false;406            }407        }408409        return candidates;410    };411412    sudoku._eliminate = function(candidates, square, val){413        /* Eliminate `val` from `candidates` at `square`, (candidates[square]),414        and propagate when values or places <= 2. Return updated candidates,415        unless a contradiction is detected, in which case, return false.416417        WARNING: This will modify the contents of `candidates` directly.418        */419420        // If `val` has already been eliminated from candidates[square], return421        // with candidates.422        if(!sudoku._in(val, candidates[square])){423            return candidates;424        }425426        // Remove `val` from candidates[square]427        candidates[square] = candidates[square].replace(val, '');428429        // If the square has only candidate left, eliminate that value from its430        // peers431        var nr_candidates = candidates[square].length;432        if(nr_candidates === 1){433            var target_val = candidates[square];434435            for(var pi in SQUARE_PEERS_MAP[square]){436                var peer = SQUARE_PEERS_MAP[square][pi];437438                var candidates_new =439                        sudoku._eliminate(candidates, peer, target_val);440441                if(!candidates_new){442                    return false;443                }444            }445446        // Otherwise, if the square has no candidates, we have a contradiction.447        // Return false.448        } if(nr_candidates === 0){449            return false;450        }451452        // If a unit is reduced to only one place for a value, then assign it453        for(var ui in SQUARE_UNITS_MAP[square]){454            var unit = SQUARE_UNITS_MAP[square][ui];455456            var val_places = [];457            for(var si in unit){458                var unit_square = unit[si];459                if(sudoku._in(val, candidates[unit_square])){460                    val_places.push(unit_square);461                }462            }463464            // If there's no place for this value, we have a contradition!465            // return false466            if(val_places.length === 0){467                return false;468469            // Otherwise the value can only be in one place. Assign it there.470            } else if(val_places.length === 1){471                var candidates_new =472                    sudoku._assign(candidates, val_places[0], val);473474                if(!candidates_new){475                    return false;476                }477            }478        }479480        return candidates;481    };482483484    // Square relationships485    // -------------------------------------------------------------------------486    // Squares, and their relationships with values, units, and peers.487488    sudoku._get_square_vals_map = function(board){489        /* Return a map of squares -> values490        */491        var squares_vals_map = {};492493        // Make sure `board` is a string of length 81494        if(board.length != SQUARES.length){495            throw "Board/squares length mismatch.";496497        } else {498            for(var i in SQUARES){499                squares_vals_map[SQUARES[i]] = board[i];500            }501        }502503        return squares_vals_map;504    };505506    sudoku._get_square_units_map = function(squares, units){507        /* Return a map of `squares` and their associated units (row, col, box)508        */509        var square_unit_map = {};510511        // For every square...512        for(var si in squares){513            var cur_square = squares[si];514515            // Maintain a list of the current square's units516            var cur_square_units = [];517518            // Look through the units, and see if the current square is in it,519            // and if so, add it to the list of of the square's units.520            for(var ui in units){521                var cur_unit = units[ui];522523                if(cur_unit.indexOf(cur_square) !== -1){524                    cur_square_units.push(cur_unit);525                }526            }527528            // Save the current square and its units to the map529            square_unit_map[cur_square] = cur_square_units;530        }531532        return square_unit_map;533    };534535    sudoku._get_square_peers_map = function(squares, units_map){536        /* Return a map of `squares` and their associated peers, i.e., a set of537        other squares in the square's unit.538        */539        var square_peers_map = {};540541        // For every square...542        for(var si in squares){543            var cur_square = squares[si];544            var cur_square_units = units_map[cur_square];545546            // Maintain list of the current square's peers547            var cur_square_peers = [];548549            // Look through the current square's units map...550            for(var sui in cur_square_units){551                var cur_unit = cur_square_units[sui];552553                for(var ui in cur_unit){554                    var cur_unit_square = cur_unit[ui];555556                    if(cur_square_peers.indexOf(cur_unit_square) === -1 &&557                            cur_unit_square !== cur_square){558                        cur_square_peers.push(cur_unit_square);559                    }560                }561            }562563            // Save the current square an its associated peers to the map564            square_peers_map[cur_square] = cur_square_peers;565        }566567        return square_peers_map;568    };569570    sudoku._get_all_units = function(rows, cols){571        /* Return a list of all units (rows, cols, boxes)572        */573        var units = [];574575        // Rows576        for(var ri in rows){577            units.push(sudoku._cross(rows[ri], cols));578        }579580        // Columns581        for(var ci in cols){582           units.push(sudoku._cross(rows, cols[ci]));583        }584585        // Boxes586        var row_squares = ["ABC", "DEF", "GHI"];587        var col_squares = ["123", "456", "789"];588        for(var rsi in row_squares){589            for(var csi in col_squares){590                units.push(sudoku._cross(row_squares[rsi], col_squares[csi]));591            }592        }593594        return units;595    };596597598    // Conversions599    // -------------------------------------------------------------------------600    sudoku.board_string_to_grid = function(board_string){601        /* Convert a board string to a two-dimensional array602        */603        var rows = [];604        var cur_row = [];605        for(var i in board_string){606            cur_row.push(board_string[i]);607            if(i % 9 == 8){608                rows.push(cur_row);609                cur_row = [];610            }611        }612        return rows;613    };614615    sudoku.board_grid_to_string = function(board_grid){616        /* Convert a board grid to a string617        */618        var board_string = "";619        for(var r = 0; r < 9; ++r){620            for(var c = 0; c < 9; ++c){621                board_string += board_grid[r][c];622            }623        }624        return board_string;625    };626627628    // Utility629    // -------------------------------------------------------------------------630631    sudoku.print_board = function(board){632        /* Print a sudoku `board` to the console.633        */634635        // Assure a valid board636        var report = sudoku.validate_board(board);637        if(report !== true){638            throw report;639        }640641        var V_PADDING = " ";  // Insert after each square642        var H_PADDING = '\n'; // Insert after each row643644        var V_BOX_PADDING = "  "; // Box vertical padding645        var H_BOX_PADDING = '\n'; // Box horizontal padding646647        var display_string = "";648649        for(var i in board){650            var square = board[i];651652            // Add the square and some padding653            display_string += square + V_PADDING;654655            // Vertical edge of a box, insert v. box padding656            if(i % 3 === 2){657                display_string += V_BOX_PADDING;658            }659660            // End of a line, insert horiz. padding661            if(i % 9 === 8){662                display_string += H_PADDING;663            }664665            // Horizontal edge of a box, insert h. box padding666            if(i % 27 === 26){667                display_string += H_BOX_PADDING;668            }669        }670671        console.log(display_string);672    };673674    sudoku.validate_board = function(board){675        /* Return if the given `board` is valid or not. If it's valid, return676        true. If it's not, return a string of the reason why it's not.677        */678679        // Check for empty board680        if(!board){681            return "Empty board";682        }683684        // Invalid board length685        if(board.length !== NR_SQUARES){686            return "Invalid board size. Board must be exactly " + NR_SQUARES +687                    " squares.";688        }689690        // Check for invalid characters691        for(var i in board){692            if(!sudoku._in(board[i], sudoku.DIGITS) && board[i] !== sudoku.BLANK_CHAR){693                return "Invalid board character encountered at index " + i +694                        ": " + board[i];695            }696        }697698        // Otherwise, we're good. Return true.699        return true;700    };701702    sudoku._cross = function(a, b){703        /* Cross product of all elements in `a` and `b`, e.g.,704        sudoku._cross("abc", "123") ->705        ["a1", "a2", "a3", "b1", "b2", "b3", "c1", "c2", "c3"]706        */707        var result = [];708        for(var ai in a){709            for(var bi in b){710                result.push(a[ai] + b[bi]);711            }712        }713        return result;714    };715716    sudoku._in = function(v, seq){717        /* Return if a value `v` is in sequence `seq`.718        */719        return seq.indexOf(v) !== -1;720    };721722    sudoku._first_true = function(seq){723        /* Return the first element in `seq` that is true. If no element is724        true, return false.725        */726        for(var i in seq){727            if(seq[i]){728                return seq[i];729            }730        }731        return false;732    };733734    sudoku._shuffle = function(seq){735        /* Return a shuffled version of `seq`736        */737738        // Create an array of the same size as `seq` filled with false739        var shuffled = [];740        for(var i = 0; i < seq.length; ++i){741            shuffled.push(false);742        }743744        for(var i in seq){745            var ti = sudoku._rand_range(seq.length);746747            while(shuffled[ti]){748                ti = (ti + 1) > (seq.length - 1) ? 0 : (ti + 1);749            }750751            shuffled[ti] = seq[i];752        }753754        return shuffled;755    };756757    sudoku._rand_range = function(max, min){758        /* Get a random integer in the range of `min` to `max` (non inclusive).759        If `min` not defined, default to 0. If `max` not defined, throw an
...

Sudoku-lib.js

Source:Sudoku-lib.js

...97    for (var si in shuffled_squares) {98      var square = shuffled_squares[si];99      // If an assignment of a random chioce causes a contradictoin, give100      // up and try again101      var rand_candidate_idx = sudoku._rand_range(candidates[square].length);102      var rand_candidate = candidates[square][rand_candidate_idx];103      if (!sudoku._assign(candidates, square, rand_candidate)) {104        break;105      }106      // Make a list of all single candidates107      var single_candidates = [];108      for (var si in SQUARES) {109        var square = SQUARES[si];110        if (candidates[square].length === 1) {111          single_candidates.push(candidates[square]);112        }113      }114      // If we have at least difficulty, and the unique candidate count is115      // at least 8, return the puzzle!116      if (117        single_candidates.length >= difficulty &&118        sudoku._strip_dups(single_candidates).length >= 8119      ) {120        var board = "";121        var givens_idxs = [];122        for (var i in SQUARES) {123          var square = SQUARES[i];124          if (candidates[square].length === 1) {125            board += candidates[square];126            givens_idxs.push(i);127          } else {128            board += sudoku.BLANK_CHAR;129          }130        }131        // If we have more than `difficulty` givens, remove some random132        // givens until we're down to exactly `difficulty`133        var nr_givens = givens_idxs.length;134        if (nr_givens > difficulty) {135          givens_idxs = sudoku._shuffle(givens_idxs);136          for (var i = 0; i < nr_givens - difficulty; ++i) {137            var target = parseInt(givens_idxs[i]);138            board =139              board.substr(0, target) +140              sudoku.BLANK_CHAR +141              board.substr(target + 1);142          }143        }144        // Double check board is solvable145        // TODO: Make a standalone board checker. Solve is expensive.146        if (sudoku.solve(board)) {147          return board;148        }149      }150    }151    // Give up and try a new puzzle152    return sudoku.generate(difficulty);153  };154  // Solve155  // -------------------------------------------------------------------------156  sudoku.solve = function (board, reverse) {157    /* Solve a sudoku puzzle given a sudoku `board`, i.e., an 81-character 158        string of sudoku.DIGITS, 1-9, and spaces identified by '.', representing the159        squares. There must be a minimum of 17 givens. If the given board has no160        solutions, return false.161        162        Optionally set `reverse` to solve "backwards", i.e., rotate through the163        possibilities in reverse. Useful for checking if there is more than one164        solution.165        */166    // Assure a valid board167    var report = sudoku.validate_board(board);168    if (report !== true) {169      throw report;170    }171    // Check number of givens is at least MIN_GIVENS172    var nr_givens = 0;173    for (var i in board) {174      if (175        board[i] !== sudoku.BLANK_CHAR &&176        sudoku._in(board[i], sudoku.DIGITS)177      ) {178        ++nr_givens;179      }180    }181    if (nr_givens < MIN_GIVENS) {182      throw "Too few givens. Minimum givens is " + MIN_GIVENS;183    }184    // Default reverse to false185    reverse = reverse || false;186    var candidates = sudoku._get_candidates_map(board);187    var result = sudoku._search(candidates, reverse);188    if (result) {189      var solution = "";190      for (var square in result) {191        solution += result[square];192      }193      return solution;194    }195    return false;196  };197  sudoku.dlx_solve = function (board) {198    var tmp = solveString(board);199    if (tmp.length !== 0) {200      var result = tmp[0];201      var solGrid = [];202      for (var i = 0; i < 9; i++) {203        solGrid.push(["", "", "", "", "", "", "", "", ""]);204      }205      for (var r = 0; r < 81; ++r) {206        solGrid[result[r].row][result[r].col] = result[r].number;207      }208      return solGrid;209    }210  };211  sudoku.dlx_solve_str = function (board) {212    var result = sudoku.dlx_solve(board);213    if (result !== undefined) {214      return sudoku.board_grid_to_string(result);215    }216  };217  sudoku.check_uniqueness = function (board) {};218  sudoku.get_candidates = function (board) {219    /* Return all possible candidatees for each square as a grid of 220        candidates, returnning `false` if a contradiction is encountered.221        222        Really just a wrapper for sudoku._get_candidates_map for programmer223        consumption.224        */225    // Assure a valid board226    var report = sudoku.validate_board(board);227    if (report !== true) {228      throw report;229    }230    // Get a candidates map231    var candidates_map = sudoku._get_candidates_map(board);232    // If there's an error, return false233    if (!candidates_map) {234      return false;235    }236    // Transform candidates map into grid237    var rows = [];238    var cur_row = [];239    var i = 0;240    for (var square in candidates_map) {241      var candidates = candidates_map[square];242      cur_row.push(candidates);243      if (i % 9 === 8) {244        rows.push(cur_row);245        cur_row = [];246      }247      ++i;248    }249    return rows;250  };251  sudoku._get_candidates_map = function (board) {252    /* Get all possible candidates for each square as a map in the form253        {square: sudoku.DIGITS} using recursive constraint propagation. Return `false` 254        if a contradiction is encountered255        */256    // Assure a valid board257    var report = sudoku.validate_board(board);258    if (report !== true) {259      throw report;260    }261    var candidate_map = {};262    var squares_values_map = sudoku._get_square_vals_map(board);263    // Start by assigning every digit as a candidate to every square264    for (var si in SQUARES) {265      candidate_map[SQUARES[si]] = sudoku.DIGITS;266    }267    // For each non-blank square, assign its value in the candidate map and268    // propigate.269    for (var square in squares_values_map) {270      var val = squares_values_map[square];271      if (sudoku._in(val, sudoku.DIGITS)) {272        var new_candidates = sudoku._assign(candidate_map, square, val);273        // Fail if we can't assign val to square274        if (!new_candidates) {275          return false;276        }277      }278    }279    return candidate_map;280  };281  sudoku._search = function (candidates, reverse) {282    /* Given a map of squares -> candiates, using depth-first search, 283        recursively try all possible values until a solution is found, or false284        if no solution exists. 285        */286    // Return if error in previous iteration287    if (!candidates) {288      return false;289    }290    // Default reverse to false291    reverse = reverse || false;292    // If only one candidate for every square, we've a solved puzzle!293    // Return the candidates map.294    var max_nr_candidates = 0;295    var max_candidates_square = null;296    for (var si in SQUARES) {297      var square = SQUARES[si];298      var nr_candidates = candidates[square].length;299      if (nr_candidates > max_nr_candidates) {300        max_nr_candidates = nr_candidates;301        max_candidates_square = square;302      }303    }304    if (max_nr_candidates === 1) {305      return candidates;306    }307    // Choose the blank square with the fewest possibilities > 1308    var min_nr_candidates = 10;309    var min_candidates_square = null;310    for (si in SQUARES) {311      var square = SQUARES[si];312      var nr_candidates = candidates[square].length;313      if (nr_candidates < min_nr_candidates && nr_candidates > 1) {314        min_nr_candidates = nr_candidates;315        min_candidates_square = square;316      }317    }318    // Recursively search through each of the candidates of the square319    // starting with the one with fewest candidates.320    // Rotate through the candidates forwards321    var min_candidates = candidates[min_candidates_square];322    if (!reverse) {323      for (var vi in min_candidates) {324        var val = min_candidates[vi];325        // TODO: Implement a non-rediculous deep copy function326        var candidates_copy = JSON.parse(JSON.stringify(candidates));327        var candidates_next = sudoku._search(328          sudoku._assign(candidates_copy, min_candidates_square, val)329        );330        if (candidates_next) {331          return candidates_next;332        }333      }334      // Rotate through the candidates backwards335    } else {336      for (var vi = min_candidates.length - 1; vi >= 0; --vi) {337        var val = min_candidates[vi];338        // TODO: Implement a non-rediculous deep copy function339        var candidates_copy = JSON.parse(JSON.stringify(candidates));340        var candidates_next = sudoku._search(341          sudoku._assign(candidates_copy, min_candidates_square, val),342          reverse343        );344        if (candidates_next) {345          return candidates_next;346        }347      }348    }349    // If we get through all combinations of the square with the fewest350    // candidates without finding an answer, there isn't one. Return false.351    return false;352  };353  sudoku._assign = function (candidates, square, val) {354    /* Eliminate all values, *except* for `val`, from `candidates` at 355        `square` (candidates[square]), and propagate. Return the candidates map356        when finished. If a contradiciton is found, return false.357        358        WARNING: This will modify the contents of `candidates` directly.359        */360    // Grab a list of canidates without 'val'361    var other_vals = candidates[square].replace(val, "");362    // Loop through all other values and eliminate them from the candidates363    // at the current square, and propigate. If at any point we get a364    // contradiction, return false.365    for (var ovi in other_vals) {366      var other_val = other_vals[ovi];367      var candidates_next = sudoku._eliminate(candidates, square, other_val);368      if (!candidates_next) {369        //console.log("Contradiction found by _eliminate.");370        return false;371      }372    }373    return candidates;374  };375  sudoku._eliminate = function (candidates, square, val) {376    /* Eliminate `val` from `candidates` at `square`, (candidates[square]),377        and propagate when values or places <= 2. Return updated candidates,378        unless a contradiction is detected, in which case, return false.379        380        WARNING: This will modify the contents of `candidates` directly.381        */382    // If `val` has already been eliminated from candidates[square], return383    // with candidates.384    if (!sudoku._in(val, candidates[square])) {385      return candidates;386    }387    // Remove `val` from candidates[square]388    candidates[square] = candidates[square].replace(val, "");389    // If the square has only candidate left, eliminate that value from its390    // peers391    var nr_candidates = candidates[square].length;392    if (nr_candidates === 1) {393      var target_val = candidates[square];394      for (var pi in SQUARE_PEERS_MAP[square]) {395        var peer = SQUARE_PEERS_MAP[square][pi];396        var candidates_new = sudoku._eliminate(candidates, peer, target_val);397        if (!candidates_new) {398          return false;399        }400      }401      // Otherwise, if the square has no candidates, we have a contradiction.402      // Return false.403    }404    if (nr_candidates === 0) {405      return false;406    }407    // If a unit is reduced to only one place for a value, then assign it408    for (var ui in SQUARE_UNITS_MAP[square]) {409      var unit = SQUARE_UNITS_MAP[square][ui];410      var val_places = [];411      for (var si in unit) {412        var unit_square = unit[si];413        if (sudoku._in(val, candidates[unit_square])) {414          val_places.push(unit_square);415        }416      }417      // If there's no place for this value, we have a contradition!418      // return false419      if (val_places.length === 0) {420        return false;421        // Otherwise the value can only be in one place. Assign it there.422      } else if (val_places.length === 1) {423        var candidates_new = sudoku._assign(candidates, val_places[0], val);424        if (!candidates_new) {425          return false;426        }427      }428    }429    return candidates;430  };431  // Square relationships432  // -------------------------------------------------------------------------433  // Squares, and their relationships with values, units, and peers.434  sudoku._get_square_vals_map = function (board) {435    /* Return a map of squares -> values436     */437    var squares_vals_map = {};438    // Make sure `board` is a string of length 81439    if (board.length !== SQUARES.length) {440      throw "Board/squares length mismatch.";441    } else {442      for (var i in SQUARES) {443        squares_vals_map[SQUARES[i]] = board[i];444      }445    }446    return squares_vals_map;447  };448  sudoku._get_square_units_map = function (squares, units) {449    /* Return a map of `squares` and their associated units (row, col, box)450     */451    var square_unit_map = {};452    // For every square...453    for (var si in squares) {454      var cur_square = squares[si];455      // Maintain a list of the current square's units456      var cur_square_units = [];457      // Look through the units, and see if the current square is in it,458      // and if so, add it to the list of of the square's units.459      for (var ui in units) {460        var cur_unit = units[ui];461        if (cur_unit.indexOf(cur_square) !== -1) {462          cur_square_units.push(cur_unit);463        }464      }465      // Save the current square and its units to the map466      square_unit_map[cur_square] = cur_square_units;467    }468    return square_unit_map;469  };470  sudoku._get_square_peers_map = function (squares, units_map) {471    /* Return a map of `squares` and their associated peers, i.e., a set of472        other squares in the square's unit.473        */474    var square_peers_map = {};475    // For every square...476    for (var si in squares) {477      var cur_square = squares[si];478      var cur_square_units = units_map[cur_square];479      // Maintain list of the current square's peers480      var cur_square_peers = [];481      // Look through the current square's units map...482      for (var sui in cur_square_units) {483        var cur_unit = cur_square_units[sui];484        for (var ui in cur_unit) {485          var cur_unit_square = cur_unit[ui];486          if (487            cur_square_peers.indexOf(cur_unit_square) === -1 &&488            cur_unit_square !== cur_square489          ) {490            cur_square_peers.push(cur_unit_square);491          }492        }493      }494      // Save the current square an its associated peers to the map495      square_peers_map[cur_square] = cur_square_peers;496    }497    return square_peers_map;498  };499  sudoku._get_all_units = function (rows, cols) {500    /* Return a list of all units (rows, cols, boxes)501     */502    var units = [];503    // Rows504    for (var ri in rows) {505      units.push(sudoku._cross(rows[ri], cols));506    }507    // Columns508    for (var ci in cols) {509      units.push(sudoku._cross(rows, cols[ci]));510    }511    // Boxes512    var row_squares = ["ABC", "DEF", "GHI"];513    var col_squares = ["123", "456", "789"];514    for (var rsi in row_squares) {515      for (var csi in col_squares) {516        units.push(sudoku._cross(row_squares[rsi], col_squares[csi]));517      }518    }519    return units;520  };521  // Conversions522  // -------------------------------------------------------------------------523  sudoku.board_string_to_grid = function (board_string) {524    /* Convert a board string to a two-dimensional array525     */526    var rows = [];527    var cur_row = [];528    for (var i in board_string) {529      cur_row.push(board_string[i]);530      if (i % 9 === 8) {531        rows.push(cur_row);532        cur_row = [];533      }534    }535    return rows;536  };537  sudoku.board_grid_to_string = function (board_grid) {538    /* Convert a board grid to a string539     */540    var board_string = "";541    for (var r = 0; r < 9; ++r) {542      for (var c = 0; c < 9; ++c) {543        board_string += board_grid[r][c];544      }545    }546    return board_string;547  };548  // Utility549  // -------------------------------------------------------------------------550  sudoku.print_board = function (board) {551    /* Print a sudoku `board` to the console.552     */553    // Assure a valid board554    var report = sudoku.validate_board(board);555    if (report !== true) {556      throw report;557    }558    var V_PADDING = " "; // Insert after each square559    var H_PADDING = "\n"; // Insert after each row560    var V_BOX_PADDING = "  "; // Box vertical padding561    var H_BOX_PADDING = "\n"; // Box horizontal padding562    var display_string = "";563    for (var i in board) {564      var square = board[i];565      // Add the square and some padding566      display_string += square + V_PADDING;567      // Vertical edge of a box, insert v. box padding568      if (i % 3 === 2) {569        display_string += V_BOX_PADDING;570      }571      // End of a line, insert horiz. padding572      if (i % 9 === 8) {573        display_string += H_PADDING;574      }575      // Horizontal edge of a box, insert h. box padding576      if (i % 27 === 26) {577        display_string += H_BOX_PADDING;578      }579    }580    console.log(display_string);581  };582  sudoku.validate_board = function (board) {583    /* Return if the given `board` is valid or not. If it's valid, return584        true. If it's not, return a string of the reason why it's not.585        */586    // Check for empty board587    if (!board) {588      return "Empty board";589    }590    // Invalid board length591    if (board.length !== NR_SQUARES) {592      return (593        "Invalid board size. Board must be exactly " + NR_SQUARES + " squares."594      );595    }596    // Check for invalid characters597    for (var i in board) {598      if (599        !sudoku._in(board[i], sudoku.DIGITS) &&600        board[i] !== sudoku.BLANK_CHAR601      ) {602        return (603          "Invalid board character encountered at index " + i + ": " + board[i]604        );605      }606    }607    // Otherwise, we're good. Return true.608    return true;609  };610  sudoku._cross = function (a, b) {611    /* Cross product of all elements in `a` and `b`, e.g.,612        sudoku._cross("abc", "123") ->613        ["a1", "a2", "a3", "b1", "b2", "b3", "c1", "c2", "c3"]614        */615    var result = [];616    for (var ai in a) {617      for (var bi in b) {618        result.push(a[ai] + b[bi]);619      }620    }621    return result;622  };623  sudoku._in = function (v, seq) {624    /* Return if a value `v` is in sequence `seq`.625     */626    return seq.indexOf(v) !== -1;627  };628  sudoku._first_true = function (seq) {629    /* Return the first element in `seq` that is true. If no element is630        true, return false.631        */632    for (var i in seq) {633      if (seq[i]) {634        return seq[i];635      }636    }637    return false;638  };639  sudoku._shuffle = function (seq) {640    /* Return a shuffled version of `seq`641     */642    // Create an array of the same size as `seq` filled with false643    var shuffled = [];644    for (var i = 0; i < seq.length; ++i) {645      shuffled.push(false);646    }647    for (var i in seq) {648      var ti = sudoku._rand_range(seq.length);649      while (shuffled[ti]) {650        ti = ti + 1 > seq.length - 1 ? 0 : ti + 1;651      }652      shuffled[ti] = seq[i];653    }654    return shuffled;655  };656  sudoku._rand_range = function (max, min) {657    /* Get a random integer in the range of `min` to `max` (non inclusive).658        If `min` not defined, default to 0. If `max` not defined, throw an 659        error.660        */661    min = min || 0;662    if (max) {...

sudoku.core.js

Source:sudoku.core.js

...85        var square = shuffled_squares[si];86        // If an assignment of a random chioce causes a contradictoin, give87        // up and try again88        var rand_candidate_idx =89            sudoku._rand_range(candidates[square].length);90        var rand_candidate = candidates[square][rand_candidate_idx];91        if (!sudoku._assign(candidates, square, rand_candidate)) {92            break;93        }94        // Make a list of all single candidates95        var single_candidates = [];96        for (var si in SQUARES) {97            var square = SQUARES[si];98            if (candidates[square].length == 1) {99                single_candidates.push(candidates[square]);100            }101        }102        // If we have at least difficulty, and the unique candidate count is103        // at least 8, return the puzzle!104        if (single_candidates.length >= difficulty &&105            sudoku._strip_dups(single_candidates).length >= 8) {106            var board = '';107            var givens_idxs = [];108            for (var i in SQUARES) {109                var square = SQUARES[i];110                if (candidates[square].length == 1) {111                    board += candidates[square];112                    givens_idxs.push(i);113                } else {114                    board += sudoku.BLANK_CHAR;115                }116            }117            // If we have more than `difficulty` givens, remove some random118            // givens until we're down to exactly `difficulty`119            var nr_givens = givens_idxs.length;120            if (nr_givens > difficulty) {121                givens_idxs = sudoku._shuffle(givens_idxs);122                for (var i = 0; i < nr_givens - difficulty; ++i) {123                    var target = parseInt(givens_idxs[i]);124                    board = board.substr(0, target) + sudoku.BLANK_CHAR +125                        board.substr(target + 1);126                }127            }128            // Double check board is solvable129            // TODO: Make a standalone board checker. Solve is expensive.130            if (sudoku.solve(board)) {131                return board;132            }133        }134    }135    // Give up and try a new puzzle136    return sudoku.generate(difficulty);137};138// Solve139// -------------------------------------------------------------------------140sudoku.solve = function (board, reverse) {141    /* Solve a sudoku puzzle given a sudoku `board`, i.e., an 81-character142    string of sudoku.DIGITS, 1-9, and spaces identified by '.', representing the143    squares. There must be a minimum of 17 givens. If the given board has no144    solutions, return false.145    Optionally set `reverse` to solve "backwards", i.e., rotate through the146    possibilities in reverse. Useful for checking if there is more than one147    solution.148    */149    // Assure a valid board150    var report = sudoku.validate_board(board);151    if (report !== true) {152        throw report;153    }154    // Check number of givens is at least MIN_GIVENS155    var nr_givens = 0;156    for (var i in board) {157        if (board[i] !== sudoku.BLANK_CHAR && sudoku._in(board[i], sudoku.DIGITS)) {158            ++nr_givens;159        }160    }161    if (nr_givens < MIN_GIVENS) {162        throw 'Too few givens. Minimum givens is ' + MIN_GIVENS;163    }164    // Default reverse to false165    reverse = reverse || false;166    var candidates = sudoku._get_candidates_map(board);167    var result = sudoku._search(candidates, reverse);168    if (result) {169        var solution = '';170        for (var square in result) {171            solution += result[square];172        }173        return solution;174    }175    return false;176};177sudoku.get_candidates = function (board) {178    /* Return all possible candidatees for each square as a grid of179    candidates, returnning `false` if a contradiction is encountered.180    Really just a wrapper for sudoku._get_candidates_map for programmer181    consumption.182    */183    // Assure a valid board184    var report = sudoku.validate_board(board);185    if (report !== true) {186        throw report;187    }188    // Get a candidates map189    var candidates_map = sudoku._get_candidates_map(board);190    // If there's an error, return false191    if (!candidates_map) {192        return false;193    }194    // Transform candidates map into grid195    var rows = [];196    var cur_row = [];197    var i = 0;198    for (var square in candidates_map) {199        var candidates = candidates_map[square];200        cur_row.push(candidates);201        if (i % 9 == 8) {202            rows.push(cur_row);203            cur_row = [];204        }205        ++i;206    }207    return rows;208};209sudoku._get_candidates_map = function (board) {210    /* Get all possible candidates for each square as a map in the form211    {square: sudoku.DIGITS} using recursive constraint propagation. Return `false`212    if a contradiction is encountered213    */214    // Assure a valid board215    var report = sudoku.validate_board(board);216    if (report !== true) {217        throw report;218    }219    var candidate_map = {};220    var squares_values_map = sudoku._get_square_vals_map(board);221    // Start by assigning every digit as a candidate to every square222    for (var si in SQUARES) {223        candidate_map[SQUARES[si]] = sudoku.DIGITS;224    }225    // For each non-blank square, assign its value in the candidate map and226    // propigate.227    for (var square in squares_values_map) {228        var val = squares_values_map[square];229        if (sudoku._in(val, sudoku.DIGITS)) {230            var new_candidates = sudoku._assign(candidate_map, square, val);231            // Fail if we can't assign val to square232            if (!new_candidates) {233                return false;234            }235        }236    }237    return candidate_map;238};239sudoku._search = function (candidates, reverse) {240    /* Given a map of squares -> candiates, using depth-first search,241    recursively try all possible values until a solution is found, or false242    if no solution exists.243    */244    // Return if error in previous iteration245    if (!candidates) {246        return false;247    }248    // Default reverse to false249    reverse = reverse || false;250    // If only one candidate for every square, we've a solved puzzle!251    // Return the candidates map.252    var max_nr_candidates = 0;253    for (var si in SQUARES) {254        var square = SQUARES[si];255        var nr_candidates = candidates[square].length;256        if (nr_candidates > max_nr_candidates) {257            max_nr_candidates = nr_candidates;258        }259    }260    if (max_nr_candidates === 1) {261        return candidates;262    }263    // Choose the blank square with the fewest possibilities > 1264    var min_nr_candidates = 10;265    var min_candidates_square = null;266    for (si in SQUARES) {267        var square = SQUARES[si];268        var nr_candidates = candidates[square].length;269        if (nr_candidates < min_nr_candidates && nr_candidates > 1) {270            min_nr_candidates = nr_candidates;271            min_candidates_square = square;272        }273    }274    // Recursively search through each of the candidates of the square275    // starting with the one with fewest candidates.276    // Rotate through the candidates forwards277    var min_candidates = candidates[min_candidates_square];278    if (!reverse) {279        for (var vi in min_candidates) {280            var val = min_candidates[vi];281            // TODO: Implement a non-rediculous deep copy function282            var candidates_copy = JSON.parse(JSON.stringify(candidates));283            var candidates_next = sudoku._search(284                sudoku._assign(candidates_copy, min_candidates_square, val)285            );286            if (candidates_next) {287                return candidates_next;288            }289        }290        // Rotate through the candidates backwards291    } else {292        for (var vi = min_candidates.length - 1; vi >= 0; --vi) {293            var val = min_candidates[vi];294            // TODO: Implement a non-rediculous deep copy function295            var candidates_copy = JSON.parse(JSON.stringify(candidates));296            var candidates_next = sudoku._search(297                sudoku._assign(candidates_copy, min_candidates_square, val),298                reverse299            );300            if (candidates_next) {301                return candidates_next;302            }303        }304    }305    // If we get through all combinations of the square with the fewest306    // candidates without finding an answer, there isn't one. Return false.307    return false;308};309sudoku._assign = function (candidates, square, val) {310    /* Eliminate all values, *except* for `val`, from `candidates` at311    `square` (candidates[square]), and propagate. Return the candidates map312    when finished. If a contradiciton is found, return false.313    WARNING: This will modify the contents of `candidates` directly.314    */315    // Grab a list of canidates without 'val'316    var other_vals = candidates[square].replace(val, '');317    // Loop through all other values and eliminate them from the candidates318    // at the current square, and propigate. If at any point we get a319    // contradiction, return false.320    for (var ovi in other_vals) {321        var other_val = other_vals[ovi];322        var candidates_next =323            sudoku._eliminate(candidates, square, other_val);324        if (!candidates_next) {325            //console.log("Contradiction found by _eliminate.");326            return false;327        }328    }329    return candidates;330};331sudoku._eliminate = function (candidates, square, val) {332    /* Eliminate `val` from `candidates` at `square`, (candidates[square]),333    and propagate when values or places <= 2. Return updated candidates,334    unless a contradiction is detected, in which case, return false.335    WARNING: This will modify the contents of `candidates` directly.336    */337    // If `val` has already been eliminated from candidates[square], return338    // with candidates.339    if (!sudoku._in(val, candidates[square])) {340        return candidates;341    }342    // Remove `val` from candidates[square]343    candidates[square] = candidates[square].replace(val, '');344    // If the square has only candidate left, eliminate that value from its345    // peers346    var nr_candidates = candidates[square].length;347    var candidates_new;348    if (nr_candidates === 1) {349        var target_val = candidates[square];350        for (var pi in SQUARE_PEERS_MAP[square]) {351            var peer = SQUARE_PEERS_MAP[square][pi];352            candidates_new = sudoku._eliminate(candidates, peer, target_val);353            if (!candidates_new) {354                return false;355            }356        }357        // Otherwise, if the square has no candidates, we have a contradiction.358        // Return false.359    }360    if (nr_candidates === 0) {361        return false;362    }363    // If a unit is reduced to only one place for a value, then assign it364    for (var ui in SQUARE_UNITS_MAP[square]) {365        var unit = SQUARE_UNITS_MAP[square][ui];366        var val_places = [];367        for (var si in unit) {368            var unit_square = unit[si];369            if (sudoku._in(val, candidates[unit_square])) {370                val_places.push(unit_square);371            }372        }373        // If there's no place for this value, we have a contradition!374        // return false375        if (val_places.length === 0) {376            return false;377            // Otherwise the value can only be in one place. Assign it there.378        } else if (val_places.length === 1) {379            candidates_new = sudoku._assign(candidates, val_places[0], val);380            if (!candidates_new) {381                return false;382            }383        }384    }385    return candidates;386};387// Square relationships388// -------------------------------------------------------------------------389// Squares, and their relationships with values, units, and peers.390sudoku._get_square_vals_map = function (board) {391    /* Return a map of squares -> values392     */393    var squares_vals_map = {};394    // Make sure `board` is a string of length 81395    if (board.length != SQUARES.length) {396        throw 'Board/squares length mismatch.';397    } else {398        for (var i in SQUARES) {399            squares_vals_map[SQUARES[i]] = board[i];400        }401    }402    return squares_vals_map;403};404sudoku._get_square_units_map = function (squares, units) {405    /* Return a map of `squares` and their associated units (row, col, box)406     */407    var square_unit_map = {};408    // For every square...409    for (var si in squares) {410        var cur_square = squares[si];411        // Maintain a list of the current square's units412        var cur_square_units = [];413        // Look through the units, and see if the current square is in it,414        // and if so, add it to the list of of the square's units.415        for (var ui in units) {416            var cur_unit = units[ui];417            if (cur_unit.indexOf(cur_square) !== -1) {418                cur_square_units.push(cur_unit);419            }420        }421        // Save the current square and its units to the map422        square_unit_map[cur_square] = cur_square_units;423    }424    return square_unit_map;425};426sudoku._get_square_peers_map = function (squares, units_map) {427    /* Return a map of `squares` and their associated peers, i.e., a set of428    other squares in the square's unit.429    */430    var square_peers_map = {};431    // For every square...432    for (var si in squares) {433        var cur_square = squares[si];434        var cur_square_units = units_map[cur_square];435        // Maintain list of the current square's peers436        var cur_square_peers = [];437        // Look through the current square's units map...438        for (var sui in cur_square_units) {439            var cur_unit = cur_square_units[sui];440            for (var ui in cur_unit) {441                var cur_unit_square = cur_unit[ui];442                if (cur_square_peers.indexOf(cur_unit_square) === -1 &&443                    cur_unit_square !== cur_square) {444                    cur_square_peers.push(cur_unit_square);445                }446            }447        }448        // Save the current square an its associated peers to the map449        square_peers_map[cur_square] = cur_square_peers;450    }451    return square_peers_map;452};453sudoku._get_all_units = function (rows, cols) {454    /* Return a list of all units (rows, cols, boxes)455     */456    var units = [];457    // Rows458    for (var ri in rows) {459        units.push(sudoku._cross(rows[ri], cols));460    }461    // Columns462    for (var ci in cols) {463        units.push(sudoku._cross(rows, cols[ci]));464    }465    // Boxes466    var row_squares = ['ABC', 'DEF', 'GHI'];467    var col_squares = ['123', '456', '789'];468    for (var rsi in row_squares) {469        for (var csi in col_squares) {470            units.push(sudoku._cross(row_squares[rsi], col_squares[csi]));471        }472    }473    return units;474};475// Conversions476// -------------------------------------------------------------------------477sudoku.board_string_to_grid = function (board_string) {478    /* Convert a board string to a two-dimensional array479     */480    var rows = [];481    var cur_row = [];482    for (var i in board_string) {483        cur_row.push(board_string[i]);484        if (i % 9 == 8) {485            rows.push(cur_row);486            cur_row = [];487        }488    }489    return rows;490};491sudoku.board_grid_to_string = function (board_grid) {492    /* Convert a board grid to a string493     */494    var board_string = '';495    for (var r = 0; r < 9; ++r) {496        for (var c = 0; c < 9; ++c) {497            board_string += board_grid[r][c];498        }499    }500    return board_string;501};502// Utility503// -------------------------------------------------------------------------504sudoku.print_board = function (board) {505    /* Print a sudoku `board` to the console.506     */507    // Assure a valid board508    var report = sudoku.validate_board(board);509    if (report !== true) {510        throw report;511    }512    var V_PADDING = ' '; // Insert after each square513    var H_PADDING = '\n'; // Insert after each row514    var V_BOX_PADDING = '  '; // Box vertical padding515    var H_BOX_PADDING = '\n'; // Box horizontal padding516    var display_string = '';517    for (var i in board) {518        var square = board[i];519        // Add the square and some padding520        display_string += square + V_PADDING;521        // Vertical edge of a box, insert v. box padding522        if (i % 3 === 2) {523            display_string += V_BOX_PADDING;524        }525        // End of a line, insert horiz. padding526        if (i % 9 === 8) {527            display_string += H_PADDING;528        }529        // Horizontal edge of a box, insert h. box padding530        if (i % 27 === 26) {531            display_string += H_BOX_PADDING;532        }533    }534    console.log(display_string);535};536sudoku.validate_board = function (board) {537    /* Return if the given `board` is valid or not. If it's valid, return538    true. If it's not, return a string of the reason why it's not.539    */540    // Check for empty board541    if (!board) {542        return 'Empty board';543    }544    // Invalid board length545    if (board.length !== NR_SQUARES) {546        return 'Invalid board size. Board must be exactly ' + NR_SQUARES +547            ' squares.';548    }549    // Check for invalid characters550    for (var i in board) {551        if (!sudoku._in(board[i], sudoku.DIGITS) && board[i] !== sudoku.BLANK_CHAR) {552            return 'Invalid board character encountered at index ' + i +553                ': ' + board[i];554        }555    }556    // Otherwise, we're good. Return true.557    return true;558};559sudoku._cross = function (a, b) {560    /* Cross product of all elements in `a` and `b`, e.g.,561    sudoku._cross("abc", "123") ->562    ["a1", "a2", "a3", "b1", "b2", "b3", "c1", "c2", "c3"]563    */564    var result = [];565    for (var ai in a) {566        for (var bi in b) {567            result.push(a[ai] + b[bi]);568        }569    }570    return result;571};572sudoku._in = function (v, seq) {573    /* Return if a value `v` is in sequence `seq`.574     */575    return seq.indexOf(v) !== -1;576};577sudoku._first_true = function (seq) {578    /* Return the first element in `seq` that is true. If no element is579    true, return false.580    */581    for (var i in seq) {582        if (seq[i]) {583            return seq[i];584        }585    }586    return false;587};588sudoku._shuffle = function (seq) {589    /* Return a shuffled version of `seq`590     */591    // Create an array of the same size as `seq` filled with false592    var shuffled = [];593    for (var i = 0; i < seq.length; ++i) {594        shuffled.push(false);595    }596    for (var i in seq) {597        var ti = sudoku._rand_range(seq.length);598        while (shuffled[ti]) {599            ti = (ti + 1) > (seq.length - 1) ? 0 : (ti + 1);600        }601        shuffled[ti] = seq[i];602    }603    return shuffled;604};605sudoku._rand_range = function (max, min) {606    /* Get a random integer in the range of `min` to `max` (non inclusive).607    If `min` not defined, default to 0. If `max` not defined, throw an608    error.609    */610    min = min || 0;611    if (max) {...

main.js

Source:main.js

...29//   var candidates = sudoku._get_candidates_map(blank_board);30//   var shuffled_squares = sudoku._shuffle(SQUARES);31//   for (var si in shuffled_squares) {32//     var square = shuffled_squares[si];33//     var rand_candidate_idx = sudoku._rand_range(candidates[square].length);34//     var rand_candidate = candidates[square][rand_candidate_idx];35//     if (!sudoku._assign(candidates, square, rand_candidate)) {36//       break;37//     }38//     var single_candidates = [];39//     for (var si in SQUARES) {40//       var square = SQUARES[si];41//       if (candidates[square].length == 1) {42//         single_candidates.push(candidates[square]);43//       }44//     }45//     if (46//       single_candidates.length >= no_of_squares &&47//       sudoku._strip_dups(single_candidates).length >= 848//     ) {49//       var board = "";50//       var givens_idxs = [];51//       for (var i in SQUARES) {52//         var square = SQUARES[i];53//         if (candidates[square].length == 1) {54//           board += candidates[square];55//           givens_idxs.push(i);56//         } else {57//           board += sudoku.BLANK_CHAR;58//         }59//       }60//       var nr_givens = givens_idxs.length;61//       if (nr_givens > no_of_squares) {62//         givens_idxs = sudoku._shuffle(givens_idxs);63//         for (var i = 0; i < nr_givens - no_of_squares; ++i) {64//           var target = parseInt(givens_idxs[i]);65//           board =66//             board.substr(0, target) +67//             sudoku.BLANK_CHAR +68//             board.substr(target + 1);69//         }70//       }71//       if (sudoku.solve(board)) {72//         return board;73//       }74//     }75//   }76//   return sudoku.generate(no_of_squares);77// };78// sudoku.solve = function (board, reverse) {79//   // Assure a valid board80//   var report = sudoku.validate_board(board);81//   if (report !== true) {82//     throw report;83//   }84//   var nr_givens = 0;85//   for (var i in board) {86//     if (board[i] !== sudoku.BLANK_CHAR && sudoku._in(board[i], sudoku.DIGITS)) {87//       ++nr_givens;88//     }89//   }90//   if (nr_givens < MIN_GIVENS) {91//     throw "Too few givens. Minimum givens is " + MIN_GIVENS;92//   }93//   reverse = reverse || false;94//   var candidates = sudoku._get_candidates_map(board);95//   var result = sudoku._search(candidates, reverse);96//   if (result) {97//     var solution = "";98//     for (var square in result) {99//       solution += result[square];100//     }101//     return solution;102//   }103//   return false;104// };105// sudoku.get_candidates = function (board) {106//   var report = sudoku.validate_board(board);107//   if (report !== true) {108//     throw report;109//   }110//   var candidates_map = sudoku._get_candidates_map(board);111//   if (!candidates_map) {112//     return false;113//   }114//   var rows = [];115//   var cur_row = [];116//   var i = 0;117//   for (var square in candidates_map) {118//     var candidates = candidates_map[square];119//     cur_row.push(candidates);120//     if (i % 9 == 8) {121//       rows.push(cur_row);122//       cur_row = [];123//     }124//     ++i;125//   }126//   return rows;127// };128// sudoku._get_candidates_map = function (board) {129//   var report = sudoku.validate_board(board);130//   if (report !== true) {131//     throw report;132//   }133//   var candidate_map = {};134//   var squares_values_map = sudoku._get_square_vals_map(board);135//   for (var si in SQUARES) {136//     candidate_map[SQUARES[si]] = sudoku.DIGITS;137//   }138//   for (var square in squares_values_map) {139//     var val = squares_values_map[square];140//     if (sudoku._in(val, sudoku.DIGITS)) {141//       var new_candidates = sudoku._assign(candidate_map, square, val);142//       if (!new_candidates) {143//         return false;144//       }145//     }146//   }147//   return candidate_map;148// };149// sudoku._search = function (candidates, reverse) {150//   if (!candidates) {151//     return false;152//   }153//   reverse = reverse || false;154//   var max_nr_candidates = 0;155//   var max_candidates_square = null;156//   for (var si in SQUARES) {157//     var square = SQUARES[si];158//     var nr_candidates = candidates[square].length;159//     if (nr_candidates > max_nr_candidates) {160//       max_nr_candidates = nr_candidates;161//       max_candidates_square = square;162//     }163//   }164//   if (max_nr_candidates === 1) {165//     return candidates;166//   }167//   var min_nr_candidates = 10;168//   var min_candidates_square = null;169//   for (si in SQUARES) {170//     var square = SQUARES[si];171//     var nr_candidates = candidates[square].length;172//     if (nr_candidates < min_nr_candidates && nr_candidates > 1) {173//       min_nr_candidates = nr_candidates;174//       min_candidates_square = square;175//     }176//   }177//   var min_candidates = candidates[min_candidates_square];178//   if (!reverse) {179//     for (var vi in min_candidates) {180//       var val = min_candidates[vi];181//       var candidates_copy = JSON.parse(JSON.stringify(candidates));182//       var candidates_next = sudoku._search(183//         sudoku._assign(candidates_copy, min_candidates_square, val)184//       );185//       if (candidates_next) {186//         return candidates_next;187//       }188//     }189//   } else {190//     for (var vi = min_candidates.length - 1; vi >= 0; --vi) {191//       var val = min_candidates[vi];192//       var candidates_copy = JSON.parse(JSON.stringify(candidates));193//       var candidates_next = sudoku._search(194//         sudoku._assign(candidates_copy, min_candidates_square, val),195//         reverse196//       );197//       if (candidates_next) {198//         return candidates_next;199//       }200//     }201//   }202//   return false;203// };204// sudoku._assign = function (candidates, square, val) {205//   var other_vals = candidates[square].replace(val, "");206//   for (var ovi in other_vals) {207//     var other_val = other_vals[ovi];208//     var candidates_next = sudoku._eliminate(candidates, square, other_val);209//     if (!candidates_next) {210//       return false;211//     }212//   }213//   return candidates;214// };215// sudoku._eliminate = function (candidates, square, val) {216//   if (!sudoku._in(val, candidates[square])) {217//     return candidates;218//   }219//   candidates[square] = candidates[square].replace(val, "");220//   var nr_candidates = candidates[square].length;221//   if (nr_candidates === 1) {222//     var target_val = candidates[square];223//     for (var pi in SQUARE_PEERS_MAP[square]) {224//       var peer = SQUARE_PEERS_MAP[square][pi];225//       var candidates_new = sudoku._eliminate(candidates, peer, target_val);226//       if (!candidates_new) {227//         return false;228//       }229//     }230//   }231//   if (nr_candidates === 0) {232//     return false;233//   }234//   for (var ui in SQUARE_UNITS_MAP[square]) {235//     var unit = SQUARE_UNITS_MAP[square][ui];236//     var val_places = [];237//     for (var si in unit) {238//       var unit_square = unit[si];239//       if (sudoku._in(val, candidates[unit_square])) {240//         val_places.push(unit_square);241//       }242//     }243//     if (val_places.length === 0) {244//       return false;245//     } else if (val_places.length === 1) {246//       var candidates_new = sudoku._assign(candidates, val_places[0], val);247//       if (!candidates_new) {248//         return false;249//       }250//     }251//   }252//   return candidates;253// };254// sudoku._get_square_vals_map = function (board) {255//   /* Return a map of squares -> values256//    */257//   var squares_vals_map = {};258//   // Make sure `board` is a string of length 81259//   if (board.length != SQUARES.length) {260//     throw "Board/squares length mismatch.";261//   } else {262//     for (var i in SQUARES) {263//       squares_vals_map[SQUARES[i]] = board[i];264//     }265//   }266//   return squares_vals_map;267// };268// sudoku._get_square_units_map = function (squares, units) {269//   var square_unit_map = {};270//   for (var si in squares) {271//     var cur_square = squares[si];272//     var cur_square_units = [];273//     for (var ui in units) {274//       var cur_unit = units[ui];275//       if (cur_unit.indexOf(cur_square) !== -1) {276//         cur_square_units.push(cur_unit);277//       }278//     }279//     // Save the current square and its units to the map280//     square_unit_map[cur_square] = cur_square_units;281//   }282//   return square_unit_map;283// };284// sudoku._get_square_peers_map = function (squares, units_map) {285//   var square_peers_map = {};286//   for (var si in squares) {287//     var cur_square = squares[si];288//     var cur_square_units = units_map[cur_square];289//     var cur_square_peers = [];290//     for (var sui in cur_square_units) {291//       var cur_unit = cur_square_units[sui];292//       for (var ui in cur_unit) {293//         var cur_unit_square = cur_unit[ui];294//         if (295//           cur_square_peers.indexOf(cur_unit_square) === -1 &&296//           cur_unit_square !== cur_square297//         ) {298//           cur_square_peers.push(cur_unit_square);299//         }300//       }301//     }302//     square_peers_map[cur_square] = cur_square_peers;303//   }304//   return square_peers_map;305// };306// sudoku._get_all_units = function (rows, cols) {307//   var units = [];308//   // Rows309//   for (var ri in rows) {310//     units.push(sudoku._cross(rows[ri], cols));311//   }312//   // Columns313//   for (var ci in cols) {314//     units.push(sudoku._cross(rows, cols[ci]));315//   }316//   // Boxes317//   var row_squares = ["ABC", "DEF", "GHI"];318//   var col_squares = ["123", "456", "789"];319//   for (var rsi in row_squares) {320//     for (var csi in col_squares) {321//       units.push(sudoku._cross(row_squares[rsi], col_squares[csi]));322//     }323//   }324//   return units;325// };326// sudoku.validate_board = function (board) {327//   if (!board) {328//     return "Empty board";329//   }330//   // Invalid board length331//   if (board.length !== NR_SQUARES) {332//     return (333//       "Invalid board size. Board must be exactly " + NR_SQUARES + " squares."334//     );335//   }336//   // Check for invalid characters337//   for (var i in board) {338//     if (339//       !sudoku._in(board[i], sudoku.DIGITS) &&340//       board[i] !== sudoku.BLANK_CHAR341//     ) {342//       return (343//         "Invalid board character encountered at index " + i + ": " + board[i]344//       );345//     }346//   }347//   return true;348// };349// sudoku._cross = function (a, b) {350//   var result = [];351//   for (var ai in a) {352//     for (var bi in b) {353//       result.push(a[ai] + b[bi]);354//     }355//   }356//   return result;357// };358// sudoku._in = function (v, seq) {359//   return seq.indexOf(v) !== -1;360// };361// sudoku._first_true = function (seq) {362//   for (var i in seq) {363//     if (seq[i]) {364//       return seq[i];365//     }366//   }367//   return false;368// };369// sudoku._shuffle = function (seq) {370//   var shuffled = [];371//   for (var i = 0; i < seq.length; ++i) {372//     shuffled.push(false);373//   }374//   for (var i in seq) {375//     var ti = sudoku._rand_range(seq.length);376//     while (shuffled[ti]) {377//       ti = ti + 1 > seq.length - 1 ? 0 : ti + 1;378//     }379//     shuffled[ti] = seq[i];380//   }381//   return shuffled;382// };383// sudoku._rand_range = function (max, min) {384//   min = min || 0;385//   if (max) {386//     return Math.floor(Math.random() * (max - min)) + min;387//   } else {388//     throw "Range undefined";389//   }...

sudoku.js

Source:sudoku.js

...51        for(var si in shuffled_squares){52            var square = shuffled_squares[si];53            54            var rand_option_idx = 55                    sudoku._rand_range(options[square].length);56            var rand_option = options[square][rand_option_idx];57            if(!sudoku._assign(options, square, rand_option)){58                break;59            }60            61            var single_options = [];62            for(var si in SQUARES){63                var square = SQUARES[si];64                65                if(options[square].length == 1){66                    single_options.push(options[square]);67                }68            }69            70            if(single_options.length >= difficulty && 71                    sudoku._strip_dups(single_options).length >= 8){72                var board = "";73                var givens_idxs = [];74                for(var i in SQUARES){75                    var square = SQUARES[i];76                    if(options[square].length == 1){77                        board += options[square];78                        givens_idxs.push(i);79                    } else {80                        board += sudoku.BLANK_CHAR;81                    }82                }83                84                var nr_givens = givens_idxs.length;85                if(nr_givens > difficulty){86                    givens_idxs = sudoku._shuffle(givens_idxs);87                    for(var i = 0; i < nr_givens - difficulty; ++i){88                        var target = parseInt(givens_idxs[i]);89                        board = board.substr(0, target) + sudoku.BLANK_CHAR + 90                            board.substr(target + 1);91                    }92                }93                94                if(sudoku.solve(board)){95                    return board;96                }97            }98        }99        100        return sudoku.generate(difficulty);101    };102    // Solve103    sudoku.solve = function(board, reverse){104        var report = sudoku.validate_board(board);105        if(report !== true){106            throw report;107        }108        109        var nr_givens = 0;110        for(var i in board){111            if(board[i] !== sudoku.BLANK_CHAR && sudoku._in(board[i], sudoku.DIGITS)){112                ++nr_givens;113            }114        }115        if(nr_givens < MIN_GIVENS){116            throw "Too few givens. Minimum givens is " + MIN_GIVENS;117        }118        reverse = reverse || false;119        var options = sudoku._get_options_map(board);120        var result = sudoku._search(options, reverse);121        122        if(result){123            var solution = "";124            for(var square in result){125                solution += result[square];126            }127            return solution;128        }129        return false;130    };131    sudoku.get_options = function(board){132        var report = sudoku.validate_board(board);133        if(report !== true){134            throw report;135        }136        137        var options_map = sudoku._get_options_map(board);138        139        if(!options_map){140            return false;141        }142        143        var rows = [];144        var cur_row = [];145        var i = 0;146        for(var square in options_map){147            var options = options_map[square];148            cur_row.push(options);149            if(i % 9 == 8){150                rows.push(cur_row);151                cur_row = [];152            }153            ++i;154        }155        return rows;156    }157    sudoku._get_options_map = function(board){158        var report = sudoku.validate_board(board);159        if(report !== true){160            throw report;161        }162        163        var option_map = {};164        var squares_values_map = sudoku._get_square_vals_map(board);165        166        for(var si in SQUARES){167            option_map[SQUARES[si]] = sudoku.DIGITS;168        }169        170        for(var square in squares_values_map){171            var val = squares_values_map[square];172            173            if(sudoku._in(val, sudoku.DIGITS)){174                var new_options = sudoku._assign(option_map, square, val);175                176                if(!new_options){177                    return false;178                }179            }180        }181        182        return option_map;183    };184    sudoku._search = function(options, reverse){185        if(!options){186            return false;187        }188        189        reverse = reverse || false;190        191        var max_nr_options = 0;192        var max_options_square = null;193        for(var si in SQUARES){194            var square = SQUARES[si];195            196            var nr_options = options[square].length;197                198            if(nr_options > max_nr_options){199                max_nr_options = nr_options;200                max_options_square = square;201            }202        }203        if(max_nr_options === 1){204            return options;205        }206        207        var min_nr_options = 10;208        var min_options_square = null;209        for(si in SQUARES){210            var square = SQUARES[si];211            212            var nr_options = options[square].length;213            214            if(nr_options < min_nr_options && nr_options > 1){215                min_nr_options = nr_options;216                min_options_square = square;217            }218        }219        220        var min_options = options[min_options_square];221        if(!reverse){222            for(var vi in min_options){223                var val = min_options[vi];224                225                var options_copy = JSON.parse(JSON.stringify(options));226                var options_next = sudoku._search(227                    sudoku._assign(options_copy, min_options_square, val)228                );229                230                if(options_next){231                    return options_next;232                }233            }234            235        } else {236            for(var vi = min_options.length - 1; vi >= 0; --vi){237                var val = min_options[vi];238                239                // TODO: Implement a non-rediculous deep copy function240                var options_copy = JSON.parse(JSON.stringify(options));241                var options_next = sudoku._search(242                    sudoku._assign(options_copy, min_options_square, val), 243                    reverse244                );245                246                if(options_next){247                    return options_next;248                }249            }250        }251        252        return false;253    };254    sudoku._assign = function(options, square, val){255        var other_vals = options[square].replace(val, "");256        for(var ovi in other_vals){257            var other_val = other_vals[ovi];258            var options_next =259                sudoku._eliminate(options, square, other_val);260            if(!options_next){261                //console.log("Contradiction found by _eliminate.");262                return false;263            }264        }265        return options;266    };267    sudoku._eliminate = function(options, square, val){268        if(!sudoku._in(val, options[square])){269            return options;270        }271        options[square] = options[square].replace(val, '');272           273        var nr_options = options[square].length;274        if(nr_options === 1){275            var target_val = options[square];276            277            for(var pi in SQUARE_PEERS_MAP[square]){278                var peer = SQUARE_PEERS_MAP[square][pi];279                280                var options_new = 281                        sudoku._eliminate(options, peer, target_val);282                        283                if(!options_new){284                    return false;285                }286            }287        288        } if(nr_options === 0){289            return false;290        }291        292        for(var ui in SQUARE_UNITS_MAP[square]){293            var unit = SQUARE_UNITS_MAP[square][ui];294            295            var val_places = [];296            for(var si in unit){297                var unit_square = unit[si];298                if(sudoku._in(val, options[unit_square])){299                    val_places.push(unit_square);300                }301            }302            303            if(val_places.length === 0){304                return false;305                306            } else if(val_places.length === 1){307                var options_new = 308                    sudoku._assign(options, val_places[0], val);309                310                if(!options_new){311                    return false;312                }313            }314        }315        316        return options;317    };318    319    // Square relationships320    // Squares, and their relationships with values, units, and peers.321    322    sudoku._get_square_vals_map = function(board){323        var squares_vals_map = {};324        325        // Make sure `board` is a string of length 81326        if(board.length != SQUARES.length){327            throw "Board/squares length mismatch.";328            329        } else {330            for(var i in SQUARES){331                squares_vals_map[SQUARES[i]] = board[i];332            }333        }334        335        return squares_vals_map;336    };337    sudoku._get_square_units_map = function(squares, units){338        var square_unit_map = {};339        for(var si in squares){340            var cur_square = squares[si];341            var cur_square_units = [];342            for(var ui in units){343                var cur_unit = units[ui];344                if(cur_unit.indexOf(cur_square) !== -1){345                    cur_square_units.push(cur_unit);346                }347            }348            square_unit_map[cur_square] = cur_square_units;349        }350        return square_unit_map;351    };352    sudoku._get_square_peers_map = function(squares, units_map){353        var square_peers_map = {};354        for(var si in squares){355            var cur_square = squares[si];356            var cur_square_units = units_map[cur_square];357            var cur_square_peers = [];358            for(var sui in cur_square_units){359                var cur_unit = cur_square_units[sui];360                for(var ui in cur_unit){361                    var cur_unit_square = cur_unit[ui];362                    if(cur_square_peers.indexOf(cur_unit_square) === -1 && 363                            cur_unit_square !== cur_square){364                        cur_square_peers.push(cur_unit_square);365                    }366                }367            }368            369            square_peers_map[cur_square] = cur_square_peers;370        }371        return square_peers_map;372    };373    374    sudoku._get_all_units = function(rows, cols){375        var units = [];376        for(var ri in rows){377            units.push(sudoku._cross(rows[ri], cols));378        }379        for(var ci in cols){380           units.push(sudoku._cross(rows, cols[ci]));381        }382        var row_squares = ["ABC", "DEF", "GHI"];383        var col_squares = ["123", "456", "789"];384        for(var rsi in row_squares){385            for(var csi in col_squares){386                units.push(sudoku._cross(row_squares[rsi], col_squares[csi]));387            }388        }389        return units;390    };391    392    // Conversions393    sudoku.board_string_to_grid = function(board_string){394        var rows = [];395        var cur_row = [];396        for(var i in board_string){397            cur_row.push(board_string[i]);398            if(i % 9 == 8){399                rows.push(cur_row);400                cur_row = [];401            }402        }403        return rows;404    };405    406    sudoku.board_grid_to_string = function(board_grid){407        var board_string = "";408        for(var r = 0; r < 9; ++r){409            for(var c = 0; c < 9; ++c){410                board_string += board_grid[r][c];411            }   412        }413        return board_string;414    };415    416    // Utility417    sudoku.print_board = function(board){418        var report = sudoku.validate_board(board);419        if(report !== true){420            throw report;421        }422        423        var V_PADDING = " ";  424        var H_PADDING = '\n'; 425        426        var V_BOX_PADDING = "  ";427        var H_BOX_PADDING = '\n';428        var display_string = "";429        430        for(var i in board){431            var square = board[i];432            433            display_string += square + V_PADDING;434            435            if(i % 3 === 2){436                display_string += V_BOX_PADDING;437            }438            439            if(i % 9 === 8){440                display_string += H_PADDING;441            }442            443            if(i % 27 === 26){444                display_string += H_BOX_PADDING;445            }446        }447        console.log(display_string);448    };449    sudoku.validate_board = function(board){450        if(!board){451            return "Empty board";452        }453        454        if(board.length !== NR_SQUARES){455            return "Invalid board size. Board must be exactly " + NR_SQUARES +456                    " squares.";457        }458        459        for(var i in board){460            if(!sudoku._in(board[i], sudoku.DIGITS) && board[i] !== sudoku.BLANK_CHAR){461                return "Invalid board character encountered at index " + i + 462                        ": " + board[i];463            }464        }465        466        return true;467    };468    sudoku._cross = function(a, b){469        var result = [];470        for(var ai in a){471            for(var bi in b){472                result.push(a[ai] + b[bi]);473            }474        }475        return result;476    };477    478    sudoku._in = function(v, seq){479        return seq.indexOf(v) !== -1;480    };481    482    sudoku._first_true = function(seq){483        for(var i in seq){484            if(seq[i]){485                return seq[i];486            }487        }488        return false;489    };490    sudoku._shuffle = function(seq){491        var shuffled = [];492        for(var i = 0; i < seq.length; ++i){493            shuffled.push(false);494        }495        496        for(var i in seq){497            var ti = sudoku._rand_range(seq.length);498            499            while(shuffled[ti]){500                ti = (ti + 1) > (seq.length - 1) ? 0 : (ti + 1);501            }502            503            shuffled[ti] = seq[i];504        }505        506        return shuffled;507    };508    sudoku._rand_range = function(max, min){509        min = min || 0;510        if(max){511            return Math.floor(Math.random() * (max - min)) + min;...

sudoku_generator_01.js

Source:sudoku_generator_01.js

...76		for(var si in shuffled_squares) {77			var square = shuffled_squares[si];78			// If an assignment of a random chioce causes a contradictoin, give79			// up and try again80			var rand_candidate_idx = sudoku._rand_range(candidates[square].length);81			var rand_candidate = candidates[square][rand_candidate_idx];82			if(!sudoku._assign(candidates, square, rand_candidate)) break;83			var single_candidates = [];84			for(var si in sudoku.SQUARES) {85				var square = sudoku.SQUARES[si];86				if(candidates[square].length == 1) single_candidates.push(candidates[square]);87			}88			// If we have at least difficulty, and the unique candidate count is89			// at least 8, return the puzzle!90			if(single_candidates.length >= difficulty && sudoku._strip_dups(single_candidates).length >= 8){91				var board = '';92				var givens_idxs = [];93				for(var i in sudoku.SQUARES){94					var square = sudoku.SQUARES[i];95					if(candidates[square].length == 1){96						board += candidates[square];97						givens_idxs.push(i);98					}99					else {100						board += sudoku.BLANK_CHAR;101					}102				}103				// If we have more than `difficulty` givens, remove some random104				// givens until we're down to exactly `difficulty`105				var nr_givens = givens_idxs.length;106				if(nr_givens > difficulty){107					givens_idxs = sudoku._shuffle(givens_idxs);108					for(var i = 0; i < nr_givens - difficulty; ++i){109						var target = parseInt(givens_idxs[i]);110						board = board.substr(0, target) + sudoku.BLANK_CHAR + board.substr(target + 1);111					}112				}113				// Double check board is solvable114				// TODO: Make a standalone board checker. Solve is expensive.115				if(sudoku.solve(board)) return board;116			}117		}118		return sudoku.generate(difficulty);119	};120	sudoku.solve = function(board, reverse) {121		sudoku.init();122		var report = sudoku.validate_board(board);123		if(report !== true) throw report;124		var nr_givens = 0;125		for(var i in board) {126			if(board[i] !== sudoku.BLANK_CHAR && sudoku.DIGITS.includes(board[i])) ++nr_givens;127		}128		if(nr_givens < sudoku.MIN_GIVENS) throw 'Too few givens. Minimum givens is' + sudoku.MIN_GIVENS;129		reverse = reverse || false;130		var candidates = sudoku._get_candidates_map(board);131		var result = sudoku._search(candidates, reverse);132		if(result) {133			var solution = '';134			for(var square in result) solution += result[square];135			return solution;136		}137		return false;138	};139	sudoku._get_candidates_map = function(board){140		var report = sudoku.validate_board(board);141		if(report !== true) throw report;142		var candidate_map = {};143		var squares_values_map = sudoku._get_square_vals_map(board);144		for(var si in sudoku.SQUARES) candidate_map[sudoku.SQUARES[si]] = sudoku.DIGITS;145		for(var square in squares_values_map){146			var val = squares_values_map[square];147			if(sudoku.DIGITS.includes(val)) {148				var new_candidates = sudoku._assign(candidate_map, square, val);149				if(!new_candidates) return false;150			}151		}152		return candidate_map;153	};154	sudoku._search = function(candidates, reverse){155		if(!candidates) return false;156		reverse = reverse || false;157		var max_nr_candidates = 0;158		var max_candidates_square = null;159		for(var si in sudoku.SQUARES) {160			var square = sudoku.SQUARES[si];161			var nr_candidates = candidates[square].length;162			if(nr_candidates > max_nr_candidates) {163				max_nr_candidates = nr_candidates;164				max_candidates_square = square;165			}166		}167		if(max_nr_candidates === 1) return candidates;168		var min_nr_candidates = 10;169		var min_candidates_square = null;170		for(si in sudoku.SQUARES) {171			var square = sudoku.SQUARES[si];172			var nr_candidates = candidates[square].length;173			if(nr_candidates < min_nr_candidates && nr_candidates > 1){174				min_nr_candidates = nr_candidates;175				min_candidates_square = square;176			}177		}178		var min_candidates = candidates[min_candidates_square];179		if(!reverse) {180			//for(var vi in min_candidates) {181			for(var vi = 0; vi < min_candidates.length; vi++) {182				var val = min_candidates[vi];183				var candidates_copy = Object.assign({}, candidates);184				var candidates_next = sudoku._search(sudoku._assign(candidates_copy, min_candidates_square, val));185				if(candidates_next) return candidates_next;186			}187		}188		else {189			for(var vi = min_candidates.length - 1; vi >= 0; --vi) {190				var val = min_candidates[vi];191				var candidates_copy = Object.assign({}, candidates);192				var candidates_next = sudoku._search(sudoku._assign(candidates_copy, min_candidates_square, val), reverse);193				if(candidates_next) return candidates_next;194			}195		}196		return false;197	};198	sudoku._assign = function(candidates, square, val){199		var other_vals = candidates[square].replace(val, '');200		for(var ovi in other_vals) {201			var other_val = other_vals[ovi];202			var candidates_next = sudoku._eliminate(candidates, square, other_val);203			if(!candidates_next) return false;204		}205		return candidates;206	};207	sudoku._eliminate = function(candidates, square, val){208		if(!candidates[square].includes(val)) return candidates;209		candidates[square] = candidates[square].replace(val, '');210		var nr_candidates = candidates[square].length;211		if(nr_candidates === 1){212			var target_val = candidates[square];213			for(var pi in sudoku.SQUARE_PEERS_MAP[square]){214				var peer = sudoku.SQUARE_PEERS_MAP[square][pi];215				var candidates_new = sudoku._eliminate(candidates, peer, target_val);216				if(!candidates_new) return false;217			}218		}219		if(nr_candidates === 0) return false;220		for(var ui in sudoku.SQUARE_UNITS_MAP[square]) {221			var unit = sudoku.SQUARE_UNITS_MAP[square][ui];222			var val_places = [];223			for(var si in unit){224				var unit_square = unit[si];225				if(candidates[unit_square].includes(val)) val_places.push(unit_square);226			}227			if(val_places.length === 0) return false;228			if(val_places.length === 1) {229				var candidates_new = sudoku._assign(candidates, val_places[0], val);230				if(!candidates_new) return false;231			}232		}233		return candidates;234	};235	sudoku._get_square_vals_map = function(board) {236		var squares_vals_map = {};237		if(board.length != sudoku.SQUARES.length) throw new Error("Board/squares length mismatch.");238		for(var i in sudoku.SQUARES) squares_vals_map[sudoku.SQUARES[i]] = board[i];239		return squares_vals_map;240	};241	sudoku._get_square_units_map = function(squares, units){242		var square_unit_map = {};243		for(var si in squares){244			var cur_square = squares[si];245			var cur_square_units = [];246			for(var ui in units){247				var cur_unit = units[ui];248				if(cur_unit.indexOf(cur_square) !== -1) cur_square_units.push(cur_unit);249			}250			square_unit_map[cur_square] = cur_square_units;251		}252		return square_unit_map;253	};254	sudoku._get_square_peers_map = function(squares, units_map){255		var square_peers_map = {};256		for(var si in squares) {257			var cur_square = squares[si];258			var cur_square_units = units_map[cur_square];259			var cur_square_peers = [];260			for(var sui in cur_square_units){261				var cur_unit = cur_square_units[sui];262				for(var ui in cur_unit){263					var cur_unit_square = cur_unit[ui];264					if(cur_square_peers.indexOf(cur_unit_square) === -1 && cur_unit_square !== cur_square) {265						cur_square_peers.push(cur_unit_square);266					}267				}268			}269			square_peers_map[cur_square] = cur_square_peers;270		}271		return square_peers_map;272	};273	sudoku._get_all_units = function(rows, cols){274		/* Return a list of all units (rows, cols, boxes)275		*/276		var units = [];277		// sudoku.ROWS278		for(var ri in rows){279			units.push(sudoku._cross(rows[ri], cols));280		}281		// Columns282		for(var ci in cols){283			 units.push(sudoku._cross(rows, cols[ci]));284		}285		// Boxes286		var row_squares = ["ABC", "DEF", "GHI"];287		var col_squares = ["123", "456", "789"];288		for(var rsi in row_squares){289			for(var csi in col_squares){290				units.push(sudoku._cross(row_squares[rsi], col_squares[csi]));291			}292		}293		return units;294	};295	sudoku.validate_board = function(board){296		if(!board) return "Empty board";	297		if(board.length !== sudoku.NR_SQUARES) return "Invalid board size. Board must be exactly " + sudoku.NR_SQUARES + " squares.";298		for(var i in board) {299			if(!sudoku.DIGITS.includes(board[i]) && board[i] !== sudoku.BLANK_CHAR){300				return "Invalid board character encountered at index " + i + ": " + board[i];301			}302		}303		return true;304	};305	sudoku._cross = function(a, b) {306		var result = [];307		for(var ai in a)308			for(var bi in b)309				result.push(a[ai] + b[bi]);310		return result;311	};312	sudoku._shuffle = function(seq){313		var shuffled = [];314		for(var i = 0; i < seq.length; ++i) shuffled.push(false);315		for(var i in seq) {316			var ti = sudoku._rand_range(seq.length);317			while(shuffled[ti]) ti = (ti + 1) > (seq.length - 1) ? 0 : (ti + 1);318			shuffled[ti] = seq[i];319		}	320		return shuffled;321	};322	sudoku._rand_range = (max = 0, min = 0) => Math.floor(Math.random() * (max - min)) + min;323	sudoku._strip_dups = (seq = []) => [...new Set(seq)];324	sudoku._force_range = (nr, max = 0, min = 0) => Math.min(max || 0, Math.max(min || 0, nr));325	return sudoku;...

Using AI Code Generation

1var sudoku = new Cypress.Sudoku();2var rand = sudoku._rand_range(0,10);3console.log(rand);4Cypress.Sudoku = function() {5  this._rand_range = function(min, max) {6    return Math.floor(Math.random() * (max - min)) + min;7  };8};

Using AI Code Generation

1var sudoku = require('sudoku');2var rand = sudoku._rand_range(0, 9);3console.log(rand);4var sudoku = require('sudoku');5var rand = sudoku._rand_range(0, 9);6console.log(rand);

Using AI Code Generation

1var sudoku = require('../sudoku.js');2var assert = require('assert');3describe('sudoku', function() {4  describe('_rand_range()', function() {5    it('should return a random number between 0 and 1', function() {6      var result = sudoku._rand_range(0, 1);7      assert.equal(result >= 0 && result <= 1, true);8    });9  });10});11var sudoku = module.exports = {};12sudoku._rand_range = function(min, max) {13  return Math.random() * (max - min) + min;14};15var sudoku = require('../sudoku.js');16var assert = require('assert');17describe('sudoku', function() {18  describe('_rand_range()', function() {19    it('should return a random number between 0 and 1', function() {20      var result = sudoku._rand_range(0, 1);21      assert.equal(result >= 0 && result <= 1, true);22    });23    it('should return a random number between 1 and 2', function() {24      var result = sudoku._rand_range(1, 2);25      assert.equal(result >= 1 && result <= 2, true);26    });27    it('should return a random number between 2 and 3', function() {28      var result = sudoku._rand_range(2, 3);29      assert.equal(result >= 2 && result <= 3, true);30    });31    it('should return a random number between 3 and 4', function() {32      var result = sudoku._rand_range(3, 4);33      assert.equal(result >= 3 && result <= 4, true);34    });35    it('should return a random number between 4 and 5',

Using AI Code Generation

1var sudoku = new Cypress.Sudoku();2var random_number = sudoku._rand_range(1, 9);3console.log(random_number);4var sudoku = new Cypress.Sudoku();5var random_number = sudoku._rand_range(1, 9);6console.log(random_number);7var sudoku = new Cypress.Sudoku();8var random_number = sudoku._rand_range(1, 9);9console.log(random_number);10var sudoku = new Cypress.Sudoku();11var random_number = sudoku._rand_range(1, 9);12console.log(random_number);13var sudoku = new Cypress.Sudoku();14var random_number = sudoku._rand_range(1, 9);15console.log(random_number);16var sudoku = new Cypress.Sudoku();17var random_number = sudoku._rand_range(1, 9);18console.log(random_number);19var sudoku = new Cypress.Sudoku();20var random_number = sudoku._rand_range(1, 9);21console.log(random_number);22var sudoku = new Cypress.Sudoku();23var random_number = sudoku._rand_range(1, 9);24console.log(random_number);

Using AI Code Generation

1var sudoku = new Cypress.Sudoku();2var i = 0;3while (i < 10) {4 console.log(sudoku._rand_range(20, 40));5 i++;6}

Using AI Code Generation

1describe('sudoku', function() {2  it('should generate a random number', function() {3    cy.window().then((win) => {4      cy.stub(win.Math, 'random').returns(0.5)5      expect(win.Math.random()).to.equal(0.5)6    })7  })8})9Because this error occurred during a navigation we are unable to tell you the location in code where this originated. This is usually caused by navigation (eg cy.visit(), clicking

Using AI Code Generation

1var sudoku = new Cypress.Sudoku();2console.log(sudoku._rand_range(1, 9));3Cypress.Sudoku = function() {4    this._rand_range = function(min, max) {5        return Math.floor(Math.random() * (max - min + 1)) + min;6    };7};8Cypress.Sudoku = function() {9    this._rand_range = function(min, max) {10        return Math.floor(Math.random() * (max - min + 1)) + min;11    };12    this._rand_range2 = function(min, max) {13        return Math.floor(Math.random() * (max - min + 1)) + min;14    };15};16Cypress.Sudoku = function() {17    this._rand_range = function(min, max) {18        return Math.floor(Math.random() * (max - min + 1)) + min;19    };20    this._rand_range2 = function(min, max) {21        return Math.floor(Math.random() * (max - min + 1)) + min;22    };23    this._rand_range3 = function(min, max) {24        return Math.floor(Math.random() * (max - min + 1)) + min;25    };26};27Cypress.Sudoku = function() {28    this._rand_range = function(min, max) {29        return Math.floor(Math.random() * (max - min + 1)) + min;30    };31    this._rand_range2 = function(min, max) {32        return Math.floor(Math.random() * (max - min + 1)) + min;33    };34    this._rand_range3 = function(min, max) {35        return Math.floor(Math.random() * (max - min + 1)) + min;36    };37    this._rand_range4 = function(min, max) {38        return Math.floor(Math.random() * (max - min + 1)) + min;39    };40};41Cypress.Sudoku = function() {42    this._rand_range = function(min, max) {

Using AI Code Generation

1Cypress._rand_range = function(min, max) {2  return Math.floor(Math.random() * (max - min + 1) + min);3};4var rand = Cypress._rand_range(1, 9);5console.log(rand);6Cypress._rand_range = function(min, max) {7  return Math.floor(Math.random() * (max - min + 1) + min);8};9var rand = Cypress._rand_range(1, 9);10console.log(rand);11Cypress._rand_range = function(min, max) {12  return Math.floor(Math.random() * (max - min + 1) + min);13};14var rand = Cypress._rand_range(1, 9);15console.log(rand);16Cypress._rand_range = function(min, max) {17  return Math.floor(Math.random() * (max - min + 1) + min);18};19var rand = Cypress._rand_range(1, 9);20console.log(rand);21Cypress._rand_range = function(min, max) {22  return Math.floor(Math.random() * (max - min +

Using AI Code Generation

1var grid = Cypress.Sudoku.grid;2var row = Cypress.Sudoku._rand_range(0,8);3var col = Cypress.Sudoku._rand_range(0,8);4grid[row][col] = Cypress.Sudoku._rand_range(1,9);5var grid = Cypress.Sudoku.grid;6var row = Cypress.Sudoku._rand_range(0,8);7var col = Cypress.Sudoku._rand_range(0,8);8grid[row][col] = Cypress.Sudoku._rand_range(1,9);9var grid = Cypress.Sudoku.grid;10var row = Cypress.Sudoku._rand_range(0,8);11var col = Cypress.Sudoku._rand_range(0,8);12grid[row][col] = Cypress.Sudoku._rand_range(1,9);13var grid = Cypress.Sudoku.grid;14var row = Cypress.Sudoku._rand_range(0,8);15var col = Cypress.Sudoku._rand_range(0,8);16grid[row][col] = Cypress.Sudoku._rand_range(1,9);17var grid = Cypress.Sudoku.grid;18var row = Cypress.Sudoku._rand_range(0,8);19var col = Cypress.Sudoku._rand_range(0,8);20grid[row][col] = Cypress.Sudoku._rand_range(1,9);

Using AI Code Generation

1var sudoku = require('sudoku');2var Cypress = require('cypress');3var cypress = new Cypress();4function randRange(min, max) {5    return cypress._rand_range(min, max);6}7var puzzle = sudoku.makepuzzle();8var solution = sudoku.solvepuzzle(puzzle);9console.log('puzzle: ', puzzle);10console.log('solution: ', solution);11var puzzle = sudoku.makepuzzle();12var solution = sudoku.solvepuzzle(puzzle);13console.log('puzzle: ', puzzle);14console.log('solution: ', solution);15var puzzle = sudoku.makepuzzle();16var solution = sudoku.solvepuzzle(puzzle);17console.log('puzzle: ', puzzle);18console.log('solution: ', solution);19var puzzle = sudoku.makepuzzle();20var solution = sudoku.solvepuzzle(puzzle);21console.log('puzzle: ', puzzle);22console.log('solution: ', solution);23var puzzle = sudoku.makepuzzle();24var solution = sudoku.solvepuzzle(puzzle);25console.log('puzzle: ', puzzle);26console.log('solution: ', solution);27var puzzle = sudoku.makepuzzle();28var solution = sudoku.solvepuzzle(puzzle);29console.log('puzzle: ', puzzle);30console.log('solution: ', solution);31var puzzle = sudoku.makepuzzle();32var solution = sudoku.solvepuzzle(puzzle);33console.log('puzzle: ', puzzle);34console.log('solution: ', solution);35var puzzle = sudoku.makepuzzle();36var solution = sudoku.solvepuzzle(puzzle);37console.log('puzzle: ', puzzle);38console.log('solution: ', solution);39var puzzle = sudoku.makepuzzle();40var solution = sudoku.solvepuzzle(puzzle);41console.log('puzzle: ', puzzle);42console.log('solution: ', solution);43var puzzle = sudoku.makepuzzle();44var solution = sudoku.solvepuzzle(puzzle);45console.log('puzzle: ', puzzle);46console.log('solution: ', solution);47var puzzle = sudoku.makepuzzle();48var solution = sudoku.solvepuzzle(puzzle);49console.log('puzzle: ', puzzle);50console.log('solution: ', solution);51var puzzle = sudoku.makepuzzle();52var solution = sudoku.solvepuzzle(puzzle);53console.log('puzzle: ', puzzle);54console.log('solution: ', solution);55var puzzle = sudoku.makepuzzle();

Cypress Tutorial

Cypress is a renowned Javascript-based open-source, easy-to-use end-to-end testing framework primarily used for testing web applications. Cypress is a relatively new player in the automation testing space and has been gaining much traction lately, as evidenced by the number of Forks (2.7K) and Stars (42.1K) for the project. LambdaTest’s Cypress Tutorial covers step-by-step guides that will help you learn from the basics till you run automation tests on LambdaTest.

Chapters:

What is Cypress? -
Why Cypress? - Learn why Cypress might be a good choice for testing your web applications.
Features of Cypress Testing - Learn about features that make Cypress a powerful and flexible tool for testing web applications.
Cypress Drawbacks - Although Cypress has many strengths, it has a few limitations that you should be aware of.
Cypress Architecture - Learn more about Cypress architecture and how it is designed to be run directly in the browser, i.e., it does not have any additional servers.
Browsers Supported by Cypress - Cypress is built on top of the Electron browser, supporting all modern web browsers. Learn browsers that support Cypress.
Selenium vs Cypress: A Detailed Comparison - Compare and explore some key differences in terms of their design and features.
Cypress Learning: Best Practices - Take a deep dive into some of the best practices you should use to avoid anti-patterns in your automation tests.
How To Run Cypress Tests on LambdaTest? - Set up a LambdaTest account, and now you are all set to learn how to run Cypress tests.

Certification

You can elevate your expertise with end-to-end testing using the Cypress automation framework and stay one step ahead in your career by earning a Cypress certification. Check out our Cypress 101 Certification.