A standard 9x9 Sudoku grid is entirely empty except for two numbers in the bottom row. The bottom row looks like: 1, blank, 2, blank, blank, blank, blank, blank, blank.
The standard Sudoku rules apply: Each row and column must contain all the digits 1 to 9 and the
smaller 3x3 blocks must also contain all the digits 1 to 9.
Two additional rules apply: Each of the positive diagonals must contain no repeating digits, and the adjacent digits along each positive diagonal must have a difference of 4 or more.
Note: the positive (sloped) diagonals are diagonals that run from southwest to northeast. To obey the difference rule, for example, the major positive diagonal can begin: 1, 5, 9, 3, ... but not 1, 6, 9, 3, ... because the difference between 9 and 6 is less than 4.
Find the unique solution for the full grid.
clearvars, clc
d=perms(1:9); goodD=[];
for i=1:length(d)
diag=d(i,:); good=true;
if diag(1)==1
for j=1:8
if abs(diag(j)-diag(j+1))<4
good=false;
break
end
end
if good
goodD=[goodD;diag];
end
end
end
goodD
size(goodD,1)
goodD1=goodD;
d0=nchoosek(1:9,8); goodD=[];
for ii=1:size(d0,1)
d=perms(d0(ii,:));
for i=1:size(d,1)
diag=d(i,:); good=true;
for j=1:7
if abs(diag(j)-diag(j+1))<4
good=false;
break
end
end
if good
goodD=[goodD;diag(1:8)];
end
end
end
goodD
size(goodD,1)
goodD2=goodD;
d0=nchoosek(1:9,8); goodD=[];
for ii=1:size(d0,1)
d=perms(d0(ii,:));
for i=1:size(d,1)
diag=d(i,:); good=true;
for j=1:7
if abs(diag(j)-diag(j+1))<4
good=false;
break
end
end
if good
goodD=[goodD;diag(1:8)];
end
end
end
goodD
size(goodD,1)
goodD3=goodD;
d0=nchoosek(1:9,7); goodD=[];
for ii=1:size(d0,1)
d=perms(d0(ii,:));
for i=1:size(d,1)
diag=d(i,:); good=true;
for j=1:6
if abs(diag(j)-diag(j+1))<4
good=false;
break
end
end
if good
goodD=[goodD;diag(1:7)];
end
end
end
goodD
size(goodD,1)
goodD4=goodD;
grid=zeros(9);
goodGrids={};
for d1=1:size(goodD1,1)
grid(9:8:73)=goodD1(d1,:); % uses linearization of the 9x9 grid
% for d2=1:size(goodD2,1)
% grid(18:8:74)=goodD2(d2,:);
% for d3=1:size(goodD3,1)
% grid(8:8:64)=goodD3(d3,:);
% for d4=1:size(goodD4,1)
% grid(7:8:55)=goodD4(d4,:);
% for d4a=1:size(goodD4,1)
% grid(27:8:75)=goodD4(d4,:);
good=true;
tst=grid(7:9,1:3);
tst=tst(tst>0);
if length(unique(tst))<length(tst)
continue
end
tst=grid(4:6,4:6);
tst=tst(tst>0);
if length(unique(tst))<length(tst)
continue
end
tst=grid(1:3,7:9);
tst=tst(tst>0);
if length(unique(tst))<length(tst)
continue
end
for row=1:9
tst=grid(row,:);
tst=tst(tst>0);
if length(unique(tst))<length(tst)
good=false;
break
end
end
for col=1:9
tst=grid(:,col);
tst=tst(tst>0);
if length(unique(tst))<length(tst)
good=false;
break
end
end
if good==false
continue
end
goodGrids{end+1}=grid;
grid;
% end
% end
% end
% end
end
goodGridsNow=goodGrids;
goodGrids={};
for g=1:length(goodGridsNow)
grid=goodGridsNow{g};
for d2=1:size(goodD2,1)
grid(18:8:74)=goodD2(d2,:);
% for d3=1:size(goodD3,1)
% grid(8:8:64)=goodD3(d3,:);
% for d4=1:size(goodD4,1)
% grid(7:8:55)=goodD4(d4,:);
% for d4a=1:size(goodD4,1)
% grid(27:8:75)=goodD4(d4,:);
. . .
same grid testing as in previous loop
. . .
% end
% end
% end
end
end
goodGridsNow=goodGrids;
goodGrids={};
for g=1:length(goodGridsNow)
grid=goodGridsNow{g};
for d3=1:size(goodD3,1)
grid(8:8:64)=goodD3(d3,:);
for d4=1:size(goodD4,1)
grid(7:8:55)=goodD4(d4,:);
% for d4a=1:size(goodD4,1)
% grid(27:8:75)=goodD4(d4,:);
. . .
same grid testing as in previous loop
. . .
% end
end
end
end
goodGridsNow=goodGrids;
goodGrids={};
for g=1:length(goodGridsNow)
grid=goodGridsNow{g};
for d4a=1:size(goodD4,1)
if goodD4(d4a,1)==2
grid(27:8:75)=goodD4(d4a,:);
. . .
same grid testing as in previous loop
. . .
end
end
end
The loops were originally nested, but that meant the inner ones were acting on unpruned trees and the program took too long to execute. The consecutive running of loops makes for a longer program but it runs faster.
To make it shorter, the middle part where the testing is done could be put into a subroutine, but the repetition works, so it's still there.
In any case, before the final loop was run, there were 89 possible sets of the four diagonals filled up to that point. After the final loop there was only one possibility for the 5 diagonals filled--something to work on manually.
The final result from the computer is:
ans =
0 0 0 0 0 0 3 5 6
0 0 0 0 0 8 1 2 4
0 0 0 0 4 6 7 9 8
0 0 0 9 2 3 5 4 0
0 0 5 7 8 1 9 0 0
0 1 3 4 6 5 0 0 0
6 8 9 2 1 0 0 0 0
4 5 7 6 0 0 0 0 0
1 3 2 0 0 0 0 0 0
Manually solving the remainder produces
8 7 4 1 9 2 3 5 6
3 9 6 5 7 8 1 2 4
5 2 1 3 4 6 7 9 8
7 6 8 9 2 3 5 4 1
2 4 5 7 8 1 9 6 3
9 1 3 4 6 5 2 8 7
6 8 9 2 1 7 4 3 5
4 5 7 6 3 9 8 1 2
1 3 2 8 5 4 6 7 9
I was halfway through the solving that I noticed that each upward diagonal contained the whole or part of the cyclic sequence ... 1 5 9 4 8 3 7 2 6 ... in order.
|
|
Posted by Charlie
on 2022-05-14 11:19:59 |
computer-aided solution (spoiler)
