This program was written Basic (yup, plain old Basic--it still works) by Walter Gilbert in October, 2001. It finds all of the ways that a 2n x 2n checkerboard (or chessboard, if you prefer) can be divided into four identical quarters. Here are all 26 of the 6x6 solutions (not including rotations and reflections).

Note that there are ways of quartering a checkerboard that have only 180º symmetry. For example, first divide the board in half down the middle, the divide each of these halves in a symmetrical way. I am not interested in those solutions here.

The Program

1 REM This program finds the ways that a grid of NxN squares (where N is even)
2 REM can be divided into 4 identical pieces that, when rotated 90, 180, and
3 REM 270 degrees, will combine to fill the square. Examples for 6x6:

10 REM  x o o o o o    x o o o o o    x x o o o o    x x x o o o    x x x o o o
11 REM  x o . . . .    x x o . o .    x x o o o o    x x x o o o    x o o o o o
12 REM  x o . @ @ .    x o o . . .    x x x o . .    x x x o o o    x x x o . o
13 REM  x o o x @ .    x x x @ @ .    x x @ . . .    @ @ @ . . .    @ x @ . . .
14 REM  x x x x @ .    x @ x @ . .    @ @ @ @ . .    @ @ @ . . .    @ x @ @ @ .
15 REM  @ @ @ @ @ .    @ @ @ @ @ .    @ @ @ @ . .    @ @ @ . . .    @ @ @ . . .

16 REM The algorithm finds all valid paths from the upper right corner to the
17 REM center; e.g., for the first diagram, above, the path would be as in step
18 REM 1, below. Then this path is rotated 90 to the left which completes the
19 REM outline of the N-omino (step 2). Except that the rotated path goes back
20 REM to the upper right corner to close the figure instead of to the upper
21 REM left (step 3).  (Example is path DLLLLDDR for a 6x6 checkerboard.)
22 REM Finally, this pattern is reflected 180 deg. to fill the board (step 4).
23 REM           Step 1:         Step 2:          Step 3:          Step 4:
24 REM        . . . . . . .   ._. . . . . .    . ._._._._._.    . ._._._._._.
25 REM        . . ._._._._!   . ! ._._._._!    . ! ._._._._!    . ! ._._._._!
26 REM        . . ! . . . .   . ! ! . . . .    . ! ! . . . .    . ! ! ._._. .
27 REM        . . !_. . . .   . ! !_. . . .    . ! !_. . . .    . ! !_!_. ! .
28 REM        . . . . . . .   . !_._! . . .    . |_ _| . . .    . |_ _| ! ! .
29 REM        . . . . . . .   . . . . . . .    . . . . . . .    ._._._._! ! .
30 REM        . . . . . . .   . . . . . . .    . . . . . . .    !_._._._._! .

31 REM There is     1 solution  for 2x2
32 REM       are    3 solutions for 4x4 (scale=2)
33 REM             26               6x6 (scale=3)
34 REM            596               8x8        4
35 REM          38171              10x10       5
36 REM        7083827              12x12       6
37 REM This is done by finding the paths from one corner (upper right) to the
38 REM center that results in outlining the "N-ominos"; what I'll call the
39 REM patterns that fill the square.

40 FILE=0:                 REM 0=no disk file of paths sequences; 1=file
41 SCALE=3:                REM Checkerboard is 2*SCALE squares on a side.
42 OMINO=0:                REM 0=don't calc & output N-ominos; 1=write RTF file
43 CPL=104:                REM Char. per line in output of diagrams
44 PRFREQ=1000:            REM Print freq.: 0=never, 1=always, N=every Nth
47 REM CPL=10:             REM Max. char. per line in output of diagrams
48 SIZE=2*SCALE: SIZESQ=SIZE*SIZE: LENG=SCALE*SCALE+10
49 NDIAG=INT(CPL/(SIZE+2)): DCTR=0: REM Diags per line; DCTR=Diag. counter

50 DIM DX(4), DY(4), X(LENG), Y(LENG), LENGTHS(LENG)
51 DIM DIR(LENG): REM This is the key array for managing the process.
52 DIM W(SIZE,SIZE): REM For determining N-ominos from paths.
53 DIM OO$(SIZE), W$(2): W$(1)="O": W$(2)="G": REM For drawing N-ominos
79 REM DIR$(1)="U": DIR$(2)="R": DIR$(3)="D": DIR$(4)="L"
80 DIR$(1)="R": DIR$(2)="D": DIR$(3)="L": DIR$(4)="U": REM Right, Down, Left, Up
81   DX(1)= 1 :   DX(2)= 0 :   DX(3)=-1 :   DX(4)= 0
82   DY(1)= 0 :   DY(2)=-1 :   DY(3)= 0 :   DY(4)= 1
83 FOR J=1 TO 4: DIR$(J+4)=DIR$(J): NEXT J: REM Fill out for reflecting path
84 RDLU$=DIR$(1)+DIR$(2)+DIR$(3)+DIR$(4)
85 FOR J=1 TO LENG: LENGTHS(J)=0: NEXT J: REM Count path lengths
86 FOR J=1 TO SIZE: OO$(J)="": NEXT J: REM For accum. diagrams, NDIAG per line.

