Brainless Sudoku
Jul. 25th, 2006 06:56 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
Puzzle people:
Is this for real? Can all Sudoku be solved - and solved relatively quickly - by this brute force method?
If so, I think that's pretty funny.
Is this for real? Can all Sudoku be solved - and solved relatively quickly - by this brute force method?
If so, I think that's pretty funny.
no subject
Date: 2006-07-25 11:07 pm (UTC)I thought sudoku was kind of entertaining the first couple of times, until I realised that they're all the same and wouldn't coming up with an algorithm be easier, oh, someone already did, I guess that saves me the trouble of doing them then.
no subject
Date: 2006-07-26 12:31 am (UTC)no subject
Date: 2006-07-26 12:44 am (UTC)no subject
Date: 2006-07-26 01:46 am (UTC)If you've ever taken intro logic, you may remember a method of determining the truth of a proposition is to search for contradictions by building an inference tree. By showing there are no contradictions you accept the proposition as true. This is a process that can be mechanized by theorem-provers, and what he is doing with sudoku looks conceptually similar: by eliminating every number that cannot be the correct answer for a given square, you are eventually left with the one that is the answer. This is a process that must yeild the correct answer eventually so long as the puzzle is consistent.
Variants of the puzzle may make this kind of dull mechanical process even more dull and mechanical, but no puzzle of this form requires any insight to solve, ever, although insight might help you solve it faster.
Personally, I've invented a new kind of puzzle called sudon'tku, which is seeded with inconsistent values, making it impossible to solve at all...
no subject
Date: 2006-07-26 03:58 am (UTC)no subject
Date: 2006-07-26 12:49 pm (UTC)Some particularly tough ones require extra tricks. For instance you may have 5 squares in a box/column/row showing these possibilities: [12345][235][123][13][123]. This looks intractable using the "brainless sudoku" method. However, the last 3 boxes have only 3 numbers to split between them, and must be filled in with 1,2 & 3 in some combination. Even though you may not yet know what this combination is, you can still eliminate 1,2&3 from the 1st 2 boxes, allowing you to solve them as 4 & 5, respectively. This scales for any number of boxes. I just encountered one puzzle in which the "brainless" method failed to specify ANY numbers, and I required multiple applications of this trick to get anywhere.
Then there are the _really_ hard ones that linear brute-force methods come to a complete dead end for. These ones you have to make a guess (usually between 2 possible numbers for a box) and see how it plays out. If it leads to an inconsistency, you then have to backtrack & test the other number instead. Extremely nasty Sudokus may force you to test multiple branchings before you find the correct combination.
no subject
Date: 2006-07-26 08:28 pm (UTC)no subject
Date: 2006-07-26 08:36 pm (UTC)no subject
Date: 2006-07-26 09:19 pm (UTC)