# Create a diagonal sudoku board

A Diagonal Sudoku board is a special case of Latin squares. It has the following properties:

• The board is a 9-by-9 matrix
• Each row contains the numbers 1-9
• Each column contains the numbers 1-9
• Each 3-by-3 sub-region contains the numbers 1-9
• Both diagonals contains the numbers 1-9

Challenge:

Create a program or function that outputs a complete board with all 81 numbers that complies with the rules above.

The number in at least one position must be random, meaning the result should vary accross executions of the code. The distribution is optional, but it must be possible to obtain at least 9 structurally different boards. A board obtained from another by transliteration is not considered structurally different. Transliteration refers to substituting each number x by some other number y, consistently in all positions of number x.

Hardcoding 9 boards is not accepted either.

Rules:

• Output format is optional, as long as it's easy to understand (list of list is OK)
• The random number can be taken as input instead of being created in the script, but only if your language doesn't have a RNG.

This is code golf so the shortest code in bytes win!

Example boards:

7   2   5  |  8   9   3  |  4   6   1
8   4   1  |  6   5   7  |  3   9   2
3   9   6  |  1   4   2  |  7   5   8
-------------------------------------
4   7   3  |  5   1   6  |  8   2   9
1   6   8  |  4   2   9  |  5   3   7
9   5   2  |  3   7   8  |  1   4   6
-------------------------------------
2   3   4  |  7   6   1  |  9   8   5
6   8   7  |  9   3   5  |  2   1   4
5   1   9  |  2   8   4  |  6   7   3


4   7   8  |  1   9   5  |  3   2   6
5   2   6  |  4   8   3  |  7   1   9
9   3   1  |  6   7   2  |  4   5   8
-------------------------------------
2   5   9  |  8   6   7  |  1   3   4
3   6   4  |  2   5   1  |  9   8   7
1   8   7  |  3   4   9  |  5   6   2
-------------------------------------
7   1   2  |  9   3   8  |  6   4   5
6   9   3  |  5   2   4  |  8   7   1
8   4   5  |  7   1   6  |  2   9   3

• Is there any limit to execution time? Commented Mar 19, 2016 at 22:06
• It should ideally finish in less than a minute, but that's not a strict requirement. There's some leeway there, but you can't have a script running for hours. Commented Mar 19, 2016 at 23:10

# APL (Dyalog Unicode), 56 bytes

(,⊖⍣(?2)↑a(3+⍳3)(10-⌽a←3?3)){⍺ ⍺⌷9 9⍴∊⌽⍵∘.⌽⍵⊖¨⊂3 3⍴⍳9}⍳3


Try it online!

A full program that randomly gives a 9-by-9 matrix of digits.

By OP mentioning "it must be possible to obtain at least 9 structurally different boards", I believe it was to prevent using just trivial transformations like reflection and rotation. But there are more possible transformations than that. I use two kinds of transformations:

• Permute R19C19, R28C28 and R37C37 (6 cases)
Example: Swap R19C19 and R28C28

a b c - - - A B C     e d f - - - D F E
d e f - - - D E F     b a c - - - A C B
g h j - - - G H J     h g j - - - G J H
- - - - - - - - -     - - - - - - - - -
- - - - - - - - - ==> - - - - - - - - -
- - - - - - - - -     - - - - - - - - -
k l m - - - K L M     l k m - - - K M L
n p q - - - N P Q     s r t - - - R T S
r s t - - - R S T     p n q - - - N Q P

• Reverse the order of boxes in both dimensions (2 cases: reverse both or keep intact)
a b c - - - A B C     K L M - - - k l m
d e f - - - D E F     N P Q - - - n p q
g h j - - - G H J     R S T - - - r s t
- - - - - - - - -     - - - - - - - - -
- - - - - - - - - ==> - - - - - - - - -
- - - - - - - - -     - - - - - - - - -
k l m - - - K L M     A B C - - - a b c
n p q - - - N P Q     D E F - - - d e f
r s t - - - R S T     G H J - - - g h j


resulting in 12 structurally different boards. Note that, in both cases, the thing that changes on the diagonals is the order of the digits. Also, the center box is always intact, so no two boards are equivalent under transliteration.

### Part 1: Construct a valid diagonal sudoku board

⍝ A 3x3 box of 1..9
⊂3 3⍴⍳9
┌─────┐
│1 2 3│
│4 5 6│
│7 8 9│
└─────┘

⍝ The box rotated upwards 1, 2, 3 times
(⍳3)⊖¨⊂3 3⍴⍳9
┌─────┬─────┬─────┐
│4 5 6│7 8 9│1 2 3│
│7 8 9│1 2 3│4 5 6│
│1 2 3│4 5 6│7 8 9│
└─────┴─────┴─────┘

⍝ The boxes rotated left 1, 2, 3 times
(⍳3)∘.⌽(⍳3)⊖¨⊂3 3⍴⍳9
┌─────┬─────┬─────┐
│5 6 4│8 9 7│2 3 1│
│8 9 7│2 3 1│5 6 4│
│2 3 1│5 6 4│8 9 7│
├─────┼─────┼─────┤
│6 4 5│9 7 8│3 1 2│
│9 7 8│3 1 2│6 4 5│
│3 1 2│6 4 5│9 7 8│
├─────┼─────┼─────┤
│4 5 6│7 8 9│1 2 3│
│7 8 9│1 2 3│4 5 6│
│1 2 3│4 5 6│7 8 9│
└─────┴─────┴─────┘

