首页 > 其他分享 >数组 - 八皇后 - 困难

数组 - 八皇后 - 困难

时间：2024-12-06 15:29:43浏览次数：8  
标签：int mask 困难 unsigned long vector 数组 皇后 row

*************

C++

topic: 面试题 08.12. 八皇后 - 力扣（LeetCode）

*************

Good morning, gays, Fridary angin and try the hard to celebrate.

Inspect the topic:

This topic I can understand it in a second.  And I do rethink a movie, which talks anout chess

This title imposes the same rectructions on queens as the rules for queens in chess. In chess, queens may move either stright and diagonally. And may by this code was applied in some chees games.

 

Back to the topic, try to find the topics I've done which is similar to t his topic. It seems like no one like this. 

Use matrix, I learned matrix from a teacher, Master Tang:

Greedy algorithm, I did yesterday, may work. Every step goes to the best way, and might have the happy ending in the end.

First, put the queen in matrix[1][1], then put the second  row, maxtrix[2][1] is forbidden cuz it is in the first column. Matrix[2][2] is forbidden cuz it in the diagonal. Put it in matrix[2][3]. Actally, make sure that  matrix[i][i] put nothing. 

From the first row,  put the queen in the first column.

To the second row, put the queen in the first column, check if it conflicts with previous queens. If not, add a row. If so, change a column.

Take an example, N = 13, The position-array has 13 elements, each ranges from 0 to 12. 

For each increatment, generate a new array of positions. Check if the condition is satisfied for each array of positions. If satisfied, save it.                                                                         

When the last queen find her place, the war end.

This is a really new algorithm called Backtracking Algorithm.A backtracking algorithm is an algorithm that tries different things until it finds the right answer. It avoids doing unnecessary work. Backtracking algorithms are used to solve many kinds of problems. The usage of backtracking algorithm follows:

void backtrack(路径参数, 选择列表参数) {
    // 检查是否满足结束条件
    if (满足结束条件) {
        // 处理解决方案
        return;
    }

    // 遍历选择列表
    for (auto i : 选择列表) {
        // 添加当前选项到路径
        路径.push_back(i);

        // 进行递归
        backtrack(路径, 更新的选择列表);

        // 回溯，移除当前选项
        路径.pop_back();
    }
}

Try to write the code:

need to find a right way to describe the chess board. matrix N × N doesnot work, the reason of it is that memory is everything for the computer, N × N use tooooooooooooo much storage. Never think about it. 

Every queen has different row, so it can be used in one-line matrix, for instace:

 it can be described as 4 multiply 4 

  1. 1 0 0 0
  2. 0 0 1 0
  3. 0 1 0 0 
  4. 0 0 0 1

also, a smarter way to describe is as follow:

array X = [1, 3, 2, 4], which means

  1. the 1st  queen laies at row 1 column 1,
  2. the 2nd queen laies at row 2 column 3,
  3. the 3rd queen laies at row 3 column  2,
  4. the 4th queen laies at row 4 column  4,

but how to tell the computer that the queens cannot stay in the diagonal? 

the same color's position is illegal. It can EZ tell that two queens on the same diagonal if and only if their row and column differences are equal. 
|row1 - row4| == |column4 - column1|

There's no need to double-check each row and column; only the diagonals. To check more efficiently, record which columns and diagonals have been used when placing the queens.

record this in three sets:

  1. Columns where queens have already been placed.
  2. Primary diagonal: row-column values on the same primary diagonal.
  3. Sub-diagonal: row + column values where identical values are on the same sub-diagonal.

 so make up the code to describe the 3 sets in backtrack structure:

void backtrack_bit(int n, int row, unsigned long long cols_mask,
                       unsigned long long diag1_mask, unsigned long long diag2_mask,
                       vector<int>& queens, vector<vector<string>>& result) 
{
    // 检查是否满足结束条件
    if (满足结束条件) {
        // 处理解决方案
        return;
    }

    // 遍历选择列表
    for (auto i : 选择列表) {
        // 添加当前选项到路径
        路径.push_back(i);

        // 进行递归
        backtrack(路径, 更新的选择列表);

        // 回溯，移除当前选项
        路径.pop_back();
    }
}

