I solved 100 LeetCode Problems using Motoko: Here's what I learned

Developers
8

New Article Problem 36 Valid Sudoku

Here’s the code. I will include 2 separate implementations as some might not be familiar with bitwise operations, the second example uses extra buffers which makes it less efficient with space but it achieves the same time complexity.

Using Bitwise operations

import Array "mo:base/Array";
import Nat32 "mo:base/Nat32";
import Nat8 "mo:base/Nat8";
import Iter "mo:base/Iter";

actor {
    type Cell = ?Nat8;
    type Row = [Cell];
    type Board = [Row];

    public func validBoardCheck(board: Board) : async Bool {
        let size = 9;
        var rows = Array.init<Nat32>(size, 0);
        var cols = Array.init<Nat32>(size, 0);
        var boxes = Array.init<Nat32>(size, 0);

        for (i in Iter.range(0, size - 1)) {
            for (j in Iter.range(0, size - 1)) {
                switch (board[i][j]) {
                    case null { /* Empty cell, skip */ };
                    case (?value) {
                        if (value < 1 or value > 9) {
                            return false; // Invalid value
                        };

                        let num = Nat32.fromNat(Nat8.toNat(value));
                        let bitMask = Nat32.bitshiftLeft(1, num - 1);

                        let boxIndex = (i / 3) * 3 + (j / 3);

                        // Check if the number is already in row, column, or box
                        if (Nat32.bitand(rows[i], bitMask) != 0 or
                            Nat32.bitand(cols[j], bitMask) != 0 or
                            Nat32.bitand(boxes[boxIndex], bitMask) != 0) {
                            return false; // Duplicate found
                        };
                        // Mark the number as seen in row, column, and box
                        rows[i] := Nat32.bitor(rows[i], bitMask);
                        cols[j] := Nat32.bitor(cols[j], bitMask);
                        boxes[boxIndex] := Nat32.bitor(boxes[boxIndex], bitMask);
                    };
                };
            };
        };
        return true; // Valid Sudoku board
    };
};

Using additional buffers + helper function

import Array "mo:base/Array";
import Iter "mo:base/Iter";
import Nat8 "mo:base/Nat8";
import Buffer "mo:base/Buffer";

actor {
    type Cell = ?Nat8;
    type Row = [Cell];
    type Board = [Row];

    func isValidValue(n: Nat8): Bool {
        n >= 1 and n <= 9
    };

    func hasDuplicates(cells: [Nat8]): Bool {
        var seen = Array.init<Bool>(10, false);
        for (n in cells.vals()) {
            if (seen[Nat8.toNat(n)]) return true;
            seen[Nat8.toNat(n)] := true;
        };
        return false;
    };

    public func validBoardCheck(board: Board): async Bool {
        // Check if the board has exactly 9 rows of 9 cells each
        if (board.size() != 9) {
            return false;
        };
        
        for (row in board.vals()) {
            if (row.size() != 9) {
                return false;
            };
        };

        // Buffer to collect filled cells for each row, column, and box
        var rows = Array.tabulate<Buffer.Buffer<Nat8>>(9, func(_) { Buffer.Buffer<Nat8>(9) });
        var cols = Array.tabulate<Buffer.Buffer<Nat8>>(9, func(_) { Buffer.Buffer<Nat8>(9) });
        var boxes = Array.tabulate<Buffer.Buffer<Nat8>>(9, func(_) { Buffer.Buffer<Nat8>(9) });

        for (i in Iter.range(0, 8)) {
            for (j in Iter.range(0, 8)) {
                switch (board[i][j]) {
                    case (?n) {
                        if (not isValidValue(n)) return false;
                        rows[i].add(n);
                        cols[j].add(n);
                        let boxIndex = (i / 3) * 3 + (j / 3); //0-8
                        boxes[boxIndex].add(n);
                    };
                    case null {};
                };
            };
        };

        // Check for duplicates in rows, columns, and boxes
        for (i in Iter.range(0, 8)) {
            if (hasDuplicates(Buffer.toArray(rows[i]))) return false;
            if (hasDuplicates(Buffer.toArray(cols[i]))) return false;
            if (hasDuplicates(Buffer.toArray(boxes[i]))) return false;
        };

        return true;
    };
};
5 Likes