Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

suduko matrix generator in Pascal

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
jfigueras

Joined: 02 Dec 2005
Posts: 7
:
Location: Orleans, MA

Items
PostPosted: Fri Dec 02, 2005 10:09 pm    Post subject: suduko matrix generator in Pascal Reply with quote

The following code in Delphi Pascal generates a Suduko matrix with 3x3 submatrices filled randomly with numerals 1..9. It is a brute-force program. On my Dell 8500 laptop, the program generates a Suduko matrix in about 20 milliseconds (averaged over a cycle of 100 trials).

The program assigns a given numeral (from 1 to 9) randomly to each of the 3x3 submatrices and uses available,a 9x9 boolean matrix, to control access to pertinent rows and columns containing the assigned values (since a new value cannot be entered into any row or column that already contains an occurence of the value). The boolean matrix is refreshed for placement of the next new digit. The assigned values are entered into theTable, a 9x9 array of integers. Selection of the 3x3 arrays contained in theTable is through the upper left corner of the sub-arrays; the row-column locations of these corners are contained in two arrays, Roffset and Coffset. Pairs of values from these two arrays define the location of a particular 3x3 sub-array.

To generate a random location inside a 3x3 array, a random number k with a value from 1 to 9 (inclusive) is generated and relative row-column indices are computed from the random number using the equations Col:= (k-1) div 3 and Row := 3*Col-1. These values are added to the Row-Col offsets to generate the Row-Col location inside the given 3x3 array and also the location relative to the major 9x9 array. (The indexing problem was the greatest stumbling block in formulating the program). The random location so selected is accepted provided the location is empty (previous assigned value is zero) and has not been excluded by a FALSE entry in the available array. If these conditions are met, all entries in the row and column of available corresponding to the new element are set to FALSE. If these conditions are not met, a new random number is tried.

Many of the attempts to place an element fail because all candidate locations are blocked, either by previous assignments or by entries in the available array. The key element in the program that provides iteration to a successful trial is contained in the repeat...until loop where locations are generated. A counter keeps track of the number of iterations, and when it has reached a large value (arbitraily taken as 50 in the program--a wild guess), the program gives up on the current table and restarts the computation (by means of a GOTO command). If the program successfully escapes the GOTO, it ends by filling the display matrix (stringGrid1, a Delphi-provided data structure).

Considering how often the algorithm fails (my experience before I set up the conditions for iteration) , it is remarkably fast --the longest generation time I observed was 100 milliseconds; the shortest time was 10 milliseconds. As noted previously, the average time is 20 milliseconds.

Code:
unit SuDokuv3;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, Grids,Math;

type
  TForm1 = class(TForm)
    QuitBtn: TButton;
    StringGrid1: TStringGrid;
    procedure QuitBtnClick(Sender: TObject);
    procedure FormCreate(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;
  {These arrays define the corners of the 9 3x3 sub-arrays}
  ROffset : array[1..3] of integer = (1,4,7);
  Coffset : array[1..3] of integer =  (1,4,7);

implementation

{$R *.dfm}

procedure TForm1.QuitBtnClick(Sender: TObject);
begin
   Close
end;

procedure TForm1.FormCreate(Sender: TObject);

var i,j,iRow,iCol,Col,Row,n,k,count : integer;
    value : string;
    flag : boolean;
    theTable : array[1..9,1..9] of integer;
    available : array[1..9,1..9] of boolean;

    label Out;


begin
OUT:
  for i:=1 to 9 do
  for j:=1 to 9 do
    theTable[i,j]:=0;
  for n := 1 to 9 do  {Select a number to be entered into 9 3x3 arrays}
  begin
 {Initialize the boolean table for each new candidate}
    for i := 1 to 9 do
    for j := 1 to 9 do available[i,j] := TRUE;
    for i:= 1 to 3 do
    begin
     iRow:=Roffset[i];
     for j :=1 to 3 do
     begin
       randomize;    {Get a new set of random numbers}
       iCol := Coffset[j];
       count := 0;
       repeat
         count := count+1;
         k:= RandomRange(1,10);
         Col :=(k-1) div 3;
         Row := k-3*Col-1;
         Row :=Row+iRow;
         Col := Col+iCol;
         if count>50 then goto OUT;
       until available[Col,Row] and (theTable[Col,Row]= 0);
      {Block row and column containing n from further entries}
       for k := 1 to 9 do
       begin
         available[Col,k] := FALSE;
         available[k,Row] := FALSE
       end;
       theTable[Col,Row] := n;
     end
    end
  end;
  {If you get this far, a solution was found. Fill in the display table}
  for i:=1 to 9 do
  for j := 1 to 9 do
  begin
    str(theTable[i,j],value);
    stringGrid1.cells[j-1,i-1] := value
  end;
end;
end.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
mrcl

Joined: 01 Dec 2005
Posts: 3
:

Items
PostPosted: Sat Dec 03, 2005 1:27 am    Post subject: Reply with quote

from your description of the program i conclude that it does not generate all possible sudokus with equal probabilita. am i right?
_________________
guenter
Back to top
View user's profile Send private message
jfigueras

Joined: 02 Dec 2005
Posts: 7
:
Location: Orleans, MA

Items
PostPosted: Sat Dec 03, 2005 3:14 pm    Post subject: Suduko matrix generator in Pascal Reply with quote

I suspect that all Suduko matrices are equally probable assuming that the random number generator is unbiassed (which may or may not be true). It is true that the number of iterations required to generate a matrix varied widely. In a series of 10 runs, the number of matrices generated before a correct one emerged varies from 65 to 800.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron