아.. 나는 checker판 문제에 너무 약하다. 풀기전에 겁부터 난다. 이번 문제는 정답을 거의 renewal하는 방법으로 해결했다. 막상 보고나면 코드도 짧은 편이고 풀만한데.. ㅎ

이번 문제도 입력의 크기를 줄이지 않으면 Time Over에 걸린다. checker판이 가운대를 기준으로 접으면 대칭이기 때문에 첫번째 row가 column의 중간까지만 보고 나머지 row들은 모든 column을 다 봐야 한다. 체커판 울렁증을 어서 어서 극복해야 할텐데.. ㅎ

Examine the 6x6 checkerboard below and note that the six checkers are arranged on the board so that one and only one is placed in each row and each column, and there is never more than one in any diagonal. (Diagonals run from southeast to northwest and southwest to northeast and include all diagonals, not just the major two.)

          Column
    1   2   3   4   5   6
  -------------------------
1 |   | O |   |   |   |   |
  -------------------------
2 |   |   |   | O |   |   |
  -------------------------
3 |   |   |   |   |   | O |
  -------------------------
4 | O |   |   |   |   |   |
  -------------------------
5 |   |   | O |   |   |   |
  -------------------------
6 |   |   |   |   | O |   |
  -------------------------

The solution shown above is described by the sequence 2 4 6 1 3 5, which gives the column positions of the checkers for each row from 1 to 6:

This is one solution to the checker challenge. Write a program that finds all unique solution sequences to the Checker Challenge (with ever growing values of N). Print the solutions using the column notation described above. Print the the first three solutions in numerical order, as if the queen positions form the digits of a large number, and then a line with the total number of solutions.

Special note: the larger values of N require your program to be especially efficient. Do not precalculate the value and print it (or even find a formula for it); that's cheating. Work on your program until it can solve the problem properly. If you insist on cheating, your login to the USACO training pages will be removed and you will be disqualified from all USACO competitions. YOU HAVE BEEN WARNED.

TIME LIMIT: 1 CPU second

PROGRAM NAME: checker

INPUT FORMAT

A single line that contains a single integer N (6 <= N <= 13) that is the dimension of the N x N checkerboard.

SAMPLE INPUT (file checker.in)

6

OUTPUT FORMAT

The first three lines show the first three solutions found, presented as N numbers with a single space between them. The fourth line shows the total number of solutions found.

SAMPLE OUTPUT (file checker.out)

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

HINTS (use them carefully!)

       HINT 1          HINT 2          HINT 3          HINT 4          HINT 5          HINT 6  

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;

/*
ID: myway761
LANG: JAVA
TASK: checker
*/
public class checker {
  Scanner in;
  PrintWriter out;
 
  public static final int MAXN = 13;
  int n;
  int solveCount;
  int printedCount;
 
  // 출력할 Row들을 저장.
  int[][] printRows;
 
  // row의 값을 저장.
  int[] row;
 
  // column에 사용 가능한지 여부를 저장. (불가능 할 때 마다 ++)
  int[] col;
 
  // 오른쪽 위 방향의 대각선에 저장 가능한지 여부를 저장한다. (i,j의 대각선은 모두  i+j)이다.
  int[] rightUpDiag;
 
  // 왼쪽 아래 방향의 대각선에 저장 가능한지 여부를 저장한다. (i, j의의 왼쪽 아래 대각선은 모두 i+j+n)이다.
  int[] leftDownDiag;
 
  public checker() throws IOException {
    in = new Scanner(new File("checker.in"));
    out = new PrintWriter(new BufferedWriter(new FileWriter("checker.out")));
   
    init();
    start();
  }
 
  public void init() {
    n = in.nextInt();
   
    row = new int[n];
    col = new int[n];
    rightUpDiag = new int[n*2];
    leftDownDiag = new int[n*2];
    printRows = new int[3][n];
  }
 
  public void start() {
    // 절반까지만 구하면 좌우가 대칭이므로 row[0]이 절반까지만 갈 때 까지만 구한다.
    find(0, (n+1)/2);
   
    // printedCount가 3보다 작으면 대칭된 것을 복사해 넣는다.
    if(printedCount<3) {
      int i;
      for(i=0 ; i<n ; i++)
        printRows[printRows.length][i] = printRows[printRows.length-1][n-i-1];
    }
   
    // 출력한다.
    print();
   
    out.close();
    System.exit(0);
  }
 
  /**
   * i번 column부터 limit column까지 Checker Position을 찾는다.
   * @param i 시작할 column
   * @param lim 끝 column
   */
  private void find(int i, int lim) { 
    if(i == n) {
     
      // 찾은 개수를 하나 증가시킨다.
      solveCount++;
     
      // column이 중간 전이라면 대칭이므로 solveCount를 하나 더 추가한다.
      if(row[0] < n/2)
        solveCount++;
     
      // printedCount가 3 미만이라면 출력할 row의 목록에 Array를 복사한다.
      if(printedCount < 3) {
        System.arraycopy(row, 0, printRows[printedCount], 0, n);
        printedCount++;
      }
      return;
    }
   
    int j;
    for(j=0 ; j<lim ; j++) {
     
      // 이 위치에 놓을 수 있다면
      if(col[j]==0 && rightUpDiag[i+j]==0 && leftDownDiag[i-j+n]==0) {
        row[i] = j;
       
        col[j]++;
        rightUpDiag[i+j]++;
        leftDownDiag[i-j+n]++;
       
        // 다음 row를 본다.
        find(i+1,n);
       
        col[j]--;
        rightUpDiag[i+j]--;
        leftDownDiag[i-j+n]--;
      }
    }
  }
 
  private void print() {
    int i, j;
    for(i=0 ; i<printRows.length ; i++) {
      for(j=0 ; j<n ; j++) {
        if(j != 0)
          out.print(" ");
        out.print(printRows[i][j]+1);
      }
      out.println();
    }
    out.println(solveCount);
  }
 
  public static void main(String[] args) throws IOException {
    new checker();
  }
}

이올린에 북마크하기