Sudoku solver program, do it like a human!

[audioinstinct]

Hi everyone. I'm writing a sudoku solving program just for fun currently in free pascal. I don't use any objects, I'm really inexperienced with OOP, and due to the complexity of the problem, I'm skipping on them currently. Later I will get into it, but I'll start with easier programs, because this turns out to be a pretty hard one.

This program doesn't use a Gauss elimination or brute forces it way through the Sudoku to find a pattern that matches the original clues, that's way too boring. I've decided that I'd rather implement very humanlike strategies in it. As I consider myself a decent Sudoku solver, I'm familiar with the concepts and strategies, and making a program doing them is quite challenging.

Here's how it works:

The 9x9 Grid is a Matrix, defined liked this in the program:




Type

Cell=Record

Number_of_Candidates:smallint;
Candidates:array[1..9] of smallint;
Solved: Boolean;

end;

Var

Grid:array[1..9,1..9] of Cell;



Now here's how it works...

First, the User inputs the clues line by line, and 0 means there is no clue in that particular cell, these are the cells the program will have to solve.

I don't yet have any procedure or function which checks the validity of the Sudoku, I'm currently using Sudokus for tests that I know to be valid, and will later care about error checking.

When the Grid is read, first the program calculates all the possible candidates for each cell, and then the fun begins.

First, it checks for "Naked Singles". These are cells, that only have one possible candidate remaining, therefore, the solution of these are certain.
After this, it checks for Hidden Singles. These are candidates that only exist in a house(row, column, or box) only once. Since every house must contain 1 of each, these must be solutions.

Each time the program finds a solution, it reevaluates the candidates. This is necessary first to avoid errors, and secondly to not make it go through unnecessary processes.

If no more naked or hidden singles can be found, it gets into the more advanced methods in this order: naked pairs, hidden pairs, pointing pairs, box-line reductions, X-wings, XY-wings.

When I've made my first post, I was struggling with coding the XY-wing process, but it's already done, altough it's pretty much an overkill of a procedure that loops about 80000 times, but I didn't really find any way around this.

Here's how an XY-wing works:

You have a Hinge Cell, and two Wing Cells. Each Cell contain only two possible candidates, and these are related in a way like this: (a,b) (a,c) and (b,c). Which Cell is the Hinge and which the Wings are determined by the position of the Cells, because the Hinge can "see" both Wings, but the Wings can't see each other. This means that if the Hinge is (a,b), one Wing is (a,c) and the other is (b,c) then one of the wings must be a c. If the Hinge is a, then the first one must be a c, if it is a b, then the other must be a c. So then, from all the cells that both wings can see, c can be eliminated as a candidate. Now I don't know if there is a simple way to program that, my way is definitely not simple, but it works, and since the actual comparison and process is short, it still runs like a charm in less than a second despite the huge number of loops. Basically, I read the data of all the cells with two candidates into a two dimensional array and check for every possible combination of three of them whether they are valid or not, and if they do, then I call the elimination for the necessary cells.

Now all this was pretty unrelated to my question, it was just to demonstrate you how my program works in short and what I'm currently capable of programming.

Basically, I want to expand my program a bit because it still can't solve the hardest Sudokus. First I will add Triples, Quads, Simple Coluring, and XY-chains. Now I don't really have an issue with triples and quads, they work the same as pairs, it's only going to take longer to write it and that's all. Now with coluring and chains, that's a whole different story though because these are not so easily defined as the former methods, on a grid. There won't really be a "one way to go about it" for the program. It also must ignore possibilities meanwhile that might confuse the procedure and make it unnecessarily long. I have come across solvers that use these methods flawlessly so it's definitely not something impossible to code.

I'll provide a link of these strategies, and I'm just going to ask the question, is it sensible for me to try and code these strategies without the use of objects? I feel like I can't sidestep them anymore unless I really want my program to loop for even more, and I don't want that. It's ugly already as it is, the reason I haven't pasted the entire code here is because you probably wouldn't understand it. Not because it's so complex but because it's so damn ugly with sometimes 10 or more consecutive "end;"s in some procedures, not to mention the 5 or even more "for loops" and the other things that would make any serious programmer cry themselves to sleep if they looked at my code :D

Links:
http://www.sudokuwiki.org/Singles_Chains
http://www.sudokuwiki.org/XY_Chains

Thanks, in advance, peace

[SilverWarior]

Making program to solve Sudoku like a human is far from being easy. So if you are novice programmer this might be a bit to much for you now. Now I don't say tht you can't do it but only that it won't be eazy. And if you are not stubbern enough I'm afraid that you might quit in the middle. Belive me I know becouse I was in your position about 5 years ago becouse I was trying to do something that was way beyond my knowledge at that time.

Anywhay the simpliest way to program Sudoku solver is by searching for posible candidates and then eliminating singles which you already implemented I belive. Now what you lack is what to do when there are no more signles.

So what do you do when you encounter situation when there are no singles? At this time you are on a crossroad with multiple choices. So you have to chose one. But which one is correct. You can't know this unless you test it out. Now the advantage of computers is that at any time you can save curent state of your Sudoku. And this is what you do when you come to this crossroads.
You save current state of your sudoku and then in one cell that has only two candidates you chose one of them. After that you try to solve the sudoku till the end. If you can't (you come to a unsolvable state) then you revert to the previosly saved state and chose other candidate from thet cell.
This approach guaratees you to solve any Sudoku. And if yo are interested in speeding this process up you can tgest both posibilities after encountering a crossroad concurently each in its own thread - requires good knowledge on multithreading and thread sycronizations).

I belive I must still have the code for this somewhere on my old laptop but to be honest I wouldn't show it to anyone as it is quite awfull. Probably much similar to your code :D

Anywhay if you are really interested in making Sudoku solver which will be solving it much like a human I recomend you learn about making decision trees becouse this will allow you to make much nicer code.
As for the need to use objects to make this Sudoku solver I don't think they are required.

[audioinstinct]

Making program to solve Sudoku like a human is far from being easy. So if you are novice programmer this might be a bit to much for you now. Now I don't say tht you can't do it but only that it won't be eazy. And if you are not stubbern enough I'm afraid that you might quit in the middle. Belive me I know becouse I was in your position about 5 years ago becouse I was trying to do something that was way beyond my knowledge at that time.

Anywhay the simpliest way to program Sudoku solver is by searching for posible candidates and then eliminating singles which you already implemented I belive. Now what you lack is what to do when there are no more signles.

So what do you do when you encounter situation when there are no singles? At this time you are on a crossroad with multiple choices. So you have to chose one. But which one is correct. You can't know this unless you test it out. Now the advantage of computers is that at any time you can save curent state of your Sudoku. And this is what you do when you come to this crossroads.
You save current state of your sudoku and then in one cell that has only two candidates you chose one of them. After that you try to solve the sudoku till the end. If you can't (you come to a unsolvable state) then you revert to the previosly saved state and chose other candidate from thet cell.
This approach guaratees you to solve any Sudoku. And if yo are interested in speeding this process up you can tgest both posibilities after encountering a crossroad concurently each in its own thread - requires good knowledge on multithreading and thread sycronizations).

