数独生成算法

碰到一个需求，需要创建指定大小的数独，这个题挺有意思的，思考了几天，在这里记录一下思考过程及结果。

数独概念

数独是一种数学游戏，它由n*n个方块组成，其中部分方块中填充从1到n的数字，玩家需要从已知方块推出未填充方块上的数字。这些数字的填充规则是每一行每一列中，每个数字仅能出现一次。

针对99的数独，还有一个额外的规则，那就是将这些方块分为9个部分，每个部分由33个方块组成，称为9宫。每个宫中1-9每个数字也只能出现一次。

我碰到的需求是创建指定n大小的数独，所以这里就判断9宫规则了。

随机解法

最开始我想到的解法是先随机生成第一行，然后接下来按顺序生成新一行的每一列。

在生成第n行时，先生成一个标准1-n的数组standardArray。在处理nLineUsedArray第m列时，需要得到1到n-1行每行的第m列，组成一个colArray，由standardArray-colArray-nLineUsedArray，剩下的数组就是可以填充在该m列的数组，随机挑选出一个值放到nLineUsedArray第m列。

具体代码如下：

//生成一个数独，参数num
function createSuduko(num) {
    let line1 = getRandomLine(num, true);
    let arr2d = [line1];
    for (let i = 1; i < num; i++) {
        //获取标准数组
        let standLine = getRandomLine(num, false);
        let line = createLine(arr2d, num, standLine);
        // while (line.indexOf(undefined) !== -1) {
        //     line = createLine(arr2d, num, standLine);
        // }
        arr2d.push(line);
    }
    console.log(arr2d);
}

function createLine(arr2d, num, standLine) {
    let line = [];
    for (let col = 0; col < num; col++) {
        //获取已经该列已经用过的数字
        let colArray = getColArray(arr2d, col);
        //得到可以用的数
        let canUsedArray = getLineUsedColArray(standLine, colArray);
        let randomValue = getRandomNum(canUsedArray);
        line.push(randomValue);
        //标准数组中移除该数
        removeItemFromLine(standLine, randomValue);
    }
    return line;
}

function getRandomLine(num, isRandom) {
    let arr = [];
    for (let i = 1; i <= num; i++) {
        arr.push(i);
    }
    if (isRandom) {
        arr.sort(function () {
            return 0.5 - Math.random();
        });
    }
    return arr;
}


function getColArray(arr2d, col) {
    let cols = [];
    for (let i = 0; i < arr2d.length; i++) {
        let line = arr2d[i];
        console.log(line[col]);
        cols.push(line[col]);
    }
    return cols;
}


function getLineUsedColArray(arr1, arr2) {
    let diff = arr1.filter(function (val) {
        return arr2.indexOf(val) === -1
    });
    return diff;
}

function getRandomNum(arr) {
    // console.log(arr);
    let num = arr[Math.floor(Math.random() * arr.length)];
    return num;
}

function removeItemFromLine(arr, item) {
    let index = arr.indexOf(item);
    arr.splice(index, 1);
}

// createSuduko(3);
createSuduko(5);

以上代码有个问题，由于数字是随机生成的，存在standardArray-colArray-nLineUsedArray最后为空的情况。在得知有此类问题后，我在createSuduko方法的creatLine调用后，判断生成的line是否有undefined，如果有就再进行createLine，直到没有undefined。结果代码陷入死循环。。。

遍历解法

在随机解法出现问题后，我又进行了思考，我发现数独的每一行都是数字n全排列中的一行。也就是说，我可以先生成数字n的全排列，然后在这些全排列中找到n行，这n行满足数独条件。

全排列网上算法有很多，我这里采用了一种递归的方法。判断n行全排列是否满足数独，有一个取巧的方法，不用生成n行数组再判断，而是在生成n行数组的过程中就进行判断，这样能节省大量时间。

本人电脑cpu是 Intel i7-5557U CPU @ 3.10GHz。平均下来9的全排列耗时800ms左右，创建数独耗时在150ms左右。以下是具体代码：

