标签: backtracking

我在网上搜索了Haskell中n-queens问题的不同解决方案,但找不到任何可以在O(1)时间内检查不安全位置的解决方案,就像你为/对角线保留一个数组而另一个用于\ diagonals.

我找到的大多数解决方案只是检查了所有以前的新女王.像这样的东西:http: //www.reddit.com/r/programming/comments/62j4m/nqueens_in_haskell/

nqueens :: Int -> [[(Int,Int)]]
nqueens n = foldr qu [[]] [1..n]
    where qu k qss = [ ((j,k):qs) | qs <- qss, j <- [1..n], all (safe (j,k)) qs ]
      safe (j,k) (l,m) = j /= l && k /= m && abs (j-l) /= abs (k-m)

在Haskell中实现这种"O(1)方法"的最佳方法是什么？我不是在寻找任何"超级优化"的东西.只是某种方式来产生"这个对角线已经被使用了吗？" 数组以功能的方式.

更新:

感谢所有答案,伙计们!我最初问这个问题的原因是因为我想解决一个更难回溯的问题.我知道如何用命令式语言解决它,但不能轻易想到一个纯粹的功能数据结构来完成这项工作.我盘算了一下,皇后问题将是一个很好的模式(即在对整个数据结构问题回溯问题:)),但它不是我的真正的,虽然问题.

我实际上想找到一个允许O(1)随机访问的数据结构,并保持处于"初始"状态(自由线/对角线,在n-queens情况下)或处于"最终"状态(被占用)的值线/对角线),转换(自由占用)为O(1).这可以使用命令式语言中的可变数组来实现,但我觉得更新值的限制​​只允许一个很好的纯函数数据结构(例如,与Quicksort相反,它真的需要可变数组).

我认为,在Haskell中使用不可变数组可以获得同样好的解决方案,而"main"函数看起来就像我想要的那样:

-- try all positions for a queen in row n-1
place :: BoardState -> …

我试图找到解决以下问题的最佳方法.最好的方式我的意思是不那么复杂.

作为输入,元组列表(开始,长度)如下:

[(0,5),(0,1),(1,9),(5,5),(5,7),(10,1)]

每个元素通过其开始和长度来表示序列,例如(5,7)等同于序列(5,6,7,8,9,10,11)- 以5开头的7个元素的列表.可以假设元组按start元素排序.

输出应返回表示最长连续序列的非重叠元组组合.这意味着,解决方案是范围的子集,没有重叠且没有间隙,并且是最长的 - 尽管可能不止一个.

例如,对于给定的输入,解决方案是:

[(0,5),(5,7)] 相当于 (0,1,2,3,4,5,6,7,8,9,10,11)

它是回溯解决这个问题的最佳方法吗？

我对人们可以建议的任何不同方法感兴趣.

此外,如果有人知道这个问题的正式参考或另一个类似的问题,我想得到参考.

顺便说一句 - 这不是功课.

编辑

为了避免一些错误,这是预期行为的另一个例子

对于[(0,1),(1,7),(3,20),(8,5)]正确答案的输入[(3,20)]相当于(3,4,5,...,22)长度为20.收到的一些答案[(0,1),(1,7),(8,5)]相当于(0,1,2,...,11,12)作为正确答案.但这最后的答案是不正确的,因为它比短于[(3,20)].

集合[1,2,3,...,n]总共包含n!独特的排列.

