Created
December 18, 2015 19:39
-
-
Save Ismael-VC/941fc35622ca298bf69c to your computer and use it in GitHub Desktop.
NQueens in Julia
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"cells": [ | |
{ | |
"cell_type": "code", | |
"execution_count": 2, | |
"metadata": { | |
"collapsed": false | |
}, | |
"outputs": [ | |
{ | |
"data": { | |
"text/plain": [ | |
"92" | |
] | |
}, | |
"execution_count": 2, | |
"metadata": {}, | |
"output_type": "execute_result" | |
} | |
], | |
"source": [ | |
"module NQueens\n", | |
"\n", | |
"export solve\n", | |
"\n", | |
"\n", | |
"type Board\n", | |
" cols :: Int\n", | |
" nodes :: Int\n", | |
" diag45 :: Int\n", | |
" diag135 :: Int\n", | |
" solutions :: Int\n", | |
"\n", | |
" Board() = new(0, 0, 0, 0, 0)\n", | |
"end\n", | |
"\n", | |
"\"Marks occupancy.\"\n", | |
"function mark!(b::Board, k::Int, j::Int)\n", | |
" b.cols $= (1 << j)\n", | |
" b.diag135 $= (1 << (j + k))\n", | |
" b.diag45 $= (1 << (32 + j - k))\n", | |
"end\n", | |
"\n", | |
"\"Tests if a square is menaced.\"\n", | |
"function test(b::Board, k::Int, j::Int)\n", | |
" b.cols & (1 << j) +\n", | |
" b.diag135 & (1 << (j + k)) +\n", | |
" b.diag45 & (1 << (32 + j - k)) == 0\n", | |
"end\n", | |
"\n", | |
"\"Backtracking solver.\"\n", | |
"function solve!(b::Board, niv::Int, dx::Int)\n", | |
" if niv > 0\n", | |
" for i in 0:dx - 1\n", | |
" if test(b, niv, i) == true\n", | |
" mark!(b, niv, i)\n", | |
" solve!(b, niv - 1, dx)\n", | |
" mark!(b, niv, i)\n", | |
" end\n", | |
" end\n", | |
" else\n", | |
" for i in 0:dx - 1\n", | |
" if test(b, 0, i) == true\n", | |
" b.solutions += 1\n", | |
" end\n", | |
" end\n", | |
" end\n", | |
" b.nodes += 1\n", | |
" b.solutions\n", | |
"end\n", | |
"\n", | |
"solve(n::Int) = solve!(Board(), n -1, n)\n", | |
"\n", | |
"\n", | |
"end\n", | |
"\n", | |
"\n", | |
"using NQueens\n", | |
"\n", | |
"\n", | |
"solve(8)" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 9, | |
"metadata": { | |
"collapsed": false | |
}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"n = 1\n", | |
"elapsed time: 3.574e-6 seconds\n", | |
"solutions = 1\n", | |
"\n", | |
"n = 2\n", | |
"elapsed time: 2.383e-6 seconds\n", | |
"solutions = 0\n", | |
"\n", | |
"n = 3\n", | |
"elapsed time: 3.024e-6 seconds\n", | |
"solutions = 0\n", | |
"\n", | |
"n = 4\n", | |
"elapsed time: 3.691e-6 seconds\n", | |
"solutions = 2\n", | |
"\n", | |
"n = 5\n", | |
"elapsed time: 4.51e-6 seconds\n", | |
"solutions = 10\n", | |
"\n", | |
"n = 6\n", | |
"elapsed time: 9.331e-6 seconds\n", | |
"solutions = 4\n", | |
"\n", | |
"n = 7\n", | |
"elapsed time: 2.9897e-5 seconds\n", | |
"solutions = 40\n", | |
"\n", | |
"n = 8\n", | |
"elapsed time: 0.000112309 seconds\n", | |
"solutions = 92\n", | |
"\n", | |
"n = 9\n", | |
"elapsed time: 0.000462868 seconds\n", | |
"solutions = 352\n", | |
"\n", | |
"n = 10\n", | |
"elapsed time: 0.002111329 seconds\n", | |
"solutions = 724\n", | |
"\n", | |
"n = 11\n", | |
"elapsed time: 0.01052219 seconds\n", | |
"solutions = 2680\n", | |
"\n", | |
"n = 12\n", | |
"elapsed time: 0.057378663 seconds\n", | |
"solutions = 14200\n", | |
"\n", | |
"n = 13\n", | |
"elapsed time: 0.330716909 seconds\n", | |
"solutions = 73712\n", | |
"\n", | |
"n = 14\n", | |
"elapsed time: 2.041111961 seconds\n", | |
"solutions = 365596\n", | |
"\n", | |
"n = 15\n", | |
"elapsed time: 13.423782691 seconds\n", | |
"solutions = 2279184\n", | |
"\n", | |
"n = 16\n", | |
"elapsed time: 97.125055795 seconds\n", | |
"solutions = 14772512\n", | |
"\n", | |
"n = 17\n", | |
"elapsed time: 712.622606898 seconds\n", | |
"solutions = 95815104\n", | |
"\n" | |
] | |
} | |
], | |
"source": [ | |
"function nqueens_test()\n", | |
" for n = 1:17\n", | |
" gc()\n", | |
" @show n\n", | |
" tic()\n", | |
" solutions = solve(n)\n", | |
" toc()\n", | |
" @show solutions\n", | |
" println()\n", | |
" end\n", | |
"end\n", | |
"\n", | |
"nqueens_test()" | |
] | |
} | |
], | |
"metadata": { | |
"kernelspec": { | |
"display_name": "Julia 0.5.0-dev", | |
"language": "julia", | |
"name": "julia-0.5" | |
}, | |
"language_info": { | |
"file_extension": ".jl", | |
"mimetype": "application/julia", | |
"name": "julia", | |
"version": "0.5.0" | |
} | |
}, | |
"nbformat": 4, | |
"nbformat_minor": 0 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment