皇后问题

Bertha 。 2022-12-06 12:52 167阅读 0赞

# 问题 #

> 国际象棋中的皇后，可以横向、纵向、斜向移动。如何在一个NXN的棋盘上放置N个皇后，使得任意两个皇后都不在同一条横线、竖线、斜线方向上？

举个栗子，下图的绿色格子是一个皇后在棋盘上的“封锁范围”，其他皇后不得放置在这些格子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]

# 递归回溯法 #

package main
    
    import "fmt"
    
    const N = 4;
    
    // 第1个N是由几行， 第2个N是有几列
    var queue [N][N]int
    
    func show()  {
        
    	for i := 0; i < N;  i++ {
         // 第i行
    		for j := 0; j < N ; j++ {
        
    			//fmt.Printf("%5d", queue[i][j])
    			if queue[i][j]==1{
        
    				fmt.Printf("%5s","■")
    			}else{
        
    				fmt.Printf("%5s","□")
    			}
    		}
    		fmt.Println()
    	}
    	fmt.Println()
    }
    
    
    // 判断 第row行，第col列是否可以存放数据
    func judge(row, col int) bool  {
        
    	for i := 0; i < col;  i++ {
        
    		if queue[row][i] == 1 {
         // 行固定， 前j列是否已经存放数据
    			return false
    		}
    	}
    
    	for j := 0; j < col; j++{
        
    		if queue[row][j] == 1 {
         // 列固定， 前j行是否已经存放数据
    			return false
    		}
    	}
    
    
    	for i, j := row - 1, col - 1; i >= 0 && j >= 0 ; i, j = i - 1, j - 1{
        
    		if queue[i][j] == 1 {
        
    			return false
    		}
    	}
    
    	for i, j := row - 1, col + 1; i >= 0 && j <= N - 1 ; i, j = i - 1, j + 1{
        
    		if queue[i][j] == 1 {
        
    			return false
    		}
    	}
    
    	for i, j := row + 1, col - 1; i <= N - 1 && j >= 0 ; i, j = i + 1, j - 1{
        
    		if queue[i][j] == 1 {
        
    			return false
    		}
    	}
    
    	for i, j := row - 1, col + 1; i >= 0 && j <= N - 1 ; i, j = i - 1, j + 1{
        
    		if queue[i][j] == 1 {
        
    			return false
    		}
    	}
    
    	return true
    }
    
    var count = 0;
    /*
     * num 的意思是：我们正在放置第i个皇后
    
    */
    func find_queue(num int)  {
        
    	//show()
    	if num == N {
         // 所有的皇后都放完了
    		count++
    		show()
    		return
    	}
    
    
    	for row := 0;row < N ; row++ {
         	// 第num个皇后放到第num列[固定好的]，[0, N)行上试探
    		if judge(row, num) {
        
    			queue[row][num] = 1
    			find_queue(num + 1)
    			queue[row][num] = 0 // 只有在皇后摆不下去的时候会执行清0的动作（避免脏数据干扰），如果皇后摆放很顺利的话从头到尾是不会走这个请0的动作的，因为已经提前走if里面的return方法结束了。
    		}
    		//show()
    	}
    }
    func main() {
        
    	find_queue(0)
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/fe3746f709984326b0eee7b00a6d3b46.png