Clarifications

If any questions or clarifications are asked which would be useful for everyone I will note them here. Please check this often.

• As a suggestion from one of you, I have recorded a bunch of example responses from the server which you can copy-paste into your code directly to allow you to work on the interesting parts of the assessment without worrying about the networking. They can be found here.
• Instead of creating a new PCB with udp_new() every time you send an ethernet message, create one and reuse it. Normally this doesn’t matter, but sometimes if you create a new PCB for each message then lwIP will send your REQUEST_INFO and REQUEST_CHUNK messages from different ports which confuses the server.
  • You will know that this issue is affecting you if the server sends you the error No active session - send REQUEST_INFO first
• The extension marks discussed in the markscheme are for solving large puzzles (potentially larger than the normal Hard tier) or for solving them particularly quickly etc. Basically they are for me and Steven to reward particularly good/interesting solutions. Most people should not worry about them.

Useful Tips

• You are not required to implement constraint propagation, but it will hugely cut down the search space.
• Similarly, there are many more complex strategies for solving Nonogram puzzles but the basic constraint propagation described in the paper is probably good enough.
• Avoid recursion. It is OK to use on the ARM, but you cannot implement a recursive function in HLS, it must be iterative.

Nonogram Server Protocol

We use a UDP-based protocol for interacting with the Nonogram server. The server is at IP 192.168.10.1 on port 51050. All multi-byte integer values in the protocol are encoded in big-endian format.

Tiers

The server supports four puzzle tiers that provide different difficulty guarantees:

• In order to get a guaranteed easy or hard puzzle, you must set seed = 0.
• When seed = 0 the server randomly selects from a curated seed list that satisfies the appropriate guarantee. These exist only for the “Available Sizes” listed above.
• If you set seed = 0 and select Medium, or Custom then the server will give you a random seed with no difficulty guarantee.
• If seed != 0 then tier is ignored entirely and you will get exactly the seed you requested.

Difficulty Field Encoding

The difficulty field in all messages is a single byte that encodes both tier and grid size:

  Bit:   7  6      5  4    3  2  1  0
      [reserved]  [tier]  [size index]

• Bits [7:6] - Reserved
• Bits [5:4] - Tier: 0b00 = Custom, 0b01 = Easy, 0b10 = Medium, 0b11 = Hard
• Bits [3:0] - Size index (0–15), maps to grid sizes per the table below

Message Structures

Communication with the server involves a sequence of request and response messages.

REQUEST_INFO

To begin, the client requests information about a puzzle by sending a REQUEST_INFO message. This specifies the desired puzzle seed and difficulty level.

The server responds with a PUZZLE_INFO message:

PUZZLE_INFO

REQUEST_CHUNK

The clue data is downloaded in parts called “chunks”. To request a chunk, the client sends a REQUEST_CHUNK message. Our puzzles currently all fit into a single chunk so we only need to send this once.

The server responds with a CHUNK_DATA message containing the requested data:

CHUNK_DATA

Clue Data Format

The chunk data forms a byte stream encoding all row clues followed by all column clues. Each clue (row or column) is encoded as a length-prefixed list:

The full clue stream is structured as:

Row 0 clue:    [count] [block_0] [block_1] ... [block_{count-1}]
Row 1 clue:    [count] [block_0] ...
  ...
Row H-1 clue:  [count] ...
Col 0 clue:    [count] [block_0] ...
Col 1 clue:    [count] ...
  ...
Col W-1 clue:  [count] ...

The total size of this stream is reported in the Clue Bytes field of the PUZZLE_INFO response.

Example: Consider this 5x5 puzzle (seed 13):

          Col clues
          3 3 1 3 3
        +-----------+
     -  | . . . . . |
   2 2  | # # . # # |
     5  | # # # # # |
   2 2  | # # . # # |
     -  | . . . . . |
        +-----------+

The complete clue data stream (20 bytes) encoding all rows then all columns:

00            ← Row 0: count=0 (empty row)
02 02 02      ← Row 1: count=2, blocks=[2, 2]
01 05         ← Row 2: count=1, blocks=[5]
02 02 02      ← Row 3: count=2, blocks=[2, 2]
00            ← Row 4: count=0 (empty row)
01 03         ← Col 0: count=1, blocks=[3]
01 03         ← Col 1: count=1, blocks=[3]
01 01         ← Col 2: count=1, blocks=[1]
01 03         ← Col 3: count=1, blocks=[3]
01 03         ← Col 4: count=1, blocks=[3]

Raw hex stream: 00 02 02 02 01 05 02 02 02 00 01 03 01 03 01 01 01 03 01 03

Submitting a Solution

Once the puzzle is solved, the client submits its solution using the SUBMIT_SOLUTION message. The solution is sent as a bitmap, where each bit represents a cell’s state (1 for filled, 0 for empty). The bitmap is packed row by row, with each row padded to a full byte.

SUBMIT_SOLUTION

The server validates the solution and replies with a RESULT message:

RESULT

ERROR

If the client sends a malformed or out-of-sequence message, the server may respond with an ERROR message (assuming my error handling caught it and you didn’t nuke the server…)

Size Index

The lower 4 bits of the difficulty byte (the size index) map to the grid size: