yukicoder No.1169 Row and Column and Diagonal

構築系の問題。
Writer解と違ったので、1つのアイディアとして書いてみます。

問題

解法

• のマスから斜め左下に向かってで埋めていく。
• 左端に達したら、次は右端のつ下のマス。
  下端に達したら、次は上端のつ左のマス。

具体例

（サンプル1）の場合、以下のようになる。

1 4 2 5 3
4 2 5 3 1
2 5 3 1 4
5 3 1 4 2
3 1 4 2 5

証明のようなもの

• 「1」で埋めるマスについて考えると、→→→・・・と埋めていくことになり、左端で折り返した後に埋めるマスがとなる。
• が奇数という前提の下では、とすると、となるため、を通らない。つまり、他の値で埋めるマスと重複しない。
  ※初期位置以外で左上から右下の対角線と交わるのは回だけ。
• 他の値についても、下端で折り返す場合についても、同様にを通ることでを通らないことが言えるはず。
• 各行と各列がの順列であることは、埋め方から自明であると思う。

なお、が偶数の場合は、必ずを通るため、この方法では絶対に構築できない。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.close();

        int[][] a = new int[n][n];
        for (int i = 1; i <= n; i++) {
            int x = i - 1;
            int y = i - 1 + n;
            for (int j = 0; j < n; j++) {
                a[x % n][y % n] = i;
                x++;
                y--;
            }
        }
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                sb.append(a[i][j]).append(' ');
            }
            sb.deleteCharAt(sb.length() - 1);
            System.out.println(sb.toString());
        }
    }
}