move next, what is 满足结束条件? it is the row == n, the last queen finds her palace.

void backtrack_bit(int n, int row, unsigned long long cols_mask,
                       unsigned long long diag1_mask, unsigned long long diag2_mask,
                       vector<int>& queens, vector<vector<string>>& result) 
{
    // 检查是否满足结束条件
    if (row == n) {
        // 处理解决方案
        return;
    }

    // 遍历选择列表
    for (auto i : 选择列表) {
        // 添加当前选项到路径
        路径.push_back(i);

        // 进行递归
        backtrack(路径, 更新的选择列表);

        // 回溯，移除当前选项
        路径.pop_back();
    }
}

and what is 处理解决方案？ That is return the result. But pay vital attention to the result like this:

make sure that the code return a string:

 

void backtrack_bit(int n, int row, unsigned long long cols_mask,
                       unsigned long long diag1_mask, unsigned long long diag2_mask,
                       vector<int>& queens, vector<vector<string>>& result) 
{
    // 检查是否满足结束条件
    if (row == n) {
        // 生成棋盘的字符串表示
            vector<string> board;
            for (int i = 0; i < n; i++) {
                string row_str(n, '.'); // 初始化一行，全部为'.'
                row_str[queens[i]] = 'Q'; // 在皇后的位置放置'Q'
                board.push_back(row_str); // 将这一行添加到棋盘表示中
            }
            result.push_back(board); // 将整个棋盘添加到结果中

            return;
    }

    // 遍历选择列表
    for (auto i : 选择列表) {
        // 添加当前选项到路径
        路径.push_back(i);

        // 进行递归
        backtrack(路径, 更新的选择列表);

        // 回溯，移除当前选项
        路径.pop_back();
    }
}

the next step is 遍历选择列表. This is the most diffcult step, including how to lay the queens. Make sure that every column has been visited.

void backtrack_bit(int n, int row, unsigned long long cols_mask,
                       unsigned long long diag1_mask, unsigned long long diag2_mask,
                       vector<int>& queens, vector<vector<string>>& result) 
{
    // 检查是否满足结束条件
    if (row == n) {
        // 生成棋盘的字符串表示
            vector<string> board;
            for (int i = 0; i < n; i++) {
                string row_str(n, '.'); // 初始化一行，全部为'.'
                row_str[queens[i]] = 'Q'; // 在皇后的位置放置'Q'
                board.push_back(row_str); // 将这一行添加到棋盘表示中
            }
            result.push_back(board); // 将整个棋盘添加到结果中

            return;
    }

    // 遍历选择列表
    for (int col = 0; col < n; col++) {
        // 添加当前选项到路径
        路径.push_back(i);

        // 进行递归
        backtrack(路径, 更新的选择列表);

        // 回溯，移除当前选项
        路径.pop_back();
    }
}

If there's already a queen in the column, main diagonal, or sub-diagonal where you're placing the queen, skip that spot.

void backtrack_bit(int n, int row, unsigned long long cols_mask,
                       unsigned long long diag1_mask, unsigned long long diag2_mask,
                       vector<int>& queens, vector<vector<string>>& result) 
{
    // 检查是否满足结束条件
    if (row == n) {
        // 生成棋盘的字符串表示
            vector<string> board;
            for (int i = 0; i < n; i++) {
                string row_str(n, '.'); // 初始化一行，全部为'.'
                row_str[queens[i]] = 'Q'; // 在皇后的位置放置'Q'
                board.push_back(row_str); // 将这一行添加到棋盘表示中
            }
            result.push_back(board); // 将整个棋盘添加到结果中

            return;
    }

   
 // 遍历选择列表
    for (int col = 0; col < n; col++) {

        if ((cols_mask & (1ULL << col)) ||
                (diag1_mask & (1ULL << d1)) ||
                (diag2_mask & (1ULL << d2))) {
                continue; // 如果不安全，跳过这一列
            }




        // 添加当前选项到路径

        路径.push_back(i);



        // 进行递归
        backtrack(路径, 更新的选择列表);



        // 回溯，移除当前选项
        路径.pop_back();
    }
}

in this special code :

if ((cols_mask & (1ULL << col)) ||
                (diag1_mask & (1ULL << d1)) ||
                (diag2_mask & (1ULL << d2))) {
                continue; // 如果不安全，跳过这一列
            }

1ULL meas 1 unsigned long long,  << means move 1 step to the left.

diag_mask is an integer, for example:

if col == 2, in binary system is 10;  1ULL << 2 is 4, in binary system is 100

see, in binary system, int 1 moves one step left.

then put the queen

void backtrack_bit(int n, int row, unsigned long long cols_mask,
                       unsigned long long diag1_mask, unsigned long long diag2_mask,
                       vector<int>& queens, vector<vector<string>>& result) 
{
    // 检查是否满足结束条件
    if (row == n) {
        // 生成棋盘的字符串表示
            vector<string> board;
            for (int i = 0; i < n; i++) {
                string row_str(n, '.'); // 初始化一行，全部为'.'
                row_str[queens[i]] = 'Q'; // 在皇后的位置放置'Q'
                board.push_back(row_str); // 将这一行添加到棋盘表示中
            }
            result.push_back(board); // 将整个棋盘添加到结果中

            return;
    }

   
 // 遍历选择列表
    for (int col = 0; col < n; col++) {

        if ((cols_mask & (1ULL << col)) ||
                (diag1_mask & (1ULL << d1)) ||
                (diag2_mask & (1ULL << d2))) {
                continue; // 如果不安全，跳过这一列
            }

 // 在当前位置放置皇后
            queens.push_back(col);





        // 进行递归
        backtrack(路径, 更新的选择列表);



        // 回溯，移除当前选项
        路径.pop_back();
    }
}

and move to the next row:

void backtrack_bit(int n, int row, unsigned long long cols_mask,
                       unsigned long long diag1_mask, unsigned long long diag2_mask,
                       vector<int>& queens, vector<vector<string>>& result) 
{
    // 检查是否满足结束条件
    if (row == n) {
        // 生成棋盘的字符串表示
            vector<string> board;
            for (int i = 0; i < n; i++) {
                string row_str(n, '.'); // 初始化一行，全部为'.'
                row_str[queens[i]] = 'Q'; // 在皇后的位置放置'Q'
                board.push_back(row_str); // 将这一行添加到棋盘表示中
            }
            result.push_back(board); // 将整个棋盘添加到结果中

            return;
    }

   
 // 遍历选择列表
    for (int col = 0; col < n; col++) {

        if ((cols_mask & (1ULL << col)) ||
                (diag1_mask & (1ULL << d1)) ||
                (diag2_mask & (1ULL << d2))) {
                continue; // 如果不安全，跳过这一列
            }

 // 在当前位置放置皇后
            queens.push_back(col);





        // 递归到下一行
            backtrack_bit(n, row + 1, cols_mask | (1ULL << col),
                          diag1_mask | (1ULL << d1), diag2_mask | (1ULL << d2),
                          queens, result);


        // 回溯，移除当前选项
        路径.pop_back();
    }
}

and next

void backtrack_bit(int n, int row, unsigned long long cols_mask,
                       unsigned long long diag1_mask, unsigned long long diag2_mask,
                       vector<int>& queens, vector<vector<string>>& result) 
{
    // 检查是否满足结束条件
    if (row == n) {
        // 生成棋盘的字符串表示
            vector<string> board;
            for (int i = 0; i < n; i++) {
                string row_str(n, '.'); // 初始化一行，全部为'.'
                row_str[queens[i]] = 'Q'; // 在皇后的位置放置'Q'
                board.push_back(row_str); // 将这一行添加到棋盘表示中
            }
            result.push_back(board); // 将整个棋盘添加到结果中

            return;
    }

   
 // 遍历选择列表
    for (int col = 0; col < n; col++) {

        if ((cols_mask & (1ULL << col)) ||
                (diag1_mask & (1ULL << d1)) ||
                (diag2_mask & (1ULL << d2))) {
                continue; // 如果不安全，跳过这一列
            }

 // 在当前位置放置皇后
            queens.push_back(col);





        // 递归到下一行
            backtrack_bit(n, row + 1, cols_mask | (1ULL << col),
                          diag1_mask | (1ULL << d1), diag2_mask | (1ULL << d2),
                          queens, result);


        // 回溯，移除当前皇后
            queens.pop_back();
    }
}

