Unveiling the Puzzle: Solving the Most Popular Number Puzzle

DeepSeek did it again!

Welcome back! This week, we will delve into solving the most popular number puzzle on the planet. In the past, many would purchase newspapers solely to engage with this intriguing puzzle. Are you prepared?

This week's topics include:

1. Valid Sudoku

2. Optimistic vs Pessimistic Locking

Estimated read time: under 4 minutes

Determine the validity of a 9 x 9 Sudoku board. Validation is required only for the filled cells based on specific rules:

- Each row must include digits 1-9 without repetition.

- Each column must include digits 1-9 without repetition.

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

Note: A Sudoku board, even if partially filled, may be valid but not necessarily solvable. Validation is required only for the filled cells based on the mentioned rules.

Example 1:

Example 2:

Solve the problem here before proceeding to the solution.

In the upcoming years, either you will be working for AI or AI will be working for you.

Validating Sudoku Boards

To validate the Sudoku board, we will check for three conditions:

1. No repetition in rows

2. No repetition in columns

3. No repetition in 3x3 sub-boxes

We will utilize sets to efficiently monitor unique digits in each row, column, and sub-box. By evaluating each condition while traversing the board, we can ascertain its validity.

The time complexity is O(1) as the board size remains fixed at 9x9. Similarly, the space complexity is also O(1) since we employ a constant amount of additional space.

Sample starting state of a Sudoku board [5]

Optimistic vs Pessimistic Locking

When multiple users attempt to update the same data in a database concurrently, it can result in data inconsistencies. Database locking aids in preventing such conflicts.

There exist two primary methods to manage concurrent updates: Optimistic Locking and Pessimistic Locking.

Optimistic Locking:

Assuming conflicts are rare, this approach permits users to make changes freely but verifies for conflicts prior to saving. Each record possesses a version number that increments with each update. During the save process, the system validates if the last version number aligns with the one during the user's initial editing. If alterations were made in between, the version numbers would not match, resulting in a failed save.

This method is ideal for systems with infrequent conflicts, such as social media posts where users typically modify their own content. It is also more efficient, allowing other users to read or edit without hindrance.

Optimistic vs. Pessimistic locking in Rails

Pessimistic Locking:

Adopting a cautious approach, Pessimistic Locking immediately locks a record once a user initiates editing. Subsequent users must await the completion of the initial user.

This method is more suitable for systems where conflicts are probable, and data consistency is vital, like in banking transactions. However, extended lock durations may lead to performance challenges as other users are compelled to wait.

TiDB Pessimistic Transaction Mode