90 A$="": REM The answer path, e.g., LLLLDDDR
91 I=1: COUNT#=0
92 X(1)=SCALE: Y(1)=SCALE: REM Starting coordinates
93 IF OMINO<>0 THEN GOSUB 1000: REM Open RTF output file.
94 IF FILE<>0 THEN OPEN "O",#2,"paths.txt": REM Open list of paths
95 Z$="": D$="": L$="": DTAB$=""
96 FOR J=1 TO SCALE: Z$=Z$+DIR$(2): NEXT J: REM Build final path string, 
97 FOR J=1 TO SCALE: Z$=Z$+DIR$(3): NEXT J: REM    it is where we stop.
98 FOR J=1 TO SIZE: D$=D$+DIR$(2): L$=L$+DIR$(3): NEXT J: REM For "reflecting" the path

100 REM The actual algorithm extends from line 100 thru line 390.
101 REM The rest is formatting, outputting, etc.
120 I=I+1:                      REM Step to the next position
130 DIR(I)=0:                   REM Set the dir. index, goes 1 to 4: R,D,L,U

200 DIR(I)=DIR(I)+1:            REM Control comes here to move forward a step.
210 IF DIR(I)<5 GOTO 300:       REM This step not complete, keep proecssing

250 I=I-1:                      REM Control comes here to go back a step.
270 A$=LEFT$(A$,LEN(A$)-1):     REM Remove letter from end of path string.
280 GOTO 200

300 X(I)=X(I-1)+DX(DIR(I)): Y(I)=Y(I-1)+DY(DIR(I)): XI=X(I): YI=Y(I)
310 IF XI=0 AND YI=0 GOTO 500:         REM At the center; the end of a seq.
320 IF XI<>X(I-1) THEN IF X(I)>SCALE-1 GOTO 200: REM Out of bounds?
330 IF YI<>Y(I-1) THEN IF Y(I)>SCALE-1 GOTO 200: REM Ditto
340 FOR J=I-1 TO 1 STEP -1
345   XJ=X(J): YJ=Y(J)
350   IF XI=XJ AND YI=YJ GOTO 200:     REM Check for a loop in the path
355   IF XI= YJ AND YI=-XJ GOTO 200:   REM Check if touching another path
360   IF XI=-YJ AND YI= XJ GOTO 200:   REM Ditto
370 NEXT J
380 A$=A$+DIR$(DIR(I)):                REM Add new step to path string.
390 GOTO 100

