Page 3 of 3 FirstFirst 123
Results 21 to 28 of 28

Thread: Sudoku solver program, do it like a human!

  1. #21
    PGD Staff / News Reporter phibermon's Avatar
    Join Date
    Sep 2009
    Location
    England
    Posts
    524
    Quote Originally Posted by SilverWarior View Post
    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?
    Last edited by phibermon; 05-01-2015 at 06:35 PM.
    When the moon hits your eye like a big pizza pie - that's an extinction level impact event.

  2. #22
    Quote Originally Posted by phibermon View Post
    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.

  3. #23
    Quote Originally Posted by SilverWarior View Post
    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:

    Code:
    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:

    Code:
    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:
    Code:
    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.
    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.

  4. #24
    @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.

  5. #25
    PGD Staff / News Reporter phibermon's Avatar
    Join Date
    Sep 2009
    Location
    England
    Posts
    524
    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
    When the moon hits your eye like a big pizza pie - that's an extinction level impact event.

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

  7. #27
    I also have made a sudoku solver, that you can possibly learn from
    Lazarus source: https://www.dropbox.com/s/u27owmiqrb...u_src.zip?dl=0
    Windows binary: https://www.dropbox.com/s/e95blmhhti...udoku.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
    Last edited by User137; 16-01-2015 at 09:03 PM.

  8. #28
    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.

Page 3 of 3 FirstFirst 123

Tags for this Thread

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •