Leetcode sudoku hợp lệ

Question

Liên kết đây

Tôi sẽ đưa vào một giải pháp bằng Python và C ++ và bạn có thể xem lại một giải pháp. Tôi chủ yếu quan tâm đến việc xem lại mã C ++, đây là thứ mà tôi mới bắt đầu học gần đây; những người không biết C ++ có thể xem lại mã Python. Cả hai giải pháp chia sẻ logic tương tự, vì vậy việc xem xét sẽ áp dụng cho bất kỳ giải pháp nào.

---

Báo cáo vấn đề

Xác định xem bảng Sudoku 9 x 9 có hợp lệ không. Chỉ các ô đã điền mới cần được xác thực theo các quy tắc sau:

• Mỗi hàng phải chứa các chữ số 1-9 không lặp lại. Mỗi cột
• phải chứa các chữ số 1-9 không lặp lại. Mỗi chín 3 x
• 3 ô con của lưới phải chứa các chữ số 1-9 không lặp lại.

Ghi chú:

Một bảng Sudoku (được điền một phần) có thể hợp lệ nhưng không nhất thiết là có thể giải được. Chỉ các ô đã điền mới cần được xác thực theo các quy tắc đã đề cập.

Ví dụ 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

Ví dụ 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.

valid_sudoku.py

def is_valid(board, empty_value='.', b_size=3):
    seen = set()
    size = b_size * b_size
    for row in range(size):
        for col in range(size):
            if (value := board[row][col]) == empty_value:
                continue
            r = f'0{row}{value}'
            c = f'1{col}{value}'
            b = f'2{row // b_size}{col // b_size}{value}'
            if r in seen or c in seen or b in seen:
                return False
            seen.update({r, c, b})
    return True


if __name__ == '__main__':
    g = [
        ["5", "3", ".", ".", "7", "5", ".", ".", "."],
        ["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"],
    ]
    print(is_valid(g))

Số liệu thống kê:

Runtime: 92 ms, faster than 81.70% of Python3 online submissions for Valid Sudoku.
Memory Usage: 14.1 MB, less than 73.95% of Python3 online submissions for Valid Sudoku.

Đây là một giải pháp thay thế bằng cách sử dụng numpy, nó ngắn hơn và dễ đọc hơn nhưng chậm hơn:

import numpy as np


def is_valid(board, size=3, empty_value='.'):
    board = np.array(board)
    blocks = board.reshape(4 * [size]).transpose(0, 2, 1, 3).reshape(2 * [size * size])
    for grid in [board, board.T, blocks]:
        for line in grid:
            non_empty = line[line != empty_value]
            if not len(non_empty) == len(set(non_empty)):
                return False
    return True

Số liệu thống kê:

Runtime: 172 ms, faster than 5.19% of Python3 online submissions for Valid Sudoku.
Memory Usage: 30.2 MB, less than 11.10% of Python3 online submissions for Valid Sudoku.

valid_sudoku.h

#ifndef LEETCODE_VALID_SUDOKU_H
#define LEETCODE_VALID_SUDOKU_H

#include <string_view>
#include <unordered_set>

bool sudoku_check_update(const size_t &row, const size_t &col, const char &value,
                         const int &block_size,
                         std::unordered_set<std::string_view> &seen);

bool sudoku_check(const std::vector<std::vector<char>> &board,
                  const char &empty_value = '.');

void test1();

#endif //LEETCODE_VALID_SUDOKU_H

valid_sudoku.cpp

#include <iostream>
#include <vector>
#include <string_view>
#include <cmath>
#include <unordered_set>


bool sudoku_check_update(const size_t &row, const size_t &col, const char &value,
                         const int &block_size,
                         std::unordered_set<std::string_view> &seen) {
    std::string_view r, c, b;
    r = "0-" + std::to_string(row) + value;
    c = "1-" + std::to_string(col) + value;
    b = "2-" + std::to_string(row / block_size) + std::to_string(col / block_size) +
        value;
    for (const auto &seen_id: {r, c, b}) {
        if (seen.find(seen_id) != seen.end())
            return false;
        seen.insert(seen_id);
    }
    return true;
}


bool sudoku_check(const std::vector<std::vector<char>> &board,
                  const char &empty_value = '.') {
    std::unordered_set<std::string_view> seen;
    const auto row_size = board.size();
    const int block_size = std::sqrt(row_size);
    for (size_t row = 0; row < row_size; ++row) {
        for (size_t col = 0; col < row_size; ++col) {
            auto value = board[row][col];
            if (value == empty_value)
                continue;
            if (!sudoku_check_update(row, col, value, block_size, seen))
                return false;
        }
    }
    return true;
}


void test1() {
    std::vector<std::vector<char>> v = {
            {'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'}
    };
    std::cout << sudoku_check(v);
}

Số liệu thống kê:

Runtime: 48 ms, faster than 17.98% of C++ online submissions for Valid Sudoku.
Memory Usage: 20.4 MB, less than 22.55% of C++ online submissions for Valid Sudoku.

Answer 1

Dưới đây là một số gợi ý về cách bạn có thể cải thiện mã của mình.

Phiên bản C ++

Sử dụng tất cả các #includes

Loại std::vector<std::vector<char>>được sử dụng trong định nghĩa của sudoku_check()trong tệp tiêu đề, nhưng #include <vector>bị thiếu trong danh sách bao gồm ở đó.

Thu nhỏ giao diện

Các .htập tin là một tuyên bố của giao diện để phần mềm của bạn. Đây .cpplà việc thực hiện giao diện đó. Thực hành thiết kế tốt là giảm thiểu giao diện đến mức mà các chương trình bên ngoài cần. Vì lý do đó, tôi sẽ loại bỏ các sudoku_check_update()và test1()các chức năng và chỉ sử dụng này:

#ifndef LEETCODE_VALID_SUDOKU_H
#define LEETCODE_VALID_SUDOKU_H

#include <vector>

bool sudoku_check(const std::vector<std::vector<char>> &board,
                  const char &empty_value = '.');

#endif //LEETCODE_VALID_SUDOKU_H

Việc triển khai phải bao gồm tiêu đề giao diện

Như tiêu đề của phần này đã nêu, việc triển khai phải bao gồm tiêu đề giao diện. Điều này đảm bảo rằng giao diện và triển khai phù hợp, đồng thời loại bỏ lỗi. Nếu chúng ta làm điều đó trong trường hợp này, chúng ta thấy rằng giá trị mặc định cho empty_valueđược khai báo hai lần. Nó chỉ nên được khai báo một lần trong tệp tiêu đề.

Tạo các chức năng cục bộ static

Với giao diện nhỏ hơn như đã đề cập ở trên, sudoku_check_updatehàm trở thành một chi tiết triển khai chỉ được sử dụng trong .cpptệp. Vì lý do đó, nó nên được thực hiện staticđể trình biên dịch biết rằng việc nội tuyến hàm là an toàn.

Từ khóa statickhi được sử dụng với khai báo hàm xác định rằng liên kết là nội bộ. Nói cách khác, nó có nghĩa là không có gì bên ngoài tệp đó có thể truy cập vào hàm. Điều này rất hữu ích để trình biên dịch biết bởi vì, ví dụ, nếu một statichàm chỉ được sử dụng một lần và / hoặc nhỏ, trình biên dịch có tùy chọn đặt mã nội tuyến. Nghĩa là, thay vì ngôn ngữ hợp ngữ thông thường call... các retlệnh để chuyển đến một chương trình con và quay lại từ nó, trình biên dịch có thể chỉ cần đặt mã cho hàm trực tiếp tại vị trí đó, tiết kiệm chi phí tính toán của các lệnh đó và giúp đảm bảo bộ nhớ cache. dự đoán là đúng (vì thông thường bộ nhớ cache tận dụng vị trí của tham chiếu .)

Ngoài ra, hãy đọc về các chỉ định của lớp lưu trữ để hiểu rõ hơn về những gì statichoạt động trong các ngữ cảnh khác và các chỉ định khai báo chung hơn để giải thích constexprvà hơn thế nữa.

Sửa lỗi!

