| jfigueras
| Joined: 02 Dec 2005 | Posts: 7 | : | Location: Orleans, MA | Items |
|
Posted: Fri Dec 02, 2005 10:09 pm Post subject: suduko matrix generator in Pascal |
|
|
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. |
|
|