回溯法——以皇后摆放问题为例

chanxe 2023-03-28 原文

回溯法(98条消息) （新手向）递归与回溯算法学习（一）——n位逐位整除数_TripleGold.的博客-CSDN博客

算法思想：

（通用的解题法）穷举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现不满足求解条件时就回退，尝试其他路径

回溯法的解题步骤：

针对给定问题确定问题的解空间树，至少包含问题的一个解或者最优解
确定结点的扩展搜索规则
以深度优先搜索解空间树，并采取剪枝手段。

框架：

非递归回溯框架

 int x[n]    //x存放解向量，全局变量
 void backtrack(int n){
     int i = 1;      //根节点的层次为1
     while(i>=1){    //尚未回溯到头        
     if(ExistSubNode(t)){    //当前结点存在子节点
         for(j=下界;j<=上界;j++){    //对于子集树，j从0到1循环
             x[i]取一个可能的值;
             if(constraint(i)&&bound(i)){    //x[i]满足约束条件和界限函数
                 if(x是一个可行的解)
                     输出x;
                 else i++;   //进入下一个层次
             }
         }
     }
     else i--;   //不存在子节点，返回上一层
     }
 }

递归回溯框架

 int x[n]
 void backtrack(int i){
     if(i>n)     //搜索叶子结点，输出一个可行解
         输出结果;
     else{
         for(j=下界;j<=上界;j++){    //用j枚举i所有可能的路径
             x[i] = j;   //产生一个可能的解分量
             ...
             if(constraint(i)&&bound(i))
                 backtrack(i+1)  //满足约束条件继续下一层
         }
    }
 }

 result = []
 def backtrack(路径, 选择列表):
     if 满足结束条件:
         result.add(路径)
         return
         
     for 选择 in 选择列表:
         做选择
         backtrack(路径, 选择列表)
         撤销选择

例题：皇后摆放问题：

题目描述

国际象棋的棋盘可以看做是一个 8 × 8 的矩阵，上面每一个格子仅能放一枚棋子，现在给出一个 8 × 8 的由 0 和 1 组成的矩阵，代表象棋棋盘，1 代表当前位置放置了一个皇后，0 则代表什么都没有放，上面有 n（n 为小于 8 的正整数）个位置已经放上了皇后棋子（相互之间不冲突，合理摆放），现在另外给你 8 - n 个皇后，问你有多少合理的摆法。

输入描述

一个 8 × 8 的由 0 和 1 组成的矩阵。

输出描述

一个整数，为摆放的种类数。

样例输入

 1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0

样例输出

问题分析

判断某位置是否可以摆放皇后

假设i行j列处已摆放上一个皇后，则下面摆放的皇后(x,y)则不能在i行和j列(即x!=i && y!=j)，且不能在已摆放皇后对角线上(即abs(x-i)!=abs(y-j))。

搜索算法

通过初始化，我们可以知道哪些位置有了皇后。通过一个路径数组path[9]来记录（1~8）行哪一列有皇后。还未探索到的行，数组赋值0。

用回溯法，从第一行开始往下，测试1~8列是否能够摆放，能则继续往下探索，不能则返回上一层。

AC代码：

 #include<iostream>
 #include<cstring>
 #include<cmath>
 using namespace std; 
 
 int path[9];
 //判断某位置是否可以摆放皇后
 bool pd(int x){
     for(int i=1;i<=8;i++){
         if(path[i]!=0 &&i!=x && (path[i]==path[x] || abs(i-x)==abs(path[i]-path[x]))){
             return false;
         }
     }
     return true;
 }
 //搜索算法
 void backtrace(int x,int &sum){
     if(x==9){
         sum++;
         return;
     }
     if(!path[x]){
         for(int i=1;i<=8;i++){
 
             path[x] = i;
             if(pd(x)) backtrace(x+1,sum);
             path[x] = 0;
         }
     }
     else backtrace(x+1,sum);
 }
 
 int main(){
     int x,sum = 0;
     memset(path,0,sizeof(path));
     for(int i=1;i<9;i++){
         for(int j=1;j<9;j++){
             cin>>x;
             if(x==1){
                 path[i]=j; 
             }
         }
     }
     backtrace(1,sum);
     cout<<sum<<endl;
     return 0;
 }

mdash 题为 span class nbsp C++

有关回溯法——以皇后摆放问题为例的更多相关文章

