Shulou(Shulou.com)05/31 Report--

This article mainly introduces "how to use MySQL to solve the eight queens problem". In the daily operation, I believe many people have doubts about how to use MySQL to solve the eight queens problem. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the doubts about how to use MySQL to solve the eight queens problem. Next, please follow the editor to study!

Preface

In new companies, hundreds of lines of SQL code are often encountered, which are mainly used for data acquisition and processing. Because the company uses Ali's ADB, it wants to put the logic of simple processing between data on ADB. It took me a while to get used to it. After all, my previous experience was to simplify SQL as much as possible, and then process the acquired data through code, so my SQL skills are not strong.

SQL is not strong, so learn it, so in the process of learning, I suddenly wonder if I can solve the method problem through MySQL. There are many holes in this process, but the process of exploration is still very interesting.

Most of the details or other knowledge of the SQL language will be given in the final reference section, which is about learning SQL grammar and solving specific problems.

Eight queens

The queen in chess can move horizontally, longitudinally and diagonally. The so-called problem of eight queens is how to put eight queens on a 8x8 chessboard, so that any two queens are not in the same horizontal line, vertical line, and diagonal direction. As shown in the following figure, if a queen is placed in the (1) position of the chessboard, then the green part of the picture cannot place other queens.

The question is: how many ways can 8 queens play on 8x8's chessboard?

This is a classic backtracking algorithm problem, the essence of backtracking algorithm is to traverse all the situations through recursion, and finally get all the situations.

The key to the backtracking algorithm, as its name is, is to do the backtracking operation. For example, a queen tries eight squares in a row, but all of them cannot meet the conditions, which means that there is something wrong with the position of the queen before. We need to go back to a previous operation and modify that operation, such as placing the queen of that operation in a new location.

The backtracking algorithm is very suitable to be implemented by recursion, and the essence of recursion is the unstack and entry of the function frame, that is, the entry and exit of the stack satisfies the characteristics of backtracking.

Differences in SQL

When you are smart, when you encounter the problem of realizing the eight queens through MySQL, you will certainly Google the previous solutions. Unfortunately, I did not find the reference answer, and the only answer related to SQL is achieved with PL/SQL.

SQL is actually a neighborhood language (DDL), which has its own standard, but different databases have different implementations of this standard, which is similar to the flow device's own implementation of the Web standard, which makes the previous SQL of different databases not universal.

PL/SQL is the Oracle database implementation of the SQL standard, it extends the standard SQL, so that it has the ability of procedural programming language, in PL/SQL, you can easily achieve array, loop, judgment and other operations.

MySQL also has its own implementation of the SQL standard. In fact, SQL implemented by MySQL is much weaker than PL/SQL, and it is better at manipulating data than procedural programming.

There are several reasons why I chose MySQL:

1. At present, no one has been found to solve the eight queens problem through MySQL, and there is no reference answer. 2.MySQL 's SQL language is a bit challenging because of its weak support for process. 3.MySQL is a database used by most programmers, which we are familiar with (it is easy to understand the B I installed).

Because no one has done it, and I am not familiar with the syntax related to MySQL process control, I am not sure at first, but the process of solving the problem is interesting.

For the convenience of description, the SQL in MySQL is represented by SQL and the database is represented by MySQL.

In addition, different versions of MySQL may have different SQL implementations. The MySQL version used in this article is 8.0.19. You can check your own MySQL version through select version ().

Python problem solving

My idea of solving the problem is very simple. I use a list with a length of 8 to store the position of the queen. specifically, the subscript of the list indicates the row of the current queen, and the corresponding value of the subscript indicates the column of the queen on the line. In this way, the rows of different queens will not be duplicated, so you only need to judge whether the columns and slanted edges will conflict.

The specific Python code is as follows:

Num = 0 def is_ok (queen, row): for r in range (1, row): # Line r is in the same column as the Queen of Line row, conflict if queen [r] = = queen [row]: return False t = abs (queen [r]-queen [row]) # Line r is on the same slash as the Queen of Line row Conflict # if the row difference of the position of the two queens is the same as the column difference Then on the same slash if t = = abs (r-row): return False return True def find (queen, row): global num # try each row from the first column to the eighth column for col in range (1, (8x1): queen [row] = col # to determine whether the condition if is_ok (queen) Row): if row = = 8: num + = 1 return # if you don't get to line 8 Then continue the recursive find (queen, row + 1) # Python list subscript starting from 0, in order to start with 1, so queen = [0L1 result is 2 3 4 4 5 6 7 8] find (queen, 1) print ('result is', num)

Without comments, the code is actually very short.

Of course, there is a better solution, you can take a look, I read the Python version of the code, I feel that there is too much code.

Python version of the solution is available, the next thing to do is to translate it into the form of SQL, this process has a lot of problems.

What if there is no array?

In SQL implemented by MySQL, there are no variables of container type, that is, arrays and dictionaries are not supported at the language level.

Through Google search, it is found that most people use strings to simulate arrays, and strings are divided by commas, and then find and update elements in strings through character-related methods, as shown in the article given in the reference section.

After testing, I found that this method is not easy to use, on my MySQL, the run will report syntax errors.

After thinking about it briefly, I decided to use a temporary table to solve the array.

Temporary table is mainly used to temporarily save some data. Its characteristic is that it is only visible to the user who created the table. At the end of the session, MySQL automatically deletes the temporary table. Its advantage is that both table creation and table deletion consume very little data, and its creation syntax is as follows:

CREATE TEMPORARY TABLE tbl_name (...)

That is, the TEMPORARY keyword can be added to the normal table statement, and the specific sentences are as follows.

-- if the temporary table exists, delete the temporary table DROP TABLE IF EXISTS queen;-- the subscript of the id mock list, and the value CREATE TEMPORARY TABLE queen (id INT, location INT) in the location list

Looking back at the code of Python, you can see that the corresponding value is set by default.

Queen = [0re1, 2, 3, 4, 5, 6, 7, 8]

In order to mimic this effect, there should also be default values in the temporary table, because the subscript of the table in MySQL starts from 1, so you only need to create 8 rows. Here, I define a stored procedure to initialize the values in the temporary table. The code is as follows:

-- delete the PROCEDURE (procedure) DROP PROCEDURE IF EXISTS init_queen; if the stored procedure exists-- define the procedure CREATE PROCEDURE init_queen () BEGIN-- declare the variable DECLARE i int DEFAULT 1;-- Loop WHILE I

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.