Mã hiện đang sử dụng string_viewkhông phù hợp. A std::string_viewthực chất là một con trỏ tới một chuỗi tồn tại. Nhưng các chuỗi của bạn được tạo và xóa động, vì vậy đây là cách sử dụng không hợp lệ std::string_view. Nếu bạn thay thế tất cả các trường hợp của string_viewbằng string, chương trình sẽ hoạt động.

Các vấn đề về bộ nhớ như thế này và lỗi đồng thời là một trong những vấn đề khó khăn nhất đối với lập trình viên để phát hiện và sửa chữa. Khi bạn có thêm kinh nghiệm, bạn sẽ thấy rằng khả năng phát hiện những vấn đề này và tránh chúng xảy ra theo phản xạ tốt hơn. Có nhiều cách tiếp cận để tìm ra những lỗi như vậy. Xem lớp đơn giản phát hiện rò rỉ cho một số trong số chúng.

Viết các hàm kiểm tra tốt hơn

Lỗi được đề cập ở trên dễ dàng được phát hiện bằng cách gọi hàm nhiều lần với các đầu vào khác nhau. Có lẽ bạn đã có một loạt các hàm kiểm tra phong phú hơn, nhưng nếu chưa, tôi thực sự khuyên bạn nên tạo và áp dụng chúng.

Sử dụng cấu trúc dữ liệu hiệu quả

Nếu mục tiêu của mã này là hiệu quả về cả thời gian chạy và bộ nhớ, thì có rất nhiều cải tiến có thể được thực hiện. Thứ nhất, cấu trúc dữ liệu std::unordered_set<std::string_view>không tối ưu. Bất cứ khi nào chúng tôi thực hiện tối ưu hóa hiệu suất, việc đo lường sẽ rất hữu ích. Vì vậy, tôi đã viết một chương trình thử nghiệm rất đơn giản dựa trên mẫu đồng hồ bấm giờ của mình . Nó ở đây:

#include "valid_sudoku.h"
#include "stopwatch.h"
#include <iostream>
#include <vector>
#include <string>

int main(int argc, char* argv[]) {
    std::vector<std::vector<char>> v = {
            {'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'}
    };
    if (argc != 2) {
        std::cout << "Usage: " << argv[0] << " num_trials\n";
        return 1;
    }
    auto iterations = std::stoul(argv[1]);

    Stopwatch<> timer{};

    bool valid{true};
    for (auto i{iterations}; i; --i) {
        valid &= sudoku_check(v);
    }

    auto elapsed{timer.stop()};
    if (!valid) {
        std::cout << "The program failed!\n";
        return 2;
    }
    std::cout << iterations << " trials took " << elapsed << " microseconds\n"
        " for an average of " << elapsed/iterations << " microseconds/trial\n";
}

Khi tôi chạy điều này trên máy của mình với 1.000.000 lần dùng thử, (với lỗi được lưu ý ở trên đã được sửa như mô tả), đây là kết quả tôi nhận được:

1000000 thử nghiệm mất 1,44351e + 07 micro giây với mức trung bình là 14,4351 micro giây / thử nghiệm

Bây giờ chúng ta hãy nghĩ về một cấu trúc dữ liệu hiệu quả hơn. Thay vì một unordered_set, chúng ta có thể sử dụng một tập hợp các mảng cố định. Có chín hàng, chín cột và chín tập hợp con. Mỗi cái có chứa một số hoặc không. Đối với tôi, điều đó cho thấy chúng ta có thể sử dụng một đối tượng như thế này:

using SeenType = std::array<std::array<std::array<bool, 9>, 9>, 3>;

Nó chứa 3 kiểu (hàng, cột, dãy con) và trong mỗi kiểu là 9 tập hợp 9 bit; một bit cho mỗi số. Hãy viết lại hàm để sử dụng:

static bool sudoku_check_update(std::size_t row, std::size_t col, 
        char value, SeenType &seen) {
    static constexpr std::size_t block_size{3};
    static_assert(block_size * block_size == row_size, "block_size must be the square root of row_size");
    const std::size_t block = col / block_size + block_size * (row / block_size);
    std::size_t dim{0};
    value -= '1';   // adjust from digits '1'-'9' to indices 0-8.
    for (const auto &seen_id: {row, col, block}) {
        if (seen[dim][seen_id][value])
            return false;
        seen[dim][seen_id][value] = true;
        ++dim;
    }
    return true;
}

Bây giờ chạy lại chương trình với một triệu bản dùng thử như trước:

1000000 thử nghiệm mất 562153 micro giây trung bình là 0,562153 micro giây / thử nghiệm

Vì vậy, một thay đổi đó đã làm cho mọi thứ nhanh hơn 25 lần . Chúng ta cũng có thể sử dụng thực tế rằng các kích thước được biết là sử dụng a std::array<std::array<char, 9>, 9>thay vì các vectơ và sử dụng constexprcho các kích thước đó. Thực hiện thay đổi đó, chúng tôi nhận được điều này:

1000000 thử nghiệm mất 160808 micro giây trung bình là 0,160808 micro giây / thử nghiệm

Vì vậy, bây giờ nó nhanh hơn 90 lần .

Ưu tiên các {}khởi tạo kiểu

Bạn có thể nhận thấy rằng đoạn mã tôi viết có xu hướng sử dụng {}kiểu khởi tạo. Có một số lý do cho điều này, bao gồm thực tế là khi bạn nhìn thấy nó, nó luôn là một lần khởi tạo và không thể nhầm với một cuộc gọi hàm. Xem ES.23 để biết thêm chi tiết.

Chuyển các giá trị thay vì tham chiếu cho các kiểu dữ liệu ngắn

Thay vì vượt qua const size_t &colhoặc const char& value, nói chung tốt hơn là vượt qua những thứ đó theo giá trị. Điều này thường có lợi vì con trỏ có thể dài hơn thứ mà nó trỏ tới và vì nó cho phép loại bỏ việc tra cứu bộ nhớ và chuyển hướng.

Di chuyển các phép tính từ thời gian chạy sang thời gian biên dịch nếu thực tế

Nó có thể không mất nhiều thời gian, nhưng dòng này không nhanh như nó có thể:

const int block_size = std::sqrt(row_size);

Điều này làm là chuyển đổi row_sizethành a double, gọi hàm dấu phẩy sqrtđộng và chuyển đổi doublengược lại thành an int. Ngược lại, chúng ta chỉ có thể viết thế này:

constexpr std::size_t block_size{3};

Bây giờ không mất thời gian trong thời gian chạy vì giá trị được biết tại thời gian biên dịch. Nó cũng giúp loại bỏ việc phải truyền giá trị và như trên, định nghĩa của nó có thể được đặt ở vị trí duy nhất mà nó thực sự cần thiết, đó là bên trong sudoku_check_updatehàm.

Nói chung, chúng tôi muốn chuyển mọi thứ từ thời gian chạy sang thời gian biên dịch vì ba lý do:

1. các chương trình thường được chạy nhiều lần hơn so với khi chúng được biên dịch, vì vậy chúng tôi tối ưu hóa để xảy ra phổ biến hơn
2. chúng tôi phát hiện lỗi càng sớm, chúng càng rẻ và dễ sửa hơn
3. nó có xu hướng làm cho phần mềm nhỏ hơn và nội bộ, đơn giản hơn, giúp cải thiện tốc độ tải, hiệu suất bộ nhớ cache và phần mềm đơn giản hơn có xu hướng cải thiện chất lượng

Phiên bản Python

Tránh continuebằng cách cơ cấu lại vòng lặp

Về bản chất, không có gì sai khi bạn sử dụng toán tử hải mã, nhưng dường như có rất ít lý do để không đảo ngược ý nghĩa của phép so sánh và chỉ cần xử lý cập nhật hơn là sử dụng continue. Nó không ảnh hưởng đến hiệu suất, nhưng hỗ trợ người đọc mã hiểu được dòng chương trình. Tôi có xu hướng đặt sớm các mệnh đề "cứu trợ" trong một hàm để nhanh chóng từ chối các điều kiện không hợp lệ, nhưng tránh continuelặp lại; cuối cùng đó là câu hỏi về khả năng đọc và phong cách trong C ++ hoặc Python.

Sử dụng cấu trúc dữ liệu hiệu quả hơn

Những gì đúng trong C ++ cũng hoạt động trong Python. Chúng ta có thể sử dụng các ý tưởng tương tự và tăng tốc mã lên hệ số 6:

