回溯法:n皇后有关问题
回溯法:n皇后问题
Bound function:
算法伪代码:
/** * n-皇后问题 */ package com.iteye.caoruntao.nqueen; /** * @author caoruntao * */ public class NQueen { private int x[]; private int n; public NQueen(int n){ this.n = n; this.x = new int[n]; } public boolean place(int k){ int i = 0; while(i < k){ if((x[i] == x[k]) || (Math.abs(x[i]-x[k]) == Math.abs(i-k))){ return false; } i++; } return true; } public void printResult(){ for(int i=0; i<x.length; i++){ System.out.println(x[i]+" "); } } public void ComputerNQueen(){ int k = 0; this.x[0] = 0; while(k >= 0){ x[k] = x[k]+1; while(x[k] <= n && !place(k)){ x[k] = x[k]+1; } if(x[k] <= n){ if(k == n-1){ printResult(); System.out.println("************"); x[k] = x[k]+1; //return; } else{ k = k+1; x[k] = 0; } } else{ k = k-1; } } } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub NQueen nQueen = new NQueen(4); nQueen.ComputerNQueen(); } }