On the search for nice problems to solve using my computer and our favorite programming language, I came across an old familiar problem. The placing of 8 queens on the chessboard.
So I decided to have my take and solve this using some language specific features that Ren-C has to offer.<\/p>\n\n\n\n
; REN-C solution to the N Queens problem\n;\n; Place all N queens on the NxN chessboard where every queen is to be placed \n; on a field that is not taken nor covered by any of the other queens.\n;\n; We know the solutions are not symmetrical themselves but the solutions can be\n; mirror images of other solutions or turned solutions.\n\n; This solution works as follows\n; By symmetry we only need to test the first half of the row or column with\n; the first queen. On an odd sized board we only cannot double the number of\n; results for the middle position.\n\n; We do not know or even care if we work horizontally or vertically and even if we are\n; starting at the first or last row or column is irrelevant.\n\n; We start with adding our first queen to the board. This is a number in a\n; solution block. The we go to the next level and determine the free choices\n; for our next queen. This is a collection of all fields minus the ones other\n; queens cover. This propagates through all rows \/ columns. At the end we\n; reach an empty set so no solution or a set of solutions.\n\n; This global variable is a quick and dirty fix.\nnumber-of-solutions: 0\n\nreset-number-of-solutions: does [\n number-of-solutions: 0\n]\n\nadd-one-to-number-of-solutions: does [\n number-of-solutions: number-of-solutions + 1\n]\n\nget-number-of-solutions: does [\n number-of-solutions\n]\n\n; This variable is to signal that results should not be duplicated for\n; this value.\nodd-symmetry-limit: 0\n\nreset-symmetry-limit: does [\n odd-symmetry-limit: 0\n]\n\nadd-to-symmetry-limit: does [\n odd-symmetry-limit: odd-symmetry-limit + 1\n]\n\n;\nlogic-countonly: 0\n\nset-countonly-true: does [\n logic-countonly: 1\n]\n\nset-countonly-false: does [\n logic-countonly: 0\n]\n\n; Function to print the board for a solution\n\nprint-board: function [n [integer!]\n board-values [block!]\n][\n a: copy \"\"\n for-each b board-values [\n repeat t b - 1 [ append a \". \"]\n append a \"Q \"\n repeat t n - b [ append a \". \"]\n append a newline\n ]\n print a\n]\n\n; Function for recursion\nadd-queen: function [n [integer!]\n solution [block!]\n free-places [block!]\n][\n ; Determine the free choices for this queen\n forbidden-places: copy []\n can-see: 1\n rsolution: reverse copy solution\n for-each sol rsolution [\n append forbidden-places sol\n append forbidden-places sol + can-see\n append forbidden-places sol - can-see ; too lazy to check for out of bounds\n can-see: can-see + 1\n ]\n free-choices: exclude free-places forbidden-places\n if not empty? free-choices [\n either n = 1 [\n ; now check for a solution, no more recursion possible\n for-each place free-choices [\n append solution place\n if logic-countonly = 0 [print-board length-of solution solution]\n add-one-to-number-of-solutions\n if any [odd-symmetry-limit > first solution\n odd-symmetry-limit = 0]\n [\n if logic-countonly = 0 [print-board length-of solution reverse copy solution]\n add-one-to-number-of-solutions\n ]\n clear skip solution ((length-of solution) - 1)\n ]\n ][\n for-each place free-choices [\n append solution place\n add-queen n - 1 solution free-places\n clear skip solution ((length-of solution) - 1)\n ]\n ]\n ]\n]\n\n; Function for main solution\n\nsolve-n-queens: function [\n n [integer!] \"The number queens to place on the board of size nxn\"\n \/countonly \"Only print the number of solutions found\"\n][\n ; We need to know this within our recursive function\n either \"\/countonly\" = mold countonly [\n set-countonly-true\n ][\n set-countonly-false\n ]\n\n ; make a basic block of the row \/ column numbers\n places-block: copy []\n count-up i n [append places-block i]\n\n reset-number-of-solutions\n\n ; We need only do half of the first row \/ column for reasons of symmetry\n half: either odd? n [(n + 1) \/ 2][n \/ 2]\n reset-symmetry-limit\n if odd? n [\n loop half [add-to-symmetry-limit]\n ]\n\n either n > 1 [\n count-up first-queen half [\n solution: copy []\n append solution first-queen\n\n add-queen n - 1 solution places-block\n\n clear solution ; this is okay because we are in the outermost loop here\n ]\n ][\n add-one-to-number-of-solutions\n print-board n [1]\n ]\n\n ; print the number of solutions now\n print spaced [\"Total number of solutions for n =\" n \"is\" get-number-of-solutions]\n]\n<\/code><\/pre>\n\n\n\nAgreed there is some room for improvement \ud83d\ude42<\/p>\n\n\n\n
Anyway it works and relatively fast also. If we want to know how slow REN-C is on my machine<\/p>\n\n\n\n
delta-time [solve-n-queens\/countonly 5]\nTotal number of solutions for n = 5 is 10\n== 0:00:00.00145<\/code><\/pre>\n\n\n\ndelta-time [solve-n-queens\/countonly 8]\nTotal number of solutions for n = 8 is 92\n== 0:00:00.041275<\/code><\/pre>\n\n\n\ndelta-time [solve-n-queens\/countonly 12]\nTotal number of solutions for n = 12 is 14200\n== 0:00:08.126828<\/code><\/pre>\n\n\n\ndelta-time [solve-n-queens\/countonly 14]\nTotal number of solutions for n = 14 is 365596\n== 0:06:21.679977<\/code><\/pre>\n\n\n\nI don’t think that is bad for an interpreted language. And I like the way this solving method works, I consider it to be rather intuitively.<\/p>\n\n\n\n
Agree or disagree?<\/p>\n\n\n\n
One thing, do not expect this code to just work out of the box today! Ren-C is subject to many changes lately especially the working of refinement has been changed a little. But the main idea of the solving method still holds.<\/p>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
On the search for nice problems to solve using my computer and our favorite programming language, I came across an old familiar problem. The placing of 8 queens on the chessboard. So I decided to have my take and solve … Continue reading