新・明解Javaで学ぶアルゴリズムとデータ構造

戻る  

演習5-9の解答

// 演習5-9
// ８王妃問題を非再帰的に解く（盤面を□と■で表示）

class EightQueenN {

   static boolean[] flag_a = new boolean[8];    // 各行に王妃が配置済みか
   static boolean[] flag_b = new boolean[15]; // ／対角線に王妃が配置済みか
   static boolean[] flag_c = new boolean[15]; // ＼対角線に王妃が配置済みか
   static int[] pos = new int[8];   // 各列の王妃の位置

   //--- 盤面（各列の王妃の位置）を出力 ---//
   static void print() {
      for (int i = 0; i < 8; i++) {
         for (int j = 0; j < 8; j++)
            System.out.printf("%s", j == pos[i] ? "■" : "□");
         System.out.println();
      }
      System.out.println();
   }

   //--- i列目の適切な位置に王妃を配置 ---//
   static void set(int i) {
      int j;
      int[] jstk = new int[8];

      Start : while (true) {
         j = 0;
         while (true) {
            while (j < 8) {
               if (!flag_a[j] && !flag_b[i + j] && !flag_c[i - j + 7]) {
                  pos[i] = j;
                  if (i == 7)               // 全列に配置終了
                     print();
                  else {
                     flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = true;
                     jstk[i++] = j;         // i列目の行をPush
                     continue Start;
                  }
               }
               j++;
            }
            if (--i == -1) return;
            j = jstk[i];                  // i列目の行をPop
            flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = false;
            j++;
         }
      }
   }

   public static void main(String[] args) {
      set(0);
   }
}

戻る