注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

TOTO

Think and Be Different

 
 
 

日志

 
 

NQueen Problemd的java代码  

2007-05-31 13:58:31|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

昨天晚上写了一下N皇后问题的代码,由于开始设计和后来自己的想法之间出现了点冲突,造成debug了挺长时间的,不过最后还是完成了。

import java.util.*;
import java.lang.Math;

public class NQueen{
 
 
 public static void main(String[] args) {
  State s = new State(4);
  ArrayList<State> stack = new ArrayList<State>();
  int index = 0;
  //stack[index++] = s;
  stack.add(index++, s);
  State tem;
  State pp;
  while(!stack.isEmpty()) {
   tem = stack.remove(--index);
   if(tem.isResult()) {              
                     // Whether the POP object is the Object State
    State.show(tem);
   }
   pp = State.generateNextState(tem);
                        //Generate the next state by Pop one
   tem.grid[tem.level]++;        
                       
         //if next level is impossible, test present level
                     //whether it can generate state which is satisfy
                     //the constraints
   if(pp == null) {    
                    
    while(!tem.isSatisfyConstraint() && !tem.isOutOfBound())
     tem.grid[tem.level]++;
   }
   if(tem.isSatisfyConstraint() && !tem.isOutOfBound())
    stack.add(index++, tem);
   if(pp != null)
    stack.add(index++, pp);
  }
 }

}
class State {
 public int[] grid;
 public int level;
 public static int bound;
 public State(int n) {
  grid = new int[n];
  for(int i = 0; i < n; i++)
   grid[i] = 0;
  //level = -1;
  level = 0;
  bound = n - 1;
 }

 public static State generateNextState(State s) {
  State t = new State(State.bound + 1);
  for(int i = 0; i <= State.bound; i++)
   t.grid[i] = s.grid[i];
  t.level = s.level;
  if(s.level < State.bound)
  {
   t.level = s.level + 1;
   while(!t.isSatisfyConstraint() && !t.isOutOfBound()) {
    t.grid[t.level]++;
   }
   if(t.isSatisfyConstraint() && !t.isOutOfBound())
    return t;
   else
    return null;
  }
  else
   return null;
 }
 public boolean isResult(){
  return (this.level == State.bound);
 }
 public boolean isOutOfBound() {
  if (this.grid[this.level] <= State.bound)
   return false;
  else
   return true;
 }
 
 public boolean isSatisfyConstraint() {
  int testOb = this.grid[this.level];
  if(this.level == 0)     //there is no confilct when only one exist
   return true;
  for(int i = 0; i < this.level; i++) {
   if(this.grid[i] == testOb)
    return false;
   if(Math.abs(this.grid[i] - testOb) == Math.abs(i - this.level))
    return false;
  }
  return true;
 }
 public static void show(State s) {
  for(int i = 0; i <= State.bound; i++)
   System.out.print(s.grid[i]+ " ");
  System.out.println();
 }
}

About N-Queen Problem or similar problem, there is some common method(function/procedure)

(1)Generate the next state based on the current state;

(2)Whether the state is the your destination

(3)Whether the state's parameter is out of bounds

if we have the three, we can write the program easily!

  评论这张
 
阅读(233)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017