역추적 알고리즘의 8황후 문제의 해답--java 실현

최근에 데이터 구조와 알고리즘이라는 것을 배우고 다른 사람의 코드를 참고하여 자신이 역추적 알고리즘을 쓴 팔황후 실현을 기록하여 자신이 복습할 수 있도록 했다.
더 이상 말하지 말고 코드로 바로 올라가세요.
public class Backtrack8Queens {

    private static int[][] result = new int[8][8];
    public static void main(String[] args) {
        System.out.println("hello,world!");
        calc8queens(0);
    }

    public static void calc8queens(int row) {
        if(row == 8) {
            print8queens(result);
            return;
        }

        for(int col = 0; col < 8; ++col) {
            if(check(row, col)) {
                result[row][col] = 1;
                calc8queens(row + 1);
                result[row][col] = 0;
            }
        }
    }

    public static boolean check(int row, int col) {
        int leftup = col - 1;
        int rightup = col + 1;
        for(int i = row - 1; i >= 0; --i) {
            if(result[i][col] == 1) return false;
            if(leftup >= 0 && result[i][leftup] == 1) return false;
            if(rightup < 8 && result[i][rightup] == 1) return false;
            --leftup;
            ++rightup;
        }
        return true;
    }

    public static void print8queens(int[][] result) {
        for(int i = 0; i < result.length; ++i) {
            for(int j = 0; j < result[0].length; ++j) {
                System.out.print(String.format("%s\t", result[i][j]));
            }
            System.out.println();
        }
        System.out.println();
    }
}

실행 결과는 다음과 같습니다.
hello,world!
1	0	0	0	0	0	0	0	
0	0	0	0	1	0	0	0	
0	0	0	0	0	0	0	1	
0	0	0	0	0	1	0	0	
0	0	1	0	0	0	0	0	
0	0	0	0	0	0	1	0	
0	1	0	0	0	0	0	0	
0	0	0	1	0	0	0	0	

1	0	0	0	0	0	0	0	
0	0	0	0	0	1	0	0	
0	0	0	0	0	0	0	1	
0	0	1	0	0	0	0	0	
0	0	0	0	0	0	1	0	
0	0	0	1	0	0	0	0	
0	1	0	0	0	0	0	0	
0	0	0	0	1	0	0	0	

1	0	0	0	0	0	0	0	
0	0	0	0	0	0	1	0	
0	0	0	1	0	0	0	0	
0	0	0	0	0	1	0	0	
0	0	0	0	0	0	0	1	
0	1	0	0	0	0	0	0	
0	0	0	0	1	0	0	0	
0	0	1	0	0	0	0	0	

1	0	0	0	0	0	0	0	
0	0	0	0	0	0	1	0	
0	0	0	0	1	0	0	0	
0	0	0	0	0	0	0	1	
0	1	0	0	0	0	0	0	
0	0	0	1	0	0	0	0	
0	0	0	0	0	1	0	0	
0	0	1	0	0	0	0	0	

0	1	0	0	0	0	0	0	
0	0	0	1	0	0	0	0	
0	0	0	0	0	1	0	0	
0	0	0	0	0	0	0	1	
0	0	1	0	0	0	0	0	
1	0	0	0	0	0	0	0	
0	0	0	0	0	0	1	0	
0	0	0	0	1	0	0	0	

0	1	0	0	0	0	0	0	
0	0	0	0	1	0	0	0	
0	0	0	0	0	0	1	0	
1	0	0	0	0	0	0	0	
0	0	1	0	0	0	0	0	
0	0	0	0	0	0	0	1	
0	0	0	0	0	1	0	0	
0	0	0	1	0	0	0	0	

0	1	0	0	0	0	0	0	
0	0	0	0	1	0	0	0	
0	0	0	0	0	0	1	0	
0	0	0	1	0	0	0	0	
1	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	1	
0	0	0	0	0	1	0	0	
0	0	1	0	0	0	0	0

...

좋은 웹페이지 즐겨찾기