[es6][javascript] 10 lines Sudoku Solver by ES6 generator

sudoku-backtrack.js

"use strict"; // enable "block scope" `const` on iojs

// usual backtrack style sudoku solver
var sudoku = function* (board) {
    // used number data in each row/column/block as bitfield
    const masks = [0, 1<<0, 1<<1, 1<<2, 1<<3, 1<<4, 1<<5, 1<<6, 1<<7, 1<<8];
    const rows = [0, 0, 0, 0, 0, 0, 0, 0, 0];
    const cols = [0, 0, 0, 0, 0, 0, 0, 0, 0];
    const blks = [0, 0, 0, 0, 0, 0, 0, 0, 0];

    // row/column/block index from board index
    const row = function (i) {return 0|(i / 9);};
    const col = function (i) {return i % 9;};
    const blk = function (i) {return (0|i / 27) * 3 + (0|i % 9 / 3);};

    // collect used number data from the initial board
    for (var i = 0; i < 81; i++) {
        const mask = masks[board[i]];
        rows[row(i)] |= mask, cols[col(i)] |= mask, blks[blk(i)] |= mask;
    }

    // backtrack solver
    var solve = function* solve(i) {
        if (i === 81) return yield board;
        if (board[i] !== 0) return yield* solve(i + 1);
        
        const r = row(i), c = col(i), b = blk(i);
        const used = rows[r] | cols[c] | blks[b];
        for (var v = 1; v <= 9; v++) {
            const mask = masks[v];
            if (used & mask) continue;
            board[i] = v;
            rows[r] |= mask, cols[c] |= mask, blks[b] |= mask;
            yield* solve(i + 1);
            rows[r] &= ~mask, cols[c] &= ~mask, blks[b] &= ~mask;
            board[i] = 0;
        }
    };
    // run solver
    yield* solve(0);
};

var format = function (board) {
    var split = function (a, n) {
        var r = [];
        for (var i = 0; i < a.length; i += n) r.push(a.slice(i, i + n));
        return r;
    };

    var lines = split(board, 9).map(function (line) {
        return split(line, 3).map(function (c3) {
            return c3.join("");
        }).join("|");
    });
    return split(lines, 3).map(function (l3) {
        return l3.join("\n");
    }).join("\n---+---+---\n");
};


// example case from http://rosettacode.org/wiki/Sudoku
var problem = [
    8, 5, 0, 0, 0, 2, 4, 0, 0,
    7, 2, 0, 0, 0, 0, 0, 0, 9,
    0, 0, 4, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 1, 0, 7, 0, 0, 2,
    3, 0, 5, 0, 0, 0, 9, 0, 0,
    0, 4, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 8, 0, 0, 7, 0,
    0, 1, 7, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 3, 6, 0, 4, 0
];

for (var solution of sudoku(problem, 0)) {
    console.log(format(solution));
}

sudoku-function.js

// 11 lines Sudoku Solver 

// structure of board b: 81-element flat-array of 1-9 or 0 as blank cell
var solve = function solve(b, i) {
    if (i === 81) return b; // <= solution
    if (b[i] !== 0) return solve(b, i + 1);
    var used = b.filter(function (_, j) {
        return (i % 9) === (j % 9) || (0|i / 9) === (0|j / 9) ||
            (0|i / 27) === (0|j / 27) && (0|i % 9 / 3) === (0|j % 9 / 3);
    });
    for (var v = 1; v <= 9; v++) if (used.indexOf(v) === -1) {
        var r = solve(b.slice(0, i).concat([v]).concat(b.slice(i + 1)), i + 1);
        if (r) return r;
    }
};


// for output board
var format = function (board) {
    var split = function (a, n) {
        var r = [];
        for (var i = 0; i < a.length; i += n) r.push(a.slice(i, i + n));
        return r;
    };
    
    var lines = split(board, 9).map(function (line) {
        return split(line, 3).map(function (c3) {
            return c3.join("");
        }).join("|");
    });
    return split(lines, 3).map(function (l3) {
        return l3.join("\n");
    }).join("\n---+---+---\n");
};


// example case from http://rosettacode.org/wiki/Sudoku
var problem = [
    8, 5, 0, 0, 0, 2, 4, 0, 0,
    7, 2, 0, 0, 0, 0, 0, 0, 9,
    0, 0, 4, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 1, 0, 7, 0, 0, 2,
    3, 0, 5, 0, 0, 0, 9, 0, 0,
    0, 4, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 8, 0, 0, 7, 0,
    0, 1, 7, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 3, 6, 0, 4, 0
];
//console.log(format(problem);
var solution = solve(problem, 0);
console.log(format(solution));

sudoku-list.js

// 11 lines Sudoku Solver 

// structure of board b: 81-element flat-array of 1-9 or 0 as blank cell
var solve = function solve(b, i) {
    if (i === 81) return [b]; // <= solution
    if (b[i] !== 0) return solve(b, i + 1);
    var used = b.filter(function (_, j) {
        return (i % 9) === (j % 9) || (0|i / 9) === (0|j / 9) ||
            (0|i / 27) === (0|j / 27) && (0|i % 9 / 3) === (0|j % 9 / 3);
    });
    var before = b.slice(0, i), after = b.slice(i + 1), r = [];
    for (var v = 1; v <= 9; v++) if (used.indexOf(v) === -1) 
        r = r.concat(solve(before.concat([v]).concat(after), i + 1));
    return r;
};


// for output board
var format = function (board) {
    var split = function (a, n) {
        var r = [];
        for (var i = 0; i < a.length; i += n) r.push(a.slice(i, i + n));
        return r;
    };
    
    var lines = split(board, 9).map(function (line) {
        return split(line, 3).map(function (c3) {
            return c3.join("");
        }).join("|");
    });
    return split(lines, 3).map(function (l3) {
        return l3.join("\n");
    }).join("\n---+---+---\n");
};


// example case from http://rosettacode.org/wiki/Sudoku
var problem = [
    8, 5, 0, 0, 0, 2, 4, 0, 0,
    7, 2, 0, 0, 0, 0, 0, 0, 9,
    0, 0, 4, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 1, 0, 7, 0, 0, 2,
    3, 0, 5, 0, 0, 0, 9, 0, 0,
    0, 4, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 8, 0, 0, 7, 0,
    0, 1, 7, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 3, 6, 0, 4, 0
];
//console.log(format(problem);
var solutions = solve(problem, 0);
solutions.forEach(function (solution) {
    console.log(format(solution));
});

sudoku.c

// sudoku solver in C11: clang -Wall -Wextra -O3 -std=c11 sudoku.c -o sudoku
#include <stdio.h>

// helpers for board data
static const unsigned MASKS[] = {
  0, 1 << 0, 1 << 1, 1 << 2, 1 << 3, 1 << 4, 1 << 5, 1 << 6, 1 << 7, 1 << 8};
static inline unsigned row(unsigned i) {return i / 9;}
static inline unsigned col(unsigned i) {return i % 9;}
static inline unsigned blk(unsigned i) {return i / 27 * 3 + i % 9 / 3;}
static void output(unsigned board[])
{
  for (unsigned y = 0; y < 9; y++) {
    for (unsigned x = 0; x < 9; x++) {
      putchar(board[y * 9 + x] > 0 ? board[y * 9 + x] + '0' : '.');
      if (x % 3 == 2) putchar(x == 8 ? '\n' : '|');
    }
    if (y % 3 == 2) puts(y == 8 ? "" : "---+---+---");
  }
}

// sudoku solver
typedef struct {
  unsigned board[81];
  unsigned rows[9], cols[9], blks[9];
} sudoku_t;

static void sudoku_init(sudoku_t* s, unsigned board[])
{
  for (unsigned i = 0; i < 81; i++) {
    const unsigned mask = MASKS[board[i]];
    s->rows[row(i)] |= mask, s->cols[col(i)] |= mask, s->blks[blk(i)] |= mask;
    s->board[i] = board[i];
  }
}

static void sudoku_solve(sudoku_t* s, unsigned i)
{
  if (i == 81) {
    output(s->board);
  } else if (s->board[i] != 0) {
    sudoku_solve(s, i + 1);
  } else {
    const unsigned r = row(i), c = col(i), b = blk(i);
    const unsigned used = s->rows[r] | s->cols[c] | s->blks[b];
    for (unsigned v = 1; v <= 9; v++) {
      const unsigned mask = MASKS[v];
      if (used & mask) continue;
      s->board[i] = v;
      s->rows[r] |= mask, s->cols[c] |= mask, s->blks[b] |= mask;
      sudoku_solve(s, i + 1);
      s->rows[r] &= ~mask, s->cols[c] &= ~mask, s->blks[b] &= ~mask;
      s->board[i] = 0;
    }
  }
}

void sudoku(unsigned board[])
{
  sudoku_t s = {.board = {0}, .rows = {0}, .cols = {0}, .blks = {0}};
  sudoku_init(&s, board);
  sudoku_solve(&s, 0);
}

// example problem from http://rosettacode.org/wiki/Sudoku
static unsigned problem[] = {
  8, 5, 0, 0, 0, 2, 4, 0, 0,
  7, 2, 0, 0, 0, 0, 0, 0, 9,
  0, 0, 4, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 1, 0, 7, 0, 0, 2,
  3, 0, 5, 0, 0, 0, 9, 0, 0,
  0, 4, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 8, 0, 0, 7, 0,
  0, 1, 7, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 3, 6, 0, 4, 0
};

int main(int argc, char* argv[])
{
  if (argc <= 1) {
    puts("[problem]");
    output(problem);
    puts("[solution]");
    sudoku(problem);
  } else {
    for (int i = 1; i < argc; i++) {
      char ch = -1;
      for (int c = 0; c < 81; c++) {
        if (ch == '\0') {
          problem[c] = 0;
        } else {
          ch = argv[i][c];
          problem[c] = '0' <= ch && ch <= '9' ? ch - '0' : 0;
        }
      }
      puts("[problem]");
      output(problem);
      puts("[solution]");
      sudoku(problem);
    }
  }
  return 0;
}

sudoku.js

// 10 lines Sudoku Solver as ES6 generator

// structure of board b: 81-element flat-array of 1-9 or 0 as blank cell
var solve = function* solve(b, i) {
    if (i === 81) return yield b; // <= solution
    if (b[i] !== 0) return yield* solve(b, i + 1);
    var used = b.filter(function (_, j) {
        return (i % 9) === (j % 9) || (0|i / 9) === (0|j / 9) ||
            (0|i / 27) === (0|j / 27) && (0|i % 9 / 3) === (0|j % 9 / 3);
    });
    for (var v = 1; v <= 9; v++) if (used.indexOf(v) === -1) 
        yield* solve(b.slice(0, i).concat([v]).concat(b.slice(i + 1)), i + 1);
};


// for output board
var format = function (board) {
    var split = function (a, n) {
        var r = [];
        for (var i = 0; i < a.length; i += n) r.push(a.slice(i, i + n));
        return r;
    };
    
    var lines = split(board, 9).map(function (line) {
        return split(line, 3).map(function (c3) {
            return c3.join("");
        }).join("|");
    });
    return split(lines, 3).map(function (l3) {
        return l3.join("\n");
    }).join("\n---+---+---\n");
};


// example case from http://rosettacode.org/wiki/Sudoku
var problem = [
    8, 5, 0, 0, 0, 2, 4, 0, 0,
    7, 2, 0, 0, 0, 0, 0, 0, 9,
    0, 0, 4, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 1, 0, 7, 0, 0, 2,
    3, 0, 5, 0, 0, 0, 9, 0, 0,
    0, 4, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 8, 0, 0, 7, 0,
    0, 1, 7, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 3, 6, 0, 4, 0
];
//console.log(format(problem);
for (var solution of solve(problem, 0)) {
    console.log(format(solution));
}