Recursion/Backtracking - Revision history

Admin: /* 8 Queens Problem */

2017-03-12T21:42:56Z

8 Queens Problem

← Older revision		Revision as of 21:42, 12 March 2017
Line 21:		Line 21:
	Let's examine the 8 queens problem to see backtracking in action.		Let's examine the 8 queens problem to see backtracking in action.

			The 8 queens problem asks the following question: what are the possible configurations of placing 8 queens on a chessboard, such that no queen may attack any other queen?

			The 8 queens problem is essentially a chess version of the [https://en.wikipedia.org/wiki/Mexican_standoff Mexican standoff (Wikipedia)], in which no participants may retreat or proceed without exposing themselves to danger. In chess, the most heavily-armed piece is the Queen, so having 8 Queens on the chessboard is like having many heavily-armed individuals in a small space. Solutions to the 8 queens problem may be found by roving around a small neighborhood. The 8 queens problem seeks to find positions for each of the 8 queens (the gunfighters of chess) that result in a standoff.

			This problem may be solved using backtracking. If we imagine the problem space of deciding which squares to place queens onto, the problem space is enormous:

			<math>
			\frac{64!}{(64-8)!}
			</math>

			or, approximately 9 trillion different configurations. However, if we utilize information we know about the rules of chess, and about where queens have already been placed on the chessboard, thus ruling out certain squares, we can reduce the problem space substantially, closer to 80,000 possible solutions.

			Solution in Java: https://github.com/charlesreid1/hello-world/blob/master/java/NQueens.java

			Solution in Perl: https://github.com/charlesreid1/hello-world/blob/master/perl/8queens.pl

Admin at 21:34, 12 March 2017

2017-03-12T21:34:29Z

← Older revision		Revision as of 21:34, 12 March 2017
Line 20:		Line 20:

	Let's examine the 8 queens problem to see backtracking in action.		Let's examine the 8 queens problem to see backtracking in action.










			[[Category:Computer Science]]

Admin: Created page with "The idea behind backtracking is to use recursion to explore a problem. The recursive backtracking method follows a common generic template:

 explore(choices):     if(no..."

2017-03-12T10:33:21Z

Created page with "The idea behind backtracking is to use recursion to explore a problem. The recursive backtracking method follows a common generic template: <pre> explore(choices): if(no..."

New page

The idea behind backtracking is to use recursion to explore a problem.

The recursive backtracking method follows a common generic template:

<pre>
explore(choices):
if(no choices left):
check if this is a solution
if this is a solution:
save it
else:
make a choice
explore(remaining choices)
unmake choice
</pre>

=Examples=

==8 Queens Problem==

Let's examine the 8 queens problem to see backtracking in action.