Kakuro solver

kakuro-sample.txt

  -1,  -1,1000, 400,  -1,  -1
  -1, 703,   0,   0,3000, 800
  16,   0,   0,   0,   0,   0
   3,   0,   0, 913,   0,   0
  17,   0,   0,   0,   0,   0
  -1,  -1,  16,   0,   0,  -1

kakuro.js

#! /usr/bin/env node

'use strict';

// https://www.npmjs.com/package/logic-solver
const Logic = require('logic-solver')

const BITS = 4

const Horz = 0
const Vert = 1

function solveKakuro(field) {
  const logicSolver = new Logic.Solver()

  // Locations
  const locs = field.map((row, r) =>
    row.map((e, c) =>
      e === 0 ? Logic.variableBits(varName(r, c), BITS) : null))

  const segments = listUpSegments(field)

  // Constraints
  for (const loc of locs.flat()) {
    if (loc == null)
      continue
    logicSolver.require(Logic.greaterThanOrEqual(loc, Logic.constantBits(1)))
    logicSolver.require(Logic.lessThanOrEqual(loc, Logic.constantBits(9)))
  }

  const StepTable = [{vr: 0, vc: 1}, {vr: 1, vc: 0}]
  for (const segment of segments) {
    const r = segment.row
    const c = segment.col
    const {vr, vc} = StepTable[segment.dir]
    const terms = [...Array(segment.seq)].map((_, i) => locs[r + vr * i][c + vc * i])

    for (let i = 0; i < terms.length - 1; ++i)
      for (let j = i; ++j < terms.length; )
        logicSolver.forbid(Logic.equalBits(terms[i], terms[j]))

    logicSolver.require(Logic.equalBits(Logic.sum(terms), Logic.constantBits(segment.sum)))
  }

  const solutions = []
  for (;;) {
    const sol = logicSolver.solve()
    if (sol == null)
      break
    solutions.push(sol)
    logicSolver.forbid(sol.getFormula())
  }
  if (solutions.length === 1) {
    const sol = solutions[0]
    return locs.map(row => row.map(v => v != null ? sol.evaluate(v) : 0))
  }
  if (solutions.length === 0) {
    console.error('No solution')
  } else {
    console.error(`Many solutions: #${solutions.length}`)
  }
  return null
}

function varName(r, c) {
  return `V${r},${c}`
}

function listUpSegments(field) {
  function rowsum(e) { return e > 0 ? e % 100 : 0 }
  function colsum(e) { return e > 0 ? (e / 100) | 0 : 0 }

  const h = field.length
  const w = field[0].length
  const segments = []
  for (let row = 0; row < h; ++row) {
    for (let col = 0; col < w; ++col) {
      const sum = rowsum(field[row][col])
      if (sum === 0)
        continue
      col += 1
      let seq = 0
      for (; col + seq < w && field[row][col + seq] === 0; ++seq);
      if (seq <= 1) {
        console.error(`Illegal data horz at (${row}, ${col - 1}), seq=${seq}`)
      }
      segments.push({dir: Horz, row, col, seq, sum})
      col += seq - 1
    }
  }

  for (let col = 0; col < w; ++col) {
    for (let row = 0; row < h; ++row) {
      const sum = colsum(field[row][col])
      if (sum === 0)
        continue
      row += 1
      let seq = 0
      for (; row + seq < h && field[row + seq][col] === 0; ++seq);
      if (seq <= 1) {
        console.error(`Illegal data vert at (${row - 1}, ${col}), seq=${seq}`)
      }
      segments.push({dir: Vert, row, col, seq, sum})
      row += seq - 1
    }
  }
  return segments
}

function dispSolution(solution) {
  const digits = '　１２３４５６７８９'
  for (let r = 1; r < solution.length; ++r) {
    const row = solution[r]
    const line = row.slice(1).map((_, c) => digits[row[c + 1]])
    console.log(line.join(''))
  }
}

function processInput(input) {
  const field = input
    .split('\n')
    .filter(line => line)
    .map(line => line.split(',').map(e => parseInt(e.trim())))

  const solution = solveKakuro(field)
  if (solution != null)
    dispSolution(solution)
}

async function main() {
  if (process.argv.length > 2) {
    const fs = require('fs')
    const util = require('util')
    const readFileAsync = util.promisify(fs.readFile)
    for (let i = 2; i < process.argv.length; ++i) {
      const input = await readFileAsync(process.argv[i], 'utf-8')
      processInput(input)
    }
  } else {
    const buffers = []
    for await (const chunk of process.stdin)
      buffers.push(chunk)
    const buffer = Buffer.concat(buffers)
    processInput(buffer.toString())
  }
}

if (require.main == module)
  main()