天天看點

八皇後問題 java代碼

具體的結果在tmp.txt檔案裡面

package test;

import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class EightQueenDemo
{
    private static final int MAX_NUM = ;
    private static int[][] arr = new int[MAX_NUM][MAX_NUM];
    private static int[] res = new int[MAX_NUM];
    private static int index = ;

    private static PrintWriter pw = null;

    private static Set<String> resSet = new HashSet<String>();

    /**
     * 在8*8格的國際象棋上擺放八個皇後,使其不能互相攻擊,即任意兩個皇後都不能處于同一行、同一列或同一斜線上,問有多少種擺法
     * 
     * @param args
     * @throws IOException
     */
    public static void main(String[] args) throws IOException
    {
        // TODO Auto-generated method stub
        initArr();
        initStream();
        show();
        procedure();
        closeStream();
        System.out.println("result = "+index);
        System.out.println("check distinct "+(resSet.size()));
    }

    private static void initArr()
    {
        for (int i = ; i < MAX_NUM; i++)
        {
            for (int j = ; j < MAX_NUM; j++)
            {
                arr[i][j] =  * i +  + j + ;
            }
        }
    }

    private static void initStream() throws IOException
    {
        File file = new File("tmp.txt");
        if (!file.exists())
        {
            file.createNewFile();
        }else
        {
            file.delete();
            file.createNewFile();
        }
        pw = new PrintWriter(new OutputStreamWriter(new FileOutputStream(file)));
    }

    private static void closeStream()
    {
        if (pw != null)
        {
            pw.flush();
            pw.close();
        }
    }

    private static void show()
    {
        for (int i = ; i < MAX_NUM; i++)
        {
            for (int j = ; j < MAX_NUM; j++)
            {
                System.out.print(arr[i][j] + "    ");
            }
            System.out.println();
        }
    }

    private static void show(int[] res)
    {
        System.out.println(Arrays.toString(res));
    }

    private static boolean isSameCol(int res, int obj)
    {
        return (res %  == obj % ) && obj > ;
    }

    private static boolean isSameLine(int res, int obj)
    {
        return (res /  == obj / ) && obj > ;
    }

    // private static boolean isBias(int res, int obj) {
    // return ((res % 10 == res / 10) && (obj % 10 == obj / 10) || (res % 10 +
    // res / 10 == MAX_NUM + 1)
    // && (obj % 10 + obj / 10 == MAX_NUM + 1))
    // && obj > 0;
    // }
    private static boolean isBias2(int res, int obj)
    {
        return ((res %  - res /  == obj %  - obj / ) || (res %  + res /  == obj %  + obj / ))
                && obj > ;
    }

    private static boolean isConflict(int res, int obj)
    {
        // boolean flag = isSameLine(res, obj) || isSameCol(res, obj) ||
        // isBias2(res, obj);
        boolean flag = isSameLine(res, obj) || isBias2(res, obj) || isSameCol(res, obj);
        // System.out.println("flag="+flag+"&&res="+res+"||obj="+obj);
        return flag;
    }

    private static void isAccordCond(int arrInt, int line)
    {
        boolean isConflickFlag = false;
        for (int j = ; j < line; j++)
        {
            if (isConflict(arrInt, res[j]))
            {
                isConflickFlag = true;
                break;
            }
        }
        if (!isConflickFlag)
        {
            res[line] = arrInt;
            if (line == MAX_NUM - )
            {
                // show(res);
                String str = Arrays.toString(res);
                // System.out.println(str);
                resSet.add(str);
                draw(res);
                index++;
            } else
            {
                line++;
                procedure(line);
            }

        }

    }

    private static void procedure(int line)
    {
        for (int i = ; i < MAX_NUM; i++)
        {
            res[line] = ;
            isAccordCond(arr[line][i], line);
        }
    }

    private static void draw(int[] res)
    {
        StringBuffer sb = new StringBuffer();
        for (int i = ; i < MAX_NUM; i++)
        {
            for (int j = ; j < MAX_NUM; j++)
            {
                if (checkNum(res, arr[i][j]))
                {
                    sb.append(" @");
                } else
                {
                    sb.append(" $");
                }
            }
            pw.println(sb.toString());
            sb.delete(, sb.length());
        }
        pw.println();
        pw.println("--------------------------------------------------------");
    }

    private static boolean checkNum(int[] res, int obj)
    {
        boolean flag = false;
        for (int i = ; i < MAX_NUM; i++)
        {
            if (obj == res[i])
            {
                flag = true;
                break;
            }
        }
        return flag;
    }

}