Wenglor Students Software Challenge 2025

Task 2: Web app

Framework: Rocket (Rust)

Author: Vlad Oleksik

This application relies on the solver in the vladoleksik/sudoku-solver-wssc2025 repository.

Functionality overview

This app represents an interface for users to get challenged with sudoku puzzles generated on the server, or to get assistance with their own puzzles, either by loading them manually or by uploading a picture of a sudoku board, which will have its cells automatically processed.

Solving interface

The solving interface is centered around an interactive Sudoku board, accompanied by a top bar with buttons that provide various functionalities to enhance the solving experience. The board can be interacted with using either a pointer or keys on the keyboard, with intuitive shortcuts wirtten in. Upon a violation of the uniqueness constraints of the sudoku, the conflicting cells are highlighted in red.

Below is an overview of the available features:

Top Bar Functionalities

1. New Game
   Starts a new game by generating a fresh Sudoku puzzle. This resets the board and timer.

2. Clear
   Clears the current board and restarts the game. Any progress made is lost.

3. Solve
   Automatically solves the Sudoku puzzle. Using this feature does not grant any credit for solving the puzzle.

4. Check Cell
   Allows the user to verify the correctness of a specific cell:

   • If the value is incorrect, the cell is marked as an error, and it counts as a mistake.
   • If the value is correct, the cell is marked as a given, and it counts as a hint.

5. Reveal Cell
   Reveals the correct value for a specific cell. This action counts as a hint.

6. Hint
   Highlights a cell that can be filled with a single value based on the simplest Sudoku rules. This feature is designed to assist users without solving the puzzle for them.

Timer and Completion Modal

The application tracks the time taken to solve the puzzle. Upon successful completion, a "Congratulations!" modal is displayed, showcasing the total time spent solving the puzzle, as well as the hints taken and the mistakes made.

Screenshots

Below are a few screenshots illustrating the solving interface and its features:

The main Sudoku board with the top bar functionalities.

The "Congratulations!" modal displayed upon puzzle completion.

This intuitive interface ensures a smooth and engaging experience for users of all skill levels.

Image board recognition

The application is able to recognize a Sudoku puzzle from an image using OpenCV.js for image processing and Tesseract for optical character recognition (OCR).

Steps:

1. The input image is loaded and preprocessed using OpenCV.js:
   • The image is blurred and segmented to enhance feature detection.
   • The largest contour in the image is identified and approximated to a quadrilateral.
   • A perspective transformation is applied to isolate the Sudoku grid, and the resulting image is resized for further processing.
2. The transformed image is divided into 81 equal-sized square chunks, corresponding to the cells of the Sudoku grid.
3. Each cell is passed to Tesseract for OCR to detect any digits present.
4. The recognized digits are compiled into the state of the Sudoku puzzle.

Note:

• The server handles only Sudoku puzzle logic and does not process or store image data.
• This design ensures that, since the image processing is not critical, it remains client-side, avoiding the transmission of unnecessary information.

Generation

This module implements the logic for generating puzzles on the server side.

The puzzle generation process begins with an empty grid, which is then filled using a backtracking algorithm with randomized branching. The backtracking approach ensures that the grid is filled in a valid manner, adhering to the rules of the puzzle. The randomization in branching introduces variability in the generated puzzles, making each puzzle unique.

Once the grid is fully populated, the algorithm transitions to the puzzle reduction phase. In this phase, the algorithm attempts to remove one cell value at a time from the grid. After each removal, the solver is invoked to verify that the puzzle still has exactly one unique solution. If removing a cell causes the puzzle to have multiple solutions or no solution, the removal is reverted, and the cell value is restored.

The target number of cells to remove is determined by the desired difficulty level of the puzzle. Higher difficulty levels aim to remove more cells, making the puzzle more challenging to solve, while lower difficulty levels retain more cells, resulting in easier puzzles. The algorithm carefully balances cell removal and solution uniqueness to ensure that the generated puzzle meets the specified difficulty criteria.

This approach ensures that the generated puzzles are both solvable and appropriately challenging for the intended difficulty level.

Automatic solving

The solving algorithm is implemented as a Rust module on the server. The algorithm relies on backtracking with early pruning to achieve a low solve time.

A board state is represented as an array of cells, each cell being allocated a bit to mark the possibility for each of the 9 values to be contained in the cell.

To achieve early pruning, I have implemented three constraint propagation rules that are each applied as long as they continue to propagate information about the board. The rules are as follows:

1. Uniqueness constraint: For each (newly) filled cell, the cells on the same row, column, or block will have the respective value marked as impossible.
2. Existence constraint: Among all cells on each row, column, and block, is a specific value is only possible in one of them, then the respective cell will be marked as containing the value in question.
3. Naked pairs constraint: If two cells in a common area each only have the same two possible values, then the respective values will be considered impossible in any other cells in the respective area of interest (row/column/block).

While these rules are largely arbitrary and can be extended with more heuristics (to narrow down the recursive breadth and depth while doing backtracking) – which would reduce the time complexity for the hardest puzzles (and for generalized sudoku/graph colouring problems) – or partly eliminated to ensure lower "constants" at a given backtracking level – which would facilitate solving the easiest puzzles –, this strategy has been largely found to optimise the solving performance.

Mobile support

This app is designed to provide an intuitive and seamless user experience on mobile devices. It features custom keyboard events tailored for efficient input, ensuring users can interact with the app effortlessly. Additionally, fluent animations enhance the overall experience, making transitions and interactions feel smooth and responsive.

The mobile interface.

While the app performs well on most devices, minor visual artifacts may occasionally appear on certain niche models, browsers, or screen sizes, particularly in landscape mode.

Building and deploying the app

To build and deploy this Rocket app on Windows, follow these steps:

1. Install Rust
   Ensure you have Rust installed on your system. You can install Rust using rustup:
   Open PowerShell and run:

   iwr -useb https://sh.rustup.rs | iex

   After installation, ensure cargo (Rust's package manager) is available:

   cargo --version

2. Clone the repository
   Clone this repository to your local machine:
   Open a terminal and run:

   git clone https://github.com/vladoleksik/sudoku-web-app.git
   cd sudoku-web-app

3. Build the application
   Use cargo to build the application:

   cargo build --release

4. Run the application locally
   Start the Rocket server locally:

   cargo run

   By default, the app will be available at http://localhost:8000.

5. Deploy the application
   The application can be deployed with a platform such as Shuttle for Rust applications:

   • Installing the Shuttle CLI:

     cargo install shuttle-cli

   • Logging in to Shuttle:

     shuttle login

   • Deploying the app:

     shuttle deploy

For more details, refer to the Rocket documentation.