I belive I must still have the code for this somewhere on my old laptop but to be honest I wouldn't show it to anyone as it is quite awfull. Probably much similar to your code :D

Anywhay if you are really interested in making Sudoku solver which will be solving it much like a human I recomend you learn about making decision trees becouse this will allow you to make much nicer code.
As for the need to use objects to make this Sudoku solver I don't think they are required.

Hey, thanks for the reply, now some of the things I have mentioned were probably not well explained in my post so I will try to elaborate.

I really want to avoid the decision tree type of solution, that would be pretty much brute forcing through the puzzle. I'm pretty confident in that I could write that, there's no fun in that though, I like challenges to improve my scope as a hobby-programmer. Now with the extremely hard sudokus, even humans are left with very complicated methods. Some of these techniques include the 3D Medusa for example, or the Death Blossom, they're really hard to spot, let alone execute for an inexperienced sudoku solver. I don't plan on implementing those, because for 99.9% of the puzzles they are not needed.

What I do want to do however is the easier methods. Pairs, X-wings and XY-wings are already completed in my program. You know what? I'm just going to paste the XY-wing method here... I will add some comments to the code so you don't have to go through everything in it, because it really is a big mess...



Type

TCoord=array[1..2] of smallint; //There are lots of way I use this in the program

TBox=array[1..3,1..3] of TCoord;


TCell=array[1..4] of smallint;

{The first element of the array stores the row number of the cell. The second, the column number.
The third and the fourth are the two possible candidates in that cell }

TArr=array[1..6] of smallint;

TPointCell=^TCell;

TPossibles=array[1..81] of TCell;
Cell=Record

Solved:boolean;
Candidates:array[1..9] of smallint;
Num_of_Candidates:smallint;

end;

Var

Grid:array[1..9,1..9] of Cell;
Finished:integer;
{Why is this integer? I was getting unexplainable and weird errors when the function was boolean.
It stored weird stuff like "0x4ecwhatever" instead of "true" or "false" and somehow it works with integer... weird }

Have_Result:Boolean;

Function GetBox(x,y:smallint):TBox;

{What this function does is it returns a 3x3 size Box for every x,y coordinate, or if y is set to 0, then box #x.
Boxes are numbered 1-9 from left to right, up to bottom like this:

1 2 3
4 5 6
7 8 9 }

var

i,j:smallint;

Begin

if y<>0 then

begin

for i:=1 to 3 do

begin

for j:=1 to 3 do

begin

if x<=3 then GetBox[i,j][1]:=i
else
if x>6 then GetBox[i,j][1]:=i+6
else
GetBox[i,j][1]:=i+3;


if y<=3 then GetBox[i,j][2]:=j
else
if y>6 then GetBox[i,j][2]:=j+6
else
GetBox[i,j][2]:=j+3;

end;

end;

end

else

begin

if x=1 then

begin

for i:=1 to 3 do

begin

for j:=1 to 3 do

begin

GetBox[i,j][1]:=i;
GetBox[i,j][2]:=j;

end;

end;

end

else
if x=2 then

begin

for i:=1 to 3 do

begin

for j:=1 to 3 do

begin

GetBox[i,j][1]:=i;
GetBox[i,j][2]:=j+3;

end;

end;

end

else
if x=3 then

begin

for i:=1 to 3 do

begin

for j:=1 to 3 do

begin

GetBox[i,j][1]:=i;
GetBox[i,j][2]:=j+6;

end;

end;

end

else
if x=4 then

begin

for i:=1 to 3 do

begin

for j:=1 to 3 do

begin

GetBox[i,j][1]:=i+3;
GetBox[i,j][2]:=j;

end;

end;

end

else
if x=5 then

begin

for i:=1 to 3 do

begin

for j:=1 to 3 do

begin

GetBox[i,j][1]:=i+3;
GetBox[i,j][2]:=j+3;

end;

end;

end

else
if x=6 then

begin

for i:=1 to 3 do

begin

for j:=1 to 3 do

begin

GetBox[i,j][1]:=i+3;
GetBox[i,j][2]:=j+6;

end;

end;

end

else
if x=7 then

begin

for i:=1 to 3 do

begin

for j:=1 to 3 do

begin

GetBox[i,j][1]:=i+6;
GetBox[i,j][2]:=j;

end;

end;

end

else
if x=8 then

begin

for i:=1 to 3 do

begin

for j:=1 to 3 do

begin

GetBox[i,j][1]:=i+6;
GetBox[i,j][2]:=j+3;

end;

end;

end

else

begin

for i:=1 to 3 do

begin

for j:=1 to 3 do

begin

GetBox[i,j][1]:=i+6;
GetBox[i,j][2]:=j+6;

end;

end;

end;

end;

End;


Function BoxCalc(x,y:smallint):smallint;

{This was written early as a quick comparison. I could use the above function too, but I have written this before I realized the above would be necessary later, and I've already had a bunch of procedures using this one, so I've decided to keep it}

Begin

if (x<=3) and (y<=3) then BoxCalc:=1;
if (x>3) and (x<=6) and (y<=3) then BoxCalc:=2;
if (x>6) and (y<=3) then BoxCalc:=3;
if (x<=3) and (y>3) and (y<=6) then BoxCalc:=4;
if (x>3) and (x<=6) and (y>3) and (y<=6) then BoxCalc:=5;
if (x>6) and (y>3) and (y<=6) then BoxCalc:=6;
if (x<=3) and (y>6) then BoxCalc:=7;
if (x>3) and (x<=6) and (y>6) then BoxCalc:=8;
if (x>6) and (y>6) then BoxCalc:=9;

end;


Function Candidate_Exists(x,y,cand:smallint):boolean;

