Valid Soduku

Problem

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  • Each row must contain the digits 1-9 without repetition.
  • Each column must contain the digits 1-9 without repetition.
  • Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

  • A Sudoku board (partially filled) could be valid but is not necessarily solvable.
  • Only the filled cells need to be validated according to the mentioned rules.

Example 1:

Input: board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

Example 2:

Input: board =
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Constraints:

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit 1-9 or ’.‘.

Solution

The algorithm is simple. The difficulty with this problem is managing complexity.

There are more terse solutions, but they are harder to understand. I think my solution is easy to understand, though it could be simplified e.g. by using Java streams or the standard library’s unique function.

Because the size of the input is fixed to a 9x9 board, the time and space complexity is O(1).

class Solution {
    public boolean isValidSudoku(char[][] board) {
        // check rows
        for (var i = 0; i < board.length; i++) {
            if (unique(board[i])) {
                continue;
            } else {
                return false;
            }
        }

        // check cols
        for (var i = 0; i < board.length; i++) {
            var col = col(board, i);
            if (unique(col)) {
                continue;
            } else {
                return false;
            }
        }

        // check blocks
        for (var x = 0; x < 3; x++) {
            for (var y = 0; y < 3; y++) {
              var block = block(board, x, y);
              if (unique(block)) {
                continue;
              } else {
                  return false;
              }
            }
        }

        return true;
    }

    // convert a block into an array
    public char[] block(char[][] board, int x, int y) {
        var offsetX = x * 3;
        var offsetY = y * 3;

        var boundX = offsetX + 3;
        var boundY = offsetY + 3;

        var block = new char[9];
        var i = 0;

        for (var cx = offsetX; cx < boundX; cx++) {
            for (var cy = offsetY; cy < boundY; cy++) {
                block[i] = board[cx][cy];
                i += 1;
            }
        }

        return block;
    }

    // convert a col into an array
    public char[] col(char[][] board, int n) {
        var col = new char[board.length];
        // iterate over every row, grab the nth char
        for (var i = 0; i < board.length; i++) {
            col[i] = board[i][n];
        }
        return col;
    }

    public boolean unique(char[] c) {
        var set = new HashSet<Character>();
        for (var i = 0; i < c.length; i++) {
            if (c[i] == '.') {
                continue;
            }
            if (set.contains(c[i])) {
                return false;
            }
            set.add(c[i]);
        }
        return true;
    }
}

Recent posts from blogs that I like

Guerrilla event planning at larger conferences

How to capitalism with care

via Xe Iaso

Creating an already-completed asynchronous activity in C++/WinRT, part 9

Cheating the delegates. The post Creating an already-completed asynchronous activity in C++/WinRT, part 9 appeared first on The Old New Thing.

via The Old New Thing

Weeknotes: GPT-4o mini, LLM 0.15, sqlite-utils 3.37 and building a staging environment

via Simon Willison