Sudoku v2

sudoku.js

const zeroToEight = [0, 1, 2, 3, 4, 5, 6, 7, 8]
const oneToNine = zeroToEight.map(x => x + 1)

function rowCoords({ x, y }) {
  return zeroToEight.map(i => { return { x, y: i } })
}

function colCoords({ x, y }) {
  return zeroToEight.map(i => { return { x: i, y } })
}

function blockCoords({ x, y }) {
  const nX = Math.floor(x / 3)
  const nY = Math.floor(y / 3)
  return zeroToEight.map(i => {
    const dX = Math.floor(i / 3)
    const dY = i % 3
    return { x: nX * 3 + dX, y: nY * 3 + dY }
  })
}

function ruleOutByCoords(candidates, map, coords) {
  const values = coords.map(({ x, y }) => map[x][y].value).filter(x => x)
  return candidates.filter(x => values.indexOf(x) === -1)
}

function ruleOut(coord, map) {
  const c0 = map[coord.x][coord.y].candidates
  const c1 = ruleOutByCoords(c0, map, rowCoords(coord))
  const c2 = ruleOutByCoords(c1, map, colCoords(coord))
  const c3 = ruleOutByCoords(c2, map, blockCoords(coord))
  return c3
}

function reduceByRow(row, x, map) {
  return row.map((point, y) => {
    if (point.value) {
      return point
    }
    const candidates = ruleOut({ x, y }, map)
    if (candidates.length === 1) {
      return { value: candidates[0] }
    } else {
      return { candidates }
    }
  })
}

function reduce(map) {
  return map.map((row, x) => reduceByRow(row, x, map))
}

function gather(coords, map) {
  return coords.map(({ x, y }) => map[x][y])
}

function necessaryByCoords(coords, map) {
  const points = gather(coords, map)
  const values = points.map(x => x.value).filter(x => x)
  const candidates = points.map(x => x.candidates).filter(x => x)

  oneToNine.forEach(value => {
    if (values.indexOf(value) !== -1) {
      return
    }

    const possibles = candidates.filter(x => x.indexOf(value) !== -1)
    if (possibles.length > 1) {
      return
    }
    for (let i = 0; i < coords.length; i ++) {
      const { x, y } = coords[i]
      const point = map[x][y]
      if (point.candidates && point.candidates.indexOf(value) !== -1) {
        map[x][y] = { value }
        break
      }
    }
  })
}

function copy(map) {
  return map.map(x => x.slice(0))
}

function necessary(map) {
  let map_ = map.map(x => x.slice(0))
  for (const i of zeroToEight) {
    const row = rowCoords({ x: i, y: 0 })
    const col = colCoords({ x: 0, y: i })
    const block = blockCoords({
      x: Math.floor(i / 3) * 3,
      y: i % 3 * 3
    })
    const xs = [row, col, block]
    xs.forEach(coords => necessaryByCoords(coords, map_))
  }
  return map_
}

function validByCoords(coords, map) {
  const points = gather(coords, map)
  const values = points.map(x => x.value).filter(x => x)
  let flags = {}
  for (const value of values) {
    if (flags[value]) {
      return false
    }
    flags[value] = true
  }
  return true
}

function valid(map) {
  for (const i of zeroToEight) {
    const row = rowCoords({ x: i, y: 0 })
    const col = colCoords({ x: 0, y: i })
    const block = blockCoords({
      x: Math.floor(i / 3) * 3,
      y: i % 3 * 3
    })
    if (!validByCoords(row, map)) {
      return false
    }
    if (!validByCoords(col, map)) {
      return false
    }
    if (!validByCoords(block, map)) {
      return false
    }
  }
  return true
}

function buildMap(input) {
  return input.map(row => {
    return row.map(x => x === 0 ? { candidates: oneToNine } : { value: x })
  })
}

function computeSize(map) {
  let sum = 0
  for (const x of zeroToEight) {
    for (const y of zeroToEight) {
      if (map[x][y].candidates) {
        sum += map[x][y].candidates.length
      }
    }
  }
  return sum
}

function print(map) {
  map.forEach(row => {
    let output = ''
    row.forEach(point => {
      if (point.value) {
        output += point.value
      } else {
        output += '-'
      }
    })
    console.log(output)
  })
}

const input = [
  [4,0,0, 9,0,7, 1,2,5],
  [9,0,0, 0,0,2, 6,0,0],
  [0,0,0, 0,0,0, 3,8,9],

  [0,0,0, 2,7,0, 5,9,0],
  [0,5,0, 3,9,0, 0,1,6],
  [0,0,9, 0,0,1, 2,0,0],

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

function isSolved(map) {
  for (const x of zeroToEight) {
    for (const y of zeroToEight) {
      if (map[x][y].candidates) {
        return false
      }
    }
  }
  return true
}

function minCandidate(map) {
  let count = 9
  let bestX = -1
  let bestY = -1
  for (const x of zeroToEight) {
    for (const y of zeroToEight) {
      if (!map[x][y].candidates) {
        continue
      }
      let current = map[x][y].candidates.length 
      if (current < count) {
        count = current
        bestX = x
        bestY = y
      }
    }
  }
  return {
    count,
    x: bestX,
    y: bestY
  }
}

function totalCombination(map) {
  let mul = 1
  for (const x of zeroToEight) {
    for (const y of zeroToEight) {
      if (!map[x][y].candidates) {
        continue
      }
      mul *= map[x][y].candidates.length
    }
  }
  return mul
}

function printCandidates(map) {
  map.forEach(row => {
    let output = ''
    row.forEach(point => {
      if (point.value) {
        output += '-'
      } else {
        output += `${point.candidates.length}`
      }
    })
    console.log(output)
  })
}

function guess_impl(map, countBox) {
  if (isSolved(map)) {
    console.log("Map is solved:")
    print(map)
    return true
  }

  if (countBox.value >= 100) {
    console.log("No answer after 100 iterations. Abort.")
    return true
  }

  countBox.value += 1

  console.log()
  console.log(`Iteration ${countBox.value}.`)
  
  const { x, y } = minCandidate(map)
  const item = map[x][y]
  for (const value of item.candidates) {
    map[x][y] = { value }
    console.log(`Placing ${value} at (${x + 1}, ${y + 1}). Reduced map is:`)
    const reduced = reduce(map)
    map[x][y] = item
    print(reduced)
    if (!valid(reduced)) {
      console.log('Invalid layout.')
    } else if (guess_impl(reduced, countBox)) {
      return true
    }
    console.log(`Redo placing ${value} at (${x + 1}, ${y + 1}).`)
  }

  return false
}

function guess(map) {
  guess_impl(map, { value: 0 })
}

console.log("Initial map:")
let map = buildMap(input)
print(map)
console.log()
map = reduce(map)
console.log("Reduced initial map:")
print(map)
console.log()
guess(map)