回溯法与八皇后问题

        昨天晚上写了一个OJ上的八皇后问题,然后居然TLE了。。。。(本人弱鸡)。。。然后就躺在床上想怎么优化,想着想着就睡着了,做了一个令人感到忧伤的梦,然后醒了,然后就想到了怎么优化了。。。。当然我很菜。。。用的还是简单回溯的算法,其实就是DFS,皇后多了还是很耗时的,所以,各位皇帝麻烦您们专一一点好吧。

        好吧,先说回溯法吧,回溯法和DFS差不多,其思想就是:“我就是要一条路走到黑,走到黑了然后感觉不对,就赶紧返回上一层,看看有没有其他的路,如果没有走到黑,反而走到白了,那就恭喜我,我成功搞出一条通天大道,那么,我。。我。。我我我还是要返回上一层。。。。看看有没有其他的路。。。“讲道理一条路就中了,但可恶的出题人太贪心,总喜欢让我们把所有的路都找到,这不是坑爹呢吗。。。。

大致的框架可以写为:

void func(int step){

    1判断路是不是死路,如果是就返回;

    2如果判断是不是已经走出一条通天大道了,如果已经是了,那就在这里搞一些操纵,然后。。。还是要返回上一层。。。

   for chioce in allOption{

       标记一下这个chioce被选过了(某些情况下需要)

        func(step+1);//走下一步        

     }

}

注意,一定不要把1嵌入2里面,如果这样做的话,会DFS出所有选择的全排列,然后再判断是否可行,这样就没有剪枝的效果了。

 

 

好吧我知道本人讲的很渣渣,很坑爹,应该没有人能看懂。。。。嗯。。。如果能画图就好了。。。。但是我很懒。。不想画完图用手机拍照然后再传到电脑上然后在传到博客上。。。。。。。


题目:

检查一个如下的6 x 6的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。

上面的布局可以用序列2 4 6 1 3 5来描述,第i个数字表示在第i行的相应位置有一个棋子,如下:

行号 1 2 3 4 5 6

列号 2 4 6 1 3 5

这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。

解法(代码里面的注释应该很清楚):

#include <iostream>
using namespace std;
void queen(int step);
int n;//有多少个皇后
int count;//记录成功的方案
int book[14];//标记
int a[14];//a[1]表示第一行的皇后在第几列,a[2]表示第二行的。。。。。
int main(){
    cin>>n;
    queen(n);
    cout<<count;
    return 0;
}
void queen(int step){
    int LastLine=n-step;//上一步摆下来的皇后,因为摆放皇后时候已经用了book数组进行标记约束,所以不需要判断行列
    for(int i=1;i<LastLine;i++){//判断是否在同同一斜线上
        if(a[LastLine]-a[i]==LastLine-i||a[LastLine]-a[i]==i-LastLine){
            return;
        }
    }
    /*for(int i=1;i<=n-step;i++){//这里是原来的判断是否在同一条斜线上的算法,但是算法复杂度很高,分析原因发现
        for(int j=i+1;j<=n-step;j++){//这个算法是,对于每一行,都有对比其他的行,重复了很多
            if(a[j]-a[i]==j-i||a[j]-a[i]==i-j){//仔细思考发现,只需要判断新加入的皇后符不符合要求就行,所以
                return;//换成了上面的算法,复杂度是o(N)
            }
        }
    }*/
    if(step==0){//拜访了最后一个皇后,已经得出了一种解法
        count++;
        if(count<=3){
            for(int i=1;i<=n;i++){
                cout<<a[i]<<' ';
            }
            cout<<endl;
        }
    }else{
        //进行本次放置,然后递归下一次
        for(int i=1;i<=n;i++){//每次摆放这一行的皇后的时候,都有N列可以摆,意思就是有N个岔路口。
                              //我们选一个深入,等这个返回之后,再选下一个进行深入,所以是一个for循环
            if(!book[i]){//如果第i列还没有黄后占场子
                book[i]=1;//标记一下我要占上
                a[n+1-step]=i;//摆放皇后
                queen(step-1);//深入下一个路口
                book[i]=0;//返回了,就要开始走下一个差路口(下一列),所以这一列的标记取消掉
            }
        }
    }
}

 

