Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Eight queens puzzle
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
==Sample program== The following program is a translation of [[Niklaus Wirth]]'s solution into the [[Python (programming language)|Python]] programming language, but does without the [[Array data type|index arithmetic]] found in the original and instead uses [[List (abstract data type)|lists]] to keep the program code as simple as possible. By using a [[coroutine]] in the form of a [[Generator (computer programming)|generator function]], both versions of the original can be unified to compute either one or all of the solutions. Only 15,720 possible queen placements are examined.<ref>{{cite book|last=Wirth |first=Niklaus |author-link=Niklaus Wirth |title=Algorithms + Data Structures = Programs |series=Prentice-Hall Series in Automatic Computation |publisher=Prentice-Hall |year=1976 |isbn=978-0-13-022418-7 |title-link=Algorithms + Data Structures = Programs |bibcode=1976adsp.book.....W}} p. 145</ref><ref>{{cite book |last=Wirth |first=Niklaus |date=2012 |orig-date=orig. 2004 |title=Algorithms and Data Structures |version=Oberon version with corrections and authorized modifications |url=https://informatika-21.ru/ADen/AD2012.pdf |chapter=The Eight Queens Problem |pages=114β118}}</ref> <syntaxhighlight lang="python"> def queens(n: int, i: int, a: list, b: list, c: list): if i < n: for j in range(n): if j not in a and i + j not in b and i - j not in c: yield from queens(n, i + 1, a + [j], b + [i + j], c + [i - j]) else: yield a for solution in queens(8, 0, [], [], []): print(solution) </syntaxhighlight>The following program is an implementation of [[Donald Knuth]]'s informal description of the solution on Page 31, Section 7.2.2 ''Backtrack Programming'' from [[The Art of Computer Programming]], Volume 4B into the Python programming language.<ref>{{Cite book |last=Knuth |first=Donald Ervin |title=The art of computer programming. volume 4B part 2: Combinatorial algorithms |date=2023 |publisher=Addison-Wesley |isbn=978-0-201-03806-4 |location=Boston Munich}}</ref> <syntaxhighlight lang="python3"> def property(perm: list): for k in range(0, len(perm)): for j in range(0, len(perm)): if j < k: if perm[k] == perm[j]: return False elif abs(perm[k] - perm[j]) == k - j: return False return True def extend(perm: list, n: int): new_perm = [] for p in perm: for i in range(0, n): new_perm.append(p + [i]) return new_perm def n_queens(n: int): domain = list(range(0, n)) perm = [[]] for i in range(n): new_perm = list(filter(property, extend(perm, n))) perm = new_perm return len(perm) </syntaxhighlight>
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)