banjalukaforum.com

{
  BHOI2006 Program sudoku
  Resenje: Nemanja Tatic
}
{$mode objfpc} 
program sudoku;
type
  TPoint = record
    X : integer;
    Y : integer;
  end; 
var
  Matrix : array[1..9, 1..9] of integer; //Matrica sa podatcima
  Empty : array[1..81] of TPoint;  //Niz sa kordinatama polja koja nedostaju
  Ends : integer; //Broj Polja koja nedostaju
 
procedure LoadData(FileName : string); //Procedure za ucitavanje
var
  i, j : integer;
  fText : TextFile; 
begin
  AssignFile(fText, Filename);
  Reset(fText);
  for i := 1 to 9 do
    for j := 1 to 9 do
      Read(fText, Matrix[j, i]);
  CloseFile(fText);
end;

procedure SaveData(FileName : string);  //Procedure za ispis matrice
var
  i : integer;
  fText : TextFile;
begin
  AssignFile(fText, FileName);
  Rewrite(fText);
  for i := 1 to 9 do
    Writeln(fText, Matrix[1, i], ' ', Matrix[2, i], ' ', Matrix[3, i], ' ', Matrix[4, i], ' ', Matrix[5, i], ' ',
                   Matrix[6, i], ' ', Matrix[7, i], ' ', Matrix[8, i], ' ', Matrix[9, i]);
  CloseFile(fText);
end;

procedure FillMatrix(Index : integer);  //Glavna rekuzivna procedura
var
  i, j, X, Y : integer;
  List : array[1..9] of boolean;
begin
  if Index > Ends then //Ukoliko se ispune uspjesno sva polja ispisi rezultat i prekini program
    begin
      SaveData('sudoku.out');
      Halt(0);
    end;   
  X := Empty[Index].X; //Iz niza prebacuje kordinate praznog polja u lokalne varijable
  Y := Empty[Index].Y;
  for i := 1 to 9 do List[i] := false; //Resetuje niz na false. To se ocekuje od paskala da sam uradi ali ipak
  for i := 1 to 9 do if Matrix[X, i] > 0 then List[Matrix[X, i]] := true; //Izbacuje br. iz liste koji su u redu
  for i := 1 to 9 do if Matrix[i, Y] > 0 then List[Matrix[i, Y]] := true; //Izbacuje br. iz liste koji su u koloni
  for i := 1 to 3 do  //izbacuje brojeve koji su u sektoru
    for j := 1 to 3 do
      if Matrix[j + (3 * ((X - 1) div 3)), i + (3 * ((Y - 1) div 3))] > 0 then
        List[Matrix[j + (3 * ((X - 1) div 3)), i  + (3 * ((Y - 1) div 3))]] := true;
  for i := 1 to 9 do if not List[i] then
    begin           
      if Index < Ends then Matrix[Empty[Index + 1].X, Empty[Index + 1].Y] := 0;  //Brise sledeci iz Empty jer
      //kombinacija nije uspela i vraca se na proslu procedure a svakoj sledecoj njen bi argument smetao a nije potreban
      Matrix[X, Y] := i; //Sa svakim prolazom popunjava polje po redu iz liste kojeg nema u koloni, redu i sektoru
      FillMatrix(Index + 1);  //Procedura poziva samu sebe, a kao argment uzima sledeci broj iz Empty liste
    end; 
end; 

procedure CreateEmptyList;  //Ubacuje u Empty listu sva polja koja nisu definisana
var
  i, j : integer;
begin
  Ends := 0;
  for i := 1 to 9 do
    for j := 1 to 9 do
      if Matrix[j, i] = 0 then
        begin
          Ends := Ends + 1;
          Empty[Ends].X := j;
          Empty[Ends].Y := i;
        end;
end; 

begin
  LoadData('sudoku.in');
  CreateEmptyList;
  FillMatrix(1);
end.