Skip to content

Instantly share code, notes, and snippets.

@notcome
Created September 11, 2022 15:42
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save notcome/cd3409faf739b93c7b0621f83de9f367 to your computer and use it in GitHub Desktop.
Save notcome/cd3409faf739b93c7b0621f83de9f367 to your computer and use it in GitHub Desktop.
Sudoku v2
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment