数独

数独（Sudoku）是一种数学逻辑游戏，游戏由9×9个格子组成，玩家需要根据格子提供的数字推理出其他格子的数字。游戏设计者会提供最少17个数字使得解答谜题只有一个答案。数独的图示表示其实也是一个邻接矩阵。

标准数独是由一个给与了提示数字的9x9网格组成，每行、列、宫各自都要填上1-9的数字，要做到每行、列、宫里的数字都不重复。宫是由3×3的小格子组成的。

数独基础解法：

• 唯一余数法：点算某格的 [等位群格位] 中已经出现过哪些数，如果已经出现1 – 9中的8格，那么这格就是第9个数，此数被称为唯一余数。

• 排除法：就是利用数独中行、列和宫内不能填入相同数字的规则，利用已出现的数字对同行、同列和同宫内其他格进行排斥相同数字的方法。

📐 数学公式

📌 JavaScript

参考代码：index.js


/**
 * 索引 => 行列坐标
 * @param {Number} index - 索引值
 * @returns 
 */
function i2rc(index) {
    return { row: Math.floor(index / 9), col: index % 9 };
}

/**
 * 行列坐标 => 索引
 * @param {Number} row  - 行数
 * @param {Number} col  - 列数
 * @returns 
 */
function rc2i(row, col) {
    return row * 9 + col;
}

/**
 * 有哪些可用选项，即在给定单元格中可以接受哪些数字（也将它们称为“移动”）
 * @param {Array} board  - 一个数组,它就是数独的面板，使用数组矩阵表示
 * @param {Number} index  - 索引
 * @returns 
 */
function getChoices(board, index) {
    let choices = [];
    for (let value = 1; value <= 9; ++value) {
        if (acceptable(board, index, value)) {
            choices.push(value);
        }
    }
    return choices;
}


/**
 * 棋盘是我们的数组，包含81个元素，此函数将返回当前在该索引的单元格上允许的数字数组。
 * 拼图的实际规则是在函数acceptable()中实现的：我们可以使用未在同一行、同一列或同一 3x3 正方形中使用的数字
 * @param {Array} board  - 一个数组,它就是数独的面板，使用数组矩阵表示
 * @param {Number} index  - 索引值
 * @param {Number} value  - 1~9中的某个值
 * @returns 
 */
function acceptable(board, index, value) {
    let { row, col } = i2rc(index);

    /* 列上已经存在，则不可接受 */
    for (let r = 0; r < 9; ++r)
        if (board[rc2i(r, col)] == value) return false;

    /* 行上已经存在，则不可接受 */
    for (let c = 0; c < 9; ++c)
        if (board[rc2i(row, c)] == value) return false;

    /* 如果已经出现在同一个 3x3 方格中，也不能接受 */
    let r1 = Math.floor(row / 3) * 3;
    let c1 = Math.floor(col / 3) * 3;
    for (let r = r1; r < r1 + 3; ++r) {
        for (let c = c1; c < c1 + 3; ++c) {
            if (board[rc2i(r, c)] == value) return false;
        }
    }

    return true;
}


/**
 * 回溯检查问题是否解决
 * @param {Array} board  - 一个数组,它就是数独的面板，使用数组矩阵表示
 * @returns 
 */
function solve(board) {


    /* 遍历每个索引 */
    /* 再次为每个字段寻找填充和计算移动的最佳位置 */
    /* ----------------- */
    let index, moves;
    
    for (let i = 0; i < board.length; ++i) {
        if (!board[i]) {

            let m = getChoices(board, i);
            moves = m;
            index = i;

            if (m.length === 0) break;
        }
    }
 
    /* 回溯检查问题是否解决 */
    /* ----------------- */
    if (index == null) return true;

    for (let m of moves) {
        /* 尝试一种选择 */
        board[index] = m;

        /* 如果我们能解决下一个单元格 */
        if (solve(board)) return true;
    }
    

    /* 没有任何动作；失败并清除单元格 */
    board[index] = 0;

    /* 回溯 */
    return false; 

}


/**
 * 数独的解题器
 * @param {Array} matrix - 一个数组,它就是数独的面板，使用数组矩阵表示
 * @returns 
 */
export function sudokuSolver(matrix) {
    if (solve(matrix) === true) {
        return matrix;
    }
    return '不能找到解决方案';
}

测试：test.js

import { sudokuSolver } from './index';


const myBoard = [
    0, 0, 0,  0, 0, 0,  0, 0, 6,
    0, 3, 0,  0, 7, 1,  0, 4, 0,
    0, 0, 0,  0, 0, 0,  8, 0, 0,

    0, 0, 0,  9, 0, 8,  0, 7, 1,
    1, 0, 3,  0, 0, 0,  0, 0, 0,
    0, 0, 2,  0, 3, 0,  9, 0, 0,

    5, 0, 7,  0, 0, 6,  0, 0, 0,
    2, 0, 0,  0, 0, 0,  7, 0, 0,
    0, 0, 1,  8, 0, 0,  0, 0, 2,
];

console.log( sudokuSolver(myBoard) );


/* 结果：
[
    7, 2, 4,  3, 8, 9,  1, 5, 6, 
    6, 3, 8,  5, 7, 1,  2, 4, 9, 
    9, 1, 5,  6, 4, 2,  8, 3, 7, 
    
    4, 5, 6,  9, 2, 8,  3, 7, 1, 
    1, 9, 3,  7, 6, 4,  5, 2, 8, 
    8, 7, 2,  1, 3, 5,  9, 6, 4, 
    
    5, 8, 7,  2, 9, 6,  4, 1, 3, 
    2, 6, 9,  4, 1, 3,  7, 8, 5, 
    3, 4, 1,  8, 5, 7,  6, 9, 2
]
*/