⍝ Horizontally reverse the boxes, keeping the contents inside the boxes
⌽(⍳3)∘.⌽(⍳3)⊖¨⊂3 3⍴⍳9
┌─────┬─────┬─────┐
│2 3 1│8 9 7│5 6 4│
│5 6 4│2 3 1│8 9 7│
│8 9 7│5 6 4│2 3 1│
├─────┼─────┼─────┤
│3 1 2│9 7 8│6 4 5│
│6 4 5│3 1 2│9 7 8│
│9 7 8│6 4 5│3 1 2│
├─────┼─────┼─────┤
│1 2 3│7 8 9│4 5 6│
│4 5 6│1 2 3│7 8 9│
│7 8 9│4 5 6│1 2 3│
└─────┴─────┴─────┘

⍝ Enlist the digits and reshape into 9x9 matrix
⍝ (Each box goes to each row)
9 9⍴∊⌽(⍳3)∘.⌽(⍳3)⊖¨⊂3 3⍴⍳9
2 3 1 5 6 4 8 9 7
8 9 7 2 3 1 5 6 4
5 6 4 8 9 7 2 3 1
3 1 2 6 4 5 9 7 8
9 7 8 3 1 2 6 4 5
6 4 5 9 7 8 3 1 2
1 2 3 4 5 6 7 8 9
7 8 9 1 2 3 4 5 6
4 5 6 7 8 9 1 2 3


### Part 2: Generate permutation vector

,⊖⍣(?2)↑a(3+⍳3)(10-⌽a←3?3)
a←3?3   ⍝ Generate a permutation of 1 2 3
⍝ ex) 2 3 1
a(3+⍳3)(10-⌽a    )  ⍝ Permutation vector in chunks of 3
⍝ ex) (2 3 1)(4 5 6)(9 7 8)
↑                    ⍝ Promote to matrix
⊖⍣(?2)                     ⍝ Reverse vertically 1 or 2 times
⍝ ex) [9 7 8][4 5 6][2 3 1]
,                           ⍝ Flatten ex) 9 7 8 4 5 6 2 3 1


### Part 3: Permute the rows and columns

⍝ Permute both rows and columns of the matrix through indexing function
perm perm⌷mat
⍝ Using the example permutation above, the sudoku board is:
3 1 2 7 8 9 5 6 4
9 7 8 4 5 6 2 3 1
6 4 5 1 2 3 8 9 7
8 9 7 6 4 5 1 2 3
5 6 4 3 1 2 7 8 9
2 3 1 9 7 8 4 5 6
4 5 6 2 3 1 9 7 8
1 2 3 8 9 7 6 4 5
7 8 9 5 6 4 3 1 2


# SWI-Prolog, 438 bytes

:-use_module(library(clpfd)).
a(R):-l(9,R),m(l(9),R),append(R,V),V ins 1..9,transpose(R,C),d(0,R,D),maplist(reverse,R,S),d(0,S,E),r(R),m(m(all_distinct),[R,C,[D,E]]),get_time(I),J is ceil(I),m(labeling([random_value(J)]),R).
l(L,M):-length(M,L).
r([A,B,C|T]):-b(A,B,C),r(T);!.
b([A,B,C|X],[D,E,F|Y],[G,H,I|Z]):-all_distinct([A,B,C,D,E,F,G,H,I]),b(X,Y,Z);!.
d(X,[H|R],[A|Z]):-nth0(X,H,A),Y is X+1,(R=[],Z=R;d(Y,R,Z)).
m(A,B):-maplist(A,B).


Returns the answer as a list of lists, e.g. a(Z) unifies Z with [[2, 3, 6, 4, 9, 8, 7, 1, 5], [4, 5, 9, 2, 1, 7, 8, 3, 6], [7, 8, 1, 5, 3, 6, 9, 2, 4], [3, 2, 8, 7, 6, 4, 5, 9, 1], [5, 1, 4, 9, 8, 2, 3, 6, 7], [9, 6, 7, 1, 5, 3, 4, 8, 2], [1, 9, 2, 3, 4, 5, 6, 7, 8], [8, 7, 5, 6, 2, 9, 1, 4, 3], [6, 4, 3, 8, 7, 1, 2, 5, 9]].

### Explanation

:-use_module(library(clpfd)).          % Constraint Programming Library

a(R):-                                 % Main Predicate
l(9,R),m(l(9),R),append(R,V),      % R is a list of 9 lists, each of length 9
V ins 1..9,                        % Values in R are between 1 and 9
transpose(R,C),                    % C is the transpose of R
d(0,R,D),                          % D is the diagonal of R
maplist(reverse,R,S),d(0,S,E),     % E is the anti-diagonal of R
r(R),                              % All 3*3 blocks must contain numbers from 1 to 9
m(m(all_distinct),[R,C,[D,E]]),    % Each row of R, each row of C, D and E must contain
% only distinct numbers
get_time(I),J is ceil(I),          % Set J to a random number based on the current time
m(labeling([random_value(J)]),R).  % Randomly find a solution for R

l(L,M):-                               % L is the length of M
length(M,L).

r([A,B,C|T]):-                         % For each group of 3 rows, the 3*3 blocks must
b(A,B,C),r(T);!.                   % contain distinct numbers

b([A,B,C|X],[D,E,F|Y],[G,H,I|Z]):-     % Checks that the 3 3*3 blocks of 3 rows have
% distinct numbers inside them
all_distinct([A,B,C,D,E,F,G,H,I]),
b(X,Y,Z);!.

d(X,[H|R],[A|Z]):-                     % [A|Z] is the diagonal of [H|R]
nth0(X,H,A),
Y is X+1,
(R=[],Z=R;d(Y,R,Z)).

m(A,B):-
maplist(A,B).