sudoku.js

const board = `
    _ _ _  _ _ _  _ 3 _
    _ _ _  _ _ _  _ _ 6
    _ 3 _  _ _ _  _ _ _

    _ _ 1  _ _ _  _ _ _
    _ _ _  _ _ _  _ _ _
    _ _ _  3 _ _  _ _ _

    _ _ _  _ 1 _  _ _ _
    _ _ _  _ _ 3  _ _ _
    _ _ _  _ _ _  6 _ _
`;

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

const FD = require('fdjs');

var rows = ['A','B','C','D','E','F','G','H','I'];
var cols = ['1','2','3','4','5','6','7','8','9'];

// (I did not write this myself; I was going to, but saw that
// fd.js had this exact thing already written as part of its
// test suite - I just wrote a simple CLI wrapper around it
// instead of its HTML test harness -- Qix-)
function sudoku(board) {
    return function (S) {
        var root = [];
        var i, j, k, i2, j2;

        // Declare board places.
        for (i = 0; i < 9; ++i) {
            for (j = 0; j < 9; ++j) {
                root.push(rows[i] + cols[j]);
            }
        }

        S.decl(root, [[1,9]]);

        // Add row constraints.
        for (i = 0; i < 9; ++i) {
            k = [];
            for (j = 0; j < 9; ++j) {
                k.push(rows[i] + cols[j]);
            }
            S.distinct(k);
        }

        // Add column constraints
        for (i = 0; i < 9; ++i) {
            k = [];
            for (j = 0; j < 9; ++j) {
                k.push(rows[j] + cols[i]);
            }
            S.distinct(k);
        }

        // Add box constraints.
        for (i = 0; i < 3; ++i) {
            for (j = 0; j < 3; ++j) {
                k = [];
                for (i2 = 0; i2 < 3; ++i2) {
                    for (j2 = 0; j2 < 3; ++j2) {
                        k.push(rows[i * 3 + i2] + cols[j * 3 + j2]);
                    }
                }
                S.distinct(k);
            }
        }

        // Initialize the board.
        for (i in board) {
            S.num(i, board[i]);
        }

        // Distribution strategy is fail first, since that is
        // likely to cause maximum propagation for this puzzle.
        FD.distribute.fail_first(S, root);
        return S;
    };
}

function parse_board(b) {
    let pieces = [];
    let reg = /[_0-9]/g;
    let match;
    while (match = reg.exec(b)) {
        pieces.push(match[0]);
    }

    let board = {};
    for (let i = 0; i < 81; ++i) {
        if (pieces[i] !== '_') {
            board[rows[Math.floor(i / 9)] + cols[i % 9]] = parseInt(pieces[i]);
        }
    }

    return board;
}

function format_board(original, s) {
    let b = '';
    for (let i = 0; i < 9; ++i) {
        for (let j = 0; j < 9; ++j) {
            let v = s[rows[i] + cols[j]];
            v = v ? v : '_';

            let o = original[rows[i] + cols[j]];
            if (o != null) {
                v = o == v ? `\x1b[92m${v}\x1b[0m` : `\x1b[91m${v}\x1b[0m`;
            }

            b += v ? v : '_';
            b += ' ';

            if (j % 3 === 2) {
                b += ' ';
            }
        }
        b += '\n';

        if (i % 3 === 2) {
            b += '\n';
        }
    }
    return b;
}

let b = parse_board(board);
let S = sudoku(b)(new FD.space());
if (!S) { throw new Error('Failed to create space'); }
let state = {space: S};
state = FD.search.depth_first(state);

if (state.status === 'solved') {
    console.log(format_board(b, state.space.solution()));
} else {
    console.log('No solution found');
}