sudoku.js

const { cloneDeep } = require('lodash');


class Solver {
  constructor() {
    this.fields = {};
    this.avaliableValues = {};
    this.queue = [];
    this.result = 0;
  }

  branch(operation) {
    console.log('branching of to ', operation);
    const result = new Solver();
    result.fields = cloneDeep(this.fields);
    result.avaliableValues = cloneDeep(this.avaliableValues);
    result.result = this.result;
    result.queue = [operation];
    return result.solve();
  }

  startAndSolve(board) {
    this.initialize();

    for (let row = 0; row < 9; row++) {
      for (let column = 0; column < 9; column++) {
        if (board[row][column]) {
          this.markAsTaken(row, column, board[row][column]);
        }
      }
    }

    const solution = this.solve();
    if (solution) {
      solution.print();
    } else {
      this.print();
    }
  }

  print() {
    this.validate()
    for (let row = 0; row < 9; row++) {
      const partial = [];

      for (let column = 0; column < 9; column++) {
        const key = this.getKey(row, column);
        partial.push(this.fields[key] || '_');
      }

      console.log(partial.join(' '));
    }
    console.log('');
  }

  solve() {
    if (!this.queue.length) {
      this.findAlternatives();
    }

    while (this.queue.length) {
      const args = this.queue.pop();
      this.markAsTaken(args.row, args.column, args.value);
      if (this.result === 81) {
        return this;
      }

      if (!this.queue.length) {
        this.findAlternatives();
      }
    }

    return this.makeBet();
  }

  initialize() {
    for (let row = 0; row < 9; row++) {
      for (let column = 0; column < 9; column++) {
        const key = this.getKey(row, column);
        this.avaliableValues[key] = new Array(9).fill(true);
      }
    }
  }

  getKey(row, column) {
    return `${row},${column}`;
  }

  markAsTaken(row, column, value) {
    const key = this.getKey(row, column);
    if (!this.fields[key]) {
      this.result++;
      this.fields[key] = value;
      this.avaliableValues[key] = new Array(9).fill(false);
      this.markColumn(column, value);
      this.markRow(row, value);
      this.markSquare(row, column, value);
    }
  }

  markColumn(column, value) {
    for (let row = 0; row < 9; row++) {
      const key = this.getKey(row, column);
      if (!this.fields[key]) {
        this.avaliableValues[key][value - 1] = false;

        const filter = this.avaliableValues[key].filter(free => free);
        if (filter.length === 1) {
          const nextValue = this.avaliableValues[key].indexOf(true) + 1;
          this.queue.push({ row, column, value: nextValue });
        }
      }
    }
  }

  markRow(row, value) {
    for (let column = 0; column < 9; column++) {
      const key = this.getKey(row, column);
      if (!this.fields[key]) {
        this.avaliableValues[key][value - 1] = false;

        if (this.avaliableValues[key].filter(free => free).length === 1) {
          const nextValue = this.avaliableValues[key].indexOf(true) + 1;
          this.queue.push({ row, column, value: nextValue });
        }
      }
    }
  }

  markSquare(row, column, value) {
    const startRow = Math.floor(row / 3) * 3;
    const startColumn = Math.floor(column / 3) * 3;

    for (let rowIndex = startRow; rowIndex < startRow + 3; rowIndex++) {
      for (let columnIndex = startColumn; columnIndex < startColumn + 3; columnIndex++) {
        const key = this.getKey(rowIndex, columnIndex);

        if (!this.fields[key]) {
          this.avaliableValues[key][value - 1] = false;

          if (this.avaliableValues[key].filter(free => free).length === 1) {
            const nextValue = this.avaliableValues[key].indexOf(true) + 1;
            this.queue.push({ row: rowIndex, column: columnIndex, value: nextValue });
          }
        }
      }
    }
  }

  findAlternatives() {
    for (let index = 0; index < 9; index++) {
      this.findWithinRow(index);
      this.findWithinColumn(index);
    }

    for (let row = 0; row < 3; row++) {
      for (let column = 0; column < 3; column++) {
        this.findWithinSquare(row, column);
      }
    }
  }

  findWithinSquare(squareRow, squareColumn) {
    let available = {};

    for (let row = squareRow * 3; row < squareRow * 3 + 3; row++) {
      for (let column = squareColumn * 3; column < squareColumn * 3 + 3; column++) {
        available = this.updateAvailable(available, row, column);
      }
    }

    this.pushToQueue(available);
  }

  findWithinRow(row) {
    let available = {};

    for (let column = 0; column < 9; column++) {
      available = this.updateAvailable(available, row, column);
    }

    this.pushToQueue(available);
  }