dont forget to initialize at the very beginning:

class Solution {
public:
    // 主函数，接收一个整数n，表示棋盘的大小
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result; // 用于存储所有可能的解
        vector<int> queens; // 用于存储当前放置皇后的列位置
        // 从第0行开始回溯
        backtrack_bit(n, 0, 0, 0, 0, queens, result);
        return result; // 返回所有可能的解
    }

private:
    // 回溯函数，参数包括棋盘大小n，当前行row，以及三个掩码
    void backtrack_bit(int n, int row, unsigned long long cols_mask,
                       unsigned long long diag1_mask, unsigned long long diag2_mask,
                       vector<int>& queens, vector<vector<string>>& result) {
        // 如果到达最后一行，说明找到了一个解
        if (row == n) {
            // 生成棋盘的字符串表示
            vector<string> board;
            for (int i = 0; i < n; i++) {
                string row_str(n, '.'); // 初始化一行，全部为'.'
                row_str[queens[i]] = 'Q'; // 在皇后的位置放置'Q'
                board.push_back(row_str); // 将这一行添加到棋盘表示中
            }
            result.push_back(board); // 将整个棋盘添加到结果中
            return;
        }
        // 尝试在当前行的每一列放置皇后
        for (int col = 0; col < n; col++) {
            int d1 = row - col + (n - 1); // 对角线1的索引
            int d2 = row + col; // 对角线2的索引
            // 检查当前位置是否安全
            if ((cols_mask & (1ULL << col)) ||
                (diag1_mask & (1ULL << d1)) ||
                (diag2_mask & (1ULL << d2))) {
                continue; // 如果不安全，跳过这一列
            }
            // 在当前位置放置皇后
            queens.push_back(col);
            // 递归到下一行
            backtrack_bit(n, row + 1, cols_mask | (1ULL << col),
                          diag1_mask | (1ULL << d1), diag2_mask | (1ULL << d2),
                          queens, result);
            // 回溯，移除当前皇后
            queens.pop_back();
        }
    }
};

and of course it works:

unsigned longlong can be replaced as unsigned long, to save the storge.

class Solution {
public:
    // 主函数，接收一个整数n，表示棋盘的大小
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result; // 用于存储所有可能的解
        vector<int> queens; // 用于存储当前放置皇后的列位置
        // 从第0行开始回溯
        backtrack_bit(n, 0, 0, 0, 0, queens, result);
        return result; // 返回所有可能的解
    }

private:
    // 回溯函数，参数包括棋盘大小n，当前行row，以及三个掩码
    void backtrack_bit(int n, int row, unsigned long cols_mask,
                       unsigned long diag1_mask, unsigned long diag2_mask,
                       vector<int>& queens, vector<vector<string>>& result) {
        // 如果到达最后一行，说明找到了一个解
        if (row == n) {
            // 生成棋盘的字符串表示
            vector<string> board;
            for (int i = 0; i < n; i++) {
                string row_str(n, '.'); // 初始化一行，全部为'.'
                row_str[queens[i]] = 'Q'; // 在皇后的位置放置'Q'
                board.push_back(row_str); // 将这一行添加到棋盘表示中
            }
            result.push_back(board); // 将整个棋盘添加到结果中
            return;
        }
        // 尝试在当前行的每一列放置皇后
        for (int col = 0; col < n; col++) {
            int d1 = row - col + (n - 1); // 对角线1的索引
            int d2 = row + col; // 对角线2的索引
            // 检查当前位置是否安全
            if ((cols_mask & (1UL << col)) ||
                (diag1_mask & (1UL << d1)) ||
                (diag2_mask & (1UL << d2))) {
                continue; // 如果不安全，跳过这一列
            }
            // 在当前位置放置皇后
            queens.push_back(col);
            // 递归到下一行
            backtrack_bit(n, row + 1, cols_mask | (1UL << col),
                          diag1_mask | (1UL << d1), diag2_mask | (1UL << d2),
                          queens, result);
            // 回溯，移除当前皇后
            queens.pop_back();
        }
    }
};

 and here is the magic:

 consume memory ranges from 11.96 to 12.15. 

