`

回溯法应用之n皇后问题

 
阅读更多
在n行n列的棋盘上,如果两个皇后位于棋盘上的同一行或者同一列或者同一对角线上,则称他们为互相攻击。现要求找出使n元棋盘上的n个皇后互不攻击的所有布局,即是n皇后问题

package 数据结构及算法.回溯法应用之n皇后问题;

import java.util.Iterator;

import 数据结构及算法.回溯法.Application;
import 数据结构及算法.回溯法.Position;

public class Queen implements Application{
    private int[][]grid;
    private int[][]path;
    public Queen(int n){
    	this.grid=new int[n][n];
    	this.path=new int[n][2];
    	for(int i=0;i<n;i++){
    		for(int j=0;j<n;j++){
    			this.grid[i][j]=0;
    		}
    	}
    }
	@Override
	public boolean valid(Position pos) {
		if(this.grid[pos.getRow()][pos.getColumn()]==0)
		return true;
		return false;
	}

	@Override
	public void record(Position pos) {
		for(int i=0;i<this.grid.length;i++){
			if(i!=pos.getColumn())
			    this.grid[pos.getRow()][i]+=1;//横
			if(i!=pos.getRow())
				this.grid[i][pos.getColumn()]+=1;//竖		
		}
		int x=pos.getRow()-1;
		int y=pos.getColumn()-1;
		while(x>=0&&y>=0){//左上
			this.grid[x][y]+=1;
			x--;
			y--;
		}
		x=pos.getRow()+1;
		y=pos.getColumn()-1;
		while(x<this.grid.length&&y>=0){//左下
			this.grid[x][y]+=1;
			x++;
			y--;
		}
		x=pos.getRow()-1;
		y=pos.getColumn()+1;
		while(y<this.grid.length&&x>=0){//右上
			this.grid[x][y]+=1;
			x--;
			y++;
		}
		x=pos.getRow()+1;
		y=pos.getColumn()+1;
		while(x<this.grid.length&&y<this.grid.length){//右下
			this.grid[x][y]+=1;
			x++;
			y++;
		}
		this.grid[pos.getRow()][pos.getColumn()]+=2*this.grid.length;
	}

	@Override
	public boolean done(Position pos) {
		if(pos.getRow()==this.grid.length-1)
			return true;
		return false;
	}

	@Override
	public void undo(Position pos) {
		for(int i=0;i<this.grid.length;i++){
			if(i!=pos.getColumn())
			    this.grid[pos.getRow()][i]-=1;//横
			if(i!=pos.getRow())
				this.grid[i][pos.getColumn()]-=1;//竖		
		}
		int x=pos.getRow()-1;
		int y=pos.getColumn()-1;
		while(x>=0&&y>=0){//左上
			this.grid[x][y]-=1;
			x--;
			y--;
		}
		x=pos.getRow()+1;
		y=pos.getColumn()-1;
		while(x<this.grid.length&&y>=0){//左下
			this.grid[x][y]-=1;
			x++;
			y--;
		}
		x=pos.getRow()-1;
		y=pos.getColumn()+1;
		while(y<this.grid.length&&x>=0){//右上
			this.grid[x][y]-=1;
			x--;
			y++;
		}
		x=pos.getRow()+1;
		y=pos.getColumn()+1;
		while(x<this.grid.length&&y<this.grid.length){//右下
			this.grid[x][y]-=1;
			x++;
			y++;
		}
		this.grid[pos.getRow()][pos.getColumn()]-=2*this.grid.length;
	}
	
	public String toString(){
		String result="";
    	for(int i=0;i<this.grid.length;i++){
    		for(int j=0;j<this.grid[0].length;j++){
    			if(this.grid[i][j]==2*this.grid.length)
    				result+="*"+" ";
    			else
    				result+=this.grid[i][j]+" ";
    			
    		}
    		result+="\n";
    	}
    	return result;
    }

	@Override
	public Iterator iterator(Position pos) {
		
		return new QueenIterator(pos,this.grid.length);
	}
    private class QueenIterator implements Iterator{
    	private int size;
    	private int count=0;
    	private int row;
    	//private int col;
        public QueenIterator(Position pos,int queenGridLength){
        	 this.row=pos.getRow();
        	 //this.col=pos.getColumn();
        	 this.size=queenGridLength;
        }
		@Override
		public boolean hasNext() {
			return count<this.size;
		}

		@Override
		public Object next() {
			Position nextPos=new Position(this.row+1,count); 
			count++;
			return nextPos;
		}

		@Override
		public void remove() {
			throw new UnsupportedOperationException();
		}
    	
    }
}

初始情况是整个棋盘每个位置初始值为0,public boolean valid(Position pos)中判断为0 有效
在public void record(Position pos)中我让该位置为中心的横竖斜的方向上每个位置之加1,该位置加2*this.grid.length;
public void undo(Position pos),撤销时与上是逆过程;

private class QueenIterator implements Iterator为内部类,记录某位置的下一行可选位置,



一下是测试程序:
package 数据结构及算法.回溯法应用之n皇后问题;

import java.util.Iterator;
import java.util.Scanner;

import 数据结构及算法.回溯法.Application;
import 数据结构及算法.回溯法.BackTrack;
import 数据结构及算法.回溯法.Position;


public class QueenTest {
	
    private int n;
    public QueenTest(){
    	Scanner sc=new Scanner(System.in);
    	String  prompt="请输入皇后的大于3的维数!";
    	System.out.println(prompt);
    	this.n=sc.nextInt();
    	pocessInput();
    }
	
	public void pocessInput() {
		
		Application app=new Queen(n);
		BackTrack backTrack=new BackTrack(app);
		
		println("开始为:");
		println(app.toString());
		Position pos=new Position(-1,0);
		Iterator itr=app.iterator(pos);
		int count=0;
		while(itr.hasNext()){
			Position startPosition=(Position) itr.next();
			app.record(startPosition);
			if(backTrack.tryToSolve(startPosition)){
				println("success");
				count++;
				println("第"+count+"个满足的为:");
				println(app.toString());
				app=new Queen(this.n);
				backTrack=new BackTrack(app);
			}
			else{
				app=new Queen(this.n);
				backTrack=new BackTrack(app);
				println("failure!");
			}
			
		}
		
	}
	
	public void println(String s){
		System.out.println(s);
	}
	public static void main(String[]args){
		new QueenTest();
	}
}


测试时可找到从第一排每个位置开始的可能的n皇后结果,还有什么不妥的地方,欢迎拍砖
分享到:
评论

相关推荐

    n 皇后问题n 皇后 回溯法n 皇后 回溯法

    N皇后问题的回溯法求解是一个典型的递归加回溯的应用案例。通过递归的方式尝试在每一行放置一个皇后,并利用回溯机制撤销不成功的决策,最终可以找到所有可行的解决方案。此方法虽然简单直观,但在N较大时可能会面临...

    回溯法实现N皇后问题

    **回溯法实现N皇后问题** N皇后问题是一个经典的计算机科学问题,它的目标是在一个N×N的棋盘上放置N个皇后,使得任意两个皇后都不能在同一行、同一列或同一对角线上。这是一个典型的约束满足问题,可以利用回溯法...

    算法设计与分析 回溯法 n皇后问题

    通过分析这个文件,我们可以深入理解如何将回溯法应用于解决实际问题,以及C++中如何实现这种算法。 总之,n皇后问题是回溯法的经典应用,它展示了如何通过系统地尝试所有可能的解决方案来解决一个复杂的约束满足...

    黑板风格,管道风格,调用返回风格,回溯法等解决N皇后问题

    本篇文章将深入探讨“黑板风格”、“管道风格”、“调用返回风格”以及“回溯法”这四种方法在解决N皇后问题中的应用。 首先,N皇后问题是一个经典的计算机科学问题,要求在N×N的棋盘上放置N个皇后,使得任何两个...

    n皇后问题--回溯法实验

    **回溯法是一种在搜索解决问题时采用的有效算法,...**总的来说,通过理解并分析`n皇后问题.cpp`源代码,我们可以学习到如何利用C++和回溯法解决复杂的问题。这不仅有助于提升编程技能,还能培养解决问题的思维能力。**

    回溯法n后问题实验报告

    ### 回溯法n后问题实验报告知识点解析 #### 实验背景与目的 - **实验背景**:本实验属于华南师范大学计算机软件学院本科生课程“算法分析与设计”中的一项实践内容,旨在通过实际操作加深学生对回溯法的理解与应用...

    C#控制台回溯法实现n皇后问题

    总结起来,"C#控制台回溯法实现n皇后问题"是一个利用C#编程语言在控制台环境下,通过回溯算法解决经典计算机科学问题的实例。它涉及到的主要知识点包括:回溯法的概念和实现,递归算法,二维数组的使用,以及控制台...

    N皇后问题(回溯法)

    N皇后问题(回溯法) N皇后问题是计算机科学中的一类经典问题,它是指在一个NxN的棋盘上,如何将N个皇后摆放的方式,使得每个皇后都不会攻击到其他皇后。这个问题可以使用回溯法来解决。 回溯法是一种常用的搜索...

    C语言解决n皇后问题 例如八皇后问题 列出所有解的情况

    n皇后问题是一个经典的回溯法问题,它涉及到在n×n的棋盘上放置n个皇后,使得任意两个皇后都不能在同一行、同一列或同一对角线上。以八皇后问题为例,即在8×8的棋盘上放置8个皇后,找出所有可能的解决方案。这个...

    n皇后问题回溯法C++代码

    通过这种方式,我们可以使用C++的回溯法解决N皇后问题,深入理解回溯法的基本思想,并掌握其在实际问题中的应用。这种方法不仅可以解决N皇后问题,还可以扩展到其他类似的问题,如八数码难题、迷宫问题等。

    回溯法-N皇后问题_N皇后回溯法C++_

    N皇后问题是一个经典的回溯法应用实例。这个问题要求在n×n的棋盘上放置n个皇后,使得任意两个皇后都不能在同一行、同一列或同一对角线上。它具有很高的复杂性,随着棋盘大小n的增加,解决方案的数量呈指数级增长,...

    C++n个皇后回溯法求解

    代码示例中使用了回溯法来求解n皇后问题。具体步骤如下: 1. **定义变量**:定义了一个整型数组`a[n]`用来存储每个皇后所在的列号,其中`n`是棋盘的大小。 2. **函数`place(int k)`**:此函数用于检查第`k`个皇后...

    回溯法解 N皇后问题

    ### 回溯法解决N皇后问题 #### 一、N皇后问题概述 ...综上所述,通过回溯法解决N皇后问题是解决此类问题的一种有效途径,它不仅能够得到所有可能的解决方案,还能帮助理解搜索算法的基本思想及其在实际问题中的应用。

    回溯法之N皇后问题C语言.doc

    回溯法之 N 皇后问题 C 语言 回溯法是一种常用的搜索算法,应用于解决复杂的问题,例如 N 皇后问题。该算法的基本思想是通过递归搜索所有可能的路径,直到找到满足条件的解答。 在 N 皇后问题中,我们需要将 N 个...

    回溯法解决n后问题

    回溯法是一种强大的算法策略,常用于解决组合优化问题,如经典的八皇后问题。在这个问题中,目标是在一个8x8的...理解和掌握回溯法不仅有助于解决n皇后问题,还能应用于其他类似的问题,如图的着色问题、数独求解等。

    回溯算法n皇后问题

    总结来说,回溯算法在N皇后问题中的应用展示了其在解决约束优化问题中的灵活性和有效性。通过尝试所有可能的解并适时回溯,可以找到所有满足条件的解,而不仅仅是第一个解。此外,N皇后问题的解法也揭示了如何将问题...

    矩阵链乘和n皇后问题的程序和解题报告(随机法+回溯法)

    综合以上,矩阵链乘问题展示了如何运用动态规划解决优化问题,而n皇后问题则揭示了回溯法在解决约束满足问题中的威力。这两种问题的解决方法都对理解算法设计和分析有着重要的启示作用,不仅适用于理论学习,也在...

    基本算法回溯法N皇后问题

    **回溯法与N皇后问题** 回溯法是一种在搜索问题解决方案时,通过尝试所有可能的解决方案,并在遇到错误或无效解时退回一步,尝试其他可能性的算法。它主要用于解决那些具有约束条件的问题,其中解决方案可能有多个...

    用回溯法实现n皇后问题(java源码)

    在编程领域,n皇后问题是一个经典的算法问题,它要求在n×n的棋盘上放置n个皇后,使得任意两个皇后不能...通过Java实现的n皇后问题源码,我们可以深入学习到回溯法、数据结构、设计模式以及软件工程中的许多重要概念。

    回溯法实验(n皇后问题)(迭代法).pdf

    回溯法实验(n皇后问题)(迭代法) 回溯法是解决约束满足问题的一种常用方法,通过在解空间中搜索满足约束条件的解。本次实验的目的是掌握回溯法求解问题的思想,并学会利用其原理求解相关问题。 实验原理 回溯法...

Global site tag (gtag.js) - Google Analytics