  updateAvailable(available, row, column) {
    const result = { ...available };

    const key = this.getKey(row, column);
    if (!this.fields[key]) {
      this.avaliableValues[key].forEach((free, index) => {
        if (free) {
          if (!result[index + 1]) {
            result[index + 1] = [];
          }
          result[index + 1].push({ row, column });
        }
      });
    }

    return result;
  }

  findWithinColumn(column) {
    let available = {};

    for (let row = 0; row < 9; row++) {
      available = this.updateAvailable(available, row, column);
    }

    this.pushToQueue(available);
  }

  pushToQueue(available) {
    Object.entries(available)
      .filter(([, places]) => places.length === 1)
      .forEach(([value, [entry]]) => this.queue.push({ ...entry, value }));
  }

  makeBet() {
    const bets = Object.entries(this.avaliableValues)
      .filter(([key]) => !this.fields[key])
      .sort(([, places], [, otherPlaces]) => places.filter(entry => entry).length - otherPlaces.filter(entry => entry).length);

    while (bets.length) {
      const [key, available] = bets.pop();
      const [row, column] = key.split(',').map(value =>parseInt(value));
      for (let index = 0; index < 9; index++) {
        if (available[index]) {
          const value = index + 1;
          const solution = this.branch({ row, column, value });
          if (solution) {
            return solution;
          }
        }
      }
    }
  }

  validate() {
    const presentInColumn = { 0: {}, 1: {}, 2: {}, 3: {}, 4: {}, 5: {}, 6: {}, 7: {}, 8: {} };
    const presentInRow = { 0: {}, 1: {}, 2: {}, 3: {}, 4: {}, 5: {}, 6: {}, 7: {}, 8: {} };
    const presentInSquare = { 0: {}, 1: {}, 2: {}, 3: {}, 4: {}, 5: {}, 6: {}, 7: {}, 8: {} };

    for (let row = 0; row < 9; row++) {
      for (let column = 0; column < 9; column++) {
        const key = this.getKey(row, column);
        const value = this.fields[key];

        if (presentInColumn[column][value]) {
          throw new Error('invalid', value, row, column);
        }
        presentInColumn[column][value] = true;
        if (presentInRow[row][value]) {
          throw new Error('invalid', value, row, column);
        }
        presentInRow[row][value] = true;
        const squareRow = Math.floor(row / 3);
        const squareColumn = Math.floor(column / 3);

        if (presentInSquare[squareRow * 3 + squareColumn][value]) {
          throw new Error('invalid square', value, row, column);
        }
        presentInSquare[squareRow * 3 + squareColumn][value] = true;
      }
    }

    for (let index = 0; index < 9; index++) {
      const validSquares = Object.keys(presentInSquare[index]).length === 9;
      const validRows = Object.keys(presentInRow[index]).length === 9;
      const validColumns = Object.keys(presentInColumn[index]).length === 9;
      if (validColumns && validRows && validSquares) {
        return;
      }
      throw new Error('Invalid', { validSquares, validRows, validColumns });
    }
  }

}

const _ = 0;

// new Solver().start([
//   [5, 3, _, _, 7, _, _, _, _],
//   [6, 3, _, 1, 9, 5, _, _, _],
//   [_, 9, 8, _, _, _, _, 6, _],
//   [8, _, _, _, 6, _, _, _, 3],
//   [4, _, _, 8, _, 3, _, _, 1],
//   [7, _, _, _, 2, _, _, _, 6],
//   [_, 6, _, _, _, _, 2, 8, _],
//   [_, _, _, 4, 1, 9, _, _, 5],
//   [_, _, _, _, 8, _, _, 7, 9],
// ]);
//
// new Solver().start([
//   [_, 7, _, 6, _, _, _, _, 2],
//   [_, _, 8, _, _, 1, _, 7, 5],
//   [_, 5, _, _, 4, _, _, _, 8],
//   [_, _, _, _, _, 4, _, _, _],
//   [_, 4, 3, 5, _, 6, 7, 8, _],
//   [_, _, _, 1, _, _, _, _, _],
//   [2, _, _, _, 1, _, _, 4, _],
//   [7, 9, _, 8, _, _, 5, _, _],
//   [8, _, _, _, _, 7, _, 6, _],
// ]);

new Solver().startAndSolve([
  [8, _, _, _, _, _, _, _, _],
  [_, _, 3, 6, _, _, _, _, _],
  [_, 7, _, _, 9, _, 2, _, _],
  [_, 5, _, _, _, 7, _, _, _],
  [_, _, _, _, 4, 5, 7, _, _],
  [_, _, _, 1, _, _, _, 3, _],
  [_, _, 1, _, _, _, _, 6, 8],
  [_, _, 8, 5, _, _, _, 1, _],
  [_, 9, _, _, _, _, 4, _, _],
]);