| This program finds all the possible ways that N queens can | be placed on an NxN chessboard so that the queens cannot | capture one another -- that is, so that no rank, file or | diagonal is occupied by more than one queen. By default, | the program prints the first solution it finds. You can | use the -a option to print all solutions, or the -c option | just to count them. The program allows the chess board | to be from 1x1 (trivial case) to 100x100. Warning: the | larger the chess board, the longer it typically takes to | find each solution, even though there may be more of them. | This is a terrific example of the utility of recursion. The | algorithm uses recursion to drastically limit the number | of board positions that are tested. The program is able | to find all 8x8 queen solutions in a fraction of a second | (not counting print time). The code makes no attempt to | eliminate symmetrical solutions, so the number of solutions | reported will always be higher than the actual number of | distinct solutions.
The Forth QUEENS benchmark shows the quality of your compiler's integer code as compared to that of an optimizing "C" compiler. Results for a large number of C compilers on a variety of systems are available in the .tbl file.
This benchmark fits completely into even a quite small cache. The code is quite well suited to agressive register-based optimization. For the P54C iForth can't keep up with the pack, for the Athlon it's a brute-force win.
14 queens on a 14x14 board... ...there are 365596 solutions Run Time (sec) = 163.933
14 queens on a 14x14 board... ...there are 365596 solutions Run Time (sec) = 16.424
The QUEENS result puts iForth in the following company (queens.tbl):
<<<<<<<<<<<<<<<<<<<<<<<<<<<( queens -c 14 )>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> System OS, CPU/FPU CPU Run Time REF (MHz) (seconds) ### ----------------------- -------------- ----------- ----- --------- --- 001 Alphastation 500 5/333 DEC UNIX V4.0B DEC 21164 333 16.135 36 --- ---------------------------------------------------------------------- AMD Athlon Windows 2000 Athlon 900 16.424 --- ---------------------------------------------------------------------- 002 AlphaServer 8400 5/300 OSF/1 V3.2C DEC 21164 300 19.984 4 003 AMD K6 Windows 95 AMD K6 200 20.54 37 004 AMD K6 Linux 2.0.30 AMD K6 200 20.78 38 005 PowerPC 7300 BeOS 604e 200 21.805 39 006 SGI Indigo2 Irix 6.2 MIPS R10000 195 23.509 17 007 SGI Origin 200 Irix 6.4 MIPS R10000 180 24.800 40 008 Pentium P5-166 Windows 95 Pentium 166 25.480 27 009 SGI Indigo2 Irix 6.2 MIPS R10000 195 26.050 17 010 Pentium Pro Windows 95 Pentium P6 200 27.130 35 011 Dell XPS Pro 200n NT 3.51 Pentium P6 200 27.440 20 012 Dell Dimension P6-200 OS/2 Warp Pentium P6 200 27.460 10 013 SGI Origin 200 Irix 6.4 MIPS R10000 180 28.242 28 014 Sun Ultra 4000 (4 CPU) Solaris 2.5.1 UltraSPARC 167 28.582 22 015 SGI O2 Irix 6.3 MIPS R10000 175 30.500 25 016 Sun Ultra 1 Solaris 2.5 UltraSPARC 167 30.580 5 017 Brett Station ATX Linux 2.0.0 Pentium Pro 180 31.020 31 018 Pentium P5-133 Windows 95 Pentium P5 133 31.420 19 019 Pentium P5-133 MS DOS 6.22 Pentium P5 133 34.880 18 020 Pentium P5-133 MS DOS 6.22 Pentium P5 133 34.880 18 021 Mac PowerPC 604 MacOS 7.5.2 PowerPC 604 120 34.983 7 022 Pentium P5-120 Windows 95 Pentium P5 120 34.990 16 023 Mac PowerPC 604 MacOS 7.5.3 PowerPC 604 120 35.155 9 024 AMD K5-PR133 -------------- AMD-PR133 100 36.720 30 025 HP 9000/J210XC HP-UX 10.20 PA7200_2CPU 120 37.15 32 026 Sun Ultra 1 Solaris 2.5 UltraSPARC 143 37.450 5 027 Pentium P5-120 Windows 95 Pentium P5 120 38.720 16 028 Sun SPARCstation20/HS21 Solaris 2.4 HyperSPARC 125 38.800 3 029 SGI Indy Irix 6.2 MIPS R5000 150 40.845 28 030 SGI Challenge S Irix 6.2 MIPS R4400 200 41.501 26 031 Pentium P5-100 Windows 95 Pentium P5 100 41.640 14 032 Acorn RiscPC 610 RiscOS 3.7 SA-110 202 42.240 34 033 AMD5K86-P90 Windows 95 AMD5K86-P90 90 44.600 23 034 HP 9000/J210 HP-UX 10.01 PA-RISC 120 45.290 24 035 AMD5K86-P90 Windows 95 AMD5K86-P90 90 45.480 23 036 Escom P100 Win95/DOS Pentium 100 45.970 20 037 Pentium P5-100 Windows 95 Pentium P5 100 46.240 14 038 Pentium P5-100 Windows 95 Pentium P5 100 46.250 15 039 HP 9000/712 HP-UX 10.20 HP-PA7100LC 100 46.460 32 040 Gateway Pentium P5-90 Linux 1.1.95 Pentium 90 49.07 2 041 DATEL Pentium P5-90 MS DOS 6.22 Pentium 90 51.630 1 042 AMD 5x86-133 MS DOS 6.22 Am5x86-P75 133 55.110 21 043 Pentium P5-75 Windows 95 Pentium 75 56.680 12 044 Dell XPS P 200n No opt NT 3.51 Pentium P6 200 58.890 20 045 SGI Onyx Irix 6.2 MIPS R8000 75 60.485 29 046 Pentium P5-75 Windows 95 Pentium 75 62.340 11 047 IBM RS/6000 25E AIX 3.2.5 PPC601 66 63.04 33 048 Pentium P5-75 SCO UNIX5.0.0b Pentium 75 65.760 13 049 Sharp PC-3060 -------------- Cyrix 5x86 100 75.850 8 050 486DX4/100 Windows 95 80486DX4 100 76.400 14 051 486DX4/100 Windows 95 80486DX4 100 76.410 14 052 486DX4/100 Windows 95 AMD 486DX4 100 80.800 14 053 Sun SPARCsystem 600 SunOS 4.1.3 SuperSPARC 50 84.050 1 054 486DX4/100 Linux 1.2.10 80486DX4 100 88.170 6 055 Sun SPARCstation 2 SunOS 4.1.3 Weitek 80 95.380 1 056 Sun SPARCsystem 600 SunOS 4.1.3 SuperSPARC 50 101.870 1 057 Sun SPARCstation 10/41 SunOS 4.1.3 SuperSPARC 40 106.840 1 058 Escom 486 Win95/DOS 80486DX2 66 130.830 20 059 Escom P100 No opt Win95/DOS Pentium 100 151.320 20 --- ---------------------------------------------------------------------- P54C NT 4.0 Pentium 166 163.933 --- ---------------------------------------------------------------------- 060 IBM RS/6000 25E AIX 3.2.5 PPC601 66 182.44 33 061 Vega 80486DX/33 MS DOS 5.0 80486DX 33 230.800 1 062 Vega 80496DX/33 MS DOS 5.0 80486DX 33 249.360 1 063 Escom 486 No opt Win95/DOS 80486DX2 66 325.660 20 --- ### ----------------------------------------------------------------------free counter