500 REM Complete results path developed, print it.
510 A$=A$+DIR$(DIR(I)):                REM Add last piece to path.
520 COUNT#=COUNT#+1
527 REM The path that has been created is the "long way around". Its rotation
528 REM will be constructed, the short path. Together, they completely outline
529 REM the N-omino for this path.
530 FOR J=SIZE-1 TO 1 STEP -1: IF LEFT$(A$,J)<>LEFT$(D$,J) THEN NEXT J
540 B$=LEFT$(L$,SIZE-J):               REM B$ is the path up to the first turn.
544 REM The next line generates the path string rotated 90 degrees.
545 FOR K=J+1 TO LEN(A$): B$=B$+DIR$(INSTR(RDLU$,MID$(A$,K,1))+3): NEXT K
546 IF PRFREQ=0 GOTO 560
547 IF PRFREQ>1 THEN IF PRFREQ*INT(COUNT#/PRFREQ)<>COUNT# GOTO 560
550 IF FILE<>0 THEN PRINT #2,COUNT#,B$
555                 PRINT    COUNT#,B$
560 LENGTHS(LEN(B$))=LENGTHS(LEN(B$))+1
565 IF OMINO<>0 THEN GOSUB 600: REM Construct N-omino from paths
570 IF A$=Z$ GOTO 900: REM Check for half-way point (then we're done, the rest are reflections)
580 A$=LEFT$(A$,LEN(A$)-1)
590 GOTO 250

600 REM Construct N-omino from paths A$ & B$
610 FOR YI=1 TO SIZE:                  REM Clear the checkerboard array.
611   FOR XI=0 TO SIZE: W(XI,YI)=0: NEXT XI
612 NEXT YI
615 P$=A$: GOSUB 700:                  REM Mark N-omino edge on checkerboard.
620 P$=B$: GOSUB 700:                  REM Mark the other edge.
650 FOR YI=1 TO SIZE:                  REM Now generate the N-omino
652 K=1: IF W(0,YI)>0 THEN K=2:        REM W$(1) is a solid black square
655   FOR XI=1 TO SIZE:                REM W$(2) is a solid white square
660     O$=O$+W$(K)
665     IF W(XI,YI)<>0 THEN K=3-K:     REM Toggle K between 1 & 2
670   NEXT XI
675   OO$(YI)=OO$(YI)+DTAB$+O$: O$="": REM Insert RTF tab at edge of c'board
680 NEXT YI:                           REM Note that several diagrams are
681 DTAB$="\tab ":                     REM   created in a row.
682 DCTR=DCTR+1
684 IF DCTR=NDIAG THEN DCTR=0: GOSUB 800: REM Go output diagrams.
690 RETURN

700 REM Insert markers in the W() array for the paths A$ & B$ (in P$)
701 REM In effect, we are putting in the "!"s as they appear in Step 4 of
702 REM the diagrams drawn at the top of this program. (We do not need to 
703 REM draw the horizontal lines.) After this is done,
704 REM we will sweep left to right across each row of the board and output
705 REM black or white squares.
706 REM The color of the square changes whenever an edge (!) is encountered.
710 XI=SIZE: YI=SIZE
715 W(XI,YI)=1: W(0,1)=2
720 FOR J=1 TO LEN(P$)
725   C$=MID$(P$,J,1):                  REM Extract a dir.: R,L,Up or Dn
730   IF C$="L" THEN XI=XI-1: GOTO 750
735   IF C$="R" THEN XI=XI+1: GOTO 750
740   IF C$="D" THEN W(XI,YI)=1: YI=YI-1: W(SIZE-XI,SIZE-YI)=1: GOTO 750
745   IF C$="U" THEN W(SIZE-XI,SIZE-YI)=1: YI=YI+1: W(XI,YI)=1
750 NEXT J
790 RETURN

800 REM Output diagrams
801 REM Note that NDIAG diagrams are accumulated in OO$() and output as a unit.
820 IF LEN(OO$(1))=0 GOTO 890: REM For the last call, is array empty?
830 REM FOR J=SIZE TO 1 STEP -1: PRINT OO$(J): NEXT J
832 TB$="{\f1"
835 FOR J=NDIAG*INT((COUNT#-1)/NDIAG)+1 TO COUNT#: REM Print diagram numbers
836   PRINT #3,TB$;J;: TB$="\tab"
837 NEXT J
839 PRINT #3,"\par}"
840 FOR J=SIZE TO 1 STEP -1: PRINT #3,"{\par \f2 ";OO$(J);"}": OO$(J)="": NEXT J
850 PRINT #3,"\par\par\par"
880 DTAB$=""
890 RETURN

900 REM Done
910 IF FILE<>0 THEN PRINT #2,COUNT#;" solutions found."
911 PRINT    COUNT#;" solutions found."
919 PRINT "Path lengths:"
920 FOR J=1 TO LENG: IF LENGTHS(J)>0 THEN PRINT J;" ";LENGTHS(J)
930 NEXT J
950 IF OMINO<>0 THEN GOSUB 800: PRINT #3,"}": CLOSE #3
980 IF FILE<>0 THEN CLOSE #2
990 STOP

1000 REM Open RTF output file and write header.
1001 REM When complete, this RTF file can be opened in MS Word or WordPerfect
1002 REM to display all of the diagrams.
1010 OPEN "O",#3,"nominos.rtf"
1050 PRINT #3,"{\rtf1\ansi \deff0{\fonttbl{\f0\froman Times New Roman;}{\f2\fswiss WP TypographicSymbols;}}"
1051 PRINT #3,"{\colortbl \red0\green0\blue0;}"
1052 PRINT #3,"{\stylesheet{\fs16 \snext0 Normal;}}": REM fs16=8pt type
1053 PRINT #3,"\margl1080\margr1080\margt1080\margb1080\ftnbj\ftnrestart \sectd \sbknone\endnhere "
1060 R$="\pard \fs16\tx0": REM Paragraph definition: 8pt type
1065 K=INT(7*1440/NDIAG): REM Add equal tabs across 7" of page. 1"=1440 units
1070 FOR J=1 TO NDIAG: R$=R$+"\tx"+MID$(STR$(J*K),2): NEXT J
1080 PRINT #3,R$
1085 PRINT #3,"{\f1 Set line spacing to 0.55, letter spacing to 70%, adjust bottom margin to prevent bad breaks.\par}
1090 RETURN

9999 END