GCJ2020-Q5: Indicium

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> board;
int q, n;
bool lock;

void PrintBoard(){
    cout << "POSSIBLE\n";
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            cout << board[i][j] << " ";
        }
        cout << "\n";
    }
    return;
}

bool Valid(int r, int c, int x){
    for(int i = 0; i < n; ++i){
        if(board[r][i] == x || board[i][c] == x){
            return false;
        }
    }
    return true;
}

void Sudoku(int r, int c){
    //cout << r << " " << c << "\n";
    if(r == n && c == 0){
        PrintBoard();
        lock = true;
        return;
    } else if(board[r][c] != 0){
        if(c == n - 1){
            Sudoku(r + 1, 0);
        } else {
            Sudoku(r, c + 1);
        }
        return;
    } else {
        for(int j = 1; j <= n; ++j){
            if(Valid(r, c, j) && !lock){
                board[r][c] = j;
                if(c == n - 1){
                    Sudoku(r + 1, 0);
                } else {
                    Sudoku(r, c + 1);
                }
                board[r][c] = 0;
            }
        }
        return;
    }
}

void GenTrace(int i, int t){ /// i = 0 to n - 1
    if(i == n){
        if(t == 0 && !lock){
            Sudoku(0, 0);
        }
    } else {
        for(int j = 1; j <= n; ++j){
            if(j <= t && !lock){
                board[i][i] = j;
                GenTrace(i + 1, t - j);
                board[i][i] = 0;
            }
        }
    }
}

int main(){

    int t;

    scanf("%d", &q);
    for(int k = 1; k <= q; ++k){
        scanf("%d %d", &n, &t);
        board.assign(n, vector<int>(n, 0));
        lock = false;
        cout << "Case #" << k << ": ";
        GenTrace(0, t);
        if(!lock){
            cout << "IMPOSSIBLE\n";
        }
    }

    return 0;
}