@algoritm.ts/sudoku (英语)

中文文档

这个库用于解决数独问题并用独特的解决方案生成数独问题.

数独问题被描述为大小(a*a) *(a*a)的平方矩阵,以及a的值 平方矩阵中的位置是 [-1, a*a] 之间的整数. 其中, -1 表示没有值是 已经填满了这个职位 一个典型的"数独"问题需要满足以下的制约:

1. 平方矩阵中的每个位置需要用 [0, a*a] 之间的整数填充
2. 平方矩阵的每行没有重复的数字
3. 平方矩阵的每列没有重复的数字
4. 平方矩阵可分为:大小的子平方a,没有重复 下方各栏中的数字 苏多库 算法.

sudoku是一个shuffle算法,它可以在$O(N)美元时间复杂度的基础上完成shuffle 仅使用常数的额外空间.

如果你对这个算法好奇,你可以访问[这里][sudoku]了解更多细节.

安装

• 无

  npm install --save @algorithm.ts/sudoku
  

• 小时

  pnpm add @algorithm.ts/sudoku
  

使用量

• SudokuSolver:解决一个数独谜题.

• SudokuCreator: 创建一个只有独特解决方案的数独数据(谜题和解决方案).

• 工具函数

  函数	说明
  createSudokuBoardData	创建 sudoku 板( 一维阵列) .
  fillSudokuBoardData	用给定的值填充sudoku板.
  copySudokuBoardData	从 src 改为 dst。 。 。 .
  verifySolution	检查给定的数独游戏的解决方案是否有效 .
  toMatrixStyleBoardData	将一维阵列转换为二维阵列.
  createMatrixCodeMap
  createMatrixCoordinateMap

实例

解开谜题

• 解决一个 16x16 sudoku 谜题

  import type { ISudokuBoardData } from '@algorithm.ts/sudoku'
  import { SudokuSolver, createSudokuBoardData } from '@algorithm.ts/sudoku'
  
  // 4 x 4 = 16
  const solver = new SudokuSolver({ childMatrixSize: 4 })
  
  const puzzle: ISudokuBoardData =  [
     2,  3, 14, -1,  8,  6, -1, -1, -1, 13, -1, -1, -1, 10, 12, -1,
     0, -1, -1, -1, -1, -1,  1,  9, -1, -1,  4, -1,  8, -1, -1,  2,
    -1, -1, -1,  6,  7, -1,  2, -1, -1, -1, 10,  1, -1,  0, -1, 15,
    -1,  8, -1, -1, -1, -1, 12, -1, -1,  5,  0,  7,  4, -1,  1,  6,
     7,  1, -1,  3, -1,  4, 10, 14, -1, -1, -1, -1,  2, -1, 15,  9,
    14, 12, -1, -1,  2,  3, -1, -1,  1, -1,  7, -1, -1,  6, 13, -1,
    10,  2,  5, -1, -1,  0,  7, -1,  3, -1, -1,  8, 11,  1, -1,  4,
    -1, 13,  6, -1, -1, -1, -1,  1, -1, -1, 14,  2, -1,  3,  7, -1,
    -1, -1, -1,  2,  1, -1, -1, -1, -1, -1,  8,  9, 14,  7, -1, -1,
     8,  9, 10, -1,  3, -1, -1,  2,  6, -1, 11, -1, -1, -1,  5,  0,
     1, -1,  3,  5, -1, -1, -1, -1,  4,  0, -1, -1, -1, 11, -1, 12,
     6, -1, -1,  4,  5, -1, 15, 11, 14, -1,  1, -1, 13,  9,  8, -1,
    -1,  6, -1, -1, -1,  2, -1, 12, -1, -1, -1, 14,  9, -1,  0, 13,
    -1, -1,  0,  7, -1,  9, 13,  8, -1, -1,  3, -1, -1,  2,  6, 14,
    -1, -1, -1,  8, -1, 11, -1, -1, -1, 12, -1, -1, 15,  5,  3,  1,
     3, -1, -1, -1, -1, -1, -1, -1,  9, 15,  2,  0, -1,  8, -1, 11
  ]
  
  solver.solve(puzzle, null)  // => true
  
  const solution: ISudokuBoardData = createSudokuBoardData(16)
  solver.solve(puzzle, solution)  // => true
  
  solution
  /** ===>
   * [
   *    2,  3, 14,  1,  8,  6,  0,  4, 11, 13,  9, 15,  5, 10, 12,  7,
   *    0,  5,  7, 10, 14, 15,  1,  9, 12,  3,  4,  6,  8, 13, 11,  2,
   *   12, 11,  4,  6,  7,  5,  2, 13,  8, 14, 10,  1,  3,  0,  9, 15,
   *   15,  8,  9, 13, 11, 10, 12,  3,  2,  5,  0,  7,  4, 14,  1,  6,
   *    7,  1,  8,  3,  6,  4, 10, 14,  0, 11, 13,  5,  2, 12, 15,  9,
   *   14, 12, 15, 11,  2,  3,  9,  5,  1,  4,  7, 10,  0,  6, 13,  8,
   *   10,  2,  5,  9, 13,  0,  7, 15,  3,  6, 12,  8, 11,  1, 14,  4,
   *    4, 13,  6,  0, 12,  8, 11,  1, 15,  9, 14,  2, 10,  3,  7,  5,
   *   13, 15, 11,  2,  1, 12,  6,  0,  5, 10,  8,  9, 14,  7,  4,  3,
   *    8,  9, 10, 14,  3, 13,  4,  2,  6,  7, 11, 12,  1, 15,  5,  0,
   *    1,  7,  3,  5,  9, 14,  8, 10,  4,  0, 15, 13,  6, 11,  2, 12,
   *    6,  0, 12,  4,  5,  7, 15, 11, 14,  2,  1,  3, 13,  9,  8, 10,
   *   11,  6,  1, 15, 10,  2,  3, 12,  7,  8,  5, 14,  9,  4,  0, 13,
   *    5,  4,  0,  7, 15,  9, 13,  8, 10,  1,  3, 11, 12,  2,  6, 14,
   *    9, 10,  2,  8,  0, 11, 14,  7, 13, 12,  6,  4, 15,  5,  3,  1,
   *    3, 14, 13, 12,  4,  1,  5,  6,  9, 15,  2,  0,  7,  8, 10, 11
   * ]
   */
  

创建 sudoku 游戏数据

• 创建一个 9x9 语句谜题

  import { SudokuCreator } from '@algorithm.ts/sudoku'
  
  // 3 x 3 = 9
  const creator = new SudokuCreator({ childMatrixSize: 3 })
  

  • 创建一个简单的谜题 .

    creator.createSudoku()
    // or
    creator.createSudoku(0.2)
    

    结果是一个 js 对象,类似于下面显示的对象 :

    {
      "puzzle": [
         8, -1, 6,  1,  0,  2,  3,  5, -1,
         0, -1, 5, -1,  4, -1,  8,  1,  7,
         4,  3, 1,  8, -1, -1,  2,  6,  0,
        -1,  0, 7,  4, -1,  1,  5,  8,  2,
         2,  1, 4,  5,  3, -1, -1,  7,  6,
         5,  6, 8,  0,  2,  7,  4,  3,  1,
         1,  4, 3,  2, -1,  6,  7,  0,  8,
         6,  5, 0,  7,  8,  4,  1,  2,  3,
        -1, -1, 2,  3, -1, -1,  6,  4,  5
      ],
      "solution": [
        8, 7, 6, 1, 0, 2, 3, 5, 4,
        0, 2, 5, 6, 4, 3, 8, 1, 7,
        4, 3, 1, 8, 7, 5, 2, 6, 0,
        3, 0, 7, 4, 6, 1, 5, 8, 2,
        2, 1, 4, 5, 3, 8, 0, 7, 6,
        5, 6, 8, 0, 2, 7, 4, 3, 1,
        1, 4, 3, 2, 5, 6, 7, 0, 8,
        6, 5, 0, 7, 8, 4, 1, 2, 3,
        7, 8, 2, 3, 1, 0, 6, 4, 5
      ]
    }
    

  • 创建困难的谜题 .

    creator.createSudoku(1.0)
    

    结果是一个 js 对象,类似于下面显示的对象 :

    {
      "puzzle": [
        -1, -1, -1, -1, -1,  8, -1, -1,  4,
        -1, -1, -1,  3, -1, -1,  5,  8, -1,
        -1, -1, -1,  6,  4, -1,  0, -1, -1,
        -1, -1, -1, -1,  2, -1,  6, -1, -1,
        -1,  0, -1, -1, -1, -1,  7,  3,  5,
        -1,  7, -1, -1,  3, -1, -1, -1, -1,
         3, -1, -1, -1, -1,  2, -1, -1,  0,
        -1, -1, -1,  8,  6,  5, -1, -1, -1,
         2, -1,  4, -1, -1, -1, -1, -1, -1
      ],
      "solution": [
        0, 6, 1, 2, 5, 8, 3, 7, 4,
        4, 2, 7, 3, 0, 1, 5, 8, 6,
        8, 3, 5, 6, 4, 7, 0, 2, 1,
        5, 4, 3, 7, 2, 0, 6, 1, 8,
        6, 0, 2, 1, 8, 4, 7, 3, 5,
        1, 7, 8, 5, 3, 6, 4, 0, 2,
        3, 8, 6, 4, 7, 2, 1, 5, 0,
        7, 1, 0, 8, 6, 5, 2, 4, 3,
        2, 5, 4, 0, 1, 3, 8, 6, 7
      ]
    }
    

• 创建一个 16x16 sudoku 谜题

  import { SudokuCreator } from '@algorithm.ts/sudoku'
  
  // 4 x 4 = 16
  const creator = new SudokuCreator({ childMatrixSize: 4 })
  creator.createSudoku(0.8)
  

  结果是一个 js 对象,类似于下面显示的对象 :

  {
    "puzzle": [
      -1, -1, -1, 12, -1,  5, -1,  9, -1, -1,  6, -1, -1,  1, -1, 14,
      -1,  2,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 15, -1,
      -1, -1,  8, -1, 12, 13,  4,  7,  2, -1, -1, -1, -1, -1, -1, -1,
       7, -1, -1, -1, -1, -1, -1, 14, -1, -1, -1, 12, -1, -1, -1, -1,
       4, -1, 15, -1,  6, -1, -1, -1, -1, -1, 11, -1,  3, -1, -1, -1,
      -1,  8, 10, 14, -1, -1, -1, -1,  5, 13, -1, -1, -1,  9, -1, -1,
      -1, -1,  6, 11,  3, 14, -1, -1,  0,  2, -1,  4, -1, -1, -1, 15,
      -1,  5, 13, -1, -1,  7, -1, -1,  9, -1, -1,  3,  2, -1, 10, -1,
      -1, -1, -1, -1, -1, -1, 14, -1,  6,  9, -1, -1, 10,  8, -1, -1,
      -1, -1, 14,  0,  7,  3, -1,  2, -1, 10, -1, -1, 15, 13, -1,  9,
      -1,  9,  7, -1, -1, -1, -1, 12, -1, 15, -1,  1, -1, -1,  0, -1,
      11, -1,  3, -1, -1,  0, -1, 15, 14,  5, -1, -1, -1,  2, 12,  6,
      -1, -1,  0, 13, -1, -1, -1,  5, -1, 11,  9, -1,  4, -1,  6,  3,
      -1, -1,  2, -1, -1, -1, 10, -1, 15,  6, -1, -1, 14, -1, -1, -1,
      -1, -1, -1, -1, 15, 12, -1, -1, -1,  4,  7, -1, -1, -1,  9, -1,
       6, -1, -1, -1, -1, -1,  8, -1, -1, -1,  5, -1, -1,  0, -1, -1
    ],
    "solution": [
      10,  3, 11, 12,  8,  5,  2,  9,  4,  7,  6, 15,  0,  1, 13, 14,
      13,  2,  4,  9,  1,  6,  3,  0, 11,  8, 14,  5, 12,  7, 15, 10,
       0, 14,  8, 15, 12, 13,  4,  7,  2,  1, 10,  9,  6,  3, 11,  5,
       7,  6,  1,  5, 11, 10, 15, 14, 13,  0,  3, 12,  9,  4,  8,  2,
       4,  0, 15,  2,  6,  9,  1, 13,  7, 12, 11, 10,  3,  5, 14,  8,
       3,  8, 10, 14,  2, 15, 12,  4,  5, 13,  1,  6, 11,  9,  7,  0,
       9,  7,  6, 11,  3, 14,  5, 10,  0,  2,  8,  4, 13, 12,  1, 15,
      12,  5, 13,  1,  0,  7, 11,  8,  9, 14, 15,  3,  2,  6, 10,  4,
      15, 13, 12,  4,  5, 11, 14,  1,  6,  9,  2,  0, 10,  8,  3,  7,
       5,  1, 14,  0,  7,  3,  6,  2,  8, 10, 12, 11, 15, 13,  4,  9,
       2,  9,  7,  6, 10,  8, 13, 12,  3, 15,  4,  1,  5, 14,  0, 11,
      11, 10,  3,  8,  4,  0,  9, 15, 14,  5, 13,  7,  1,  2, 12,  6,
       1, 12,  0, 13, 14,  2,  7,  5, 10, 11,  9,  8,  4, 15,  6,  3,
       8,  4,  2,  7,  9,  1, 10,  3, 15,  6,  0, 13, 14, 11,  5, 12,
      14, 11,  5,  3, 15, 12,  0,  6,  1,  4,  7,  2,  8, 10,  9, 13,
       6, 15,  9, 10, 13,  4,  8, 11, 12,  3,  5, 14,  7,  0,  2,  1
    ]
  }
  

相关

• {\fn黑体\fs22\bord1\shad0\3ahbe\4ah00\fscx67\fscy66\2chffffff\3ch808080}你觉得呢
• {\fn黑体\fs22\bord1\shad0\3ahbe\4ah00\fscx67\fscy66\2chffffff\3ch808080}你这混蛋
• {\fn黑体\fs22\bord1\shad0\3aHBE\4aH00\fscx67\fscy66\2cHFFFFFF\3cH808080}你觉得呢