{This is simple, it checks if a candidate is possible on an unsolved cell. It's very useful and pretty much necessary}

var

i,j:smallint;

check:boolean;

Begin

check:=false;

for i:=1 to Grid[x,y].Num_of_Candidates do

begin

if Grid[x,y].Candidates[i]=cand then check:=true;

end;

Candidate_Exists:=check;

End;


Function Cells_Collide(x1,y1,x2,y2:smallint):string;

{A key function for the XY-wing. This checks if two cells can see each other and what house they share.
This latter is not too important XY-wing wise, but I do use it in other procedures too.}

Begin

if (x1=x2) and (y1=y2) then Cells_Collide:='null'
else
if x1=x2 then Cells_Collide:='row'
else
if y1=y2 then Cells_Collide:='column'
else
if BoxCalc(x1,y1)=BoxCalc(x2,y2) then Cells_Collide:='box'
else
Cells_Collide:='null';


End;

Procedure Eliminate(x,y,cand:smallint);

{This is just a simple procedure to save me some typing}

var

i,j:smallint;

Begin


if Candidate_Exists(x,y,cand) then

begin

for i:=1 to Grid[x,y].Num_of_Candidates do

begin

if Grid[x,y].Candidates[i]=cand then

begin

Grid[x,y].Candidates[i]:=Grid[x,y].Candidates[Grid[x,y].Num_of_Candidates];
Grid[x,y].Candidates[Grid[x,y].Num_of_Candidates]:=0;
Grid[x,y].Num_of_Candidates:=Grid[x,y].Num_of_Candidates-1;

Have_Result:=True;

end;

end;

end;

End;




Function Num_of_Cands(arr:TArr;Cand:smallint):smallint;

{This is also very simple and specific. If three cells all have 2 candidates and I read ALL candidates into an array,
and each candidate only has an incidence of two,
then they can not be other than (a,b) (b,c) and (a,c) since one candidate can not reside twice in any of the cells.
An XY-wing works with cells like this, so this is to check that}

var

i:smallint;

base:smallint;

Begin

base:=0;

for i:=1 to 6 do

begin

if arr[i]=Cand then base:=base+1;

end;

Num_of_Cands:=base;

End;

Function ValidCandidates(Square1,Square2,Square3:TCell):Boo lean;

{This uses the above method to check for possibly valid XY-wings }

var

i:smallint;

base:boolean;

Candidates:array[1..6] of smallint;

Begin

base:=false;

Candidates[1]:=Square1[3];
Candidates[2]:=Square1[4];

Candidates[3]:=Square2[3];
Candidates[4]:=Square2[4];

Candidates[5]:=Square3[3];
Candidates[6]:=Square3[4];

if ( Num_of_Cands(Candidates,Square1[3])=2 ) and (Num_of_Cands(Candidates,Square1[4])=2 ) then

if ( Num_of_Cands(Candidates,Square2[3])=2 ) and (Num_of_Cands(Candidates,Square2[4])=2 ) then

if ( Num_of_Cands(Candidates,Square3[3])=2 ) and (Num_of_Cands(Candidates,Square3[4])=2 ) then

base:=true;

ValidCandidates:=base;

End;


Function ValidPosition(Square1,Square2,Square3:TCell):small int;

{This function checks if the position of the cells are good to form an XY-wing.
If it is valid, it also returns which one will be the Hinge, and which two the Wings.
Which wing will be wing 1 or wing 2 is fortunately irrelevant so I don't really have to deal with that.
If it is not valid, it returns a 0}

Var

base:smallint;

x1,x2,x3:smallint;

y1,y2,y3:smallint;



Begin

base:=0;

x1:=Square1[1];
y1:=Square1[2];

x2:=Square2[1];
y2:=Square2[2];

x3:=Square3[1];
y3:=Square3[2];



if (Cells_Collide(x1,y1,x2,y2)<>'null') and (Cells_Collide(x1,y1,x3,y3)<>'null') and (Cells_Collide(x2,y2,x3,y3)='null')

then base:=1

else

if (Cells_Collide(x1,y1,x2,y2)<>'null') and (Cells_Collide(x1,y1,x3,y3)='null') and (Cells_Collide(x2,y2,x3,y3)<>'null')

then base:=2

else

if (Cells_Collide(x1,y1,x2,y2)='null') and (Cells_Collide(x1,y1,x3,y3)<>'null') and (Cells_Collide(x2,y2,x3,y3)<>'null')

then base:=3

else

base:=0;

ValidPosition:=base;

End;

Function Common_Candidate(Square1,Square2:TCell):smallint;

{This function will be called when a valid XY-wing is found to determine which candidate should be removed from particular cells
Obviously, it's going to be the one that the two Wings share.}

var

i:smallint;

base:smallint;

arr:TArr;

Begin

arr[1]:=Square1[3];
arr[2]:=Square1[4];

arr[3]:=Square2[3];
arr[4]:=Square2[4];

arr[5]:=0;
arr[6]:=0;

for i:=1 to 2 do

begin

if Num_of_Cands(arr,arr[i])=2 then base:=arr[i];

end;

Common_Candidate:=base;

End;

{And finally, here's the actual procedure}

Procedure Find_XY_Wing;


Var


i,j:smallint;

count:integer;

tries1,tries2,tries3:integer;

remove:smallint;

Point1: TPointCell;
Point2: TPointCell;
Point3: TPointCell;

Cell1: TCell;
Cell2: TCell;
Cell3: TCell;

Hinge: TCell;
Wing1: TCell;
Wing2: TCell;

Possibles:TPossibles;


Begin

// Nullify everything and set pointers

Have_Result:=false;


for i:=1 to 4 do

begin

Cell1[i]:=0;
Cell2[i]:=0;
Cell3[i]:=0;

Hinge[i]:=0;
Wing1[i]:=0;
Wing2[i]:=0;

Point1:=@Cell1;
Point2:=@Cell2;
Point3:=@Cell3;

end;

//Fill in Possibles and determine number of pairs;

count:=1;

for i:=1 to 9 do

begin

for j:=1 to 9 do

begin

if Grid[i,j].Num_of_Candidates=2 then

begin

Possibles[count][1]:=i;
Possibles[count][2]:=j;

Possibles[count][3]:=Grid[i,j].Candidates[1];
Possibles[count][4]:=Grid[i,j].Candidates[2];

count :=count+1;

end;

end;

end;


//Check for all possible combination of the pairs on the Grid whether they're valid XY-wings or not. This is loop land...

for tries1:=1 to count do

begin

Point1^:=Possibles[tries1];

for tries2:=1 to count do

begin

if tries2<>tries1 then

begin

Point2^:=Possibles[tries2];

for tries3:=1 to count do

begin

if (tries3<>tries1) and (tries3<>tries2) then

begin

Point3^:=Possibles[tries3];

//Now all pairs have a unique pointer

//Check if they form an XY-Wing based on Candidates and Position

if (ValidCandidates(Point1^,Point2^,Point3^)) and (ValidPosition(Point1^,Point2^,Point3^)<>0) then

begin

if ValidPosition(Point1^,Point2^,Point3^)=1 then

begin

Hinge:=Point1^;
Wing1:=Point2^;
Wing2:=Point3^;

end

else

if ValidPosition(Point1^,Point2^,Point3^)=2 then

begin

Hinge:=Point2^;
Wing1:=Point1^;
Wing2:=Point3^;

end

else

begin

Hinge:=Point3^;
Wing1:=Point1^;
Wing2:=Point2^;

end;

//The XY-Wing is set if found

remove:=Common_Candidate(Wing1,Wing2); //This Candidate will be eliminated

//Go through the grid and find cells from which the candidate should be eliminated

for i:=1 to 9 do

begin

for j:=1 to 9 do

begin

If ( Cells_Collide(i,j,Wing1[1],Wing1[2])<>'null' ) and (Cells_Collide(i,j,Wing2[1],Wing2[2])<>'null' ) then

begin

//Elimination

Eliminate(i,j,remove);

end;

end;

end;

//End of Grid Check

end;

//End of XY-Wing Check

end;
end;
end;
end;
end;

//End of try loop

Point1:=nil;
Point2:=nil;
Point3:=nil;

//Clearing pointers

End; //End of Procedure



Now belive it or not, this mess does work very well, and I didn't even have to debug it too much, there were some minor issues with the basic functions, but not the main procedure.

Here's a picture of what is happening here:

http://www.pascalgamedevelopment.com/attachment.php?attachmentid=1334&stc=1

Now this procedure works perfectly, my problem is the one step more advanced things such as Simple Chains and XY-Chains (entirely different from XY-wings...) Right now I have some pretty nasty exams so I don't even really have time, I just started this topic so I could get help for problems arising. This solver is pretty neat already, it can solve many sudokus, when I'm going to start implementing the more advanced stuff into it, I'm pretty sure I will come back with more specific questions.

[audioinstinct]

Making program to solve Sudoku like a human is far from being easy. So if you are novice programmer this might be a bit to much for you now. Now I don't say tht you can't do it but only that it won't be eazy. And if you are not stubbern enough I'm afraid that you might quit in the middle. Belive me I know becouse I was in your position about 5 years ago becouse I was trying to do something that was way beyond my knowledge at that time.

Anywhay the simpliest way to program Sudoku solver is by searching for posible candidates and then eliminating singles which you already implemented I belive. Now what you lack is what to do when there are no more signles.

So what do you do when you encounter situation when there are no singles? At this time you are on a crossroad with multiple choices. So you have to chose one. But which one is correct. You can't know this unless you test it out. Now the advantage of computers is that at any time you can save curent state of your Sudoku. And this is what you do when you come to this crossroads.
You save current state of your sudoku and then in one cell that has only two candidates you chose one of them. After that you try to solve the sudoku till the end. If you can't (you come to a unsolvable state) then you revert to the previosly saved state and chose other candidate from thet cell.
This approach guaratees you to solve any Sudoku. And if yo are interested in speeding this process up you can tgest both posibilities after encountering a crossroad concurently each in its own thread - requires good knowledge on multithreading and thread sycronizations).

I belive I must still have the code for this somewhere on my old laptop but to be honest I wouldn't show it to anyone as it is quite awfull. Probably much similar to your code :D

Anywhay if you are really interested in making Sudoku solver which will be solving it much like a human I recomend you learn about making decision trees becouse this will allow you to make much nicer code.
As for the need to use objects to make this Sudoku solver I don't think they are required.

Oh man, I just see that for some reason my reply didn't get posted. Well, anyway. Short story is that I don't feel like doing this decision tree method, because the goal is not really to write a program that can solve any sudoku, I could do that, I'm confident in that, it's not that hard. The goal is to implement the human-like strategies, so that later when I do a visual interface for it, it can actually show you how to solve it.

I'm not really stuck when there are no more singles, as I've said, I've already written quite a few methods for this. The most complicated one is the XY-Wing, which is a real mess if you looked at the code, you'd see, but it does work, and it is fast thanks to that I used pointers for the arrays. So even if it has to loop for 80000 times, not only this procedure alone, but the entire solution takes less than a second, if it is easy enough that the XY-wing is the most advanced strategy required for the solution.

Where I am really stuck is when I'd need the program do something, that is called "Chaining" in sudoku strategy. This is not based on general rules and different formations on the grid like the X-wing, or XY-wing. These strategies work with assumptions.

For example I choose a Cell where only 2 candidates are left, and I follow a chain with strong links, so I pretty much only care about cells that only have 2 candidates, and my target cells are going to be cells that are seen by multiple cells with strong links. So first I choose a candidate, and follow the chain. Then I choose the second candidate and follow the chain. If at any cell on the grid, there is a match between the two chains(e.g. a cell can not take a value, or a cell takes a value in both cases), then that must be correct. This is called an XY-chain, it is one of the more advanced strategies that are required to solve the hardest puzzles.

Another idea is a bit more simple, it's called Simple coluring, or Singles chaining. In this case, we only pay attention for one candidate, and search for cells that are linked strongly together. Strong link between two cells mean that for at least one candidate they are the only two cells in a house(row, column, or box). Why this is important is because we know for sure that one of them HAS to take the value of that candidate. So I can follow these strong links for this one candidate and assign a colour to each cell inside the chain, one for a colour "A" and one for a colour "B". And then I can draw the consequences, we know that either all cells coloured "A" are correct, or all cells coloured "B" are correct, there is no way some of "A" and some of "B" could be correct it would lead to a contradiction. So if an uncoloured cell sees two cells with different colours, then that candidate can not exist there. Or, for example if two cells of the same colour share a house, then we know that this colour can not be the solution, the other colour has to be correct.

This sounds a bit complicated, but it's actually very easy for a human to applicate, it's a bit more tough to code it though, especially the XY-Chains, because those can involve "weak links" , and the program would have to be able to differentiate between strong and weak links and how to use both of them too, this is crucial, or else it will start searching for completely useless chains, so to make it efficient, there is a bit of theory the program needs to "know".

[SilverWarior]

There are two reasons why I sugested the above mentioned approach.
1. While implementing a simple algorithm that is capable of solving sudoku like I sugested above is probably to easy for you ;) having that in your program might actually be usefull when designing your more advanced algorithms becouse it gives you the ability to compare the results which I belive could quickly alow you to find errors in your more advanced algorithms.
2. My knowledge on solvig sudoku is more or les basic. When you are mentioning all those advanced aproaches for solving sudoku it is simply giving me a headacke becouse I probably have never used them or perhaps did used them without being aware of it :D

Anywhay as I sad my knowledge on sovig Sudoku is prety limited. I have been taught the verry basics of solving the Sudoku from my mother. But later I actually learned a bit more, especially about searching for singles, from studying a soruce code for a sudoku solver that is written in pascal (using Delphi) and has been posted on Delphi.About comunity by Ron Malizia but I can't find it anymore.
Ron Malizia's sudoku solver gratly influenced the way how I did mine. Later on I trued to improve mine even further by adding support for multithreading and provide a way for 4 by 4 sudoku. Now if my memory serves me corectly I have sucsesfully implemented 4 by 4 sudoku solver but I failed on multithreading support becouse my knowledge on that matter was just to weak at the time (I kept corrupting my data and the biggest mistake was accesing VCL from other threads).

So in short I probably won't be of to much help to you unless I learn how to use all these advanced approaches myself :(

EDIT: As for your post not being seen after you have posted it. I suggest that next time you try to refresh the webpage before asuming the post wasn't posted. PGD site is being hosted from multiple synchronized servers to provide load balancing capability and sometimes it happens that all the servers might not be in perfect sync therefore your post is still not seen.
Unfortunately we don't have direct controll on this as it is being controlled by our site host (GoDaddy) so we can't debug the main cause for this. Fortunately these ocurances are quite rare. Infact I belive it has been almost a yer since such thing was last reported.
EDIT2: I just noticed that the reason why your post wasn't seen is becouse it was waiting for moderation. That shouldn't have happen since you are already a full member. I will report this isue to the site Admin so we can figure out why this happened.

[audioinstinct]

There are two reasons why I sugested the above mentioned approach.
1. While implementing a simple algorithm that is capable of solving sudoku like I sugested above is probably to easy for you ;) having that in your program might actually be usefull when designing your more advanced algorithms becouse it gives you the ability to compare the results which I belive could quickly alow you to find errors in your more advanced algorithms.
2. My knowledge on solvig sudoku is more or les basic. When you are mentioning all those advanced aproaches for solving sudoku it is simply giving me a headacke becouse I probably have never used them or perhaps did used them without being aware of it :D