/**
 * 创建数的全排列
 */
function createPermutation(num) {
    return doCreatePermutation(Array.from({length: num}, (v, i) => [i + 1]), num)
}

/**
 * @param upData 上一轮生成的二维数组
 * @param num 应当生成的数组长度
 */
function doCreatePermutation(upData, num) {
    // 如果上一轮生成的二维数组中，每行的长度等于num，说明已经满了
    if (upData[0].length === num) {
        return upData;
    }
    let data = [];
    for (let line = 0; line < upData.length; line++) {
        // 得到其中一行
        let oneLineArray = upData[line];
        for (let value = 1; value <= num; value++) {
            // 如果这一行中不包含在循环的值，则复制原数组，添加该值，然后放入新数组
            if (oneLineArray.indexOf(value) < 0) {
                let oneLineCopy = oneLineArray.concat();
                oneLineCopy.push(value);
                data.push(oneLineCopy);
            }
        }
    }
    // 进行下一轮
    return doCreatePermutation(data, num);
}

/**
 * 随机成成一个整数
 */
function random(n) {
    return Math.floor(Math.random() * Math.floor(n));
}


/**
 * 创建数独num*num的数独
 * 先创建一个数的全排列集合，然后再从全排列集合中寻找合适的num行组成数独
 */
function createSudoku(num) {
    let start = new Date().getTime();
    let permutation = createPermutation(num)
    console.log(new Date().getTime() - start);

    start = new Date().getTime();
    let result = doCreateSudoku(permutation, [], num);
    console.log(new Date().getTime() - start)
    return result;
}


/**
 * 从全排列创建数独
 */
function doCreateSudoku(permutation, sudoku, num) {
    // 如果数独的长度等于num说明已经满了
    if (sudoku.length === num) {
        return sudoku;
    }
    // 随机取全排列中的初始下标
    let randomNum = random(permutation.length);
    // 循环遍历全排列
    for (let i = 0; i < permutation.length; i++) {
        // 得到真实下标
        let index = (randomNum + i) % permutation.length;
        // 将该行放入数独中
        sudoku.push(permutation[index])
        // 如果将该行放入数独后, 还能满足数独要求
        if (isOK(sudoku, num)) {
            // 递归进入下一轮数独创建
            let realResult = doCreateSudoku(permutation, sudoku, num)
            // 如果递归后的长度等于num则说明创建完毕
            if (realResult.length === num) {
                return realResult;
            } else {
                // 如果递归完后数独长度不等于num，则说明在该轮中放入该行不能满足要求
                sudoku.pop();
            }
        } else {
            // 如果将该行放入数独后, 不能满足数独要求，需要弹出
            sudoku.pop();
        }
    }
    return sudoku;
}

// 判断准数独是否满足数独要求
function isOK(permutation, num) {
    for (let col = 0; col < num; col++) {
        let colArray = [];
        for (let line = 0; line < permutation.length; line++) {
            let oneLineArray = permutation[line];
            // 每一列中都不能有重复值
            if (colArray.indexOf(oneLineArray[col]) >= 0) {
                return false;
            } else {
                colArray.push(oneLineArray[col])
            }
        }
    }
    return true;
}


createSudoku(9).forEach(arr => console.log(arr))

附赠一个扣数字方法

function createEmptySudoku(num, emptyNum) {
    let allNum = num * num;
    if (allNum <= emptyNum) {
        return suduku;
    }
    let suduku = createSudoku(num);
    for (let i = 0; i < emptyNum; i++) {
        let randomIndex = random(allNum);
        while (suduku[Math.floor(randomIndex / num)][randomIndex % num] === undefined) {
            randomIndex = (randomIndex + 1) % allNum;
        }
        suduku[Math.floor(randomIndex / num)][randomIndex % num] = undefined;
    }
    return suduku;
}

createEmptySudoku(4,5).forEach(arr => console.log(arr))