reverse upgrading, sad.

anyway 

wish me have a good weekend.

标签：int,mask,困难,unsigned,long,vector,数组,皇后,row
From： https://blog.csdn.net/ElseWhereR/article/details/144280715

相关文章

  • leetcode第4题 如何求出两个有序数组的中位数
    leetcode原题大意，给定两个升序排列的有序数组，例如nums1=[1,2],nums2=[3,4]那么，这两个有序数组的所有数字的中位数为(2+3)/2=1.5，现在要求以O(log(m+n))的时间复杂度。funcfindMedianSortedArrays(nums1[]int,nums2[]int)float64{ length:=len(nums1)+len(nums2) ......
  • C语言实验 二维数组
    时间：2024.12.6一、实验7-1矩阵运算代码 #include<stdio.h>intmain(){inta[20][20]={0};intn,i,j;intsum=0;scanf("%d",&n);for(i=0;i<n;i++){for(j=0;j<n;j++){scanf("%d",&a[i][j])......
  • 20241205：3001. 捕获黑皇后需要的最少移动次数
    现有一个下标从 1 开始的 8x8 棋盘，上面有 3 枚棋子。给你 6 个整数 a 、b 、c 、d 、e 和 f ，其中：(a,b) 表示白色车的位置。(c,d) 表示白色象的位置。(e,f) 表示黑皇后的位置。假定你只能移动白色棋子，返回捕获黑皇后所需的最少移动次数。......
  • 11-数组
    11-数组一、数组的定义一组相同类型元素的集合，并且使用英文的,（逗号）隔开，这就是数组的创建及初始化。#define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>intmain(){ /*10个整型：1~10*/ intarr[10]={1,2,3,4,5,6,7,8,9,10}; /*不完全初始化，剩余的......
  • 05.数组概述
    Java内存堆​ 存放所有new出来的对象和数组​ 可以被所有的线程共享，不会存放别的对象引用栈​ 存放基本变量类型(会包含这个基本类型的具体数值)​ 引用对象的变量(会存放这个引用在堆里面的具体地址)方法区​ 可以被所有的线程共享​ 包含了所有的class和static变量数......
  • [面试题]在一个无序数组中，找到数字满足 该数字大于下标小于该数字的任何数 和 小于下
    即找出数组中左边比该数字小右边比该数字大的数思想：遍历一次数组，动态记录访问该下标时的最大值（正序）同理，可以记录访问该下标时的最小值（倒序）得出结论：两个数组相同的时候满足题目所给条件时间复杂度：O(sN)s为常数级若有数据可以hack掉，请在评论区告诉我TT#include<iostream......
  • 力扣 LeetCode 51. N皇后（Day14：回溯算法）
    解题思路：每次进入backtracking都表示进入下一行每个backtracking中处理当前行的各个列，看各列是否合法isValid中因为是一行一行向下遍历的，所以对应的当前行一定满足条件，没有放置过其他皇后，只需要看对应的列是否满足即可是否符合需要看左上45°和右上45°，之所以是往上看，......
  • hot100-一刷-05普通数组(共5道题)
    53.最大子数组和题目链接题目描述代码实现分析：贪心：只要当前累加的值≥0，就是对整个结果是有贡献的，但是一旦＜0，就拖累了整体结果。sum就是用来计算某一段上的局部总和。ans用来计算最终答案，取每一段里最大的。sum一旦小于0，则需要清空这一段。动态规划：代码：//贪心classSo......
  • 来学习typescript 吧！ --4 数组类型
    1.类型[]letarr1:number[]=[1,2,3]letarr2:string[]=['a','b','c']letarr3:(number|string)[]=[1,'a',2,'b'] 2.Array<类型>数组泛型letarr4:Array<number>=[1,2,3]letarr5:Array&l......
  • vue中json对象数组求最大、最小、合计方法
    可以使用Array.reduce()方法来求最大、最小、合计值。示例代码如下：//假设有以下json对象数组letarr=[{name:'tina',score:90},{name:'tom',score:80},{name:'john',score:70},{name:'jane',score:85}]//求最高分letmaxScor......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99