The Lounge - CodeProject

First Prev Next

Re: Difficult-to-solve Sudoku wanted

kalberts19-Mar-18 8:33

kalberts

19-Mar-18 8:33

Would you care to reveal details about the logic of the program, or is that "company confidential"?

Can you reveal whether it is multi-threaded or not, and how many CPU cores were activated in that run?

Re: Difficult-to-solve Sudoku wanted

Dezhi Zhao19-Mar-18 9:21

Dezhi Zhao

19-Mar-18 9:21

It is still a simple brutal search program though I added some cutoffs to improve efficiency and also optimized it quite a bit.
I don't see a need to go parallel for classical Sudoku at all. So, the numbers I mentioned here is coming from one core off an old laptop with i5-4200M.

It is not a secret at all. It is a result of a hobby project. I will publish the code along a short descriptions of design considerations when I get the time.
In fact, I did promise a friend of mine a short article about it months ago Smile | :)

Re: Difficult-to-solve Sudoku wanted

Dezhi Zhao19-Mar-18 7:30

Dezhi Zhao

19-Mar-18 7:30

Your worst case could be worse than the previous example which was my most time consuming problem.
So, here is another one that took my program 0.00002s:

.........
.....1..2
..3.2..4.
....5..6.
.1.....2.
7..8.....
...7..3..
..2..6...
5.......7

modified 19-Mar-18 22:12pm.

Re: Difficult-to-solve Sudoku wanted

kalberts19-Mar-18 9:18

kalberts

19-Mar-18 9:18

20 microseconds is impressive (assuming, of course, that your program is a general solver that can find a solution for every valid Sudoku game).

Now, I didn't write my little routine in an attempt to create the world's fastest Sudoku solver (in that case, lots of people would have beaten me to it: I use a straightforward backtracking routine, and that has been done many times before!). What happened was that a colleague of mine with not-too-much formal education in programming asked me if I had any hints for making a Sudoku solver. "Why don't you start out with a simple backtracking algorithm?" I suggested. "Backtracking, what is that?" ... So I wrote this little routine to illustrate what backtracking is - not to win any speed competition.

I've never tried to multithread backtracking, and am curious to see if multithreading can speed up backtracking algorithms, or if the administration eats up the gain from multithreading. If you want to measure reductions in total execution time, you do not do it on a problem solved in 20 microseconds! That is why I asked for hard-to-solve Sudokus, because that was the problem for the backtracking I had been written a couple of days ago, fresh in my mind. And Wikipedia claims that the general problem of Sudoku-solving is NP-complete, so I was assuming that I could easily find games that would take "ages" to find a solution to, as good candidates for speedup by engaging multiple CPU cores.

You may have interpreted the discussion between W∴ Balboos and me as if I claim that backtracking is faster that "logic" and "analytical". That is not what I am saying, but that "logic" and "analytical" approaches are not in any way "intellectually superior" or principally different from any other algorithmic solution. "Logic" and "analysis" are algorithmic as well. W∴ Balboos seems to be wanting to split algorithmic solutions into two classes: Those never evaluating a case, and then rejecting it (that represents this detestable "trial and error"), and those that allow themselves to conclude that an alternative is not a viable case for further investigation. But it seems as if W∴ Balboos wants to keep the "logic" and "analytical" approaces to Sudoku in the "magic" realm that cannot be expressed algorithmically.

I believe they can, and I believe that if you do, it will be difficult to find a clear cut distinction between intellectually inferior "trial and error" type algorithms on the one side and intellectually superior "logic" and "analysis" algorithms on the other side. Unless, of course your logic can be programmed entirely without "if" statements, "while" statements and "repeat until" statements. These all express making assumptions (aka. guessing) and testing whether they hold true. I very much doubt that any Sudoku solver can create a solution without conditional tests in loops or if-statements.

If your 20-microsecond-solver can find the solution without any conditional tests, I am impressed. Actually, I do not care for Sudoku as such - I never solved a Sudoku game by hand! - so my only interest in in the algorithmic expression of intellectual "logic" and "analysis". But of course I will respect your wish if you do not want to reveal how you do it at that speed!

Re: Difficult-to-solve Sudoku wanted

Dezhi Zhao19-Mar-18 9:35

Dezhi Zhao

19-Mar-18 9:35

Certainly my solver is a general one, cracking any classical Sudoku problems. It can do exhaustive search to see if a problem has multiple solutions. It checks validity before search.

I agree most what you said here. I said to a friend when discussing Sudoku:
We all know that knowledge is power. But do you still need knowledge if you have power? Smile | :)

Modern physics is trying to tell us that power and knowledge are the same thing.
So, I picked power Smile | :)

Re: Difficult-to-solve Sudoku wanted

PIEBALDconsult19-Mar-18 16:37

PIEBALDconsult

19-Mar-18 16:37

But that and the other don't lead to a single solution, do they?

Re: Difficult-to-solve Sudoku wanted

Dezhi Zhao20-Mar-18 3:06

Dezhi Zhao

20-Mar-18 3:06

The 2 puzzles I posted here are classical Sudoku that dictates one and only one possible solution.

Re: Difficult-to-solve Sudoku wanted

PIEBALDconsult19-Mar-18 10:34

PIEBALDconsult

19-Mar-18 10:34

Additionally, if you want puzzles that are better suited to back-tracking, you might want N-Queens or Knight's Tour.

Kid Sister Safe These Days...

megaadam18-Mar-18 23:17

megaadam

18-Mar-18 23:17

...Is that when does not reveal all the details about her Saturday night?

... such stuff as dreams are made on

Re: Kid Sister Safe These Days...

OriginalGriff18-Mar-18 23:27

OriginalGriff

18-Mar-18 23:27

It's when she wakes up Sunday afternoon and has to check FarceBok and SnapCat to find out what she did that you need to worry...

Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
AntiTwitter: @DalekDave is now a follower!

Re: Kid Sister Safe These Days...

W∴ Balboos, GHB19-Mar-18 3:54

W∴ Balboos, GHB

19-Mar-18 3:54

Well - my kids, fortunately, where that age long enough ago where the internet smutlogs weren't standard operating tools for the youngin's.

On the other hand - that headache is theirs.

Ravings en masse^
"The difference between genius and stupidity is that genius has its limits." - Albert Einstein
"If you are searching for perfection in others, then you seek disappointment. If you are seek perfection in yourself, then you will find failure." - Balboos HaGadol Mar 2010