Essay about N-Queens Recursive Algorithm with Multi-threading

1253 Words 6 Pages
Now we place the 3rd queen in the available column. Here again, we don’t have a place to put the fourth queen. So we back track to the first queen and change its position to the second column as shown in Fig.7 below.

Fig. 7 Placement of three queens

As, shown in the Fig. 8 below, for the 2nd queen we only have one place to put it on the chessboard.

Fig. 8 Placement of first queen with next column after backtracking
After placing the 2nd queen, the available options for next queen are shown below.

Fig. 9 Placement of two queens with different positions

Again, after placing third queen, the available option is as shown in Fig. 10 below.

Fig. 10 Placement of three queens with varying positions

…show more content…
Because of the recursive and backtracking nature of this algorithm, the execution time increases gradually as the number of queens increase.
In order to reduce the execution time we need to parallelize the problem in such a way that the original problem is divided into sub-problems. These individual sub-problems can be executed in parallel using multiple threads.

2.2. Proposed Multi-threading approach

2.2.1 Time Slice for threads more than cores

Allow me to explain the basics of threading first. A thread is essentially a single sequence of instructions[10]. A process contains one or more threads. It is nothing but an instance of the program. Therefore, threads and cores are directly related to each other. For the operating system(OS), a thread is a unit of work which can be scheduled to execute on a single core[10]. Time division multiplexing is a type of technique which generally used by the operating system to make a single core able to run multiple threads. The OS sets up a timer which interrupts the system at a fixed interval[10]. A single interval is known as a time slice. At the occurrence of this interrupt, the OS selects the next thread to be executed using its scheduling mechanism. The state of the currently executing thread is then saved and then control passed to the next thread. The execution of the current instruction resumes from the state of this new thread. This process is known as context switching. Therefore, on a multiple

Related Documents