Ismael-VC · September 18, 2018 18:37 · Ismael-VC · Dec 12, 2015
diff --git a/eight_queens_puzzle.jl b/eight_queens_puzzle.jl
 #!/usr/bin/env julia

 #=
 The following code is licensed under the MIT "Expat" License:
 
 Copyright (c) 2015: Ismael Venegas Castelló.
  
 Permission is hereby granted, free of charge, to any person obtaining a copy
 of this software and associated documentation files (the "Software"), to deal
 in the Software without restriction, including without limitation the rights
 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 copies of the Software, and to permit persons to whom the Software is
 furnished to do so, subject to the following conditions:
  
 The above copyright notice and this permission notice shall be included in all
 copies or substantial portions of the Software.
  
 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 SOFTWARE.
 =#


 __precompile__(true)


 """
 # EightQueensPuzzle

 Ported to **Julia** from examples in several languages from
 here: https://hbfs.wordpress.com/2009/11/10/is-python-slow
 """
 module EightQueensPuzzle

 export main


 type Board
    cols::Int
    nodes::Int
    diag45::Int
    diag135::Int
    solutions::Int

    Board() = new(0, 0, 0, 0, 0)
 end


 "Marks occupancy."
 function mark!(b::Board, k::Int, j::Int)
    b.cols    $= (1 << j)
    b.diag135 $= (1 << (j+k))
    b.diag45  $= (1 << (32+j-k))
 end


 "Tests if a square is menaced."
 function test(b::Board, k::Int, j::Int)
    b.cols    & (1 << j)        +
    b.diag135 & (1 << (j+k))    +
    b.diag45  & (1 << (32+j-k)) == 0
 end


 "Backtracking solver."
 function solve!(b::Board, niv::Int, dx::Int)
    if niv > 0
        for i in 0:dx-1
            if test(b, niv, i) == true
                mark!(b, niv, i)
                solve!(b, niv-1, dx)
                mark!(b, niv, i)
            end
        end
    else
        for i in 0:dx-1
            if test(b, 0, i) == true
                b.solutions += 1
            end
        end
    end
    b.nodes += 1
    b.solutions
 end


 "C/C++-style `main` function."
 function main()
    for n = 1:17
        gc()
        b = Board()
        @show n
        print("elapsed:")
        solutions = @time solve!(b, n-1, n)
        @show solutions
        println()
    end
 end


 end


 using  EightQueensPuzzle


 main()
	#!/usr/bin/env julia

	#=
	The following code is licensed under the MIT "Expat" License:

	Copyright (c) 2015: Ismael Venegas Castelló.

	Permission is hereby granted, free of charge, to any person obtaining a copy
	of this software and associated documentation files (the "Software"), to deal
	in the Software without restriction, including without limitation the rights
	to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
	copies of the Software, and to permit persons to whom the Software is
	furnished to do so, subject to the following conditions:

	The above copyright notice and this permission notice shall be included in all
	copies or substantial portions of the Software.

	THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
	IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
	FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
	AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
	LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
	OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
	SOFTWARE.
	=#


	__precompile__(true)


	"""
	# EightQueensPuzzle

	Ported to Julia from examples in several languages from
	here: https://hbfs.wordpress.com/2009/11/10/is-python-slow
	"""
	module EightQueensPuzzle

	export main


	type Board
	cols::Int
	nodes::Int
	diag45::Int
	diag135::Int
	solutions::Int

	Board() = new(0, 0, 0, 0, 0)
	end


	"Marks occupancy."
	function mark!(b::Board, k::Int, j::Int)
	b.cols $= (1 << j)
	b.diag135 $= (1 << (j+k))
	b.diag45 $= (1 << (32+j-k))
	end


	"Tests if a square is menaced."
	function test(b::Board, k::Int, j::Int)
	b.cols & (1 << j) +
	b.diag135 & (1 << (j+k)) +
	b.diag45 & (1 << (32+j-k)) == 0
	end


	"Backtracking solver."
	function solve!(b::Board, niv::Int, dx::Int)
	if niv > 0
	for i in 0:dx-1
	if test(b, niv, i) == true
	mark!(b, niv, i)
	solve!(b, niv-1, dx)
	mark!(b, niv, i)
	end
	end
	else
	for i in 0:dx-1
	if test(b, 0, i) == true
	b.solutions += 1
	end
	end
	end
	b.nodes += 1
	b.solutions
	end


	"C/C++-style `main` function."
	function main()
	for n = 1:17
	gc()
	b = Board()
	@show n
	print("elapsed:")
	solutions = @time solve!(b, n-1, n)
	@show solutions
	println()
	end
	end


	end


	using EightQueensPuzzle


	main()
Language	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
Julia	0.000001	0.000001	0.000001	0.000001	0.000003	0.000008	0.000028	0.000108	0.000463	0.002146	0.010646	0.057603	0.334600	2.055078	13.480449	97.192552	720.314676
C++	0.000000	0.000002	0.000003	0.000046	0.000005	0.000012	0.000036	0.000126	0.000569	0.002973	0.016647	0.080705	0.448602	2.830424	18.648028
C++-fixed	0.000000	0.000001	0.000001	0.000007	0.000005	0.000011	0.000033	0.000104	0.000500	0.002369	0.011468	0.065407	0.462506	2.765098	18.032639
C#	0.007315	0.007260	0.008356	0.007302	0.007864	0.007451	0.007421	0.008287	0.008452	0.012481	0.033548	0.154490	0.877194	5.444645	35.769138
Java	0.000001	0.000002	0.000002	0.000003	0.000005	0.000015	0.000049	0.000198	0.000895	0.004244	0.022947	0.128498	0.692349	4.457763	29.321677
Python	0.000012	0.000029	0.000054	0.000136	0.000424	0.001708	0.006078	0.026174	0.115218	0.546922	2.822554	15.405020	91.170068	581.983903	3762.739785
Python-2	0.000012	0.000028	0.000045	0.000109	0.000318	0.001275	0.004125	0.017448	0.077854	0.348823	1.701767	9.349661	55.532111	339.244132	2259.010794
Bash	0.003054	0.010938	0.006067	0.011355	0.026913	0.091869	0.347451	1.472102	6.483076	30.813085	163.061341	891.828031	5031.663741	31746.000000	209162.000000