#include #define rep(i, n) for(int i = 0; i < (int)(n); ++i) using namespace std; using ll = long long; template inline bool chmin(T& a, T b) { if(a > b) { a = b; return true; } return false; } template inline bool chmax(T& a, T b) { if(a < b) { a = b; return true; } return false; } using Field = vector>; void solver(int n, vector> &field, vector &res) { int empty_i = -1; int empty_j = -1; for(int i = 0; i < n && empty_i == -1; ++i) { for(int j = 0; j < n && empty_j == -1; ++j) { if(field[i][j] == -1) { empty_i = i; empty_j = j; break; } } } if(empty_i == -1 || empty_j == -1) { res.push_back(field); return; } // どの数値を入れるか vector can_use(n+1, true); for(int i = 0; i < n; ++i) { if(field[empty_i][i] != -1) can_use[field[empty_i][i]] = false; if(field[i][empty_j] != -1) can_use[field[i][empty_j]] = false; } for(int num = 1; num <= n; ++num) { if(!can_use[num]) continue; field[empty_i][empty_j] = num; solver(n, field, res); } field[empty_i][empty_j] = -1; } int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); int n; cin >> n; Field field(n, vector(n, -1)); rep(i, n) { rep(j, n) { if(i == j) { field[i][j] = i+1; } } } vector res; solver(n, field, res); Field ans = res[0]; rep(i, n) { rep(j, n) { printf("%d ",ans[i][j]); } printf("\n"); } }