3

I'm participating in an online Sudoku-solving challenge where you create an account, and the server gives you a JWT token. Every request (getting the board, submitting answers, etc.) must include that token.

The workflow is:

  1. POST to /turns/start with JWT token → receive Sudoku grid

    POST /turns/start
    Authorization: Bearer <token>
    
  2. Solve the puzzle locally

  3. POST each cell solution to /turns/submit → server responds {"correct":true,"status":"next"} or {"correct":true,"status":"completed","time":470}

    POST /turns/submit
    Authorization: Bearer <token>
    Content-Type: application/json
    {"answer":{"row":x,"col":y,"value":z}}
    
  4. Repeat indefinitely

I'm doing all of this in C (expecting to be faster), using libcurl. Right now I'm using curl easy interface + pthreads, one thread per submission. it works However, I'm seeing strange behavior where cells don't seem to persist between rounds: Example: First Sudoku has 24 empty cells → I send 24 requests

but on the next iteration the server gives me the same board again but now with fewer empty cells (e.g., 18). This looks like the server didn't accept some of the submissions, even though every all the responses I read says: "correct": true, "status": "next" and I can comfirm that because the servers only gives point per sudoku solved and gives a 20-30 of empty cells to submit and my points aren't proportional with the number of iterations

Here is the code:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <unistd.h>
#include <pthread.h>
#include <curl/curl.h>
#include <json-c/json.h>

struct Response
{
    char data[4096];
    size_t size;
};

struct Cell{
    int row;
    int col;
    int value;
};

struct Thread_data{
    pthread_t thread;
    CURL* handle;
    struct Response received_data;
    struct Cell cell;
};

CURL *main_handle;
struct Response receive_board;
int sudoku[9][9];

///////////////////////////////////////////////////////////////////////

// Check if a number can be placed at a given position
bool is_valid(int sudoku[9][9], int row, int col, int num) {
    // Check the row
    for (int i = 0; i < 9; i++) {
        if (sudoku[row][i] == num) {
            return false;
        }
    }
    
    // Check the column
    for (int i = 0; i < 9; i++) {
        if (sudoku[i][col] == num) {
            return false;
        }
    }
    
    // Check the 3x3 box
    int start_row = (row / 3) * 3;
    int start_col = (col / 3) * 3;
    for (int i = start_row; i < start_row + 3; i++) {
        for (int j = start_col; j < start_col + 3; j++) {
            if (sudoku[i][j] == num) {
                return false;
            }
        }
    }
    
    return true;
}

// Recursive function to solve the sudoku (backtracking)
bool solve_recursive(int sudoku[9][9]) {
    // Find an empty cell (represented by 0)
    for (int row = 0; row < 9; row++) {
        for (int col = 0; col < 9; col++) {
            if (sudoku[row][col] == 0) {
                // Try digits from 1 to 9
                for (int num = 1; num <= 9; num++) {
                    if (is_valid(sudoku, row, col, num)) {
                        sudoku[row][col] = num;
                        
                        // Recursion to solve the rest
                        if (solve_recursive(sudoku)) {
                            return true;
                        }
                        
                        // Backtracking: if it doesn't work, reset
                        sudoku[row][col] = 0;
                    }
                }
                // If no digit works, return false
                return false;
            }
        }
    }
    // All cells are filled
    return true;
}

int solve_sudoku(int (*sudoku)[9]) {
    if (solve_recursive(sudoku)) {
        return 0;  // Success
    } else {
        return -1; // Failure
    }
}

///////////////////////////////////////////////////////////////////////


size_t write_data(void *buffer, size_t size, size_t nmemb, void *userp)
{
    size_t total = size * nmemb;
    struct Response *data = (struct Response *)userp;

    // we assume that the data in the response structure has enough memory
    memcpy(&(data->data[data->size]), buffer, total);
    data->size += total;
    data->data[data->size] = '\0';

    return total;
}

int get_board()
{
    CURLcode res;
    receive_board.size = 0;

    res = curl_easy_perform(main_handle);

    if(res != CURLE_OK)
    {
        fprintf(stderr, "curl failed: %d", res);
        return -1;
    }
     
    // Parsing JSON
    struct json_object *root = json_tokener_parse(receive_board.data);
    if (!root) {
        fprintf(stderr, "Error parsing JSON\n");
        return -1;
    }

    struct json_object *board;
    if (!json_object_object_get_ex(root, "board", &board)) {
        // that means we didn't receved the board!

        json_object_object_get_ex(root, "statusCode", &board);  // this MUST succeed

        fprintf(stderr, "Get board failed with StatusCode: %d\n", json_object_get_int(board));
        json_object_put(root);
        return -1;
    }

    for (int i = 0; i < 9; i++) {
        struct json_object *row = json_object_array_get_idx(board, i);

        for (int j = 0; j < 9; j++) {
            struct json_object *cell = json_object_array_get_idx(row, j);
            sudoku[i][j] = json_object_get_int(cell);
        }
    }

    json_object_put(root);  // freeing memory
    return 0;
}