ruby-on-rails - Ruby无一异常(exception)地获得回溯 - 2
我有一个RubyonRails应用程序，其中一个模型的验证失败。对于此验证可能失败的地方，代码库有不同的入口点。我有兴趣弄清楚它是从哪里来的。由于这是一个简单的验证方法，因此不涉及任何异常，我只是从方法中返回false并且保存失败。目前是否还可以记录回溯以查明此验证源自哪个服务/路由，以便我可以查看是什么导致此对象的状态发生更改以使其验证失败？最佳答案你可以试试caller():deffoo2putscallerenddeffoofoo2#line5endfoo#line7结果:test.rb:5:in`foo'test.rb:
ruby - 如何使用消息和回溯手动创建异常 - 2
如何使用回溯创建异常？我知道我们可以做这样的事情来实现这一目标:beginraiseStandardError,"message"rescueStandardError=>exceptionexception.backtraceend或者exception=StandardError.new("message")exception.set_backtrace(caller)但我正在寻找这样的东西:exception=StandardError.new("message",backtrace:caller)有没有一种方法可以使用自定义消息和回溯来初始化异常？
ruby-on-rails - 应该破坏我的回溯吗？ - 2
我有一个或多或少像这样的测试:classFormDefinitionTest我特意加了一个raise"blah"在路上的某个地方，我得到了这个错误:RuntimeError:blahtest/unit/form_definition_test.rb:79:in`__bind_1290079321_362430'当我应该得到一些东西时:/Users/pupeno/projectx/db/seed/sheet_definitions.rb:17:in`sheet_definition':blah(RuntimeError)from/Users/pupeno/projectx/db/seed
ruby - RSpec 较短的测试失败回溯输出 - 2
我正在使用RSpec(最新版本2.12.2)来测试我正在处理的一个小型Ruby类。我的问题是，当RSpec测试失败时，测试输出看起来非常冗长，并显示了一个巨大的错误消息列表，几乎是一个完整的回溯。这意味着我必须向上滚动才能看到实际的错误消息和跟踪的顶部。我相信默认情况下RSpec应该这样做，但它似乎并没有为我做这件事。例如，如果我运行rspecspec/my_spec.rb:132(只运行一个在L132上的测试)，我得到这个输出:Failure/Error:@f.has_changed?("test").shouldbe_trueexpected:truevaluegot:fals
ruby - 如何让 ruby 打印包含传递给函数的参数的完整回溯？ - 2
有时回溯足以诊断问题。但有时在不知道传递给函数的内容的情况下，崩溃的原因并不明显。获取传递给导致崩溃的函数的信息将非常有用，特别是在重现不明显的情况下，因为它是由例如网络连接异常、奇怪的用户输入或因为程序依赖于随机化或进程引起的来自外部传感器的数据。假设有以下程序defhandle_changed_input(changed_input)raise'ops'ifchanged_input=~/magic/enddefdo_something_with_user_input(input)input="#{input.strip}c"handle_changed_input(input)e
ruby-on-rails - 在 Ruby on Rails TestCase 中开启完整回溯 - 2
运行时只显示一行回溯:raketest输出:...ERRORshouldgetsearchforkeywords(1.93s)NoMethodError:undefinedmethod`features'for#/usr/lib/ruby/gems/1.9.1/gems/activemodel-3.1.0/lib/active_model/attribute_methods.rb:385:in`method_missing'...我需要更多行的回溯信息。我试过了rake测试--traceRails.backtrace_cleaner.remove_silencers!在config/i
Ruby Rescue 显示完整的回溯 - 2
这是一个简单的例子:putsFile.join(nil,"hello")会输出test.rb:4:in'join':can'tconvertnilintoString(TypeError)fromtest.rb:4但是当我这样做的时候:beginputsFile.join(nil,"hello")rescue=>exceptionputsexception.backtraceend这将输出test.rb:4:in'join'test.rb:4现在如何捕获完整的回溯，包括“无法将nil转换为字符串(TypeError)”部分？@SarahVessels:在我的特定代码中，这个片段:put
ruby-on-rails - 如何使用默认的 Rails 记录器记录 Ruby 异常的整个回溯？ - 2
我正在从事rails项目，我正在尝试将异常记录到rails日志文件中。我知道我可以调用logger.error$!将异常的第一行记录到文件中。但是，我也想记录整个跟踪堆栈。如何使用默认的Rails记录器记录异常的整个回溯？最佳答案 logger.error$!.backtrace还有，别忘了你可以rescueErrorType=>error_name为您的错误指定一个不同于默认$!的变量名。关于ruby-on-rails-如何使用默认的Rails记录器记录Ruby异常的整个回溯？，我
ruby - 如何从 SystemStackError : stack level too deep? 获取回溯 - 2
在编写ruby代码时，我常常很难调试无限递归。有没有办法从SystemStackError中获取回溯？找出无限循环发生的确切位置？例子给定一些方法foo,bar和baz在循环中互相调用:deffoobarenddefbarbazenddefbazfooendfoo当我运行这段代码时，我只收到消息test.rb:6:stackleveltoodeep(SystemStackError).至少获取堆栈的最后100行会很有用，因此我可以立即看出这是foo之间的循环。,bar和baz，像这样:test.rb:6:stackleveltoodeep(SystemStackError)test
javascript - 有谁知道如何在 javascript 中以编程方式获取函数调用堆栈(回溯)？ - 2
有谁知道如何在javascript中以编程方式获取函数调用堆栈(回溯)？这可能吗？如果是，怎么办？最佳答案这在提出问题时不可用，但现在所有现代网络浏览器都支持console.trace()。请注意，此功能被视为非标准功能。更多相关信息:https://developer.mozilla.org/en-US/docs/Web/API/Console.trace 关于javascript-有谁知道如何在javascript中以编程方式获取函数调用堆栈(回溯)？，我们在StackOverf