| layout | title | redirect_from | date | tags | comments | dblog_post_id | |
|---|---|---|---|---|---|---|---|
post |
N queens puzzle: a scheme and x86 assembly solution |
/n-queens-puzzle-a-scheme-and-x86-assembly-solution/ |
2009-09-22 12:00:00 -0700 |
|
true |
52 |
The eight queens puzzle is the problem of putting eight chess queens on an 8×8 chessboard such that none of them is able to capture any other using the standard chess queen's moves. The queens must be placed in such a way that no two queens would be able to attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens puzzle of placing n queens on an n_×_n chessboard, where solutions exist only for n = 1 or n ≥ 4.
https://en.wikipedia.org/wiki/Eight_queens_puzzle
I dug up some old code that implemented the puzzle solution(s) in scheme and x86 assembly.
- Scheme Source
- x86 Assembly Source, Base Algorithm
- x86 Assembly Source, All Optimizations
- x86 Executable
I remember trying to get solutions for large (over 10) boards in 1995 and my PC was a little slow. Things are very different today. Here's an example of solution number 128570 for a board of 20.
(128570) 11 1 3 5 12 2 15 13 18 14 4 6 19 16 10 7 20 8 17 9