Quick Sudoku Robot

In this example below you will see how to do a Quick Sudoku Robot with some HTML / CSS and Javascript

Trying out plain JavaScript for solving a recursive search problem. I found the new Generator functionality (function* and yield) very helpful, but I'm still a Scala fan.

Thumbnail
This awesome code was written by wiebehordijk, you can see more from this user in the personal repository.
You can find the original code on Codepen.io
Copyright wiebehordijk ©

Technologies

  • HTML
  • CSS
  • JavaScript
<!DOCTYPE html>
<html lang="en" >

<head>
  <meta charset="UTF-8">
  <title>Quick Sudoku Robot</title>
  <meta name="viewport" content="width=device-width, initial-scale=1">
  
  
      <link rel="stylesheet" href="css/style.css">

  
</head>

<body>

  <section>
<header>
    <h1>Sudoku Solver</h1>
    <p></p>
<p>Enter the given numbers below</p>
</header>
<form action="solve">
<table id="sudokuTable">

    
            <tr>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell0"
            name="cell0" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell1"
            name="cell1" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell2"
            name="cell2" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell3"
            name="cell3" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell4"
            name="cell4" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell5"
            name="cell5" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell6"
            name="cell6" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell7"
            name="cell7" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell8"
            name="cell8" value="">
            </td>
            </tr>
    <tr>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell9"
            name="cell9" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell10"
            name="cell10" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell11"
            name="cell11" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell12"
            name="cell12" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell13"
            name="cell13" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell14"
            name="cell14" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell15"
            name="cell15" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell16"
            name="cell16" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell17"
            name="cell17" value="">
            </td>
            </tr>
    <tr>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell18"
            name="cell18" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell19"
            name="cell19" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell20"
            name="cell20" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell21"
            name="cell21" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell22"
            name="cell22" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell23"
            name="cell23" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell24"
            name="cell24" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell25"
            name="cell25" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell26"
            name="cell26" value="">
            </td>
            </tr>
    <tr>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell27"
            name="cell27" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell28"
            name="cell28" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell29"
            name="cell29" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell30"
            name="cell30" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell31"
            name="cell31" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell32"
            name="cell32" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell33"
            name="cell33" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell34"
            name="cell34" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell35"
            name="cell35" value="">
            </td>
            </tr>
    <tr>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell36"
            name="cell36" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell37"
            name="cell37" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell38"
            name="cell38" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell39"
            name="cell39" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell40"
            name="cell40" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell41"
            name="cell41" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell42"
            name="cell42" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell43"
            name="cell43" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell44"
            name="cell44" value="">
            </td>
            </tr>
    <tr>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell45"
            name="cell45" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell46"
            name="cell46" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell47"
            name="cell47" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell48"
            name="cell48" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell49"
            name="cell49" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell50"
            name="cell50" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell51"
            name="cell51" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell52"
            name="cell52" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell53"
            name="cell53" value="">
            </td>
            </tr>
    <tr>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell54"
            name="cell54" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell55"
            name="cell55" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell56"
            name="cell56" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell57"
            name="cell57" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell58"
            name="cell58" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell59"
            name="cell59" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell60"
            name="cell60" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell61"
            name="cell61" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell62"
            name="cell62" value="">
            </td>
            </tr>
    <tr>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell63"
            name="cell63" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell64"
            name="cell64" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell65"
            name="cell65" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell66"
            name="cell66" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell67"
            name="cell67" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell68"
            name="cell68" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell69"
            name="cell69" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell70"
            name="cell70" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell71"
            name="cell71" value="">
            </td>
            </tr>
    <tr>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell72"
            name="cell72" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell73"
            name="cell73" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell74"
            name="cell74" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell75"
            name="cell75" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell76"
            name="cell76" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell77"
            name="cell77" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell78"
            name="cell78" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell79"
            name="cell79" value="">
            </td>
                    <td>
                <input type="number" min="1" max="9" size="1" id="cell80"
            name="cell80" value="">
            </td>
            </tr>
</table>
<br>
<label for="delay">Delay in miliseconds:</label>
<select id="delay">
    <option value="10">10 ms</option>
    <option value="100">100 ms</option>
    <option value="500" selected>500 ms</option>
    <option value="1000">1000 ms</option>
</select>
<button type="submit" id="submitBtn">Solve</button>
<button type="button" id="stopBtn">Stop</button>
</form>
<p id="errorText" class="error" style="display: none"></p>
<p id="successText" class="success" style="display: none"></p>
<br>
<p><a id="testPuzzle1" href="?example=Puzzle1">Example Puzzle 1</a></p>
<p><a id="testPuzzle2" href="?example=Puzzle2">Example Puzzle 2</a></p>
<p><a id="testPuzzle3" href="?example=Puzzle3">Example Puzzle 3 (no solutions)</a></p>
<p><a id="testPuzzle4" href="?example=Puzzle4">Example Puzzle 4 (multiple solutions)</a></p>
<p><a id="testPuzzle5" href="?example=Puzzle5">Example Puzzle 5</a></p>
</section>

<script src="scripts/sudoku.js"></script>
  <script src='https://cdnjs.cloudflare.com/ajax/libs/jquery/3.1.0/jquery.min.js'></script>

  

    <script  src="js/index.js"></script>




</body>

</html>

/*Downloaded from https://www.codeseek.co/wiebehordijk/quick-sudoku-robot-aBBVNx */
table {
    border-collapse: collapse;
}

table, td {
    border: 1px solid black;
}

td {
    width: 3em;
    text-align: center;
}

td.given {
    font-weight: bold;
}

input.given {
    font-weight: bold;
    color: blue;
}

tr:nth-child(3n+0) td {
    border-bottom: 3px solid black;
}

td:nth-child(3n+0) {
    border-right: 3px solid black;
}

input {
    width: 2.5em;
    border: none;
    text-align: center;
}

.error {
    color: red;
}

.success {
    color: blue;
}

input.step {
    color: red;
    background-color: lightGrey;
}

/*Downloaded from https://www.codeseek.co/wiebehordijk/quick-sudoku-robot-aBBVNx */
"use strict";

// A Field represents a box at a given position in a Sudoku puzzle with possibly a value filled in,
// and a set of available numbers that can still be filled in.
// The parameter 'given' means that the value was given from the start.
var Field = function(row, col, value, available, given) {
    this.row = row;
    this.col = col;
    this.value = value || null;
    this.available = available || [1,2,3,4,5,6,7,8,9];
    this.given = given || false;
};

// A field is filled in when it has a value
Field.prototype.isFilledIn = function() {
    return !!this.value;
};

// Returns a field equal to this, but with one less available value
Field.prototype.without = function(n) {
    const available = this.available.filter( function(v) {
        return v !== n;
    } );
    return new Field(this.row, this.col, this.value, available, this.given);
};

// Returns a field equal to this, but with a value filled in
Field.prototype.fillIn = function(n, given) {
    return new Field(this.row, this.col, n, [n], given);
};

// Returns the field's value as a string, or else an empty string
Field.prototype.toString = function() {
    if (this.value === null) return "";
    else return "" + this.value;
};

// Fields are related if they are on the same row, column or in the same 3x3 square
Field.prototype.related = function(that) {
    if (that.constructor != Field) return false;
    if (this.row === that.row) return true;
    if (this.col === that.col) return true;
    if ((Math.floor(this.row / 3) === Math.floor(that.row / 3)) &&
        (Math.floor(this.col / 3) === Math.floor(that.col / 3))) return true;
    return false;
};

// Returns whether the fields are at the same position
Field.prototype.samePos = function(that) {
    if (that.constructor != Field) return false;
    return ((this.row === that.row) && (this.col === that.col));
};


// A Matrix represents a Sudoku puzzle, consisting of Fields
var Matrix = function(fields) {
    this.fields = fields;
};

// Returns an empty matrix, that is, a matrix with empty fields
Matrix.prototype.empty = function() {
    var fields = [];
    for (var row = 0; row < 9; row++) {
        for (var col = 0; col < 9; col++) {
            fields[row * 9 + col] = new Field(row, col);
        }
    }
    return new Matrix(fields);
};

