Skip to content

Instantly share code, notes, and snippets.

@notcome
Created June 6, 2019 01:29
Show Gist options
  • Save notcome/5e41157a20461a2b479e90a3ef0daa56 to your computer and use it in GitHub Desktop.
Save notcome/5e41157a20461a2b479e90a3ef0daa56 to your computer and use it in GitHub Desktop.
A suduko solver that I wrote on DL89.
// This solver is semi-automaitc and you can see how possibilites are removed through each step.
// It turns out that the hard mode has more than one possible solution, so next time when you
// are stuck, just try one manually.
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 = [
[0,9,0, 0,0,0, 1,0,2],
[0,7,0, 9,0,0, 0,0,4],
[5,2,0, 7,0,1, 0,9,0],
[4,0,0, 0,0,0, 0,2,0],
[0,1,0, 4,0,6, 0,8,0],
[0,3,0, 0,0,0, 0,0,9],
[0,6,0, 3,0,5, 0,4,1],
[3,0,0, 0,0,4, 0,6,0],
[8,0,7, 0,0,0, 0,5,0]
]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment