package cn.nature.tech.exercise.eightqueen;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class DestCoordFinder {
//找到下一个可以使用的坐标,从左向右,从上向下寻找下一个坐标。
public DestCoordValue findNextCorrectPosition(List<DestCoordValue> currentResult,DestCoordValue startPosition){
DestCoordValue currentPosition=startPosition;
while(true){
if(currentPosition==null){
break;
}
if(this.isCorrectPosition(currentResult,currentPosition)){
return currentPosition;
}
currentPosition=this.getNextPosition(currentPosition);
}
return null;
}
/**
* 遍历获取下一个坐标
* @param currentPostion 当前的坐标
* @return 下一个坐标,如果已经到了最后则返回null
*/
public DestCoordValue getNextPosition(DestCoordValue currentPostion){
if(currentPostion.getM()<7){
return new DestCoordValue(currentPostion.getM()+1,currentPostion.getN());
}else if(currentPostion.getN()<7){
return new DestCoordValue(currentPostion.getM(), currentPostion.getN()+1);
}else{
return null;
}
}
/**
* 获取新的起始位置
* @param currentPosition 之前成功的位置
* @return 新的起始位置
*/
public DestCoordValue newStartPosition(DestCoordValue currentPosition){
DestCoordValue newStartPosition=new DestCoordValue();
//如果n=7,则结束,否则m=n+1
if(currentPosition.getN().equals(7)){
return null;
}else{
newStartPosition.setN(currentPosition.getN()+1);
}
//如果m=0,则新的m为1,否则m为0
if(currentPosition.getM().equals(0)){
newStartPosition.setM(1);
}else{
newStartPosition.setM(0);
}
return newStartPosition;
}
/**
* 判断是否可以作为下一个皇后位置
* @param currentResult 现在已经找到的结果
* @param currentValue 当前找到的结果
* @return 是可用的结果则是true,不是则为false
*/
public Boolean isCorrectPosition(List<DestCoordValue> currentResult,DestCoordValue currentValue){
Set<Integer> mSet=new HashSet<>();
Set<Integer> nSet=new HashSet<>();
for(DestCoordValue destCoordValue:currentResult){
mSet.add(destCoordValue.getM());
nSet.add(destCoordValue.getN());
}
//判断是否存在同一行的两个坐标
if(mSet.contains(currentValue.getM())){
return false;
}
//判断是否存在同一列的两个坐标
if(nSet.contains(currentValue.getN())){
return false;
}
//左上向右下的斜线是否存在两个坐标在同一个斜线上
for(DestCoordValue item:currentResult){
//并且与前面所有的元素坐标差值不同
if((currentValue.getM()-item.getM())==(currentValue.getN()-item.getN())){
return false;
}
}
//右上向左下的斜线是否存在两个坐标在同一个斜线上
for(DestCoordValue item:currentResult){
//与前面所有元素的坐标和不同
if((currentValue.getM()+currentValue.getN())==(item.getM()+item.getN())){
return false;
}
}
//所有判断都未命中,则为可用的位置
return true;
}
//重新寻找上一个坐标
public DestCoordValue refindLastDest(List<DestCoordValue> result){
//如果
if(result.size()==0){
return null;
}
//移除结果集最后一个坐标
DestCoordValue lastDest=result.get(result.size()-1);
result.remove(lastDest);
//将最后一个元素作为起点获取下一个元素
DestCoordValue nextStart=this.getNextPosition(lastDest);
//如果不存在下一个元素则再回溯
if(nextStart==null||nextStart.getN()>lastDest.getN()){
nextStart=this.refindLastDest(result);
}
return nextStart;
}
}