数独验证

Question

问题解释

我编写了一个函数来验证sudoku。给定一个二维9×9数列：

• 每一行都应该有每一个数字1-9正好一次。
• 每一列都应该有每一个数字1-9正好一次。
• 每个正方形应该有每一个数字1-9正好一次。

 · · · | · · · | · · · 
 · · · | · · · | · · · 
 · · · | · · · | · · · 
-------+-------+-------
 · · · | · · · | · · · 
 · · · | · · · | · · · 
 · · · | · · · | · · · 
-------+-------+-------
 · · · | · · · | · · · 
 · · · | · · · | · · · 
 · · · | · · · | · · · 

查询

• 是否有更好的方法来解决这个问题，而不是为列和正方形创建数组，并单独验证这些数组？
• 是否有更好的方法来创建列数组，而不是运行neste循环和使用循环索引作为协调？
• 是否有比使用squareAnchors和运行嵌套循环(使用索引作为偏移量)更好地创建平方数组的方法？

如果它们更简洁/可读性更强，功能方法也是受欢迎的。

码

function isValidSudoku(sudoku: sudoku): boolean {
    const rows = sudoku;
    const columns = [];
    const squares = [];

    for (let r = 0; r < 9; r++) {
        const column = [];

        for (let c = 0; c < 9; c++) {
            column.push(rows[c][r]);
        }

        columns.push(column);
    }

    // Co-ordinates of top-left elements of squares
    const squareAnchors = [
        [0, 0], [3, 0], [6, 0],
        [0, 3], [3, 3], [6, 3],
        [0, 6], [3, 6], [6, 6]
    ];

    for (const anchor of squareAnchors) {
        const square = [];
        const [x, y] = anchor;

        for (let offsetX = 0; offsetX < 3; offsetX++) {
            for (let offsetY = 0; offsetY < 3; offsetY++) {
                square.push(rows[x + offsetX][y + offsetY]);
            }
        }

        squares.push(square);
    }

    const rowsValid = rows.every(isArrayValid);
    const columnsValid = columns.every(isArrayValid);
    const squaresValid = squares.every(isArrayValid);

    if (rowsValid && columnsValid && squaresValid) {
        return true;
    }

    return false;
}

isArrayValid：

function isArrayValid(array: row): boolean {
    const oneThroughNine = [1, 2, 3, 4, 5, 6, 7, 8, 9];
    array = array.sort();

    for (let i = 0; i < 9; i++) {
        if (array[i] !== oneThroughNine[i]) return false;
    }

    return true;
}

types/sudoku.ts：

import row from './row';

type sudoku = [
    row, row, row, row, row, row, row, row, row
];

export default sudoku;

types/row.ts：

type row = [number, number, number, number, number, number, number, number, number];

export default row;

示例

const validSudoku: sudoku = [
    [5, 3, 4,  6, 7, 8,  9, 1, 2],
    [6, 7, 2,  1, 9, 5,  3, 4, 8],
    [1, 9, 8,  3, 4, 2,  5, 6, 7],

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

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

const invalidSudoku: sudoku = [
    [5, 3, 4,  6, 7, 8,  9, 1, 2],
    [6, 7, 2,  1, 9, 0,  3, 4, 9],
    [1, 0, 0,  3, 4, 2,  5, 6, 0],

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

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

Answer 1

低效

由于糟糕的逻辑顺序和设计，您的代码有两个主要的低效率。

不需要排序

如果您写信给isArrayValid以标记所找到的数字，那么在oneThroughNine中的排序将非常慢，并且不需要。在标记找到的号码之前，检查它是否已被标记，如果是，则游戏无效。

function isArrayValid(array: row): boolean {
    const mustInclude = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]; // except for 0

    for (const val of array) {
        if (!mustInclude[val]) { return false }
        mustInclude[val] = 0; // mark the position as found
    }
    return true;    
}

当结果已知为

时，

处理

在主函数的底部，检查行、列和方格。问题是，如果其中一行无效，即使您知道游戏是无效的，您仍然会检查列和方块。

如果将行、列和正方形放置在数组中并使用Array.every进行测试，则可以在第一个糟糕的集合中退出。

return [rows, columns, squares].every(set => set.every(isArrayValid));

然而..。

不要在需要数据之前创建数据，

在检查行之前创建和保存列和方块，可能不需要它们，因为行可能会发现无效的游戏。

你也不需要保留每一列和每一个正方形。在创建它们时检查它们，如果第一个列无效，则没有创建9列的意义。广场也是一样

我还将isArrayValid的名称更改为isInvalid，以避免每次测试时都使用!。

function isValidSudoku(sudoku: sudoku): boolean {
    if (sudoku.some(isInvalid)) { return false }

    for (let r = 0; r < 9; r++) {
        const column = [];
        for (let c = 0; c < 9; c++) { column.push(sudoku[c][r]) }
        if (isInvalid(column)) { return false }

    }
    const squareAnchors = [[0, 0], [3, 0], [6, 0], [0, 3], [3, 3], [6, 3], [0, 6], [3, 6], [6, 6]];

    for (const [x, y] of squareAnchors) {
        const square = [];
        for (let ix = 0; ix < 3; ix++) {
            const row = sudoku[x + ix];
            for (let iy = 0; iy < 3; iy++) { square.push(row[y + iy]) }
        }
        if (isInvalid(square)) { return false }
    }
    return true;
}
function isInvalid(set: row): boolean {
    const mustInclude = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]; // except for 0

    for (const val of set) {
        if (!mustInclude[val]) { return true }
        mustInclude[val] = 0; // mark the position as found
    }
    return false;    
}   

还可以做许多其他事情来改进代码，例如

• 在创建列和方阵时检查每个值。
• 使用位字段而不是数组来标记包含的值。
• 将输入数组作为一维(平面)，这样就不必执行所有的双索引和嵌套循环。

但是，只有当你有数以百万计的游戏需要检查，并且需要每一盎司的表现时，你才会这样做。进一步的优化只会给您带来几个百分点的改进。