回溯法与八皇后问题》有47个想法

  1. Brian

    Good crew it’s cool 🙂 cheap viagra online
    “The guy or gal who’s 35, they have a chance to go todefined contribution, get another job, get a second-jobsupplement, get married, handle their affairs,” he said.”Frankly there’s some validity to that kind of argument.”

  2. Carol

    Is there ? write essay cheap After the disputed 2007 election, angry supporters of opposition candidate Raila Odinga turned on those — usually identified by tribe — they believed had voted for incumbent President Mwai Kibaki. Kibaki supporters attacked members of Odinga’s tribe in retaliation, and marauding gangs burned, hacked and raped their opponents in weeks of violence. 

  3. Darell

    I’m a housewife cheap viagra online
    The Department of Health and Human Services saidHealthcare.gov has attracted nearly 9 million visitors since thestart of enrollment, but has not given any details on how manyapplications for insurance or enrollments have been processed.

  4. Charlotte

    We used to work together buy cialis 10mg
    Vigneault, 52, will shed light on his plans to turn this team’s hopes of raising the Stanley Cup into a reality, and by all accounts he will demonstrate just by being himself how different the franchise’s new culture will be from the occasionally successful but overbearing one John Tortorella cultivated.

  5. James

    Photography cheap viagra online
    “It's not surprising. We develop in unbuildable areas, we build with garbage and we design without planning,” Jesus Silva-Herzog Marquez, a law professor at the Autonomous Technological Institute of Mexico, wrote in Reforma newspaper.

  6. Genesis

    It’s OK write essay fast
    Another important piece is Pablo Prigioni, who is a restricted free agent. Prigioni’s leadership and defense are critical — especially with Jason Kidd retired and coaching the Brooklyn Nets. The Knicks are optimistic that Prigioni will return.

  7. Ahmad

    Which year are you in? cheap viagra online
    “This is fundamentally how we create one Google experience across the Internet,” said Seth Sternberg, product management director for Google . “It’s that link between Google, you, and the rest of the Net.”

  8. Dwight

    I want to make a withdrawal write essay cheap Clinton made the comments in recalling the deals her husband, President Clinton, struck with Republicans to balance the budget and approve welfare reform — a sharp contrast to the looming fiscal fights between President Obama and congressional Republicans that could lead to a government shutdown for the first time since Clinton’s White House days.

  9. Kareem

    Which year are you in? cheap cialis online Then there’s Henrik Lundqvist, who took Monday’s practice off for no urgent reason other than to rest, the Rangers said. No one knows exactly what’s going on in Lundqvist’s head during the most difficult stretch of his career (3.44 GAA, 89% saves) but his trademark mental focus undoubtedly is clouded. The team’s play, his unresolved contract negotiations and his own on-ice failures all are swirling in the background.

  10. Loren

    I’m on business cheap viagra online
    Giamatti and Rudd banter with appeal, but Melissa James Gibson’s lackluster script doesn’t offer either much to work with. Gibson is a playwright making her screenwriting debut, and it shows. The film’s drab look and deliberately limited viewpoints don’t suggest restricted lives so much as an unsuccessfully adapted stage play.

  11. Brooke

    What qualifications have you got? buy cialis 10mg
    Currency traders contacted by Reuters said it was unsurprising that dealers tried to profit from advance knowledgeof client orders but given the size of the market, manipulatingthe benchmarks would be difficult unless the trader had a verylarge order or was dealing in two rarely traded currencies.

  12. Caden

    How many days will it take for the cheque to clear? buy viagra 100mg Cheick Fantamady Bouare, the local prefect, said four people had been killed in total, including a child. The bomber was believed to have ferried other fighters to the town’s outskirts before detonating his charge, Bouare said.

  13. Manual

    I don’t like pubs kamagra oral jelly kaufen per paypal How totally ironic that the US government and its willing accomplices, who together possess and control some of the very largest series of stock piles of Chemical Weapons on Earth are pontificating about controlling the chemical weapons in Syria, of which large quantities are likely already in the hands of the so-called “Free Syrian Army”, a motely collection of fanatical, butchering Terrorists, flooding into Syria from all over the Middle East.

  14. Kirby

    I’d like to tell you about a change of address cheap viagra online
    Lewis Ferguson, at the time a Zoetis reliability engineer, looked at medical equipment makers but struck out. “I thought about calling my pals from the space program at Boeing and Lockheed”–his previous job was at NASA–“but I didn’t think we could afford that,” he says with a laugh. Then he stumbled upon Marlin Steel’s website, where he saw baskets that looked close to what he needed. He talked to someone at the company and agreed on a basic design. Then he asked Marlin to add handles. “They said, ‘Okay, handles are no problem,'” says Ferguson. Then he decided the baskets needed a lid. “The folks at Marlin said, ‘Okay, a lid, we can do that.'” Then he asked for higher-quality steel. “They said, ‘Okay, that’s a stretch, but we’ll see what we can do.'”

  15. Quinn

    I love this site buy viagra 100mg A spokesperson for Peterborough and Stamford Hospitals NHS Foundation Trust said: “The trust is now in the final stages of contract discussions regarding the sale of the former Peterborough District Hospital site. We hope these will be concluded shortly.”

  16. Denis

    Would you like to leave a message? write essay cheap “The risk going in doesn’t seem to matter on the outcome,” said Dr. Douglas Packer at the Mayo Clinic in Rochester, Minnesota. “Those at the highest risk (of stroke) still appear to have received substantial benefit from the ablation.”

  17. Raymon

    Do you know each other? buy cialis 10mg
    Casa Diablo bills itself as the “world’s first vegan strip club,” and its tagline is “Portland’s hottest dancers, incredible vegan food.” Its menu includes burgers and burritos, but it is all meat-free.

  18. Arlie

    Could I order a new chequebook, please? cheap viagra online
    The data countered lingering negative sentiment surroundingexpectations that the U.S. Federal Reserve may start next monthto tighten monetary policy measures that have driven much ofthis year’s global equity rally.

  19. Damian

    Can I call you back? write essay cheap Thanet Earth employs a 40-strong quality control department, a necessary expense because even a few flawed fruits can jeopardise an entire delivery to a supermarket chain. It claims that only two per cent of its produce fails to meet the retailers’ exacting standards.

  20. Bennie

    I’ve got a part-time job buy viagra 100mg The study found that the more people used Facebook during one time period, the worse they subsequently felt. Researchers also asked people to rate their level of life satisfaction at the start and end of the study.

  21. Jamar

    Can I take your number? write essay fast
    Heard, 27, stars as Miss San Antonio, a secret agent working undercover as a beauty queen. Rodriguez had wanted to work with Heard — who’s dating the director’s “Once Upon a Time in Mexico” star Johnny Depp — for some time.

  22. Sammie

    I’d like to order some foreign currency buy cialis 10mg
    Yes there are a number of options available, you can set your browser either to reject all cookies, to allow only “trusted” sites to set them, or to only accept them from the site you are currently on.

  23. Kenny

    I’ve got a very weak signal write essay cheap On this week’s Daily News Fifth Yankees Podcast, Mark Feinsand sits down with Yankees outfielder Vernon Wells to discuss the current state of the team, the Ryan Braun and Alex Rodriguez controversies and much more.

  24. Quincy

    I’m interested in this position write essay cheap Moral principles are heavy burdens to carry and even harder to maintain over time. For too many leaders they are inconveniences easy to cast aside in the face of greater riches and power, and often in the face of diplomatic failures. For others moral principles in governance are signs of weakness, not strength. They are words to be used for convenience, to be cast aside when equally convenient.

  25. Orlando

    Best Site Good Work buy viagra 100mg Verity's last first-class match was against Sussex at Hove in September 1939, when he took seven wickets for nine runs to bowl Sussex out for 33 in their second innings. After that, the County Championship was postponed because of the war, although Yorkshire had already done enough to claim their seventh title of the 1930s.

  26. Jasmine

    Hello good day write essay cheap ROME, Aug 21 (Reuters) – Italian Prime Minister Enrico Lettamet with Silvio Berlusconi’s centre-right party on Wednesday toseek a solution to a stand-off that threatens his fragilecoalition, but positions remained “distant”, a government sourcesaid.

  27. Felipe

    What’s the current interest rate for personal loans? write essay fast
    “What a good idea – the only problem is, he’s on a hiking tour of the Paps of Jura,” said Nick, exhaling with relief. “Anyway, who needs anyone else? We’re together for the duration, aren’t we? Joined at the hip, stuck like glue.”

  28. Ronald

    An accountancy practice cheap cialis online (HealthDay)—Adults with psychiatric illnesses such as schizophrenia, depression, and bipolar disorder who participate in clinical trials of psychopharmacological drugs have a higher mortality risk, in many …

  29. Harold

    A packet of envelopes buy viagra 100mg Climate skeptics have seized upon the change in world weather patterns, some citing it as evidence that global warming itself has decelerated or even stopped. Benny Peiser, director of the Global Warming Policy Foundation, said the slowdown was a far larger issue than the report shows.

  30. Arron

    How much is a First Class stamp? buy cialis 10mg
    For too long, the US backed Mubarak’s undemocratic and corrupt regime, and the military that kept him in power. Those officials had little interest in economic growth; their interest was staying in power and enriching themselves while the country remained poor. And the US bought into it.

  31. Luciano

    Do you know the address? buy cialis 10mg
    After meeting on the set of the 1996 horror film ‘Scream,’ Courteney Cox and David Arquette wed at Grace Cathedral in San Francisco on June 12, 1999. Hundreds of fans stood outside the church hoping to catch a glimpse of the Valentino-clad bride and her groom as they made their way to their reception at Bimbo’s, a 1930s speakeasy-style club where they were joined by celeb guests, including ‘Friends’ co-stars Jennifer Aniston and Lisa Kudrow, Arquette’s sisters Roseanna and Patricia, Nicolas Cage and Paul (Pee-Wee Herman) Reubens. After splitting up, the pair filed for divorce in June 2012.

  32. Carroll

    The United States buy cialis 10mg
    ** Indonesia expects a deal on Monday to buy out theJapanese shareholders of PT Indonesia Asahan Aluminium (Inalum),a government minister said, avoiding a legal dispute and pavingthe way for the aluminum producer to be nationalized.

  33. Aaliyah

    I’ve been made redundant kamagra paypal australia
    Carmichael was familiar with the Alzheimer’s Association at that time and wanted to learn more, but didn’t begin participating in the walk until after her mother’s passing due to the time and work involved in her care. In the three years since then, however, she has been active in the walk, including helping a couple of other teams get organized and involved in the event.

  34. Damien

    Do you know each other? cheap cialis online Nissan’s Castelli was philosophical in defeat. “Change is difficult, and change within the New York taxi industry is even tougher. You have a lot of competing interests. Add to this a robust political environment layered by an election cycle, and some might say that the ‘Taxi of Tomorrow’ program was challenged from the start.”

  35. Sheldon

    International directory enquiries buy viagra 100mg These near-simultaneous U.S. special forces strikes Saturday are a potent reminder to members of Al Qaeda, Al-Shabaab and other jihadists in regions without a strong central government that America has a long memory, and a long arm to match.

  36. Laverne

    I’m sorry, she’s buy viagra 100mg “I believe pastors will be charged with hate crimes and promoting violence against homosexuality by just preaching what the Bible teaches,” he told Fox News. “I don’t believe they are going to pass any legislation protecting pastors.”

  37. Coco888

    I’ll put him on cheap viagra online
    Hefner said he had pitched the entire season through discomfort or pain, though in June and most of July it was hardly noticeable. From June 4 through the All-Star break, Hefner was 3-1 with a 1.76 ERA. In five starts after the All-Star break, he went 0-2 with a 9.13 ERA.

  38. Albert

    Could you tell me my balance, please? write essay cheap In seeking to stop the American-US Airways deal, the government contends that airlines already follow each other’s moves in setting prices and adding new fees. They even bully each other out of offering sales.

  39. Warren

    i’m fine good work kamagra günstig kaufen paypal
    The Republican-controlled House passed and sent to theSenate on Wednesday a funding bill that would re-open theNational Institutes of Health, which conducts medical research,and another bill to reopen shuttered federal parks and museums,such as the Smithsonian museums, the National Gallery of Art andthe Holocaust Memorial Museum in Washington.

  40. Abram

    Where’s the nearest cash machine? cialis fedex overnight shipping Many financial businesses depend on repo funding, and any disruption could spread to other markets. So far, liquidity issues appear contained. But even a brief default could cause large disruptions to payments, settlement and transfers of affected Treasuries.

  41. Frankie

    I’ve come to collect a parcel cheap cialis online Tossing pancakes is a definite skill; but students and staff at the University of Sheffield certainly have it mastered. In February 2012, 890 members of the university and local residents broke the record for most people tossing pancakes. Unfortunately, some hadn’t practised beforehand, as 40 participants had to be discounted due to either failing to toss their pancake within the time, or for dropping their pancake.

  42. Rubin

    Do you like it here? cheap viagra online
    The electric motor produces 125lbft of torque to boost acceleration and drives the vehicle in EV Mode. It also acts as a generator, harvesting kinetic energy through regenerative braking, charging the battery when the vehicle is slowing.

评论已关闭。