How to use sudoku.validate_board method in Cypress

...182        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];
...

...146    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) {...

...396// Utility397// =======398module("Utility");399test("Validate board", function(){400   var report_empty             = sudoku.validate_board();401   var report_invalid_size      = sudoku.validate_board("123");402   var report_invalid_char      = sudoku.validate_board(403        ".3.9564272..784136764231589327149658.4.56..73..637._14412893765.8.627"+404        "341673415892");405   var report_good              = sudoku.validate_board(406        ".3.9564272..784136764231589327149658.4.56..73..637..14412893765.8.627"+407        "341673415892");408   409   ok(report_empty !== true);410   ok(report_invalid_size !== true);411   ok(report_invalid_char !== true);412   ok(report_good);413});414test("Cross product", function(){415    // Simple case416    deepEqual(sudoku._cross('a','1'), ["a1"], "Simple case");417    // Classic case418    deepEqual(419        sudoku._cross("abc", "123"),...

...154    possibilities in reverse. Useful for checking if there is more than one155    solution.156    */157    // Assure a valid board158    var report = sudoku.validate_board(board);159    if (report !== true) {160      throw report;161    }162    // Check number of givens is at least MIN_GIVENS163    var nr_givens = 0;164    for (var i in board) {165      if (board[i] !== sudoku.BLANK_CHAR && sudoku._in(board[i], sudoku.DIGITS)) {166        ++nr_givens;167      }168    }169    if (nr_givens < MIN_GIVENS) {170      throw "Too few givens. Minimum givens is " + MIN_GIVENS;171    }172    // Default reverse to false173    reverse = reverse || false;174    var candidates = sudoku._get_candidates_map(board);175    var result = sudoku._search(candidates, reverse);176    if (result) {177      var solution = "";178      for (var square in result) {179        solution += result[square];180      }181      return solution;182    }183    return false;184  };185  sudoku.get_candidates = function (board) {186    /* Return all possible candidatees for each square as a grid of 187    candidates, returnning `false` if a contradiction is encountered.188    189    Really just a wrapper for sudoku._get_candidates_map for programmer190    consumption.191    */192    // Assure a valid board193    var report = sudoku.validate_board(board);194    if (report !== true) {195      throw report;196    }197    // Get a candidates map198    var candidates_map = sudoku._get_candidates_map(board);199    // If there's an error, return false200    if (!candidates_map) {201      return false;202    }203    // Transform candidates map into grid204    var rows = [];205    var cur_row = [];206    var i = 0;207    for (var square in candidates_map) {208      var candidates = candidates_map[square];209      cur_row.push(candidates);210      if (i % 9 == 8) {211        rows.push(cur_row);212        cur_row = [];213      }214      ++i;215    }216    return rows;217  }218  sudoku._get_candidates_map = function (board) {219    /* Get all possible candidates for each square as a map in the form220    {square: sudoku.DIGITS} using recursive constraint propagation. Return `false` 221    if a contradiction is encountered222    */223    // Assure a valid board224    var report = sudoku.validate_board(board);225    if (report !== true) {226      throw report;227    }228    var candidate_map = {};229    var squares_values_map = sudoku._get_square_vals_map(board);230    // Start by assigning every digit as a candidate to every square231    for (var si in SQUARES) {232      candidate_map[SQUARES[si]] = sudoku.DIGITS;233    }234    // For each non-blank square, assign its value in the candidate map and235    // propigate.236    for (var square in squares_values_map) {237      var val = squares_values_map[square];238      if (sudoku._in(val, sudoku.DIGITS)) {239        var new_candidates = sudoku._assign(candidate_map, square, val);240        // Fail if we can't assign val to square241        if (!new_candidates) {242          return false;243        }244      }245    }246    return candidate_map;247  };248  sudoku._search = function (candidates, reverse) {249    /* Given a map of squares -> candiates, using depth-first search, 250    recursively try all possible values until a solution is found, or false251    if no solution exists. 252    */253    // Return if error in previous iteration254    if (!candidates) {255      return false;256    }257    // Default reverse to false258    reverse = reverse || false;259    // If only one candidate for every square, we've a solved puzzle!260    // Return the candidates map.261    var max_nr_candidates = 0;262    var max_candidates_square = null;263    for (var si in SQUARES) {264      var square = SQUARES[si];265      var nr_candidates = candidates[square].length;266      if (nr_candidates > max_nr_candidates) {267        max_nr_candidates = nr_candidates;268        max_candidates_square = square;269      }270    }271    if (max_nr_candidates === 1) {272      return candidates;273    }274    // Choose the blank square with the fewest possibilities > 1275    var min_nr_candidates = 10;276    var min_candidates_square = null;277    for (si in SQUARES) {278      var square = SQUARES[si];279      var nr_candidates = candidates[square].length;280      if (nr_candidates < min_nr_candidates && nr_candidates > 1) {281        min_nr_candidates = nr_candidates;282        min_candidates_square = square;283      }284    }285    // Recursively search through each of the candidates of the square 286    // starting with the one with fewest candidates.287    // Rotate through the candidates forwards288    var min_candidates = candidates[min_candidates_square];289    if (!reverse) {290      for (var vi in min_candidates) {291        var val = min_candidates[vi];292        // TODO: Implement a non-rediculous deep copy function293        var candidates_copy = JSON.parse(JSON.stringify(candidates));294        var candidates_next = sudoku._search(295          sudoku._assign(candidates_copy, min_candidates_square, val)296        );297        if (candidates_next) {298          return candidates_next;299        }300      }301      // Rotate through the candidates backwards302    } else {303      for (var vi = min_candidates.length - 1; vi >= 0; --vi) {304        var val = min_candidates[vi];305        // TODO: Implement a non-rediculous deep copy function306        var candidates_copy = JSON.parse(JSON.stringify(candidates));307        var candidates_next = sudoku._search(308          sudoku._assign(candidates_copy, min_candidates_square, val),309          reverse310        );311        if (candidates_next) {312          return candidates_next;313        }314      }315    }316    // If we get through all combinations of the square with the fewest317    // candidates without finding an answer, there isn't one. Return false.318    return false;319  };320  sudoku._assign = function (candidates, square, val) {321    /* Eliminate all values, *except* for `val`, from `candidates` at 322    `square` (candidates[square]), and propagate. Return the candidates map323    when finished. If a contradiciton is found, return false.324    325    WARNING: This will modify the contents of `candidates` directly.326    */327    // Grab a list of canidates without 'val'328    var other_vals = candidates[square].replace(val, "");329    // Loop through all other values and eliminate them from the candidates 330    // at the current square, and propigate. If at any point we get a 331    // contradiction, return false.332    for (var ovi in other_vals) {333      var other_val = other_vals[ovi];334      var candidates_next =335        sudoku._eliminate(candidates, square, other_val);336      if (!candidates_next) {337        //console.log("Contradiction found by _eliminate.");338        return false;339      }340    }341    return candidates;342  };343  sudoku._eliminate = function (candidates, square, val) {344    /* Eliminate `val` from `candidates` at `square`, (candidates[square]),345    and propagate when values or places <= 2. Return updated candidates,346    unless a contradiction is detected, in which case, return false.347    348    WARNING: This will modify the contents of `candidates` directly.349    */350    // If `val` has already been eliminated from candidates[square], return351    // with candidates.352    if (!sudoku._in(val, candidates[square])) {353      return candidates;354    }355    // Remove `val` from candidates[square]356    candidates[square] = candidates[square].replace(val, '');357    // If the square has only candidate left, eliminate that value from its 358    // peers359    var nr_candidates = candidates[square].length;360    if (nr_candidates === 1) {361      var target_val = candidates[square];362      for (var pi in SQUARE_PEERS_MAP[square]) {363        var peer = SQUARE_PEERS_MAP[square][pi];364        var candidates_new =365          sudoku._eliminate(candidates, peer, target_val);366        if (!candidates_new) {367          return false;368        }369      }370      // Otherwise, if the square has no candidates, we have a contradiction.371      // Return false.372    }373    if (nr_candidates === 0) {374      return false;375    }376    // If a unit is reduced to only one place for a value, then assign it377    for (var ui in SQUARE_UNITS_MAP[square]) {378      var unit = SQUARE_UNITS_MAP[square][ui];379      var val_places = [];380      for (var si in unit) {381        var unit_square = unit[si];382        if (sudoku._in(val, candidates[unit_square])) {383          val_places.push(unit_square);384        }385      }386      // If there's no place for this value, we have a contradition!387      // return false388      if (val_places.length === 0) {389        return false;390        // Otherwise the value can only be in one place. Assign it there.391      } else if (val_places.length === 1) {392        var candidates_new =393          sudoku._assign(candidates, val_places[0], val);394        if (!candidates_new) {395          return false;396        }397      }398    }399    return candidates;400  };401  // Square relationships402  // -------------------------------------------------------------------------403  // Squares, and their relationships with values, units, and peers.404  sudoku._get_square_vals_map = function (board) {405    /* Return a map of squares -> values406     */407    var squares_vals_map = {};408    // Make sure `board` is a string of length 81409    if (board.length != SQUARES.length) {410      throw "Board/squares length mismatch.";411    } else {412      for (var i in SQUARES) {413        squares_vals_map[SQUARES[i]] = board[i];414      }415    }416    return squares_vals_map;417  };418  sudoku._get_square_units_map = function (squares, units) {419    /* Return a map of `squares` and their associated units (row, col, box)420     */421    var square_unit_map = {};422    // For every square...423    for (var si in squares) {424      var cur_square = squares[si];425      // Maintain a list of the current square's units426      var cur_square_units = [];427      // Look through the units, and see if the current square is in it,428      // and if so, add it to the list of of the square's units.429      for (var ui in units) {430        var cur_unit = units[ui];431        if (cur_unit.indexOf(cur_square) !== -1) {432          cur_square_units.push(cur_unit);433        }434      }435      // Save the current square and its units to the map436      square_unit_map[cur_square] = cur_square_units;437    }438    return square_unit_map;439  };440  sudoku._get_square_peers_map = function (squares, units_map) {441    /* Return a map of `squares` and their associated peers, i.e., a set of442    other squares in the square's unit.443    */444    var square_peers_map = {};445    // For every square...446    for (var si in squares) {447      var cur_square = squares[si];448      var cur_square_units = units_map[cur_square];449      // Maintain list of the current square's peers450      var cur_square_peers = [];451      // Look through the current square's units map...452      for (var sui in cur_square_units) {453        var cur_unit = cur_square_units[sui];454        for (var ui in cur_unit) {455          var cur_unit_square = cur_unit[ui];456          if (cur_square_peers.indexOf(cur_unit_square) === -1 &&457            cur_unit_square !== cur_square) {458            cur_square_peers.push(cur_unit_square);459          }460        }461      }462      // Save the current square an its associated peers to the map463      square_peers_map[cur_square] = cur_square_peers;464    }465    return square_peers_map;466  };467  sudoku._get_all_units = function (rows, cols) {468    /* Return a list of all units (rows, cols, boxes)469     */470    var units = [];471    // Rows472    for (var ri in rows) {473      units.push(sudoku._cross(rows[ri], cols));474    }475    // Columns476    for (var ci in cols) {477      units.push(sudoku._cross(rows, cols[ci]));478    }479    // Boxes480    var row_squares = ["ABC", "DEF", "GHI"];481    var col_squares = ["123", "456", "789"];482    for (var rsi in row_squares) {483      for (var csi in col_squares) {484        units.push(sudoku._cross(row_squares[rsi], col_squares[csi]));485      }486    }487    return units;488  };489  // Conversions490  // -------------------------------------------------------------------------491  sudoku.board_string_to_grid = function (board_string) {492    /* Convert a board string to a two-dimensional array493     */494    var rows = [];495    var cur_row = [];496    for (var i in board_string) {497      cur_row.push(board_string[i]);498      if (i % 9 == 8) {499        rows.push(cur_row);500        cur_row = [];501      }502    }503    return rows;504  };505  sudoku.board_grid_to_string = function (board_grid) {506    /* Convert a board grid to a string507     */508    var board_string = "";509    for (var r = 0; r < 9; ++r) {510      for (var c = 0; c < 9; ++c) {511        board_string += board_grid[r][c];512      }513    }514    return board_string;515  };516  // Utility517  // -------------------------------------------------------------------------518  sudoku.print_board = function (board) {519    /* Print a sudoku `board` to the console.520     */521    // Assure a valid board522    var report = sudoku.validate_board(board);523    if (report !== true) {524      throw report;525    }526    var V_PADDING = " "; // Insert after each square527    var H_PADDING = '\n'; // Insert after each row528    var V_BOX_PADDING = "  "; // Box vertical padding529    var H_BOX_PADDING = '\n'; // Box horizontal padding530    var display_string = "";531    for (var i in board) {532      var square = board[i];533      // Add the square and some padding534      display_string += square + V_PADDING;535      // Vertical edge of a box, insert v. box padding536      if (i % 3 === 2) {...

...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            ...

...15export function print_board(board) {16  return sudoku.print_board(board)17}18export function validate_board(board) {19  return sudoku.validate_board(board)20}...