// Turns a string with one line per row, columns separated by pipe symbols, into a matrix
Matrix.prototype.fromStringWithPipes = function(string) {
    var matrix = Matrix.prototype.empty();
    const lines = string.split("\n");
    lines.forEach(function(line, row) {
        const vals = line.split("|");
        vals.forEach(function(val, col) {
            var value = null;
            if (val !== " ") {
                value = Number(val);
                matrix = matrix.fillInGiven(new Field(row, col, value));
            }
        });
    });
    return matrix;
};

// Turns a matrix into a string with one line per row, columns separated by pipe symbols
Matrix.prototype.toString = function() {
    var result = "";
    for (var row = 0; row < 9; row++) {
        for (var col = 0; col < 9; col++) {
            const field = this.field(row, col);
            if (field.isFilledIn()) result += field.value;
            else result += " ";
            if (col < 8) result += "|";
        }
        if (row < 8) result += "\n";
    }
    return result;
};

// Returns the field at the given position
Matrix.prototype.field = function(row, col) {
    if ((row < 0) || (row > 8) || (col < 0) || (col > 8))
        throw new Error("row and col must be between 0 and 8");
    return this.fields[row * 9 + col];
};

// Returns a matrix equal to this, but with one field filled in.
// The value filled in becomes unavailable in all related fields.
Matrix.prototype.fillIn = function(field, value, given) {
    const newFields = this.fields.map(function(f) {
        if (field.samePos(f)) return f.fillIn(value, given);
        else if (field.related(f)) return f.without(value);
        else return f;
    });
    return new Matrix(newFields);
};

// During search, fields are filled in with the parameter 'given' set to false
Matrix.prototype.fillInSearch = function(field, value) {
    return this.fillIn(field, value, false);
};

// When setting up the initial matrix, fields with a given value have 'given' set to true
Matrix.prototype.fillInGiven = function(field) {
    return this.fillIn(field, field.value, true);
};

// A matrix is a solution when every field is filled in
Matrix.prototype.isSolution = function() {
    return this.fields.every(function(f) { return f.isFilledIn(); });
};

// A matrix is a dead end when there is a field without any available values to fill in
Matrix.prototype.isDeadEnd = function() {
    return this.fields.some(function(f) { return f.available.length === 0; });
};


// Helper function for the problem solving algorithm. For every search step, we expand the search space
// by filling in an available value in one of the fields. If a field has fewer available values, then
// filling in a value for that field will lead to a solution faster than doing so for a field with many
// available values. This function finds the field with the least available values that is not filled in.
function fieldWithLeastAvailableValues(matrix) {
    var leastField = null;
    var leastAvailable = 9;
    matrix.fields.forEach(function(field) {
        if (!field.isFilledIn()) {
            if (field.available.length < leastAvailable || leastField === null) {
                leastField = field;
                leastAvailable = field.available.length;
                if (leastAvailable === 1) return field;
            }
        }
    });
    return leastField;
}

// Solver function. This function recurses depth-first through the search space. For a matrix that is
// not a solution or a dead end, it takes the field with the smallest number of available values, and
// tries filling in every available value in that field, and recurses into the matrix yielded by
// filling in that value. The function yields every step, and when a solution is found, it yields the solution.
// When no solution is found, the function returns null.
function* solve(matrix) {
    if (matrix.isSolution()) yield {"matrix": matrix, "field" : null, "value" : null, "solution" : true};
    else if (matrix.isDeadEnd()) return null;
    else {
        const field = fieldWithLeastAvailableValues(matrix);
        if (field === null) return null;
        for (const value of field.available) {
            const newMatrix = matrix.fillInSearch(field, value);
            yield {"matrix": matrix, "field" : field, "value" : value, "solution" : false};
            yield* solve(newMatrix);
        }
    }
}


// From here on we have functions that operate on the web page.

// Turns a table with input values into a matrix
function inputToMatrix() {
    var matrix = Matrix.prototype.empty();
    for (var row = 0; row < 9; row++) {
        for (var col = 0; col < 9; col++) {
            var cell = $("#cell" + (row * 9 + col));
            // Do not take intermediate solution values as given
            if (cell.hasClass("given") && cell.val()) {
                matrix = matrix.fillInGiven(new Field(row, col, cell.val()));
            }
        }
    }
    return matrix;
}