Anywhay as I sad my knowledge on sovig Sudoku is prety limited. I have been taught the verry basics of solving the Sudoku from my mother. But later I actually learned a bit more, especially about searching for singles, from studying a soruce code for a sudoku solver that is written in pascal (using Delphi) and has been posted on Delphi.About comunity by Ron Malizia but I can't find it anymore.
Ron Malizia's sudoku solver gratly influenced the way how I did mine. Later on I trued to improve mine even further by adding support for multithreading and provide a way for 4 by 4 sudoku. Now if my memory serves me corectly I have sucsesfully implemented 4 by 4 sudoku solver but I failed on multithreading support becouse my knowledge on that matter was just to weak at the time (I kept corrupting my data and the biggest mistake was accesing VCL from other threads).

So in short I probably won't be of to much help to you unless I learn how to use all these advanced approaches myself :(

EDIT: As for your post not being seen after you have posted it. I suggest that next time you try to refresh the webpage before asuming the post wasn't posted. PGD site is being hosted from multiple synchronized servers to provide load balancing capability and sometimes it happens that all the servers might not be in perfect sync therefore your post is still not seen.
Unfortunately we don't have direct controll on this as it is being controlled by our site host (GoDaddy) so we can't debug the main cause for this. Fortunately these ocurances are quite rare. Infact I belive it has been almost a yer since such thing was last reported.
EDIT2: I just noticed that the reason why your post wasn't seen is becouse it was waiting for moderation. That shouldn't have happen since you are already a full member. I will report this isue to the site Admin so we can figure out why this happened.

Yeah about my post it was interesting. It told me my post had been posted successfully and it would redirect me, it didn't mention any moderation stuff, but it also didn't appear and when I refreshed the page it told me I was trying to "duplicate" the post so it wouldn't let me do that, it was really weird, but I thought if I just waited a couple of minutes and resend the information it would post, apparently it didn't, which is understandable, well anyway...

As for the advanced methods I am talking about here, it's tough to just explain it, believe me these are really really simple things. Here's a picture of Simple Colouring...

http://www.pascalgamedevelopment.com/attachment.php?attachmentid=1336&stc=1

As you can see I could start anywhere on this grid but the simple way is this:

If A2=4 then A8 can not be a 4.

If A2=4 then H8 can not be a 4, then H7 must be a 4 then G9 can not be a 4, then C9 must be a 4.

This is simply due to the fact that all rows, columns, and boxes must contain a 4 but only one(strong links). Generally, we can say that if A2 is a 4, then all green coloured 4s are correct and all blue coloured 4s are incorrect.


Now I could start the other way and assume that A2<>4.

What I'd get is the exact opposite, this time all blue 4s would be correct, and all
green ones would be incorrect.

If we look at the grid we can see there are a few 4s that are not coloured green or blue.

We are uncertain about these because we don't have strong links to them.

But we do know that either all greens or all blues are correct, so in box 3 we can see there is a blue and there is a green 4. Since one of these must be correct and the box can only have one 4 inside it, we can conclude that on C7 and on B8 there is no way a 4 can exist.

Surely there are going to be much tougher things, but if I get the hang of how to implement chaining strategies in general into the program, then I will probably do fine on my own. The XY-wing which is already complete also contains two "chains" but they are only two steps long, and it already took me 80000 loops to check the entire grid for it, this approach would be highly inefficient with these chains that can go up to 6 or more links, I could imagine something like 9^12 loops with my original approach, absolutely insane, this should be avoided. The reason is that with the XY-Wing I had to compare all candidates of all cells that have exactly two candidates, and find 3 of them that form a valid XY-wing. Now with these chains this idea would become very inefficient, I need a different approach.

[audioinstinct]

I just posted another reply and this time, it did warn me about moderation. It seems like I can post freely but if I include a picture in the post, a moderator has to approve it.

[phibermon]

You may want to examine developing a Monte Carlo simulation as an alternative solver. I see no reason why a Sudoku solution can't be derived using the technique and in fact as a learning exercise I'd highly recommend it.

[audioinstinct]

You may want to examine developing a Monte Carlo simulation as an alternative solver. I see no reason why a Sudoku solution can't be derived using the technique and in fact as a learning exercise I'd highly recommend it.

Wow that seems super complicated, I've just read it up on wikipedia I have absolutely no idea how I would try to code a method like that. I don't even understand it completely. I'm guessing that in my case it would be a probability distribution problem? So I would have to generate a lot of already solved grids and compare the current state with these? Not sure if I'm getting this right...

[SilverWarior]

I just posted another reply and this time, it did warn me about moderation. It seems like I can post freely but if I include a picture in the post, a moderator has to approve it.

Hmm that is strange. I will however forward this information to site administrator.

[audioinstinct]

Hmm that is strange. I will however forward this information to site administrator.

Thanks for that.

Anyway, right now I'm thinking about a recursive approach to build the chain itself, a function would call itself for each candidate from 1-9 and build a chain of strong links which would return an array at the end which I could then easily check for possibilities. Well, it definitely sounds more simple than it is :D, but I think this will be most efficient way because with recursion I can ignore factors such as how many instances of the candidate exists and what's the relation of every single one of them to all the others which would just further complicate and add completely unnecessary loops into the procedure. Aaaand I need to step up my recursion capabilities anyway because I've never really written anything recursive harder than a factorial, lol.

[audioinstinct]

Ugh, this is a mess. I'm seriously considering that I'm rewriting the entire code in Object Pascal right now. I think I'm going to get used to that faster than I get around all the BS I encounter without it and I'm going to need it anyway when I want to create an interface for it. It will be million times easier to do the interface if I have to draw the properties of already existing objects, than to create new ones based on the tremendous amount of data, it would take eons to debug that.

[SilverWarior]

It will be million times easier to do the interface if I have to draw the properties of already existing objects, than to create new ones based on the tremendous amount of data, it would take eons to debug that.

I think that it will be easier to debug that is unless you don't create to big a mess with objects in the first place (yes you can do that).

Anywhay if you will need any help with classes (class inheritence, method inheritance, property inheritance, getter and setter methods of properties, some data reusability with external classes and data forwarding) do let me know and I'll help as best as I can.

[audioinstinct]

I think that it will be easier to debug that is unless you don't create to big a mess with objects in the first place (yes you can do that).

Anywhay if you will need any help with classes (class inheritence, method inheritance, property inheritance, getter and setter methods of properties, some data reusability with external classes and data forwarding) do let me know and I'll help as best as I can.

Well I've started to rewrite it, and now it fails at line 2. Weirdest error I've ever seen. Error code is 216 it says "program received signal sigsegv segmentation fault". I researched this and it seems to mean that my program is trying to refer to a memory address that it is not allowed to, but I have absolutely 0 idea why that is. Here's the code:




{$mode objfpc}

{$m+}

Program SudokuSolverObject;

uses crt;


type

Cell=Class

private

Procedure Eliminate(cand:smallint);

Procedure ReaarangeCandidates;

Function BoxCalc(x,y:smallint):smallint;



public

x,y,box:smallint;

boxnullx,boxnully:smallint;

candidates: array[1..9] of smallint;

num_of_candidates: smallint;

solved:boolean;

constructor create(a,b:smallint);

procedure ClearRow(cand:smallint);

procedure ClearColumn(cand:smallint);

procedure ClearBox(cand:smallint);

procedure Solve(cand:smallint);

End;



VAR

Grid:array[1..9,1..9] of Cell;

Completed:boolean;


Constructor Cell.create(a,b:smallint);

var

i:smallint;

Begin

x:=a;
y:=b;

for i:=1 to 9 do

begin

candidates[i]:=i;

end;

box:=BoxCalc(a,b); //This function is defined before this in the code, I didn't include it because it's not related to the error at all

num_of_candidates:=9;

solved:=false;


if box=1 then

begin

boxnullx:=1;
boxnully:=1;

end
else

if box=2 then

begin

boxnullx:=1;
boxnully:=4;

end
else

if box=3 then

begin

boxnullx:=1;
boxnully:=7;

end
else

if box=4 then

begin

boxnullx:=4;
boxnully:=1;

end
else

if box=5 then

begin

boxnullx:=4;
boxnully:=4;

end
else

if box=6 then

begin

boxnullx:=4;
boxnully:=7;

end
else

if box=7 then

begin

boxnullx:=7;
boxnully:=1;

end
else

if box=8 then

begin

boxnullx:=7;
boxnully:=4;

end
else

begin

boxnullx:=7;
boxnully:=7;

end;

End;

Procedure Cell.Solve(cand:smallint);

var

i:smallint;

Begin

for i:=1 to 9 do

begin

candidates[i]:=0;

{This is the line that gives me the error, but all the other changes do it too, I've tried to switch the orders, any change

to any variable of the classes after they were created throws me this stupid error. I've tried adding "self." before the assignments too, it didn't help.}

end;

num_of_candidates:=1;
solved:=true;

candidates[1]:=cand;

End;

// I have all the other functions and procedures for the class defined as well, but they're not related to this problem.

Procedure ReadGrid;

var

i,j:smallint;

inp:string;

act:smallint;

err:smallint;

Begin

for i:=1 to 9 do

begin

Writeln('Please give me the clues of row # ',i, ' (0 means no clue)');

Readln(inp);

for j:=1 to 9 do

begin

val(inp[j],act,err);

Grid[i,j].create(i,j); //This works just fine, there is no error yet

if act<>0 then //"act" has a valid value, I double-checked it in debug mode, it works fine.

begin

Grid[i,j].Solve(act); //This is the point where the program enters the procedure which gives the error

end;

end;

end;

End;

BEGIN

Writeln('Welcome to Sudoku solver!');

Readgrid;

Readln;

End.



Edit: I've just tried to add a watch to certain points of the Grid before I get the error. It seems that the trouble is deeper than I thought. I get to the point where the class is created, and then it's all weird. If I set the watch like this: Grid[i,j].candidates then it says it is not a structure or union type, whatever the hell that means, and if I set the watch like this: Grid[i][j].candidates then, it tells me this "Can not access memory at 0xe". Wtf is going on here? P.S: I'm administrator on this computer, mine is the only user anyway, and it might be relevant, I'm using Windows 7 as OP system.

Edit2: I've tried running this ridiculously easy program and it failed with the same BS so the problem is even deeper than I thought. Either I screw up the class definitions or it has to do something with the compiler...




{$mode objfpc}

{$m+}

Program wtf;


type

testclass=class

private

datx:integer;

public

dat1:integer;

dat2:integer;

constructor create(d1,d2,dx:integer);

end;


Constructor testclass.create(d1,d2,dx:integer);

Begin

datx:=dx;
dat1:=d1;
dat2:=d2;

End;

Var

what:testclass;

i,j,k:integer;

Procedure Whatthef(a,b,c:integer);

Begin

what.create(a,b,c);

End;

BEGIN

Writeln('Give me the first variable');

Readln(i);

Writeln('Give me the second');

Readln(j);

Writeln('Give me the third');

Readln(k);

Whatthef(i,j,k);

Writeln('The first value was: ', what.dat1);

Writeln('The second value was: ',what.dat2);

Writeln('The third value was private');

Readln;

End.

[SilverWarior]

The problem lies in the way you are creating your classes.
Whenever you are creating classes you use next sytax:


//ClassRefereneVar is variable trhrough which you will be accessing your class
//MyClass is the name of the class you are creating
ClassReferenceVar := MyClass.Create;

So in your case you need to call:


Grid[i,j] := Cell.create(i,j); //Right approach

instead of:


Grid[i,j].create(i,j //Wrong approach

EDIT: Pepole usually add T prefix to class names (TCell insted of just Cell) so that they can be quicly distinguished between normal variables in code.

[audioinstinct]

Haha omg epic fail. Object Pascal 101, well thanks, I hate stupid mistakes like this, because I never guess the problem is something so simple. It runs fine now. I will continue to rewrite the original code with objects tomorrow, and see how it turns out. It's pretty weird though, pascal is always so strict with the syntax, and it allowed me to start the program like that. Basically this means the class it creates points to nothing, so it's no wonder it couldn't access the memory address, oh well, I guess I will get used to it, just takes some time.

[pitfiend]

Haha omg epic fail. Object Pascal 101, well thanks, I hate stupid mistakes like this, because I never guess the problem is something so simple.

Never a mistake is stupid... unless you do the same twice. We learn from mistakes, to do improved versions... in more spectacular failures!


It's pretty weird though, pascal is always so strict with the syntax, and it allowed me to start the program like that.

That's a compiler problem. Never used FPC and not sure if Delphi is able to catch that kind of errors at compile time, I think it warns about uninitialized variables.

If you ever play with pointers, you are going to see weirder things for sure.

[SilverWarior]

That's a compiler problem. Never used FPC and not sure if Delphi is able to catch that kind of errors at compile time, I think it warns about uninitialized variables.

You can make same mistake with Delphi. It also took me quite some time to learn that.

Nof if I'm not mistake this is left in in Objective Pascal as backward compatibility to the verry first days of Objective Pascal when classes still didn't have capability to automatically initialize its own members (internal fields, variables, etc.).

I think I once sow a code that actually makes use of this to delay the initialization of some class members in order to speed up the creation process of the class itself.

But this is pactically not used nowadays becoouse you would usually want for your class to be the decendant of TObject class which provides you with some basic and comonly used functionality like class name property with which you can determine the class type at runtime without the use of extended RTL, then quckly creating of new instances of that particular class etc.

[audioinstinct]

So before I write the code for this method I was thinking I'd ask for a bit of advice here. I don't want to rewrite it later, and my approach is pretty brutal, I get this feeling that there just must be a more efficient way...

First, I will explain the concepts of Hidden Pairs, in Sudoku theory. This is a really simple one.

It means that in a house(row, column or box) TWO candidates both have an incidence of two in that house, and both candidates reside in the same two cells. Currently, there may be other candidates too in these cells.

What does this mean? Well, think about it... We know that both candidates must be somewhere inside that house and we know that each candidate can only occur once.

Let's say we're in row #3, and we have the following situation:

Candidates for position #4: 3 ,4, 6 ,7. Candidates for position # 7: 3 ,4,5,6,8. There is no other cell in this row that contains 3 or 6 as a candidate.

Let's assume that the cell at position #4 is not a 3 or a 6. What does this mean? Well it means that both 3 and 6 would have only one possible place in this row, and that is at position #7. Since a cell can only have one value at a time, we can conclude that the cell at position #4 must be either a 3 or a 6. We can say the same about the cell at position #7.

Now my question is, what do you think would be the most efficient way of finding these? What I have done certainly does work, but I am sure there is an easier or more efficient way. This is how it works right now:




Procedure Find_Hidden_Pairs;

var

i,j:smallint; // i always marks a row and j always marks a column in my code

box:smallint; //boxes are numbered from 1-9 from left to right, up to down.

count1,count2:smallint; //These are the variables for the possible candidates.

candidate:smallint; //This will be used in a short loop to determine which candidates can be eliminated.

TargetCell1,TargetCell2:Cell; //These will be the cells where an elimination will occur

Begin

TargetCell1:=Cell.create(1,1);
TargetCell2:=Cell.create(1,1); //It doesn't matter that yet they have the same properties, I just want to initialize them.

for count1:=1 to 9 do

begin

//Check for Rows

for i:=1 to 9 do

begin

if ( Candidate_Count(count1,i,'row')=2 ) then

//Function Candidate_Count(candidate,housenumber:smallint;hou setype:string):smallint returns how many candidates exist in a house.

begin

for count2:=1 to 9 do

begin

if (count1<>count2) and (Candidate_Count(count2,i,'row')=2) then //We don't want the program to find a 3 that pairs with 3...

begin

TargetCell1.x:=0;
TargetCell2.x:=0;

for j:=1 to 9 do

begin

if ( Candidate_Exists(i,j,count1) )and (Candidate_Exists(i,j,count2) ) then

begin

{Function Candidate_Exists(row,column,candidate:smallint):bo olean Checks if a cell has a possible candidate.

This is necessary because it is possible that 2 candidates only have 2 instances but they reside in more than 2 cells. Such as in a row:

position#1: 1,3 position#2: 5,3 position#3: 4,1. And the other cells don't have 3 or 1 as candidates, now obviously

these don't form pairs}

if TargetCell1.x=0 then

begin

TargetCell1.x:=i;
TargetCell1.y:=j;

end

else

begin

TargetCell2.x:=i;
TargetCell2.y:=j;

end;
end;
end;

if TargetCell2.x<>0 then

begin

for candidate:=1 to 9 do

begin

if (candidate<>count1) and (candidate<>count2) then

begin

Grid[TargetCell1.x,TargetCell1.y].Eliminate(candidate);

Grid[TargetCell2.x,TargetCell2.y].Eliminate(candidate);

end;
end;
end;

end;
end;
end;
end;

//End of Row Checks

{Here would come the column checks and box checks, I won't include because it follows the exact same procedure the box is only slightly

different... sooo....}

//Check for Columns

//Check for Boxes

end;

TargetCell1.done;
TargetCell2.done;

End;



As you can see it is a mass amount of loops going on here, and it looks pretty ugly.

Right now it starts with candidate 1 on each row and if it finds a row where it occurs twice it checks the row for another candidate from 1-9 that occurs twice and if they happen to form a pair then it eliminates the other possibilities, if they don't happen to form a pair, then it will search for another second candidate, and so on, and then it will go to the next row, and if it doesn't find any rows for that candidate then it goes to columns and boxes and then it starts all over again with a starting candidate for 2, and goes on until the pair 9,8 is checked for box 9.

There should be a recursive way or I don't know, anything that won't cause it to go through 5 or 6 for loops just to check one row for 2 candidates. It seems way overkill. Anyone has an idea how can I make this more simple?

[SilverWarior]

In order to reduce the number of loops you are doing I recomend you start using sets for storing the posible candidates instead of arrays. Why? Becouse this way you alow yourself to the use of set operators. In your case you are interested in intersection of two sets as this returns you another set that conatins only those elements that are present in all sets. Yes you can find duplicate elements in multiple sets with a single command.

Check this quick code to see an example of how to do this:


type
TCandidates = set of 1..9;

...

procedure TForm2.Button1Click(Sender: TObject);
var Candidates1, Candidates2, Candidates3: TCandidates;
Duplicates: TCandidates;
Candidate: Integer;
begin
Candidates1 := [3,4,6,7];
Candidates2 := [3,4,5,6,8];
Candidates3 := [4,6];
Memo1.Lines.Add('Intersection between Candidate1 and Candidates2');
Duplicates := Candidates1 * Candidates2;
for Candidate in Duplicates do
begin
Memo1.Lines.Add(IntToStr(Candidate));
end;
Memo1.Lines.Add('Intersection between Candidate1, Candidates2 and Candidates3');
Duplicates := Candidates1 * Candidates2 * Candidates3;
for Candidate in Duplicates do
begin
Memo1.Lines.Add(IntToStr(Candidate));
end;
end;

I belive that using of sets would come quite usefull even in other approaches.

EDIT: In order to be able to use for in loops you need to use Delphi 2005 or newer or FPC 2.4.2 or newer.

EDIT2: And for all those of you who still might be using older Delphi version or other pascal compilers which doesn't support for in loops you first need to declare colection of all posible items in your set and then declare set of that colection like so:


type
TCandidate = 1..9;
TSetOfCandidates = set of TCandidate;

And then you need to loop through your colection of posible items and test for each on if it is present in your set like so:

procedure TForm3.Button1Click(Sender: TObject);
var Candidates: TSetOfCandidates;
Candidate: TCandidate;
begin
Candidates := [1,5,7];
for Candidate := Low(Candidate) to High(Candidate) do
begin
if Candidate in Candidates then Memo1.Lines.Add(IntToStr(Candidate));
end;
end;

Yes this is quite messy and performance ineficient especially if you are working with sets that can have large number of posible elements.
Just imagine you have to loop through a set that can conatin all 16 bit unsigned integer values (all 65536 of them) and you have to test for each to see if it is present in your desired set. Doing something like this could take ages. ;D

[phibermon]

Nof if I'm not mistake this is left in in Objective Pascal as backward compatibility to the verry first days of Objective Pascal when classes still didn't have capability to automatically initialize its own members (internal fields, variables, etc.).

I apologize for nitpicking but it must be stressed that 'Objective Pascal' (A pascal equivalent to Objective-C for using Apple Objective-C interfaces) is something quite different to 'Object Pascal' (What everybody is thinking about)

--

I was going to write a Monte Carlo Sudoku solver for you to demonstrate the principal (The basic premise of a Monte Carlo simulation is to converge upon an answer to a problem by using random sampling (or more generally to determine the probability distribution of an unknown value which in turn can be used to estimate the true value))

However a search online provides an excellent approach to this technique that you can investigate : http://www.lptmc.jussieu.fr/user/talbot/sudoku.html

Before you get your feet too wet, a good learning exercise for the Monte Carlo method is to write a program to estimate the value of Pi by using either the ratio of a circle to a square with a length equal to the diameter of the circle or the more interesting technique which is to code a virtual buffon's needle simulation and measure the ratio of needle samples that cross lines to those that fall between.

One of the most interesting things about Monte Carlo simulations is that they become more accurate (or converge more quickly depending on the class of problem) the more 'random' your random generator is. By using a true random source of a uniform distribution you'll converge on answers more quickly or provide more accurate estimates than if you use the standard pseudo random generator provided in programming libraries. I had fascinating results (Buffon's needle Pi estimator) using a stream of true atomic random numbers as seeds for a pseudo generator. I even gained a whole decimal place of accuracy by feeding in random mouse movements (ensuring you get a good uniform distribution of samples before you re-seed - distribution of random generators and pseudo random generators in general can differ wildly, many are *not* uniform. I know that the FPC random functions are uniformly distributed but I can't vouch for Delphi)

It's truly mind blowing when you get it and it's a lot simpler than it sounds. Plus how cool is it to say you solve sudoku puzzles using the same technique that's used to model nuclear explosions?

[audioinstinct]

I apologize for nitpicking but it must be stressed that 'Objective Pascal' (A pascal equivalent to Objective-C for using Apple Objective-C interfaces) is something quite different to 'Object Pascal' (What everybody is thinking about)

--

I was going to write a Monte Carlo Sudoku solver for you to demonstrate the principal (The basic premise of a Monte Carlo simulation is to converge upon an answer to a problem by using random sampling (or more generally to determine the probability distribution of an unknown value which in turn can be used to estimate the true value))

However a search online provides an excellent approach to this technique that you can investigate : http://www.lptmc.jussieu.fr/user/talbot/sudoku.html

Before you get your feet too wet, a good learning exercise for the Monte Carlo method is to write a program to estimate the value of Pi by using either the ratio of a circle to a square with a length equal to the diameter of the circle or the more interesting technique which is to code a virtual buffon's needle simulation and measure the ratio of needle samples that cross lines to those that fall between.

One of the most interesting things about Monte Carlo simulations is that they become more accurate (or converge more quickly depending on the class of problem) the more 'random' your random generator is. By using a true random source of a uniform distribution you'll converge on answers more quickly or provide more accurate estimates than if you use the standard pseudo random generator provided in programming libraries. I had fascinating results (Buffon's needle Pi estimator) using a stream of true atomic random numbers as seeds for a pseudo generator. I even gained a whole decimal place of accuracy by feeding in random mouse movements (ensuring you get a good uniform distribution of samples before you re-seed - distribution of random generators and pseudo random generators in general can differ wildly, many are *not* uniform. I know that the FPC random functions are uniformly distributed but I can't vouch for Delphi)

It's truly mind blowing when you get it and it's a lot simpler than it sounds. Plus how cool is it to say you solve sudoku puzzles using the same technique that's used to model nuclear explosions?

Thanks, when I'll have more time I'm going to look at it. Problem is that I don't know shit about C, and these variable names like "is" and "jb" are just too confusing, they say nothing about what it means so it makes it even more difficult for me to understand what the program does.

[audioinstinct]

In order to reduce the number of loops you are doing I recomend you start using sets for storing the posible candidates instead of arrays. Why? Becouse this way you alow yourself to the use of set operators. In your case you are interested in intersection of two sets as this returns you another set that conatins only those elements that are present in all sets. Yes you can find duplicate elements in multiple sets with a single command.

Check this quick code to see an example of how to do this:


type
TCandidates = set of 1..9;

...

procedure TForm2.Button1Click(Sender: TObject);
var Candidates1, Candidates2, Candidates3: TCandidates;
Duplicates: TCandidates;
Candidate: Integer;
begin
Candidates1 := [3,4,6,7];
Candidates2 := [3,4,5,6,8];
Candidates3 := [4,6];
Memo1.Lines.Add('Intersection between Candidate1 and Candidates2');
Duplicates := Candidates1 * Candidates2;
for Candidate in Duplicates do
begin
Memo1.Lines.Add(IntToStr(Candidate));
end;
Memo1.Lines.Add('Intersection between Candidate1, Candidates2 and Candidates3');
Duplicates := Candidates1 * Candidates2 * Candidates3;
for Candidate in Duplicates do
begin
Memo1.Lines.Add(IntToStr(Candidate));
end;
end;

I belive that using of sets would come quite usefull even in other approaches.

EDIT: In order to be able to use for in loops you need to use Delphi 2005 or newer or FPC 2.4.2 or newer.

EDIT2: And for all those of you who still might be using older Delphi version or other pascal compilers which doesn't support for in loops you first need to declare colection of all posible items in your set and then declare set of that colection like so:


type
TCandidate = 1..9;
TSetOfCandidates = set of TCandidate;

And then you need to loop through your colection of posible items and test for each on if it is present in your set like so:

procedure TForm3.Button1Click(Sender: TObject);
var Candidates: TSetOfCandidates;
Candidate: TCandidate;
begin
Candidates := [1,5,7];
for Candidate := Low(Candidate) to High(Candidate) do
begin
if Candidate in Candidates then Memo1.Lines.Add(IntToStr(Candidate));
end;
end;

Yes this is quite messy and performance ineficient especially if you are working with sets that can have large number of posible elements.
Just imagine you have to loop through a set that can conatin all 16 bit unsigned integer values (all 65536 of them) and you have to test for each to see if it is present in your desired set. Doing something like this could take ages. ;D

Thanks!! That's a very helpful idea. Indeed, when I'm going to rewrite the XY-wing procedure for example, this will be great. I had a seperate function just so I could calculate the common candidates of two cells, instead with sets this will become really simple, so yeah it definitely will come in handy later on too.

[SilverWarior]

@Phibermon @AirPas

Please keep the conversation about the Phibermons engine in seperate thread as that is off-topci for this one which is about making sudoku solver. Let us keep PGD forums organized shall we.
I can move all posts about your Phibermons engine to another thread. Just say where OK.

[phibermon]

Removed, it's not important :) I'll post about it when I'm ready to. AirPas please feel free to get in touch if you want some more details

[pitfiend]

Wandering the internet today, I found this http://www.sadmansoftware.com/sudoku/solvingtechniques.htm maybe you can found here some other approach to what you want to do.

[User137]

I also have made a sudoku solver, that you can possibly learn from
Lazarus source: https://www.dropbox.com/s/u27owmiqrbmyqj8/sudoku_src.zip?dl=0
Windows binary: https://www.dropbox.com/s/e95blmhhti6nxat/sudoku.zip?dl=0

Actual solver is recursive, nothing human related. Quick and deep scan of all possible choices, it will also display all of them (normal "proper" sudokus are built with only 1 solution though). So if any sudoku has a solution, this will find it.

But there is a bit more that human-like when building a new sudoku from scratch. First it fills the table, with algorithm i don't remember in detail, but then it starts clearing it. Each cell can have calculated a value, of how many possible numbers it can have based on the numbers already set on board. If for example the row 1 already has number 4, then none of the other 8 cells on that row can have 4, the normal gamerule check. The generator keeps track of that for each cell, and also of what those numbers are. It goes through the whole grid and then finds which ones have lowest value, then randomly picks 1 of the winners and makes it blank. Repeat until number density (filled:empty ratio) reaches the wanted difficulty level, where closest to empty is hardest. When you think about it, a cell that has low value is easy for human to figure out, so it's quite balanced on the difficulty.

edit: Lowest value, not highest... i think :D

[audioinstinct]

Hey, thanks for the replies and all the help, guys. I had to take a pause from continuing the program, I am having some difficult exams, I will continue when I'm done with them and keep this thread updated.

Peace.