检查Sudoku解决方案是否有效

Question

你得到了一个数独谜题的解决方案.编写代码以检查它是否是有效的解决方案.

你的函数签名应该是:
boolean isValid(int starti,int startj,int endi,int endj)

那些不熟悉数独的人的规则:

• 网格大小为9x9,分为9个3x3区域
• 每行必须包含1-9的所有数字
• 每列必须包含1-9中的所有数字
• 每个3x3平方必须包含1-9的所有数字

我没有问过这个问题,但是在几个 地方看到了它.检查最后一条规则可能是有趣的部分

Answer 1

// rows
for (int i=0; i<9; i++) {
    std::bitset<9> filled;
    for (int j=0; j<9; j++)
        filled.set(grid[i][j] - 1);
    if (filled.count() != 9)
        return false;
}

// ... similar with the loops "swapped" to get the columns
// (or do both in one loop)

for (int i=0; i<9; i += 3)
    for (int j=0; j<9; j += 3) {
        std::bitset<9> filled;
        for (int k=0; k<3; k++)
            for (int l=0; l<3; l++)
                filled.set(grid[i+k][j+l] - 1);
        if (filled.count() != 9)
            return false;
    }

return true;

Answer 2

对不起,我知道这一定是作业,但我无法自拔.提出一些东西真是太有趣了:-)

充满LINQ的勺子使药物下降:

public class Sudoku
{
    private int[][] sudoku;

    public Sudoku(int[][] sudoku)
    { 
        // TODO: Validate bounds and values
        this.sudoku = sudoku;
    }

    public bool Validate() =>
        VerticalLines.All(IsValid)
        && HorizontalLines.All(IsValid)
        && Squares.All(IsValid);

    IEnumerable<IEnumerable<int>> VerticalLines =>
        from line in sudoku select line;

    IEnumerable<IEnumerable<int>> HorizontalLines =>
        from y in Enumerable.Range(0, 9)
        select (
            from x in Enumerable.Range(0, 9)
            select sudoku[x][y]);

    IEnumerable<IEnumerable<int>> Squares =>
        from x in Enumerable.Range(0, 3)
        from y in Enumerable.Range(0, 3)
        select GetSquare(x, y);

    IEnumerable<int> GetSquare(int x, int y) =>
        from squareX in Enumerable.Range(0, 3)
        from squareY in Enumerable.Range(0, 3)
        select sudoku[x * 3 + squareX][y * 3 + squareY];

    bool IsValid(IEnumerable<int> line) => !(
        from item in line
        group item by item into g
        where g.Count() > 1
        select g)
        .Any();
}

关于这个解决方案的好处是,如果你说你想出这个,没有老师会相信你;-)

Answer 3

SQL允许您将规则定义为CONSTRAINTS:禁止无效的puzzel并且不能存在.

        -- Domain with only values 1..9 allowed,
        -- used for both the {x,y,z} coordinates and the cell values.
CREATE DOMAIN one_nine
        AS INTEGER
        CHECK (value >= 1 AND value <= 9)
        ;

        -- Table containing exactly one sudoku puzzle.
        -- The zzz coordinate (the "box number") is formally redundant
        -- (since it is functionally dependant on {xxx,yyy})

DROP TABLE IF EXISTS sudoku3 CASCADE;
CREATE TABLE sudoku3
        ( yyy one_nine NOT NULL
        , xxx one_nine NOT NULL
        , zzz one_nine NOT NULL
        , val one_nine
        );

        -- First constraint: (x,y) is unique
ALTER TABLE sudoku3 ADD PRIMARY KEY (xxx,yyy);

        -- Three constraints for unique values for {rows,columns,boxes}
CREATE UNIQUE INDEX sudoku_xv ON sudoku3 (xxx,val);
CREATE UNIQUE INDEX sudoku_yv ON sudoku3 (yyy,val);
CREATE UNIQUE INDEX sudoku_zv ON sudoku3 (zzz,val);

        -- Create empty board.
INSERT INTO sudoku3 (yyy, xxx, zzz)
SELECT  1+(nn/9)
        , 1+(nn%9)
        , 1+3*((nn/3)%3)+1*(nn/27)
        -- generate_series() is postgres-specific
        FROM generate_series(0,80) AS nn;

现在,可以更新 - > val成员,但结果表永远不会违反四个约束中的任何一个(三个实际上是INDEXES,但这在这里并不重要).

检查完全有效的填充表意味着:检查是否有81个非NULL条目:

SELECT 1 AS result -- COUNT(*) 
    FROM sudoku3
    WHERE val IS NOT NULL
    HAVING COUNT(*) = 81
      ;