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