通过按顺序列出和标记所有排列,我们得到以下序列(即,对于n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"给定n和k,返回第k个排列序列.

例如,给定n = 3,k = 4,ans ="231".

那里有多种解决方案.但是它们都使用阶乘或者复杂度大于O(n),例如O(n!).如果你使用阶乘并在位置找到k /(n-1)!的数字,那么当n很大(n = 100)时会出现问题.这里n很大,(n-1)!溢出并变为0.结果,我得到一个零除错误...任何解决方案或算法？

这是我的代码:

public class KthPermutation {
    public String getPermutation(int n, int k) {
        // initialize all numbers
        ArrayList<Integer> numberList = new ArrayList<Integer>();

        for (int i = 1; i <= n; i++) {
            numberList.add(i);
        }
        int fact = 1;   // set factorial of n-1

        for (int i = 1; i <= n-1; i++) {
            fact = fact * i;
        }   

        if ((long) …

我使用regex101分析了这两个正则表达式.我认为回溯/\S+:/是正确的.但我无法理解这种差异.我错了吗？

"编程挑战(编程竞赛培训手册)"可能是关于算法的最好的练习册之一.我已经解决了前11个练习,但现在我遇到了"Crypt Kicker"问题:

Crypt Kicker
加密文本的一种常见但不安全的方法是置换字母表中的字母.换句话说,字母表中的每个字母在文本中始终被其他字母替换.为确保加密是可逆的,没有两个字母被相同的字母替换.

您的任务是解密几个编码的文本行,假设每行使用不同的替换集,并且解密文本中的所有单词都来自已知单词的字典.

输入
输入由一个包含整数n的行组成,后跟n个小写单词,每行一个,按字母顺序排列.这n个单词组成可能出现在解密文本中的单词字典.
字典后面有几行输入.如上所述加密每一行.

字典中的单词不超过1000个.没有字超过16个字母.加密行仅包含小写字母和空格,长度不超过80个字符.

输出
解密每一行并将其打印到标准输出.如果有多种解决方案,任何人都可以.
如果没有解决方案,请用星号替换字母表中的每个字母.

Sample Input 6
和
dick
jane
puff
spot
yertle

bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn
xxxx yyy zzzz www yyyy aaa bbbb ccc dddddd

样品输出
鸡巴和jane和粉扑和斑点和yertle ...

我应该采取什么策略来解决这个问题？我正在考虑一个经典而野蛮的回溯解决方案,但我正在努力避免这种情况,直到我发现更聪明的东西.

PS:这不是与家庭作业有关,我只是想提高我的整体技能.

在访谈中询问了这个问题并处理了递归/回溯问题.假设我们有两个布尔数组:bool* source并且bool* target,每个布尔数组的长度相同n(源/目标/ n作为参数给出).问题的目标是转换source为target使用操作 开关.

• 如果有几个变换器:出现其中任何一个变换器
• 如果没有解决方案:断言没有解决方案

定义:操作switch(int i, bool* arr)反转arr [i]和arr [i-1]以及arr [i + 1]的值(如果这些索引在0 ... n-1范围内).

换句话说,switch操作通常会翻转三位(i及其邻居),但最后只有两位.

例如:

• switch(0,arr)仅切换arr [0]和arr [1]的值
• switch(n-1,arr)将仅切换arr [n-1]和arr [n-2]的值

提前感谢您对算法的建议.

我一直试图理解如何从回溯的Prolog谓词中产生一系列值.内置谓词between/3将在回溯时一次生成一个范围内的所有整数,因此编写它的示例可以帮助我完成任务.

我在现有的Prolog系统中寻找了一个实现,但between/3GNU Prolog 的实现是一个C函数,其技巧是调用另一个C函数"Pl_Create_Choice_Point",它允许它在回溯时产生额外的值.

所以univ运营商.我并不完全理解.

例如:

foo(PredList,[H|_]) :- bar(PredList,H).
foo(PredList,[_|T]) :- foo(PredList,T),!.

bar([H|_],Item) :- G =.. [H,Item],G.
bar([_|T],Item) :- bar(T,Item).

这是做什么的？这样可以查看另一个谓词是否为真.我不明白".."的作用.

如果没有univ运算符,你会如何重写它？

我正在审查本地编程竞赛中的编程问题.

你可以在这里下载问题(pdf).这是荷兰语,但图片将有助于理解它.

您收到am*m grid作为输入,包含一些管道和一些缺失点(问号).其余的管道必须放在网格中,以便它们与其他管道连接.

每个管道都用一个字母表示(见第2页的图片).字母'A'的值为1,'B'的值为2,..

我尝试用回溯解决它(它还没有完成工作).但由于网格可能是10x10,因此速度太慢.有人可以提出更好(更快)的解决方案/方法吗？

#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

#define sz(a) int((a).size())
#define pb push_back

int m, found;
string letters;
vector<int> done;
vector<string> a;

int ok(char letter, int c, int r)
{
    int val = letter - 'A' + 1;

    //checking if no side goes outside
    if (r == 0 && (val & 1))
        return 0;
    if (r == m - 1 && (val & 4))
        return 0;
    if (c == 0 …

现在我正在使用递归回溯,我的任务是找到迷宫中最长的路径,质量表示为用坐标覆盖的字段,并且墙壁的坐标在文件中是酸痛的.我已经制作了一个解析器来解析输入文件并构建墙,但是我还将这个坐标存储在一个对象类型Coordinate的数组中,以检查是否有可能在下一个上移动下一段"蛇"字段,然后我创建了这个方法,现在我已经明白我需要一个方法来从数组中删除最后一个坐标,当我使用回溯时,我该怎么办？目标不是使用数组列表或链表只有数组!谢谢!

public class Coordinate {
int xCoord;
int yCoord;

 Coordinate(int x,int y) {
     this.xCoord=x;
     this.yCoord=y;
 }

 public int getX() {
     return this.xCoord;
 }

 public int getY() {
     return this.yCoord;
 }
 public String toString() {
     return this.xCoord + "," + this.yCoord;

 }

 }

和

public class Row {
static final int MAX_NUMBER_OF_COORD=1000;

Coordinate[] coordArray;
int numberOfElements;


Row(){
    coordArray = new Coordinate[MAX_NUMBER_OF_COORD];
    numberOfElements=0;

   }


void add(Coordinate toAdd) {
    coordArray[numberOfElements]=toAdd;
    numberOfElements +=1;
}
boolean ifPossible(Coordinate c1){
    for(int i=0;i<numberOfElements;i++){

        if(coordArray[i].xCoord==c1.xCoord && coordArray[i].yCoord==c1.yCoord){
                return false; …