#Modification of Oren Ben-Kiki's original N-Queens style-sheet by Tom Myers
#One minor fix was applied: an element named "xmp" was renamed to "pre" to avoid invalid HTML
#Note: as of 20000123 4XSLT took 1533 seconds to crunch a board of size 8
# and as of 20030222, it took 16.597 seconds (on a faster machine, but still...)
from Xml.Xslt import test_harness
sheet_1 = """
N Queens
We will now call "queens"
to generate all solutions of the
-Queens problem.
queens(lim,list,upd,downd,listlen)=list, if lim=listlen
=queenstry(1,lim,list,upd,downd,listlen) otherwise
queenstry(val,lim,list,upd,downd,listlen)= "", if val>lim
=addifnew(val,lim,list,upd,downd,listlen) +
queenstry(val+1,lim,list,listlen) otherwise.
addifnew(val,lim,list,upd,downd,listlen)="",
if val in list or udv in upd or ddv in downd
= queens(lim,list+val+",",
upd+udv+",",downd+ddv+",",listlen+1) otherwise.
where udv=val+listlen, ddv=boardsize+val-listlen;
In other words,
queens(lim,list,upd,downd,listlen) assumes that "list" is
of length "listlen", with each number followed by a
comma, and the goal of queens is to add to that list
in every possible way to bring it to length "lim"
with numbers no greater than "lim" and without repeats.
queenstry(val,lim,list,upd,downd,listlen) will try the
value "val" and all values between it and "lim" in
extending the list.
addifnew(val,lim,list,upd,downd,listlen) does nothing
if "val" is already in the list; otherwise adds it
and goes on with "queens" of the longer list.
|
"""
source_1="""ignored, anyway"""
expected_1="""
N Queens
We will now call "queens"
to generate all solutions of the
8-Queens problem.
| 1 |
5 |
8 |
6 |
3 |
7 |
2 |
4 |
| 1 |
6 |
8 |
3 |
7 |
4 |
2 |
5 |
| 1 |
7 |
4 |
6 |
8 |
2 |
5 |
3 |
| 1 |
7 |
5 |
8 |
2 |
4 |
6 |
3 |
| 2 |
4 |
6 |
8 |
3 |
1 |
7 |
5 |
| 2 |
5 |
7 |
1 |
3 |
8 |
6 |
4 |
| 2 |
5 |
7 |
4 |
1 |
8 |
6 |
3 |
| 2 |
6 |
1 |
7 |
4 |
8 |
3 |
5 |
| 2 |
6 |
8 |
3 |
1 |
4 |
7 |
5 |
| 2 |
7 |
3 |
6 |
8 |
5 |
1 |
4 |
| 2 |
7 |
5 |
8 |
1 |
4 |
6 |
3 |
| 2 |
8 |
6 |
1 |
3 |
5 |
7 |
4 |
| 3 |
1 |
7 |
5 |
8 |
2 |
4 |
6 |
| 3 |
5 |
2 |
8 |
1 |
7 |
4 |
6 |
| 3 |
5 |
2 |
8 |
6 |
4 |
7 |
1 |
| 3 |
5 |
7 |
1 |
4 |
2 |
8 |
6 |
| 3 |
5 |
8 |
4 |
1 |
7 |
2 |
6 |
| 3 |
6 |
2 |
5 |
8 |
1 |
7 |
4 |
| 3 |
6 |
2 |
7 |
1 |
4 |
8 |
5 |
| 3 |
6 |
2 |
7 |
5 |
1 |
8 |
4 |
| 3 |
6 |
4 |
1 |
8 |
5 |
7 |
2 |
| 3 |
6 |
4 |
2 |
8 |
5 |
7 |
1 |
| 3 |
6 |
8 |
1 |
4 |
7 |
5 |
2 |
| 3 |
6 |
8 |
1 |
5 |
7 |
2 |
4 |
| 3 |
6 |
8 |
2 |
4 |
1 |
7 |
5 |
| 3 |
7 |
2 |
8 |
5 |
1 |
4 |
6 |
| 3 |
7 |
2 |
8 |
6 |
4 |
1 |
5 |
| 3 |
8 |
4 |
7 |
1 |
6 |
2 |
5 |
| 4 |
1 |
5 |
8 |
2 |
7 |
3 |
6 |
| 4 |
1 |
5 |
8 |
6 |
3 |
7 |
2 |
| 4 |
2 |
5 |
8 |
6 |
1 |
3 |
7 |
| 4 |
2 |
7 |
3 |
6 |
8 |
1 |
5 |
| 4 |
2 |
7 |
3 |
6 |
8 |
5 |
1 |
| 4 |
2 |
7 |
5 |
1 |
8 |
6 |
3 |
| 4 |
2 |
8 |
5 |
7 |
1 |
3 |
6 |
| 4 |
2 |
8 |
6 |
1 |
3 |
5 |
7 |
| 4 |
6 |
1 |
5 |
2 |
8 |
3 |
7 |
| 4 |
6 |
8 |
2 |
7 |
1 |
3 |
5 |
| 4 |
6 |
8 |
3 |
1 |
7 |
5 |
2 |
| 4 |
7 |
1 |
8 |
5 |
2 |
6 |
3 |
| 4 |
7 |
3 |
8 |
2 |
5 |
1 |
6 |
| 4 |
7 |
5 |
2 |
6 |
1 |
3 |
8 |
| 4 |
7 |
5 |
3 |
1 |
6 |
8 |
2 |
| 4 |
8 |
1 |
3 |
6 |
2 |
7 |
5 |
| 4 |
8 |
1 |
5 |
7 |
2 |
6 |
3 |
| 4 |
8 |
5 |
3 |
1 |
7 |
2 |
6 |
| 5 |
1 |
4 |
6 |
8 |
2 |
7 |
3 |
| 5 |
1 |
8 |
4 |
2 |
7 |
3 |
6 |
| 5 |
1 |
8 |
6 |
3 |
7 |
2 |
4 |
| 5 |
2 |
4 |
6 |
8 |
3 |
1 |
7 |
| 5 |
2 |
4 |
7 |
3 |
8 |
6 |
1 |
| 5 |
2 |
6 |
1 |
7 |
4 |
8 |
3 |
| 5 |
2 |
8 |
1 |
4 |
7 |
3 |
6 |
| 5 |
3 |
1 |
6 |
8 |
2 |
4 |
7 |
| 5 |
3 |
1 |
7 |
2 |
8 |
6 |
4 |
| 5 |
3 |
8 |
4 |
7 |
1 |
6 |
2 |
| 5 |
7 |
1 |
3 |
8 |
6 |
4 |
2 |
| 5 |
7 |
1 |
4 |
2 |
8 |
6 |
3 |
| 5 |
7 |
2 |
4 |
8 |
1 |
3 |
6 |
| 5 |
7 |
2 |
6 |
3 |
1 |
4 |
8 |
| 5 |
7 |
2 |
6 |
3 |
1 |
8 |
4 |
| 5 |
7 |
4 |
1 |
3 |
8 |
6 |
2 |
| 5 |
8 |
4 |
1 |
3 |
6 |
2 |
7 |
| 5 |
8 |
4 |
1 |
7 |
2 |
6 |
3 |
| 6 |
1 |
5 |
2 |
8 |
3 |
7 |
4 |
| 6 |
2 |
7 |
1 |
3 |
5 |
8 |
4 |
| 6 |
2 |
7 |
1 |
4 |
8 |
5 |
3 |
| 6 |
3 |
1 |
7 |
5 |
8 |
2 |
4 |
| 6 |
3 |
1 |
8 |
4 |
2 |
7 |
5 |
| 6 |
3 |
1 |
8 |
5 |
2 |
4 |
7 |
| 6 |
3 |
5 |
7 |
1 |
4 |
2 |
8 |
| 6 |
3 |
5 |
8 |
1 |
4 |
2 |
7 |
| 6 |
3 |
7 |
2 |
4 |
8 |
1 |
5 |
| 6 |
3 |
7 |
2 |
8 |
5 |
1 |
4 |
| 6 |
3 |
7 |
4 |
1 |
8 |
2 |
5 |
| 6 |
4 |
1 |
5 |
8 |
2 |
7 |
3 |
| 6 |
4 |
2 |
8 |
5 |
7 |
1 |
3 |
| 6 |
4 |
7 |
1 |
3 |
5 |
2 |
8 |
| 6 |
4 |
7 |
1 |
8 |
2 |
5 |
3 |
| 6 |
8 |
2 |
4 |
1 |
7 |
5 |
3 |
| 7 |
1 |
3 |
8 |
6 |
4 |
2 |
5 |
| 7 |
2 |
4 |
1 |
8 |
5 |
3 |
6 |
| 7 |
2 |
6 |
3 |
1 |
4 |
8 |
5 |
| 7 |
3 |
1 |
6 |
8 |
5 |
2 |
4 |
| 7 |
3 |
8 |
2 |
5 |
1 |
6 |
4 |
| 7 |
4 |
2 |
5 |
8 |
1 |
3 |
6 |
| 7 |
4 |
2 |
8 |
6 |
1 |
3 |
5 |
| 7 |
5 |
3 |
1 |
6 |
8 |
2 |
4 |
| 8 |
2 |
4 |
1 |
7 |
5 |
3 |
6 |
| 8 |
2 |
5 |
3 |
1 |
7 |
4 |
6 |
| 8 |
3 |
1 |
6 |
2 |
5 |
7 |
4 |
| 8 |
4 |
1 |
3 |
6 |
2 |
7 |
5 |
queens(lim,list,upd,downd,listlen)=list, if lim=listlen
=queenstry(1,lim,list,upd,downd,listlen) otherwise
queenstry(val,lim,list,upd,downd,listlen)= "", if val>lim
=addifnew(val,lim,list,upd,downd,listlen) +
queenstry(val+1,lim,list,listlen) otherwise.
addifnew(val,lim,list,upd,downd,listlen)="",
if val in list or udv in upd or ddv in downd
= queens(lim,list+val+",",
upd+udv+",",downd+ddv+",",listlen+1) otherwise.
where udv=val+listlen, ddv=boardsize+val-listlen;
In other words,
queens(lim,list,upd,downd,listlen) assumes that "list" is
of length "listlen", with each number followed by a
comma, and the goal of queens is to add to that list
in every possible way to bring it to length "lim"
with numbers no greater than "lim" and without repeats.
queenstry(val,lim,list,upd,downd,listlen) will try the
value "val" and all values between it and "lim" in
extending the list.
addifnew(val,lim,list,upd,downd,listlen) does nothing
if "val" is already in the list; otherwise adds it
and goes on with "queens" of the longer list.
"""
def Test(tester):
source = test_harness.FileInfo(string=source_1)
sheet = test_harness.FileInfo(string=sheet_1)
test_harness.XsltTest(tester, source, [sheet], expected_1)
return