void* submit_threaded(void* arg)
{
    struct Thread_data* thread = (struct Thread_data*)arg;

    thread->received_data.size = 0;
    char post_data[50];

    snprintf(post_data, 50, "{\"answer\":{\"row\":%d,\"col\":%d,\"value\":%d}}", thread->cell.row, thread->cell.col, thread->cell.value);
    curl_easy_setopt(thread->handle, CURLOPT_POSTFIELDS, post_data);
    curl_easy_perform(thread->handle);
}

int main()
{
    struct curl_slist *list = NULL;

    struct Thread_data threads[32];

    curl_global_init(CURL_GLOBAL_DEFAULT);

    main_handle = curl_easy_init();

    list = curl_slist_append(list, "Authorization: Bearer eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJwaG9uZU51bWJlciI6IjY0MjMyMDMwIiwiYm9vc3RUaW1lcyI6MCwiY3JlYXRlZEF0IjoiMjAyNS0wNy0wMlQxNDo1MjoxOC45MzJaIiwiaXNTdWJzY3JpYmUiOnRydWUsImlzU3Vic2NyaWJlSW5EYXkiOmZhbHNlLCJtb250aFNjb3JlIjowLCJuYW1lIjoiU29waGlhMjM0IiwicGxheVRpbWVzIjowLCJzdWJzY3JpYmVGcm9tIjoid2ViIiwidG9kYXlTY29yZSI6MCwidXBkYXRlZEF0IjoiMjAyNS0wNy0wMlQxNDo1MjoxOC45MzJaIiwid2luRGF5IjowLCJ3aW5Nb250aCI6IjAiLCJ3aW5XZWVrIjowLCJmYXN0ZXN0RHVyYXRpb24iOjIxNywiaWF0IjoxNzYzNDE3MjM3LCJleHAiOjE3NjYwMDkyMzd9.pxfbyCrr3lgU-rQN_NWv5zqUinsBX8BoCo8vIzj_euU");

    curl_easy_setopt(main_handle, CURLOPT_URL, "https://sudoku.lumitelburundi.com:8083/turns/start");
    curl_easy_setopt(main_handle, CURLOPT_POST, 1L);
    curl_easy_setopt(main_handle, CURLOPT_POSTFIELDS, "");
    curl_easy_setopt(main_handle, CURLOPT_HTTPHEADER, list);
    curl_easy_setopt(main_handle, CURLOPT_WRITEFUNCTION, write_data);
    curl_easy_setopt(main_handle, CURLOPT_WRITEDATA, &receive_board);

    list = curl_slist_append(list, "Content-Type: application/json");   // adding this header for submitting in json

    for(int i = 0; i < 32; i++)
    {
        threads[i].handle = curl_easy_init();
        curl_easy_setopt(threads[i].handle, CURLOPT_URL, "https://sudoku.lumitelburundi.com:8083/turns/submit");
        curl_easy_setopt(threads[i].handle, CURLOPT_POST, 1L);
        curl_easy_setopt(threads[i].handle, CURLOPT_HTTPHEADER, list);
        curl_easy_setopt(threads[i].handle, CURLOPT_WRITEFUNCTION, write_data);
        curl_easy_setopt(threads[i].handle, CURLOPT_WRITEDATA, &threads[i].received_data);
    }

    while(1)
    {
         if(get_board() != 0)
        {
            fprintf(stderr, "Error while fetching the board\n");
            return -1;
        }

        int solved_sudoku[9][9];

        memcpy(solved_sudoku, sudoku, sizeof(int) * 81);

        if(solve_sudoku(solved_sudoku) != 0)
        {
            fprintf(stderr, "Error while fetching the board\n");
            return -1;
        }

        int thread_count = 0;

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if(sudoku[i][j] == 0)
                {
                    threads[thread_count].cell.row = i;
                    threads[thread_count].cell.col = j;
                    threads[thread_count].cell.value = solved_sudoku[i][j];

                    pthread_create(&threads[thread_count].thread, NULL, submit_threaded, &threads[thread_count]);
                    thread_count++;
                }
            }
        }

        for(int i = 0; i < thread_count; i++)
        {
            pthread_join(threads[i].thread, NULL);  // wait for every thread to finish
            //printf("sent: %s\n", threads[i].received_data.data);
        }

        printf("\033[31mSolved cell submitted: %d\033[0m\n", thread_count);
    }

    curl_global_cleanup();

    return 0;
}

and here is an exemple of an output:

Solved cell submitted: 23
Solved cell submitted: 8
Solved cell submitted: 3
Solved cell submitted: 1
Solved cell submitted: 27
Solved cell submitted: 17
Solved cell submitted: 9
Solved cell submitted: 3
Solved cell submitted: 28
Solved cell submitted: 16
Solved cell submitted: 12
Solved cell submitted: 7
Solved cell submitted: 4
Solved cell submitted: 1
Solved cell submitted: 29
Solved cell submitted: 14
Solved cell submitted: 7
Solved cell submitted: 2
Solved cell submitted: 1
Solved cell submitted: 22
Solved cell submitted: 19
Solved cell submitted: 12
Solved cell submitted: 5
Solved cell submitted: 2
Solved cell submitted: 1
Solved cell submitted: 24
Solved cell submitted: 18
Solved cell submitted: 11
Solved cell submitted: 4
Solved cell submitted: 1

My hypothesis is that the server might be rate-limiting or throttling requests per token, so some submissions are simply ignored (even though the server says "correct" "next" which would be strange).

Would creating multiple user accounts (thus multiple JWT tokens) and distributing my threads across them solve this? Or is there a better approach to handle high-frequency concurrent submissions with JWT authentication?

If not, what would be the right way to maximize request throughput in C(or any other language) for this kind of challenge?

Here is the server header if it helps:

HTTP/1.1 500 Internal Server Error
X-Powered-By: Express
Access-Control-Allow-Origin: *
Content-Type: application/json; charset=utf-8
Connection: keep-alive
Keep-Alive: timeout=5

On the website the server sets a cookie named FADC_Persistence_Cookie. Its value looks something like rs1|aSBDB, but it changes on every reload and isn’t included in any of the requests made by the client.

4
  • I doubt your problem is the JWT token. I would be inclined to think that the server expects clients to operate serially -- no overlapping requests -- and that you create problems for yourself by making your client behave in a way that is observably non-serial. That need not even be an intentional aspect of the server design. Commented Nov 21 at 13:46
  • 1
    I/O is slow, especially especially over a network, so I understand why you are trying to speed that up. From the look of it, though, I bet your solver itself is even slower. Maybe that's not so clear (or even not so true) with so few empty cells in the initial grid, but if you can expect the puzzles to get harder then you will really benefit from writing a smarter solver. Commented Nov 21 at 15:39
  • @JohnBollinger I don’t think that’s the case. There were already moments where I had extremely good performance (for example, solving a Sudoku in about 200 ms), whereas sending requests sequentially gives me an average of around 2 seconds. So I don’t believe the issue comes from parallel requests. I genuinely think there is something going on with the session handling instead. Commented Nov 22 at 12:39
  • Like I said, you're more likely to see performance issues if the puzzles get harder. But even your 200ms is pretty slow for a Sudoku with only 30 open cells. Commented Nov 22 at 13:52

1 Answer 1

3

A JWT is used in order to authenticate yourself at a Service Provider (SP) using an IDentity Provider (IDP). The mechanism usually is to visit the SP and if you don't have a valid session, then request a JWT from your valid IDP session or to redirect to your IDP in order to authenticate (and ideally after authentication it would auto-authenticate in the issuer SP and redirect there).

When you have a valid session at your SP, you need to somehow tell the IDP that you are authenticated, this is why you are sending the Bearer Token at step 3. However, while doing so, you may encounter an issue related to parallelization which seems to be the case from what you describe. If you send

  • request1
  • request2

in that order and for whatever reason (network is a likely culprit) request2 is processed before request1, then the first response that you receive will be for request2, and only after that you will get the response for request1, at which point whatever you sent later may have had a different state and your state is updated accordingly to the response of request1 after to the one of request2. A solution for this problem, when the order of the requests needs to be the order of the processing it makes sense to have a request queue where you would push request1 first and request2 next and to make sure that you wait for request1 to be responded to (or to time out) before you send request2.

We don't know anything of the server you are communicating with, so if there is some throttling, rate limitation there to protect against bots such as (likely) yours, then your project should not be completed. However, if your use of the server is valid and the only issue is the order of the responses, then this request queue will be the solution.

Sign up to request clarification or add additional context in comments.

5 Comments

"it makes sense to have a request queue" -- well yes, that's one way to do it. But if requests need to be serialized, which seems plausible, then a simpler and more natural approach would be to just dedicate a single thread to all of the comms. Indeed, in that case, it's unclear whether there is any advantage to multithreading in this program at all.
Yes indeed it makes sense to have a single thread for the communication, however, the processing/calculation can be parallelized.
So if I understand correctly, even if I log in multiple times and get multiple tokens, all the tokens I receive will still share the same underlying session on the server, right? I was thinking that if I could somehow create multiple independent sessions and distribute my requests across them, the whole process would be faster. Am I wrong about that? Also, when you mention putting the requests in a queue, do you mean sending them sequentially? If that’s the case, I’ve already tried that approach and it actually seems slower than sending everything in parallel.
If you log in multiple times then each time you log in a new session is being created. However, your separate sessions will be racing with each-other. It is way better to have a single session and make sure that your threads share the resources. Indeed, queuing requests will slow down the communication as you noticed, but if the order of the requests is important, which seems to be the case, then you need to do it. If you figure out a way in which you don't need to sequentially send all the requests, then you can improve speed.
However, first make sure that your app reliably works with sequential query sending and when you achieve that you will have a milestone reached and a next problem to figure out would be to handle the requests. If request1 does not have something resolved from request2 and you process the request1's response first, then it will cause inconsistencies. So first make sure your queued requests are working as intended and only then try to figure out the next steps.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.