Results 1 to 10 of 28

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

Threaded View

Previous Post Previous Post   Next Post Next Post
  1. #6
    Quote Originally Posted by SilverWarior View Post
    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

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



    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.
    Attached Images Attached Images

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
  •