movelist solve(board B)
//@requires is_board(B);
{
    queue allQueue = queue_new();
    int size = 1;
    for (int i = 0; i < B->width*B->height; i++) {
        size *= 2;
    }
    hmap movesSeen = hmap_new(size);
    bool start = hmap_insert(B, NULL, movesSeen);
    enqueue(B, allQueue);
    board end = alloc(struct board);
    end->width = B->width;
    end->height = B->height;
    end->lights = 0;

    if (hmap_ktype_equal(B, end)) return NULL;
    while (!(queue_empty(allQueue))) {
        board check = dequeue(allQueue);
        if (hmap_ktype_equal(check, end)) {
            board solBoard = copy_board(check);
            move nextMove = hmap_get(solBoard, movesSeen);
            movelist sol = movelist_new(nextMove->x, nextMove->y, NULL);
            untoggle_board(solBoard, nextMove->x, nextMove->y);
            while (!hmap_ktype_equal(solBoard, B)) {
                nextMove = hmap_get(solBoard, movesSeen);
                sol = movelist_new(nextMove->x, nextMove->y, sol);
                untoggle_board(solBoard, nextMove->x, nextMove->y);
            }

            return sol;
        }
        for (int x = 0; x < (B->width); x++) {
            for (int y = 0; y < (B->height); y++) {
                board newBoard = copy_board(check);
                toggle_board(newBoard, x, y);
                move newMove = move_new(x, y);
                if (!(hmap_contains_key(newBoard, movesSeen))) {
                    hmap_insert(newBoard, newMove, movesSeen);
                    enqueue(newBoard, allQueue);
                }
            }
        }
    }
    return NULL;
}