首页 > 其他 > 详细

八皇后问题

时间:2017-12-15 13:26:44      阅读:231      评论:0      收藏:0      [点我收藏+]
import java.util.*;
import java.io.*;
import java.math.*;
public class Hello
{
    static int cnt =1;
     public static void main(String[] args) throws IOException
    {
        int n = 8;
        char[][] board = new char[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                    board[i][j] = ‘.‘;
            }

        }
        List<List<String>> res = new ArrayList<List<String>>();
        dfs(board,0,res);

        for (List<String > l:res) {
            for(String s:l)
                System.out.println(s);
            System.out.println(cnt);
            cnt++;
        }

        //System.out.println(res);
    }
    private static void dfs(char[][] board, int colIndex, List<List<String>> res){
        if(colIndex == board.length){
            res.add(construct(board)); return;
        }
        for(int i=0;i<board.length;i++){
            if(validate(board,i,colIndex)){
                board[i][colIndex] = ‘Q‘;
                dfs(board,colIndex+1,res);
                board[i][colIndex] = ‘.‘;
            }
        }

    }

    private  static  boolean validate(char[][] board,int x,int y){
        for(int i=0;i<board.length;i++){
            for(int j=0;j<y;j++){
                if(board[i][j] == ‘Q‘ && ( x+y ==i+j || x-y == i-j || x==i )){
                    return false;
                }
            }
        }
        return true;
    }

    public static List<String> construct(char[][] board){
        List<String> res = new LinkedList<String>();
        for(int i=0;i<board.length;i++){
            String s = new String(board[i]);
            res.add(s);
        }
        return res;
    }




}

 

八皇后问题

原文:http://www.cnblogs.com/vector11248/p/8042487.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!