API tools faq
paste
Advertisement
Guest User

SudokuSolver

a guest
Jun 18th, 2011
186
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Scilab 19.79 KB | None | 0 0
raw download clone embed print report
  1. //Testcases.
  2. Testcase101=[5 8 2 4 3 9 7 1 6;1 9 6 5 8 7 4 2 3;7 3 4 6 2 1 8 9 5;4 2 5 9 6 3 1 8 7;9 7 3 8 1 2 5 6 4;6 1 8 7 4 5 2 3 9;2 6 7 3 5 8 9 4 1;8 4 9 1 7 6 3 5 2;3 5 1 2 9 4 6 7 8];
  3. Testcase102=[1 6 9 7 2 4 5 8 3;4 7 3 5 8 6 9 1 2;5 2 8 1 9 3 6 7 4;2 1 5 4 0 9 3 6 8;8 9 7 3 6 1 2 4 5;6 3 4 8 5 2 7 9 1;3 8 6 9 4 5 1 2 7;9 0 1 2 3 7 8 5 6;7 5 2 6 1 8 4 3 9];
  4. Testcase103=[7 1 2 6 3 8 5 4 9;6 3 4 5 1 9 8 2 7;9 5 8 7 2 2 3 1 6;3 4 9 1 7 6 2 8 5;2 8 7 3 4 5 9 6 1;5 6 1 8 9 4 4 7 3;1 9 6 4 8 3 7 5 2;4 2 5 9 6 7 1 3 8;8 7 3 2 5 1 6 9 4];
  5. Testcase104=[5 9 6 4 8 2 5 7 3;8 5 4 7 6 3 9 2 1;2 7 3 1 9 1 4 6 8;3 4 7 6 2 8 1 9 5;5 2 9 3 1 7 6 8 4;6 1 8 9 4 5 7 3 2;4 3 2 1 7 9 8 5 6;7 6 5 8 3 4 2 1 9;9 8 1 2 5 6 3 4 7];
  6. Testcase105=[1 5 7 4 8 2 3 9 6;6 9 3 1 5 7 2 4 8;4 2 8 9 6 3 1 7 5;5 3 2 7 9 4 3 8 1;9 8 6 5 3 1 7 2 4;7 1 4 8 2 6 9 5 3;8 6 1 2 4 9 5 3 7;3 4 9 6 7 5 8 1 2;2 7 5 3 1 8 4 6 9];
  7. Testcase201=[6 4 7 9 1 2 8 5 3;5 8 2 7 4 3 6 9 1;3 1 0 0 0 0 0 7 4;9 6 1 3 2 4 7 8 5;8 5 4 6 9 7 3 1 2;7 2 3 5 8 1 4 6 9;2 3 8 1 7 9 5 4 6;4 9 6 2 5 8 1 3 7;1 7 5 4 3 6 9 2 8];
  8. Testcase202=[0 0 6 0 4 8 0 3 0;0 4 0 0 3 0 9 6 0;0 0 2 1 9 0 0 0 0;5 0 0 9 0 0 0 2 0;0 8 4 0 1 0 0 5 0;7 0 0 0 0 0 0 0 6;0 0 0 0 7 0 0 0 1;3 7 0 0 0 0 0 9 0;6 0 0 8 5 2 7 0 0];
  9. Testcase203=[0 0 6 0 2 0 0 0 0;0 0 0 0 0 9 0 1 0;4 2 0 6 0 0 8 5 7;0 0 3 2 4 0 1 0 0;0 0 0 0 1 0 0 6 5;0 7 1 0 0 0 0 9 0;8 0 0 0 0 0 0 2 0;7 3 0 0 8 0 9 0 0;6 0 0 5 0 4 0 0 0];
  10. Testcase204=[5 0 0 0 0 0 0 0 0;1 0 2 0 9 0 0 6 7;7 0 0 4 0 0 3 0 0;0 0 0 0 0 2 0 1 0;0 0 0 0 7 0 0 0 0;0 7 0 0 1 0 0 0 4;0 0 7 0 0 0 8 0 0;0 9 0 0 0 0 0 0 0;0 0 0 3 6 1 4 0 0];
  11. Testcase205=[0 1 9 0 0 3 0 0 0;5 7 6 0 0 0 0 3 0;0 0 3 0 0 6 9 0 2;1 0 0 9 6 2 8 7 0;6 0 0 7 0 5 1 0 3;8 9 0 0 0 0 0 0 0;9 0 0 8 0 0 0 0 0;0 5 8 0 0 0 0 0 0;0 4 0 0 3 0 0 0 5];
  12. Testcase206=[0 4 3 0 0 0 2 5 0;0 0 0 2 8 7 0 0 0;7 2 0 0 0 0 1 0 6;0 0 7 8 0 0 3 0 0;0 0 6 7 0 1 4 0 0;0 9 0 3 2 0 0 7 1;0 0 0 6 3 0 0 0 4;0 7 2 4 0 0 0 0 5;1 0 0 0 0 0 0 0 0];
  13. Testcase207=[2 0 0 0 6 0 8 9 1;0 8 0 0 0 0 0 0 0;7 9 6 0 0 5 3 0 0;6 0 0 8 2 7 0 0 0;0 0 9 0 4 3 2 0 6;0 0 0 9 0 0 0 0 8;0 2 0 0 9 1 0 8 0;4 6 0 0 0 0 5 0 0;0 0 8 4 0 2 1 0 7];
  14. Testcase208=[0 0 8 0 0 0 0 1 4;5 2 7 0 8 1 0 0 0;0 0 0 0 2 3 0 7 0;3 0 0 0 1 0 6 5 0;0 0 9 3 6 0 0 0 0;1 0 0 0 5 9 0 3 0;2 0 3 0 0 8 7 0 0;0 0 0 1 9 0 3 2 0;0 6 5 2 0 0 0 0 0];
  15. Testcase209=[0 6 0 7 9 0 0 0 3;2 0 0 0 0 0 9 0 0;4 0 0 6 5 3 0 8 0;0 0 0 0 1 0 5 7 8;1 0 5 3 0 0 6 4 0;9 0 7 0 6 5 0 0 2;0 0 0 9 0 0 0 0 1;0 0 0 5 0 4 0 0 0;0 9 0 0 8 6 0 5 0];
  16. Testcase210=[3 8 2 0 0 5 0 9 4;0 0 0 0 0 6 0 0 0;9 0 6 0 0 0 7 3 0;8 6 0 2 0 7 1 4 0;0 0 0 0 0 3 0 5 2;1 0 0 0 0 8 0 7 0;0 0 0 0 0 1 9 0 0;0 0 0 0 0 0 0 6 0;0 7 8 5 0 9 4 0 1];
  17. Testcase211=[0 0 1 7 0 0 0 3 0;0 7 0 0 8 1 0 0 0;0 0 0 0 6 9 0 0 7;0 0 0 0 4 0 0 8 0;9 6 7 0 1 0 0 5 0;4 0 8 0 5 2 0 0 0;8 0 5 0 3 4 7 9 6;7 1 6 0 0 0 2 4 3;0 9 4 0 0 0 8 0 0];
  18. Testcase212=[0 0 0 0 4 8 0 0 0;0 0 0 9 0 2 0 6 0;0 7 0 0 1 5 0 0 8;8 9 0 0 2 4 0 0 0;6 0 0 0 0 9 0 2 0;4 2 3 0 0 0 7 0 5;0 8 9 4 0 1 3 0 0;0 0 4 0 9 3 0 5 2;1 0 0 0 0 0 4 0 0];
  19. Testcase213=[7 0 4 0 0 0 0 9 6;5 0 8 9 0 0 7 0 1;0 0 0 0 8 7 0 0 0;8 9 0 6 0 0 2 0 0;2 0 3 0 7 9 6 1 0;6 0 0 0 2 8 0 3 4;0 6 0 8 0 0 0 7 5;1 0 7 3 0 0 0 0 0;3 8 9 0 0 0 0 0 0];
  20. Testcase214=[3 0 0 0 0 4 0 1 0;0 0 9 0 3 6 7 0 4;0 4 0 0 0 0 8 0 0;0 1 4 0 0 0 0 0 7;2 0 7 0 4 0 0 0 0;0 0 0 0 2 9 6 0 1;0 0 0 0 0 0 0 3 6;0 7 0 1 0 2 4 0 5;0 0 5 0 6 3 0 7 2];
  21. Testcase215=[0 0 0 0 4 0 2 0 6;0 0 0 0 0 0 0 9 0;6 0 2 5 0 3 0 0 0;5 4 0 0 0 0 1 7 0;0 0 0 0 0 9 0 4 0;0 1 0 0 7 0 0 8 3;4 0 0 0 3 1 0 5 0;7 0 0 0 0 0 0 0 8;0 8 0 0 0 0 4 6 0];
  22.  
  23. function D=Duwplat(A)
  24. //Duwplat zorgt dat een matrix een vector wordt.
  25.   D=[]
  26. //Gaat elke rij overlopen om deze dan allemaal achtereen te zetten.
  27.   for i=1:size(A,1)
  28.     D=[D(1,:),A(i,:)]
  29.   end
  30. endfunction
  31.  
  32. function G=alleCijfersAanwezig(A)
  33. //alleCijfersAanwezig gaat kijken of alle cijfers van 1 tot 9 er 1 maal inzitten
  34.   D=Duwplat(A)
  35.   l=length(D)
  36.   G=%T
  37.   Teller=1
  38.   for t=1:l
  39. //Bekijkt alle cijfers in de vector tot deze gevonde is en zet deze dan op 0 en erna stopt met achter dit getal te zoeken.
  40.     B=%T
  41.     for i=1:l
  42.       if D(i)==t & B then
  43.         D(i)=0;
  44.         B=%F;
  45.       end
  46.     end
  47.   end
  48.   for j=1:l
  49. //Gaat kijken of alle cijfers 0 zijn als dit niet zo is zal de uitkomst False zijn.
  50.     if D(j)~=0 then
  51.       G=%F
  52.     end
  53.   end
  54. endfunction
  55.  
  56. function B=GoedeSudoku(A)
  57. //GoedeSudoku gaat testen of deze sudoku correct is.
  58.   C=size(A,2) //aantal kolommen
  59.   H=size(A,1) //aantal rijen
  60.   if C==H then
  61.     S=sqrt(C)
  62.   else
  63.     S=3
  64.   end
  65.   B=%T
  66.   T=%T
  67.   Rij=0
  68.   Kol=0
  69.   Seg=0
  70.   while B & T
  71. //Lus 1 - Dit zal alle rijen nakijken of deze goed opgelost zijn.
  72.     for i=1:H
  73.       D=A(i,:)
  74.       if ~alleCijfersAanwezig(D) & B then
  75.         B=%F
  76.         Rij=(i)
  77.       end
  78.     end
  79. //Lus 2 - Dit zal alle kolommen nakijken of deze goed opgelost zijn.
  80.     for i=1:C
  81.       D=A(:,i)
  82.       if ~alleCijfersAanwezig(D) & B then
  83.         B=%F
  84.         Kol=(i)
  85.       end
  86.     end
  87. //Lus 3 - Dit zal alle Segmenten nakijken of deze goed opgelost zijn.
  88.     SS=S-1
  89.     for i=1:S:H-SS
  90.       for j=1:S:C-SS
  91.         D=A(i:i+SS,j:j+SS)
  92.         if ~alleCijfersAanwezig(D) & B then
  93.           B=%F
  94.           Seg=(floor((j-1)/S)+(floor((i-1)/S)*S)+1)
  95.         end
  96.       end
  97.     end
  98.     T=%F
  99.   end
  100.   if ~B&Rij>0 then
  101.     printf("De eerste fout bevindt zich in Rij %d.\n",Rij)
  102.   elseif ~B&Kol>0 then
  103.     printf("De eerste fout bevindt zich in Kolom %d.\n",Kol)
  104.   elseif ~B&Seg>0 then
  105.     printf("De eerste fout bevindt zich in Segment %d.\n",Seg)
  106.   elseif B then
  107.     printf("Deze Sudoku is correct opgesteld.\n")
  108.   end
  109. endfunction
  110.  
  111. function TC=totaalOpenCijfers(A)
  112. //Deze functie gaat kijken hoeveel vakjes in de sudoku nog moeten opgelost worden.
  113.   TC=0
  114.   B=Duwplat(A)
  115.   if GoedeSudoku(A) then
  116. //Gaat alle cijfers van B overlopen.
  117.     for i=1:length(B)
  118.       if B(i)==0 then
  119.         TC=TC+1
  120.       end
  121.     end
  122.   else
  123.     printf("Deze sudoku is foutief opgesteld.\n")
  124.   end
  125.     printf("Er zijn %d lege vakjes.\n",TC)
  126. endfunction
  127.  
  128. function B=isSudokuOpgelost(A)
  129. //isSudokuOpgelost gaat testen of deze sudoku correct is.
  130.   C=size(A,2) //aantal kolommen
  131.   H=size(A,1) //aantal rijen
  132.   if C==H then
  133.     S=sqrt(C)
  134.   else
  135.     S=3
  136.   end
  137.   B=%T
  138.   T=%T
  139.   Rij=0
  140.   Kol=0
  141.   Seg=0
  142.   while B & T
  143. //Lus 1 - Dit zal alle rijen nakijken of deze goed opgelost zijn.
  144.     for i=1:H
  145.       D=A(i,:)
  146.       if ~alleCijfersAanwezig(D) & B then
  147.         B=%F
  148.         Rij=(i)
  149.       end
  150.     end
  151. //Lus 2 - Dit zal alle kolommen nakijken of deze goed opgelost zijn.
  152.     for i=1:C
  153.       D=A(:,i)
  154.       if ~alleCijfersAanwezig(D) & B then
  155.         B=%F
  156.         Kol=(i)
  157.       end
  158.     end
  159. //Lus 3 - Dit zal alle Segmenten nakijken of deze goed opgelost zijn.
  160.     SS=S-1
  161.     for i=1:S:H-SS
  162.       for j=1:S:C-SS
  163.         D=A(i:i+SS,j:j+SS)
  164.         if ~alleCijfersAanwezig(D) & B then
  165.           B=%F
  166.           Seg=(floor((j-1)/S)+(floor((i-1)/S)*S)+1)
  167.         end
  168.       end
  169.     end
  170. //Gaat kijken of alle vakjes ingevuld zijn.
  171.     if totaalOpenCijfers(A)>0 then
  172.       B=%F
  173.     end
  174.     T=%F
  175.   end
  176.   if ~B&Rij>0 then
  177.     printf("De eerste fout bevindt zich in Rij %d.\n",Rij)
  178.   elseif ~B&Kol>0 then
  179.     printf("De eerste fout bevindt zich in Kolom %d.\n",Kol)
  180.   elseif ~B&Seg>0 then
  181.     printf("De eerste fout bevindt zich in Segment %d.\n",Seg)
  182.   elseif ~B&Seg==0&Kol==0&Rij==0 then
  183.     printf("Deze sudoku is nog niet volledig opgelost.\n")
  184.   elseif B then
  185.     printf("Deze Sudoku is correct opgelost. Proficiat!\n")
  186.   end
  187. endfunction
  188.  
  189. function V=ontbrekendeCijfers(A)
  190. //Deze functie gaat nakijken in een "matrix" of alle opeenvolgende cijfers aanwezig zijn en welke dan niet aanwezig zijn.
  191.   B=Duwplat(A)
  192.   Dubbels=~alleCijfersAanwezig(B)
  193.   V=[]
  194.   l=length(B)
  195.   teller=1
  196.   if Dubbels then
  197.     error("De vector is foutief")
  198.   else
  199.     for t=1:l
  200.       g=%F
  201.       i=1
  202.       for i=1:l
  203.         if B(i)==t & ~g then
  204.           g=%T
  205.         end
  206.       end
  207.       if ~g then
  208.         V(1,teller)=t
  209.         teller=teller+1
  210.       end
  211.     end
  212.   end
  213. endfunction
  214.  
  215. function U=uniekOntbrekende(R,K,S)
  216. //kijkt na welk uniek cijfer er ontbreekt in de 3 vectoren
  217.   A=Duwplat(R)
  218.   B=Duwplat(K)
  219.   C=Duwplat(S)
  220.   U=0
  221.   RO=ontbrekendeCijfers(R)
  222.   KO=ontbrekendeCijfers(K)
  223.   SO=ontbrekendeCijfers(S)
  224.   tel=0
  225.   if alleCijfersAanwezig(R) & alleCijfersAanwezig(K) & alleCijfersAanwezig(S) then
  226.     for i=1:length(RO)
  227.       for j=1:length(KO)
  228.         for k=1:length(SO)
  229.           if RO(i)==KO(j) & KO(j)==SO(k) then
  230.             U=RO(i)
  231.             tel=tel+1
  232.           end
  233.         end
  234.       end
  235.     end
  236.   end
  237.   if tel>1 then
  238.     U=0
  239.   end
  240. endfunction
  241.  
  242. function S=luiePoging(B)
  243. //Gaat de hele sudoku doorlopen en kijken of er een onbekend cijfer zijn die ingevuld kunnen worden. De sudoku wordt maar 1 maal doorlopen.
  244.   h=size(B,1)
  245.   b=size(B,2)
  246.   if h==b then
  247.     sd=sqrt(h)
  248.   else
  249.     sd=3
  250.   end
  251.   cijf=0
  252.   S=(B(:,:))
  253.   G=GoedeSudoku(B)
  254.   O=isSudokuOpgelost(B)
  255.   if G & ~O
  256.     for i=1:h
  257.       for j=1:b
  258.         if S(i,j)==0 then
  259. //Worden Rijen geselecteerd.
  260.           RT=S(i,:)
  261. //Worden Kolommen geselecteerd.
  262.           KT=S(:,j)
  263. //Worden Segmenten geselecteerd.
  264.           r=(floor((i-1)/sd)*sd)+1
  265.           k=(floor((j-1)/sd)*sd)+1
  266.           ST=S(r:r+sd-1,k:k+sd-1)
  267.           cijf=uniekOntbrekende(RT,KT,ST)
  268.           S(i,j)=cijf
  269. //Print het cijfer uit dat is ingevuld en de locatie.
  270.           if cijf~=0 then
  271.             printf("Het cijfer %d werd ingevuld in het vakje (%d,%d).\n",cijf,i,j)
  272.           end
  273.         end
  274.       end
  275.     end
  276.   end
  277.   O=isSudokuOpgelost(S)
  278.   if ~O then
  279.     printf("Deze sudoku is nog niet volledig opgelost.\n")
  280.   end
  281. endfunction
  282.  
  283. function S=BlijvenProberen(B)
  284. //gaat de sudoku proberen op te lossen door de luiepoging te herhalen.
  285.   h=size(B,1)
  286.   b=size(B,2)
  287.   if h==b then
  288.     sd=sqrt(h)
  289.   else
  290.     sd=3
  291.   end
  292.   cijf=0
  293.   S=(B(:,:))
  294.   G=GoedeSudoku(S)
  295.   O=isSudokuOpgelost(S)
  296.   teller=1
  297.   while G & ~O & teller>0
  298.     teller=0
  299.     for i=1:h
  300.       for j=1:b
  301.         if S(i,j)==0 then
  302. //Worden Rijen geselecteerd.
  303.           RT=S(i,:)
  304. //Worden Kolommen geselecteerd.
  305.           KT=S(:,j)
  306. //Worden Segmenten geselecteerd.
  307.           r=(floor((i-1)/sd)*sd)+1
  308.           k=(floor((j-1)/sd)*sd)+1
  309.           ST=S(r:r+sd-1,k:k+sd-1)
  310.           cijf=uniekOntbrekende(RT,KT,ST)
  311.           S(i,j)=cijf
  312. //Print het cijfer uit dat is ingevuld en de locatie.
  313.           if cijf~=0 then
  314.             printf("Het cijfer %d werd ingevuld in het vakje (%d,%d).\n",cijf,i,j)
  315.             teller=teller+1
  316.           end
  317.         end
  318.       end
  319.     end
  320.   end
  321. endfunction
  322.  
  323. function S=zoekUniekVakje(M)
  324. //Deze functie gaat 5 functies gebruiken om een sudoku proberen op te lossen.
  325.   OC=1
  326.   S=M(:,:)
  327.   OS=isSudokuOpgelost(S)
  328.   while OC>0&~OS
  329. //Wanneer geen cijfer meer ingevuld wordt zal deze lus ophouden.
  330. //Hier staan de 4 functies van de 5 die gebruikt worden: BlijvenProberen, RijenInvullen, KolommenInvullen en SegmentenInvullen.
  331. //Deze gaan de meeste sudokus oplossen.
  332.     OC=totaalOpenCijfers(S)
  333.     S=BlijvenProberen(S)
  334.     S=RijenInvullen(S)
  335.     S=KolommenInvullen(S)
  336.     S=SegmentenInvullen(S)
  337.     OS=isSudokuOpgelost(S)
  338.     OC=OC-totaalOpenCijfers(S)
  339.   end
  340. //Hier zal de methode BackTracking gestart worden wanneer alle voorgaande onsuccesvol zijn.
  341. //Deze methode werkt volgens het principe van BackTracking.
  342. //Deze methode maakt het makkelijker om elke sudoku proberen op te lossen zonder teveel methodes te moeten gebruiken.
  343.   if ~OS then
  344.     S=BackTracking(S)
  345.     OS=isSudokuOpgelost(S)
  346.   end
  347.   if ~OS then
  348.     printf("Sorry het programma krijgt deze sudoku niet opgelost.")
  349.   end
  350. endfunction
  351.  
  352. function S=RijenInvullen(M)
  353. //Deze functie gaat de rijen invullen door te kijken of er maar 1 mogelijke positie is voor elk cijfer in deze rij.
  354.   HM=size(M,1)
  355.   BM=size(M,2)
  356.   OS=isSudokuOpgelost(M)
  357.   S=M(:,:)
  358.   if HM==BM then
  359.     sd=sqrt(HM)
  360.   else
  361.     sd=3
  362.   end
  363.   if ~OS then
  364. //Alle rijen overlopen.
  365.     for i=1:HM
  366.       OCDM=ontbrekendeCijfers(S(i,:))
  367. //Alle cijfers overlopen.
  368.       for j=1:BM
  369.         T=%F
  370.         for k=1:length(OCDM)
  371. //Gaat kijken of het cijfer bij de ontbrekende cijfers zit.
  372.           if OCDM(k)==j then
  373.             T=%T
  374.           end
  375.         end
  376.         if T then
  377.           for k=1:BM
  378.             if S(i,k)==0 then
  379.               S(i,k)=j
  380.             end
  381.           end
  382.           for k=1:BM
  383.             if ~alleCijfersAanwezig(S(:,k)) then
  384.               S(i,k)=0
  385.             end
  386.           end
  387.           H=1
  388.           if i<7&i>3 then
  389.             H=4
  390.           elseif i>6 then
  391.             H=7
  392.           end
  393.           for k=1:sd:BM-sd+1
  394.             SS=S(H:H+sd-1,k:k+sd-1)
  395.             sstel=0
  396.             for l=1:sd
  397.               TSS=%T
  398.               for m=1:sd
  399.                 if TSS&SS(l,m)==j then
  400.                   sstel=sstel+1
  401.                   TSS=%F
  402.                 end
  403.               end
  404.             end
  405.             if ~alleCijfersAanwezig(SS)&sstel>1 then
  406.               for l=0:sd-1
  407.                 if S(i,k+l)==j then
  408.                   S(i,k+l)=0
  409.                 end
  410.               end
  411.             end
  412.           end
  413.           if ~alleCijfersAanwezig(S(i,:)) then
  414.             for k=1:BM
  415.               if S(i,k)==j then
  416.                 S(i,k)=0
  417.               end
  418.             end
  419.           end
  420.           for k=1:BM
  421.             if S(i,k)==j then
  422.               printf("Het cijfer %d werd ingevuld in het vakje (%d,%d).\n",j,i,k)
  423.             end
  424.           end
  425.         end
  426.       end
  427.     end
  428.   end
  429. endfunction
  430.  
  431. function S=KolommenInvullen(M)
  432. //Deze functie gaat de kolommen invullen door te kijken of er maar 1 mogelijke positie is voor elk cijfer in deze kolommen.
  433.   HM=size(M,1)
  434.   BM=size(M,2)
  435.   OS=isSudokuOpgelost(M)
  436.   S=M(:,:)
  437.   if HM==BM then
  438.     sd=sqrt(HM)
  439.   else
  440.     sd=3
  441.   end
  442.   if ~OS then
  443. //Alle kolommen overlopen.
  444.     for i=1:BM
  445.       OCDM=ontbrekendeCijfers(S(:,i))
  446. //Alle cijfers overlopen.
  447.       for j=1:HM
  448.         T=%F
  449.         for k=1:length(OCDM)
  450. //Gaat kijken of het cijfer bij de ontbrekende cijfers zit.
  451.           if OCDM(k)==j then
  452.             T=%T
  453.           end
  454.         end
  455.         if T then
  456. //Alle nullen in de kolom invullen met het cijfer dat ontbreekt en nu getest wordt (het cijfer j).
  457.           for k=1:HM
  458.             if S(k,i)==0 then
  459.               S(k,i)=j
  460.             end
  461.           end
  462. //Kijken of alle overeenkomstige rijen nog correct zijn. Indien niet hebben we een cijfer ingevuld op een plaats waar het onmogelijk kan staan en zetten we dit terug op 0.
  463.           for k=1:BM
  464.             if ~alleCijfersAanwezig(S(k,:)) then
  465.               S(k,i)=0
  466.             end
  467.           end
  468.           H=1
  469.           if i<7&i>3 then
  470.             H=4
  471.           elseif i>6 then
  472.             H=7
  473.           end
  474.           for k=1:sd:HM-sd+1
  475.             SS=S(k:k+sd-1,H:H+sd-1)
  476.             sstel=0
  477.             for l=1:sd
  478.               TSS=%T
  479.               for m=1:sd
  480.                 if TSS&SS(m,l)==j then
  481.                   sstel=sstel+1
  482.                   TSS=%F
  483.                 end
  484.               end
  485.             end
  486.             if ~alleCijfersAanwezig(SS)&sstel>1 then
  487.               for l=0:sd-1
  488.                 if S(k+l,i)==j then
  489.                   S(k+l,i)=0
  490.                 end
  491.               end
  492.             end
  493.           end
  494.           if ~alleCijfersAanwezig(S(:,i)) then
  495.             for k=1:HM
  496.               if S(k,i)==j then
  497.                 S(k,i)=0
  498.               end
  499.             end
  500.           end
  501.           for k=1:BM
  502.             if S(k,i)==j then
  503.               printf("Het cijfer %d werd ingevuld in het vakje (%d,%d).\n",j,i,k)
  504.             end
  505.           end
  506.         end
  507.       end
  508.     end
  509.   end
  510. endfunction
  511.  
  512. function S=SegmentenInvullen(M)
  513.   HM=size(M,1)
  514.   BM=size(M,2)
  515.   OS=isSudokuOpgelost(M)
  516.   S=M(:,:)
  517.   if HM==BM then
  518.     sd=sqrt(HM)
  519.   else
  520.     sd=3
  521.   end
  522.   if ~OS then
  523. //Alle Segmenten overlopen
  524.     for i=1:sd:HM-sd+1
  525.       for j=1:sd:BM-sd+1
  526.         OCDM=ontbrekendeCijfers(S(i:i+sd-1,j:j+sd-1))
  527. //Alle cijfers overlopen
  528.         for k=1:BM
  529.           T=%F
  530.           for l=1:length(OCDM)
  531.             if OCDM(l)==k then
  532.               T=%T
  533.             end
  534.           end
  535.           if T then
  536.             for m=0:sd-1
  537.               for n=0:sd-1
  538.                 if S(i+m,j+n)==0 then
  539.                   S(i+m,j+n)=k
  540.                 end
  541.               end
  542.             end
  543.             for m=0:sd-1
  544.               if ~alleCijfersAanwezig(S(i+m,:)) then
  545.                 teller=0
  546.                 for n=1:HM
  547.                   if S(i+m,n)==k then
  548.                     teller=teller+1
  549.                   end
  550.                 end
  551.                 for n=0:sd-1
  552.                   if S(i+m,j+n)==k then
  553.                     teller=teller-1
  554.                   end
  555.                 end
  556.                 if teller>0 then
  557.                   for n=0:sd-1
  558.                     if S(i+m,j+n)==k then
  559.                       S(i+m,j+n)=0
  560.                     end
  561.                   end
  562.                 end
  563.               end
  564.             end
  565.             for n=0:sd-1
  566.               if ~alleCijfersAanwezig(S(:,j+n)) then
  567.                 teller=0
  568.                 for m=1:BM
  569.                   if S(m,j+n)==k then
  570.                     teller=teller+1
  571.                   end
  572.                 end
  573.                 for m=0:sd-1
  574.                   if S(i+m,j+n)==k then
  575.                     teller=teller-1
  576.                   end
  577.                 end
  578.                 if teller>0 then
  579.                   for m=0:sd-1
  580.                     if S(i+m,j+n)==k then
  581.                       S(i+m,j+n)=0
  582.                     end
  583.                   end
  584.                 end
  585.               end
  586.             end
  587.             if ~alleCijfersAanwezig(S(i:i+sd-1,j:j+sd-1)) then
  588.               for m=0:sd-1
  589.                 for n=0:sd-1
  590.                   if S(i+m,j+n)==k then
  591.                     S(i+m,j+n)=0
  592.                   end
  593.                 end
  594.               end
  595.             end
  596.             for m=0:sd-1
  597.               for n=0:sd-1
  598.                 if S(i+m,j+n)==k then
  599.                   printf("Het cijfer %d werd ingevuld in het vakje (%d,%d).\n",k,i+m,j+n)
  600.                 end
  601.               end
  602.             end
  603.           end
  604.         end
  605.       end
  606.     end
  607.   end
  608. endfunction
  609.  
  610. function S=BackTracking(M)
  611.   Cijf=0
  612.   S=M(:,:)
  613.   BR=0
  614.   HO=0
  615.   HM=size(M,1)
  616.   BM=size(M,2)
  617.   if HM==BM then
  618.     sd=sqrt(HM)
  619.   else
  620.     sd=3
  621.   end
  622.   OS=isSudokuOpgelost(M)
  623.   if ~OS
  624.     for v=1:sd:HM-sd+1
  625.       for w=1:sd:BM-sd+1
  626.         OCDS=ontbrekendeCijfers(M(v:v+sd-1,w:w+sd-1))
  627.         rij=v
  628.         kol=w
  629.         LOCDS=length(OCDS)
  630.         while ~OS&OCDS~=zeros(1,LOCDS)
  631.           R=M(:,:)
  632.           T=%T
  633.           for i=1:length(OCDS)
  634.             if T&OCDS(i)>0 then
  635.               Cijf=OCDS(i)
  636.               OCDS(i)=0
  637.               T=%F
  638.             end
  639.           end
  640.           T=%T
  641.           for i=0:sd-1
  642.             for j=0:sd-1
  643.               if T&R(v+i,w+j)==0 then
  644.                 R(v+i,w+j)=Cijf
  645.                 BR=w+j
  646.                 HO=v+i
  647.                 T=%F
  648.                 printf("Het Random cijfer %d werd ingevuld in het vakje (%d,%d).\n",Cijf,HO,BR)
  649.               end
  650.             end
  651.           end
  652.           VC=1
  653.           TR=alleCijfersAanwezig(R(HO,:))
  654.           if TR then
  655.             TR=alleCijfersAanwezig(R(:,BR))
  656.           end
  657.           while ~OS&VC>0&TR
  658.             VC=totaalOpenCijfers(R)
  659.             R=BlijvenProberen(R)
  660.             R=RijenInvullen(R)
  661.             R=KolommenInvullen(R)
  662.             R=SegmentenInvullen(R)
  663.             VC=VC-totaalOpenCijfers(R)
  664.           end
  665.           OS=isSudokuOpgelost(R)
  666.           LOCDS=LOCDS-1
  667.           if ~OS then
  668.             printf("Het Random cijfer %d is een slechte oplossing.\n",Cijf)
  669.           elseif OS then
  670.             printf("Het cijfer %d in het vakje (%d,%d) is een goede oplossing.\n",Cijf,HO,BR)
  671.           end
  672.         end
  673.       end
  674.     end    
  675.   end
  676.   if OS then
  677.     S=R(:,:)
  678.   end
  679. endfunction
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!