Grid Counting

“That’s 3 in the corner, that’s 3 in the spotlight…”

— Simon Anthony, Cracking the Cryptic

Many fans of logic puzzles (and cryptic crosswords) are familiar with the YouTube channel “Cracking the Cryptic”. One of the memes on the channel is Simon paraphrasing an R.E.M. song whenever the digit 3 appears in the corner of a sudoku grid.

Simon now suspects that new sudoku authors intentionally create puzzles where they place a 3 into one of the corners. He needs your help in determining whether these grids appear disproportionally often among the puzzles he’s solving.

Task

An empty sudoku grid of order \(n\) is an \(n \times n\) grid that has been evenly partitioned into \(n\) non-overlapping rectangular regions, also called boxes, each consisting of \(n\) cells.

In this problem we will consider four values of \(n\): \(4\), \(6\), \(8\), and the classic: \(9\).

for \(n = 4\) the regions are four \(2\times 2\) squares
for \(n = 6\) the regions are six \(2\times 3\) rectangles (i.e., with 2 rows and 3 columns)
for \(n = 8\) the regions are eight \(2\times 4\) rectangles
for \(n = 9\) the regions are nine \(3\times 3\) squares

A valid sudoku of order \(n\) is an \(n \times n\) grid where each cell is filled with a number from \(1\) to \(n\), in which each number appears exactly once in each row, in each column, and in each region.

For each of these values of \(n\), your goal is to determine two values:

One integer: the total number of valid sudokus of order \(n\) that have a 3 in a corner.
One fraction: the probability that a valid sudoku of order \(n\), chosen uniformly at random, has a 3 in a corner.

(More precisely, in both cases “having a 3 in a corner” means “at least one of the four corner cells of the grid contains the digit 3”.)

Subproblems

There is no input. Each subproblem is fully determined by its value \(n\), which is given here:

Subproblem G1 (10 points, public): \(n = 4\)
Subproblem G2 (20 points, secret): \(n = 6\)
Subproblem G3 (20 points, secret): \(n = 8\)
Subproblem G4 (50 points, secret): \(n = 9\)

Output format

Your output file should contain two lines: one line with the integer and one line with the fraction, written as numerator/denominator. The fraction must be given in reduced form. (I.e., both the numerator and the denominator must be positive and they must be relatively prime.)

Each line of the output file is graded separately. Each correct line of output scores you half of the points for the corresponding subproblem.

Example of a syntactically valid output:

47003
23/599

Additional examples

This is one valid sudoku grid for \(n = 6\):

Below is the same grid with its regions shown using some simple ASCII art. Note that each row, column, and region does indeed contain each of the digits 1-6 once.

+-----+-----+
|1 3 6|4 5 2|
|2 4 5|6 1 3|
+-----+-----+
|6 5 3|1 2 4|
|4 1 2|3 6 5|
+-----+-----+
|5 6 4|2 3 1|
|3 2 1|5 4 6|
+-----+-----+

This sudoku does have a 3 in a corner: the cell in the bottom left corner contains the digit 3.

Two numbers that might be useful when checking your solutions:

The total number of valid sudoku grids for \(n = 4\) is 288.
Exactly 72 of those grids have a 3 specifically in the top left corner.

Finally, below is a valid sudoku grid for \(n = 4\). It does count as a sudoku that has a 3 in a corner. Note that it should only be counted once, even though it has the digit 3 appearing in two of its corners.

+---+---+
|3 1|4 2|
|2 4|3 1|
+---+---+
|1 3|2 4|
|4 2|1 3|
+---+---+