# Using js to solve the problem of Sudoku

Online Sudoku, this website has an answer

https://www.sudoku.name/index-cn.php

Algorithm idea

Use two-dimensional array to represent chessboard, 0 for null

First calculate the set of every empty possible value

The dfs search is carried out in turn. After a value is determined each time, the nine palaces and all vertical and horizontal collections where the value is located are updated, that is, the value is subtracted

Until the end of the search

Optimization ideas

One dimensional array is used to represent the chessboard, 0-9 bits of each number represent a set of possible values, and 10 bits represent whether the value is empty or not

Use bitwise acceleration

At the same time, it depends on whether it is empty or not. You can only search for it to avoid the problem that you cannot determine whether it is empty when multiple nulls delete a value and become a single number. You must use the check function

``````const _ = require('lodash')

// 0 means unknown
const INIT_MAP =
// Hard
// [
//   [8, 0, 0, 0, 0, 0, 0, 0, 0],
//   [0, 0, 3, 6, 0, 0, 0, 0, 0],
//   [0, 7, 0, 0, 9, 0, 2, 0, 0],
//   [0, 5, 0, 0, 0, 7, 0, 0, 0],
//   [0, 0, 0, 0, 4, 5, 7, 0, 0],
//   [0, 0, 0, 1, 0, 0, 0, 3, 0],
//   [0, 0, 1, 0, 0, 0, 0, 6, 8],
//   [0, 0, 8, 5, 0, 0, 0, 1, 0],
//   [0, 9, 0, 0, 0, 0, 4, 0, 0]
// ]

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

// [/ / easy
//   [7, 4, 8, 1, 2, 3, 6, 5, 9],
//   [2, 6, 3, 4, 9, 5, 1, 8, 7],
//   [1, 5, 9, 6, 7, 8, 2, 4, 3],
//   [4, 1, 5, 3, 6, 7, 9, 2, 8],
//   [3, 8, 2, 9, 5, 4, 7, 6, 1],
//   [9, 7,6, 8, 1, 2, 4, 3, 5],
//   [5, 2, 4, 7, 3, 9, 8, 1, 6],
//   [8, 9, 1, 5, 4, 6, 3, 7, 2],
//   [6, 3, 7, 2, 8, 1, 5, 9, 4]
// ]

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

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

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

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

// 1,2,5,3,6,4,9,7,8
// 9,4,6,8,2,7,1,5,3
// 7,8,3,1,5,9,2,4,6
// 2,5,4,6,8,1,3,9,7
// 6,1,9,2,7,3,4,8,5
// 3,7,8,4,9,5,6,2,1
// 5,3,2,7,4,6,8,1,9
// 8,9,1,5,3,2,7,6,4
// 4,6,7,9,1,8,5,3,2

function range(n = 9) {
return Array(n).fill(0).map((_, i) => i + 1)
}

// console.log(getSet(INIT_MAP, 0, 8))

// Calculate the possible number set of a point according to a state
// Change point must be a certain number
function getSet(m, x, y) {
// Determined number
if (1 < m[x][y] && m[x][y] <= 9)
return new Set([m[x][y]])

// A collection of numbers that returns a copy of the collection
if (m[x][y].size === 1)
return new Set([...m[x][y]]);

// Default 9, then remove illegal
let s = new Set(range(9))

for (let i = 0; i < 9; i++) {
if (i === x) continue
// Remove duplicates from columns
if (m[i][y] > 0 && m[i][y] <= 9)
s.delete(m[i][y])
if (m[x][i].size === 1)
s.delete(...m[i][y])
}

for (let i = 0; i < 9; i++) {
if (i === y) continue
// Remove row repetitions
if (m[x][i] > 0 && m[x][i] <= 9)
s.delete(m[x][i])
if (m[x][i].size === 1)
s.delete(...m[x][i])
}

// Remove the number of repetitions in the nine palace lattice
let stx = Math.floor(x / 3) * 3// Upper left x
let sty = Math.floor(y / 3) * 3// Upper left corner y
for (let i = 0; i < 3; i++)
for (let j = 0; j < 3; j++) {
let nx = stx + i
let ny = sty + j
let v = m[nx][ny]
// console.log(nx, ny)
if (v > 0 && v <= 9)
s.delete(v)
if (v.size === 1)
s.delete(...v)
}

return s
}

