Язык Sentient

[vak]

До чего же могучими могут быть декларативные языки! Вот программа в тридцать строчек, разгадывающая произвольную головоломку судоку. Язык называется Sentient, чисто декларативный, напоминает Javascript. Объяснение в блоге: https://whichdigitalblog.com/2017/02/28/sentient-sudoku-solver/

array9<array9<int>> grid;

boxes = [0, 3, 6].map(function^ (num) {
  return [0, 3, 6].map(function^ (num2) {
    return [
      grid[num2][num], grid[num2][num+1], grid[num2][num+2],
      grid[num2+1][num], grid[num2+1][num+1], grid[num2+1][num+2],
      grid[num2+2][num], grid[num2+2][num+1], grid[num2+2][num+2]
    ];
  });
});

function validCollection?(collection) {
  invariant collection.uniq?;
  invariant collection.all?(*valueValid?);
};

function valueValid?(value) {
  return value.between?(1,9);
};

grid.each(*validCollection?);
grid.transpose.each(*validCollection?);

boxes.each(function (boxRow) {
  boxRow.each(function (box) {
    validCollection?(box);
  });
});

expose grid;

Для проверки я взял первый попавшийся вариант судоку с сайта websudoku.com. Циферки надо перепереть в формат JSON, чтобы подать на вход программе:

{
  grid: [
    [undefined,undefined,undefined,undefined,undefined,undefined,undefined,6,undefined],
    [undefined,2,undefined,undefined,8,9,7,5,undefined],
    [undefined,6,4,undefined,2,undefined,undefined,3,undefined],
    [undefined,8,undefined,5,1,undefined,4,9,2],
    [4,undefined,undefined,7,undefined,6,undefined,undefined,3],
    [3,9,1,undefined,4,2,undefined,7,undefined],
    [undefined,3,undefined,undefined,7,undefined,1,4,undefined],
    [undefined,4,7,3,6,undefined,undefined,2,undefined],
    [undefined,1,undefined,undefined,undefined,undefined,undefined,undefined,undefined]
  ]
}

Запускаем, с замером времени:

$ time sentient sudoku_solver.snt --assign-file input.json 
{"grid":[[9,7,8,4,3,5,2,6,1],[1,2,3,6,8,9,7,5,4],[5,6,4,1,2,7,9,3,8],[7,8,6,5,1,3,4,9,2],[4,5,2,7,9,6,8,1,3],[3,9,1,8,4,2,6,7,5],[2,3,5,9,7,8,1,4,6],[8,4,7,3,6,1,5,2,9],[6,1,9,2,5,4,3,8,7]]}
(Use `node --trace-warnings ...` to show where the warning was created)

real	0m6.516s
user	0m7.353s
sys	0m0.261s

Решение готово через семь секунд. В более наглядном виде:

[9,7,8,  4,3,5,  2,6,1],
[1,2,3,  6,8,9,  7,5,4],
[5,6,4,  1,2,7,  9,3,8],

[7,8,6,  5,1,3,  4,9,2],
[4,5,2,  7,9,6,  8,1,3],
[3,9,1,  8,4,2,  6,7,5],

[2,3,5,  9,7,8,  1,4,6],
[8,4,7,  3,6,1,  5,2,9],
[6,1,9,  2,5,4,  3,8,7]

Спасибо spamsink  за наводку.