// Shows a matrix in the table
function showMatrix(matrix) {
    for (var row = 0; row < 9; row++) {
        for (var col = 0; col < 9; col++) {
            var cell = $("#cell" + (row * 9 + col));
            cell.val(matrix.field(row, col).value);
            cell.removeClass("step");
            if (matrix.field(row, col).given) cell.addClass("given");
            else cell.removeClass("given");
        }
    }
}

// Shows an error message. Type can be 'success' or 'error'.
function showMessage(message, type) {
    const text = $("#" + type + "Text");
    text.text(message);
    text.fadeIn();
}

// Clears any error/success messages
function clearMessage(type) {
    const text = $("#" + type + "Text");
    text.text("");
    text.fadeOut();
}

// Shows an intermediate step
function showStep(matrix, field, value) {
    showMatrix(matrix);
    var cell = $("#cell" + (field.row * 9 + field.col));
    cell.val(value);
    cell.addClass("step");
}

// Advances the solution process by one step, shows the step, and shows an error or the solution if found
function solveStep(solver, timer) {
    var next = solver.next();
    if (next.done) {      // No solution found
        showMessage("No solution found", "error");
        clearInterval(timer);
    }
    else if (next.value.solution) {
        showMessage("Solution found!", "success");
        clearInterval(timer);
    }
    else {
        showStep(next.value.matrix, next.value.field, next.value.value);
    }
}

// Starts the process of solving the puzzle with a delay between each two steps
function startSolve(e) {
    e.preventDefault();
    clearMessage("error");
    clearMessage("success");
    const matrix = inputToMatrix();
    const solver = solve(matrix);
    const timer = setInterval(function() {
        solveStep(solver, timer);
    }, $("#delay").val());
    $("#stopBtn").click( function() {
        clearInterval(timer);
    });
}

// Makes sure a cell only has one digit, and has the class 'given' when a number is filled in
function guardInput(cell) {
    if (cell.value == "") {
        cell.classList.remove("given");
    }
    else {
        if (cell.value.length > 1)
            cell.value = cell.value.substring(0, 1);
        const num = Number(cell.value);
        if (isNaN(num)) {
            cell.value = "";
            cell.classList.remove("given");
        }
        else {
            cell.classList.add("given");
        }
    }
}


// Test puzzles
var testPuzzles = {
"testPuzzle1" : "5| |1| |2| | | | \n7| |8|4|6|9|5|3|1\n4|6| | | | | | |8\n |5| | | | |6|9|4\n | | |6| |4| |5| \n |9| |3| |7|1|8| \n2|1|5|8|7| |9| | \n | |3|9|4|6| | |5\n9|4| |2| |5|8| |3",
"testPuzzle2" : " | |8| |9| |1|4|5\n7| |2| | | | | | \n | |5| |3| | | | \n3| | | | |9|4| | \n | | | |5| |3| |7\n | | | | | | |2| \n | |6|2| | | | | \n | | | |1|4|9| | \n |1| | | | | |7| ",
"testPuzzle3" : "5| |1| |2| | |4| \n7| |8|4|6|9|5|3|1\n4|6| | | | | | |8\n |5| | | | |6|9|4\n | | |6| |4| |5| \n |9| |3| |7|1|8| \n2|1|5|8|7| |9| | \n | |3|9|4|6| | |5\n9|4| |2| |5|8| |3",
"testPuzzle4" : " | |8| |9| |1|4|5\n7| |2| | | | | | \n | |5| |3| | | | \n3| | | | |9|4| | \n | | | |5| |3| | \n | | | | | | |2| \n | |6|2| | | | | \n | | | |1|4|9| | \n |1| | | | | |7| ",
"testPuzzle5" : " | | | |2| | |4|9\n1|2| | | |9| | | \n5| | |7| |6| | | \n8|7|1| | | | | | \n6| | | |9| |8| | \n | |5| | | | | |2\n | |7|3| | | | |4\n | | | |5| | |6| \n9| | | |6| | | |8"
};


// Page initialization
$(document).ready(function() {

    // Handlers for the test puzzle links
    $("a").click(function(e) {
        e.preventDefault();
        const matrix = Matrix.prototype.fromStringWithPipes(testPuzzles[this.id]);
        showMatrix(matrix);
    });

    // Handlers for the input fields in the matrix
    $("input").on("input", function() {
        guardInput(this);
    });

    // Handler for the Solve button
    $("#submitBtn").click(startSolve);
});

Comments