prog: (Default)
[personal profile] prog
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.

Date: 2006-07-25 11:07 pm (UTC)
From: [identity profile] chocorisu.livejournal.com
Yes. Most of the smarter Sudoku-solving algorithms fall back on doing it this way if their fancy tricks don't work.

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.

Date: 2006-07-26 12:31 am (UTC)
From: [identity profile] ianmcin.livejournal.com
Haven't tried this myself, so I'm not sure, but one example of a puzzle that couldn't be solved in this method would be one where you know X numbers have to go in X specific boxes, (and can therefore rule those numbers out in the other boxes in the groups/rows/columns they share).

Date: 2006-07-26 12:44 am (UTC)
From: [identity profile] rikchik.livejournal.com
The comments are pretty accurate on that page - easy sudoku puzzles can be solved quickly in that way, complicated ones not so much. I've been seeing a lot of sudoku variants lately, with different shaped regions etc., and this method may not work on all of those.

Date: 2006-07-26 01:46 am (UTC)
From: [identity profile] radtea.livejournal.com
Essentially, yes.

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

Date: 2006-07-26 03:58 am (UTC)
From: [identity profile] prog.livejournal.com
My favorite variant is [livejournal.com profile] lunchboy's Snakes on a Sudoku, though it's not like I've ever tried to solve that either.

Date: 2006-07-26 12:49 pm (UTC)
From: [identity profile] grr-plus1.livejournal.com
This is an OK strategy for easy and moderate Sudokus (although writing in all 9 numbers in each small square and erasing them is far more laborious than necessary). It is _not_ a way to solve all Sudokus. It would probably fail on a good proportion of, say, the Sunday Globe Sudokus.

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.

Date: 2006-07-26 08:28 pm (UTC)
From: [identity profile] pseudomanitou.livejournal.com
Just two weeks ago, I lost my Sudoku virginity -- and the process I used was EXACTLY like the one described. (Note: I am no good at math, I know of algorithms by definition only, my use of math in life consists of measuring out press sheets for maximum printing efficency.) Since my first instinct, numbers novice that I am, was to use this method to solve the puzzle - I'm amazed that this is even a topic of discussion... doesn't everyone do it this way?

Date: 2006-07-26 08:36 pm (UTC)
From: [identity profile] prog.livejournal.com
I only brought it up coz I had thought that sudoku was more of a puzzle than a fidget-toy. (Not that there's anything wrong with fidget-toys. Watch me play Animal Crossing any time.)

Date: 2006-07-26 09:19 pm (UTC)
From: [identity profile] dougo.livejournal.com
That's basically the first step in solving a sudoku puzzle (or maybe the first two steps). I think most newspaper puzzles will be finished after that, but for any interesting puzzle you'll run into a dead end and have to get more creative. Or use the Sudoku Sledgehammer, if you can wrap your brain around it (I haven't been able to yet, at least not to the point of being able to use it).

August 2022

S M T W T F S
 123456
78910111213
14151617181920
21222324252627
28 293031   

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Aug. 17th, 2025 05:24 pm
Powered by Dreamwidth Studios