def is_valid(board, empty_value='.', b_size=3):
    size = b_size * b_size
    seen = [[(size * [False]) for _ in range(size)] for _ in range(3)]
    for row in range(size):
        for col in range(size):
            if (value := board[row][col]) != empty_value:
                block = col // b_size + b_size * (row // b_size)
                dim = 0
                value = int(value) - 1
                for seen_id in [row, col, block]:
                    if seen[dim][seen_id][value]:
                        return False
                    seen[dim][seen_id][value] = True
                    dim += 1
    return True

Answer 2

Minor (và Python), nhưng cá nhân tôi thấy điều này hơi khó hiểu:

if (value := board[row][col]) == empty_value:
    continue
r = f'0{row}{value}'
c = f'1{col}{value}'
b = f'2{row // b_size}{col // b_size}{value}'

Bạn đang sử dụng một biểu thức gán để gán một giá trị, nhưng sau đó chỉ sử dụng nó trong trường hợp sai. Tôi nghĩ điều này sẽ gọn gàng hơn nhiều bằng cách sử dụng một câu lệnh gán đơn giản:

value = board[row][col]
if value == empty_value:
    continue
r = f'0{row}{value}'
c = f'1{col}{value}'
b = f'2{row // b_size}{col // b_size}{value}'

Tôi không nghĩ rằng dòng đã lưu đáng để chôn vùi việc tạo một biến.

Answer 3

C ++

Nó đơn giản hơn và có thể nhanh hơn để chuyển các kiểu dữ liệu đơn giản nhỏ như size_tvà chartheo giá trị, không phải bằng tham chiếu. Vì vậy, chúng ta nên có:

bool sudoku_check_update(size_t row, size_t col, char value, int block_size,
                         std::unordered_set<std::string_view> &seen)

bool sudoku_check(const std::vector<std::vector<char>> &board,
                  char empty_value = '.')

---

Quan trọng hơn: std::string_view không thể được sử dụng để lưu trữ chuỗi. Nó không sở hữu chuỗi, nó chỉ là một con trỏ và một kích thước.

Khi làm điều gì đó như thế này:

std::string_view r = "0-" + std::to_string(row) + value;

... chúng tôi xây dựng một tạm thời std::stringvà sau đó gán nó cho a string_view. Tuy nhiên, chuỗi tạm thời đi ra ngoài phạm vi ở cuối dòng này!

Nó đã trôi qua. Chuỗi này không còn nữa. Nó đã không còn nữa. Nó hết hạn và đi gặp nhà sản xuất của nó. Đây là một chuỗi muộn. Đó là một khó khăn. Bereft của cuộc sống nó yên nghỉ. Nếu chúng tôi không đóng đinh nó vào một cái std::string_viewthì nó sẽ đẩy những bông cúc lên. Nó đã hạ màn và tham gia dàn hợp xướng vô hình. Đây là một chuỗi cũ.

Nói cách khác, đó là hành vi không xác định để thử và sử dụng nó string_view. Vì vậy r, cvà bcần phải là std::stringchính họ. Và seennên a std::unordered_set<std::string>.

---

Re. std::string_view:

std::string_viewtrỏ đến một loạt các ký tự trong bộ nhớ. Các ký tự này có thể được lưu trữ trong a std::string, trong a std::array, a std::vectorhoặc trong chuỗi ký tự.

Bằng cách sử dụng, std::string_viewchúng tôi có được cùng một giao diện (tìm kiếm, so sánh, tạo chuỗi con) bất kể bộ nhớ cơ bản đó là gì. Vì vậy, nó hữu ích như một ngôn ngữ chung giữa các loại này.

Vì std::string_viewkhông sở hữu các ký tự, nó không cấp phát bộ nhớ hoặc sao chép chính nó. Điều này làm cho nó hữu ích cho những thứ như phân tích cú pháp các tệp văn bản dài - chúng ta có thể tìm kiếm và so sánh trong các chuỗi con mà không cần thực hiện thao tác sao chép std::string.

Sự cân bằng là chúng ta phải đảm bảo rằng thời gian tồn tại của chuỗi thực trong bộ nhớ dài hơn thời gian tồn tại của chuỗi string_view.