H1: N queen problem
H2: queen
"queen" is a program that is helpful to get number of solutions
of N-queen problem on grid computing environment.
"queen" searchs solutions by dividing the task into independent
small pieces of task.

H2: Original program
The original program is omp/main.c in
	qn24b-version1.0.tgz
You will find this package at
	http://www.yuba.is.uec.ac.jp/~kis/nq/
In README.txt:
	N-queens benchmark since 2004-06 by Kenji KISE
	COPYRIGHT
	N-queens OpenMP version in C is free software. 
	See the file COPYING for copying permission.

Modification for Plan 9 and for 9grid is by Kenji Arisawa

H2: How to run
H3: full solution
	queen n
where n is the size of board (number of queens)
equivalent solutions are not elliminated


H3: partial solutions
full solution is obtained from independent partial solutions.
	queen n i:j
where n is the size of board (number of queens)
and i:j is a range of small task number, the notation follows Python.
that is, i:j means the set of tasks of task number:
	i, i+1, ..., j-1
and i and j must be
	0 <= i < j <= N
where N is a number of tasks. The value N is obtained by
	queen -n n
equivalent solutions are not eliminated

H3: example
For example, you will get a value 172 from
	queen -n 8
then
	queen 8 0:50
	queen 8 50:100
	queen 8 100:150
	queen 8 150:172
will produce full solutions.

H2: Confirmation
	n	solutions
	1 	1
	2 	0
	3 	0
	4 	2
	5	10
	6	4
	7	40
	8	92
	9	352
	10	724
	11	2680
	12	14200
	13	73712
	14	365596
	15	2279184
	16	14772512
	17	95815104
	18	666090624
	19	4968057848
	20	39029188884
	21	314666222712
	22	2691008701644
	23	24233937684440
	24	227514171973736

you can get these values by just executing without arguments,
	queen

H2: mktask
mktask create files in the directory named "tasks"
the usage is
	mktask n m
where n is the size of the board (number of queens),
and m is the number of task groups.
mktask is written in Python. Therefore you need Python.

How should I chese the number of task groups m ?
I think effective m is more than 10*(number of slaves)
because slaves are not homogeneous and the computing powers
differ from one another as much as ten times.

H3: example (single computer)
2.4GHz PentiumIV/Xeon in my home. The command is:
	time queen n

	n	tasks	time
	15	7432	2.5s
	16	9844	15s
	17 14272	110s
	18 18132	760s
	19 25080	6266s
	20 30880	47858s


I guess from this table that grid computing is effective for n > 17.

H3: example (grid computing)

My experiment of grid computation with 10 slaves

  al.aichi-u.ac.jp		# 665MHz PentiumIII/Xeon
  ar.aichi-u.ac.jp		# 868MHz PentiumIII/Xeon
  b.grid.bell-labs.com	# ?
  co.aichi-u.ac.jp		# 998MHz C3
  f.grid.bell-labs.com	# ?
  g.grid.bell-labs.com	# ?
  hera.aichi-u.ac.jp	# 1808MHz AMD-Athlon
  io.home				# 2392MHz PentiumIV/Xeon
  isengard.tip9ug.jp	# 2.4GHz AMD64
  lugosi (9grid.us)		# ?

n	slaves	m		time
15	10		20		19s
16	10		30		46s
17	10		30		71s
18	10		50		
19	10		100		1520s
20	10		100		11384s
21	10		500		99331s

m is the number of task groups

The followings are the result of
	time run Q
tasks are generated by
	mktask 19 100

term% cat Q/task.*/hostname>/tmp/b
term% wc /tmp/b
    100     100    1369 /tmp/b
term% sort  /tmp/b | uniq -c
   8 al.aichi-u.ac.jp
   9 ar.aichi-u.ac.jp
   4 b.11982
   4 co.aichi-u.ac.jp
   5 f.11581
   5 g.12373
  19 hera.aichi-u.ac.jp
  21 io.home
  23 isengard.34454
   2 lugosi.45457
term% 


n=21
  33 al.aichi-u.ac.jp
  45 ar.aichi-u.ac.jp
  13 b.12238
  22 co.aichi-u.ac.jp
  21 f.11850
  26 g.12655
 100 hera.aichi-u.ac.jp
 108 io.home
 116 isengard.35353
  16 lugosi.46129

n=19
   7 al.aichi-u.ac.jp
   9 ar.aichi-u.ac.jp
   4 b.1098
   4 co.aichi-u.ac.jp
   4 f.13652
   5 g.14481
  18 hera.aichi-u.ac.jp
  24 io.home
  22 isengard.39222
   3 lugosi.50806

n=20
   6 al.aichi-u.ac.jp
  10 ar.aichi-u.ac.jp
   3 b.1191
   5 co.aichi-u.ac.jp
   4 f.13745
   4 g.14587
  20 hera.aichi-u.ac.jp
  21 io.home
  24 isengard.39577
   3 lugosi.50947


H3: time for queen n (n >20)

time required to execute
	queen n 0:1
measured on 2.4GHz PentiumIV/Xeon
	n	time	tasks
	21	5s		41176
	22	33s		49480
	23	238s	64072
	24	1751s	75516
	25	13590s	95472
note that the time to compute one piece increases rapidly