// According to the initial state, obtain the possible number set of each location
function init(m) {
let res = Array(9).fill(0).map(
() => Array(9).fill(0)
)
for (let i = 0; i < 9; i++)
for (let j = 0; j < 9; j++) {
if (0 < m[i][j] && m[i][j] <= 9) {
// If it's a number
res[i][j] = new Set([m[i][j]])
} else {
// If unknown
res[i][j] = getSet(m, i, j)
}
}
return res
}

// Deep copy an object
function copy(obj) {
return _.cloneDeep(obj)
}

// Delete m, x,y related numbers, horizontal and vertical, Jiugong grid
function delSet(m, x, y, v) {
// Delete numbers in rows and columns
for (let i = 0; i < 9; i++) {
m[i][y].delete(v)
m[x][i].delete(v)
}

// Remove the number of repetitions in the nine palace lattice
let stx = Math.floor(x / 3) * 3// Upper left x
let sty = Math.floor(y / 3) * 3// Upper left corner y
for (let i = 0; i < 3; i++)
for (let j = 0; j < 3; j++) {
let nx = stx + i
let ny = sty + j
m[nx][ny].delete(v)
}

m[x][y] = new Set([v])
for (let i = 0; i < 9; i++)
for (let j = 0; j < 9; j++)
if (m[i][j].size === 0) return false

// true means it can be the number
// Careful inspection
return check(m)
}

// Check whether the requirements are met
function check(m) {
// console.log(toStr(m))
// let rows = m.map(x => new Set(x))
// let cols = []
for (let i = 0; i < 9; i++) {
let c = new Set()
let r = new Set()
for (let j = 0; j < 9; j++) {
let colVal = m[i][j]
let rowVal = m[j][i]
if (colVal.size === 1) {
if (c.has(...colVal))
return false
c.add(...colVal)

}
if (rowVal.size === 1) {
if (r.has(...rowVal))
return false
r.add(...rowVal)

}
}
// console.log('check', c, r)
}

// squared paper for practicing calligraphy
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {

let s = new Set()
for (let x = 0; x < 3; x++) {
for (let y = 0; y < 3; y++) {
let nx = i * 3 + x
let ny = j * 3 + y
let v = m[nx][ny]
if (v.size > 1) continue

if (s.has(...v))
return false
s.add(...v)
}
}
}
}

return true
// let f1 = rows.every(x => x.size === 9)
// let f2 = cols.every(x => x.size === 9)
//
// return f1 && f2
}

function toStr(m) {
// console.log(m)
let s = m.map(
row => row.map(x => [...x].join(''))
)
return s.join('n')
}

// Start from x,y to find a place to fill, that is, the size of the set is greater than 1
function getPos(m, x, y) {
// console.log('getPos', x, y)
for (let i = 0; i < 9; i++)
for (let j = 0; j < 9; j++) {
if (i * 9 + j < x * 9 + y) continue
// console.log('getPos', i, j, m[i][j])
if (m[i][j].size > 1)
return [i, j]
}
// If not, the search is complete
return [9, 9]
}

// Deep search
// Starting from m, search in x, y coordinates
// Each coordinate is a set of possible numbers
function dfs(m, x, y, deep = 0) {
console.log('dfs', x, y, deep)
// console.log('---dfs')
// console.log(toStr(m))
// console.log('---dfsn')
if (x === 9 && y === 9) {
// console.log('---end')
// console.log(toStr(m))
// console.log('---endn')
// When the search reaches the last cell, it means the search is over
for (let i = 0; i < 9; i++)
for (let j = 0; j < 9; j++) {
if (m[i][j].size !== 1) return false
}
return m
}
let p = getPos(m, x, y)
// console.log('getPos', p)
let [i, j] = p
let v = m[i][j]
// Non skipped number, after removing a number from the set, modify all related sets
for (let delVal of v) {
let mm = copy(m)
let f = delSet(mm, i, j, delVal)
console.log('delVal', i, j, delVal, 'n', toStr(mm))
// Can't choose to change number
if (!f) continue

let [nx, ny] = getPos(mm, i, j)
// console.log('nx,ny', nx, ny)
let res = dfs(mm, nx, ny, deep + 1)
if (res)
return res
}

return false
}

function main() {
let m = init(INIT_MAP)
console.log(toStr(m))
console.log('---nnn---')
let res = dfs(m, 0, 0)
if (res)
console.log(toStr(res))

// let res = dfs(m, 0, 0)
// console.log(res)
// console.log(init(m))
}

main()

``````

Tags: Programming PHP

Posted on Sat, 30 May 2020 07:09:26 -0700 by TGWSE_GY