Click here to Skip to main content
14,580,263 members

Welcome to the Lounge

   

For discussing anything related to a software developer's life but is not for programming questions. Got a programming question?

The Lounge is rated Safe For Work. If you're about to post something inappropriate for a shared office environment, then don't post it. No ads, no abuse, and no programming questions. Trolling, (political, climate, religious or whatever) will result in your account being removed.
 
GeneralRe: Difficult-to-solve Sudoku wanted Pin
PIEBALDconsult19-Mar-18 8:59
professionalPIEBALDconsult19-Mar-18 8:59 
GeneralRe: Difficult-to-solve Sudoku wanted Pin
Dezhi Zhao19-Mar-18 5:21
MemberDezhi Zhao19-Mar-18 5:21 
GeneralRe: Difficult-to-solve Sudoku wanted Pin
Member 798912219-Mar-18 6:16
MemberMember 798912219-Mar-18 6:16 
GeneralRe: Difficult-to-solve Sudoku wanted Pin
Dezhi Zhao19-Mar-18 7:15
MemberDezhi Zhao19-Mar-18 7:15 
GeneralRe: Difficult-to-solve Sudoku wanted Pin
Member 798912219-Mar-18 8:33
MemberMember 798912219-Mar-18 8:33 
GeneralRe: Difficult-to-solve Sudoku wanted Pin
Dezhi Zhao19-Mar-18 9:21
MemberDezhi Zhao19-Mar-18 9:21 
GeneralRe: Difficult-to-solve Sudoku wanted Pin
Dezhi Zhao19-Mar-18 7:30
MemberDezhi Zhao19-Mar-18 7:30 
GeneralRe: Difficult-to-solve Sudoku wanted Pin
Member 798912219-Mar-18 9:18
MemberMember 798912219-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!
GeneralRe: Difficult-to-solve Sudoku wanted Pin
Dezhi Zhao19-Mar-18 9:35
MemberDezhi Zhao19-Mar-18 9:35 
GeneralRe: Difficult-to-solve Sudoku wanted Pin
PIEBALDconsult19-Mar-18 16:37
professionalPIEBALDconsult19-Mar-18 16:37 
GeneralRe: Difficult-to-solve Sudoku wanted Pin
Dezhi Zhao20-Mar-18 3:06
MemberDezhi Zhao20-Mar-18 3:06 
GeneralRe: Difficult-to-solve Sudoku wanted Pin
PIEBALDconsult19-Mar-18 10:34
professionalPIEBALDconsult19-Mar-18 10:34 
QuestionKid Sister Safe These Days... Pin
"mega"-in-a-fresh-shave!18-Mar-18 23:17
professional"mega"-in-a-fresh-shave!18-Mar-18 23:17 
AnswerRe: Kid Sister Safe These Days... Pin
OriginalGriff18-Mar-18 23:27
mveOriginalGriff18-Mar-18 23:27 
GeneralRe: Kid Sister Safe These Days... Pin
W Balboos, GHB19-Mar-18 3:54
mveW Balboos, GHB19-Mar-18 3:54 
GeneralWSO CCC OTD 2018-03-19 Pin
OriginalGriff18-Mar-18 23:02
mveOriginalGriff18-Mar-18 23:02 
GeneralRe: WSO CCC OTD 2018-03-19 Pin
A_Griffin18-Mar-18 23:10
MemberA_Griffin18-Mar-18 23:10 
GeneralRe: WSO CCC OTD 2018-03-19 Pin
OriginalGriff18-Mar-18 23:26
mveOriginalGriff18-Mar-18 23:26 
GeneralRe: WSO CCC OTD 2018-03-19 Pin
Munchies_Matt18-Mar-18 23:44
MemberMunchies_Matt18-Mar-18 23:44 
GeneralRe: WSO CCC OTD 2018-03-19 Pin
OriginalGriff18-Mar-18 23:51
mveOriginalGriff18-Mar-18 23:51 
GeneralRe: WSO CCC OTD 2018-03-19 Pin
The pompey19-Mar-18 0:09
MemberThe pompey19-Mar-18 0:09 
GeneralRe: WSO CCC OTD 2018-03-19 Pin
OriginalGriff19-Mar-18 0:12
mveOriginalGriff19-Mar-18 0:12 
GeneralRe: WSO CCC OTD 2018-03-19 Pin
PeejayAdams19-Mar-18 0:28
MemberPeejayAdams19-Mar-18 0:28 
GeneralRe: WSO CCC OTD 2018-03-19 - we have a winner! Pin
OriginalGriff19-Mar-18 0:32
mveOriginalGriff19-Mar-18 0:32 
GeneralRe: WSO CCC OTD 2018-03-19 - we have a winner! Pin
PeejayAdams19-Mar-18 0:46
MemberPeejayAdams19-Mar-18 0:46 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.