7
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Is there any limit to execution time? \$\endgroup\$ – andlrc Mar 19 '16 at 22:06
  • \$\begingroup\$ 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. \$\endgroup\$ – Stewie Griffin Mar 19 '16 at 23:10
4
\$\begingroup\$

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).
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.