New contest started - Sudoku Solver - Rules updated 14/6/05

[manavo11]

There is the thread discussion thread in the contest section and another thread in the games section that there is discussion about it... Why did you give up?

[eyeRmonkey]

Oh, sorry, I didn't know there were any other threads.

I gave up because I couldn't solve one by hand, so there is no way I could make a program for it.

[manavo11]

Ah, come on, try! There are still 3 weeks to go

[Something Else]

Oh, sorry, I didn't know there were any other threads.

I gave up because I couldn't solve one by hand, so there is no way I could make a program for it.

Ohh, darn!
I want a monkey!
Please, can't the monkey play???

Here's some more you can try!
http://www.vbforums.com/showpost.php...5&postcount=79

Build a list of all the values a cell could be.
Then, for each revealed cell, delete all of that cells could be's, then place in it its must be.

Then, for every cell in that mustbe's row, delete that must be from each of those cells,
Ditto per column,
Ditto for the actual 3x3 parent SQUARE.

Then, look for pairs of identical COULD BE numbers, per row, column, or SQUARE

If you find 2 cells with 2 COULD BE's, and they are the same COULD BE's, then those values cannot be anywhere else in the group your checking. Delete those values everywhere else in the group that they're in.

Look at each cell whose COULD BE count > 1.
For each value, check and see if that COULD_BE value is anywhere else in the group you are checking.
If it's not, then that cell MUST BE that number.

{Group = Row, Column, 3x3 SQUARE}



with just those three rules, you'll find you'll be able to solve some of the puzzles, AND it'll get you started thinking up more rules to include in your solver.


-Lou

[manavo11]

Just to mention that is what I haven't even done all that in my solver and it solves all the easy ones So get started monkey

[Something Else]

Manavo,
Haver you tried my newest set?
Specifically, the ones whose "difficulty" level >= 8? (The number in the solution set that corresponds to the _XXXX_ in the msk set}

-Lou

[oceanebelle]

I've decided that I can't solve (or even understand) one of these by hand, so there is no possible way I can make a program to do it.

I had fun solving it... so I guess I'm gonna try to make a program for it.. but I doubt its contest worthy... I tried a site and solved all medium and hard problems (nevermind easy ones).. hard ones are really hard.. I have not properly grasped my method for solving it.. all done by hand.

sample (4 easy, 4 medium, 4 hard)
http://www.puzzle.jp/letsplay/play_sudoku-e.html


can somebody give me more puzzles to check.. i really love number puzzles nevermind the program.

[oceanebelle]

Manavo,
Haver you tried my newest set?
Specifically, the ones whose "difficulty" level >= 8? (The number in the solution set that corresponds to the _XXXX_ in the msk set}

-Lou

uhmm Lou, solution set meaning there can be many solutions to a sudoku puzzle? I was pretty sure that it has only one solution.. well that's what I deduced from solving some puzzles.

[oceanebelle]

oh well found an answere to my problem..

... It is possible to set starting grids with more than one solution and to set grids with no solution, but such are not considered proper Sudoku puzzles...

Therefore, if the puzzle has more than one solution it is not a sudoku puzzle.... I rather like those original sudoku puzzle they have a form and they are written by hand...

what puzzles will the contest be using?

[eyeRmonkey]

Ok, I might try it if I can find the time. I tried solving an online version and I did alright. Thanks for the motivations guys.

[manavo11]

Lou, haven't had a chance yet... I can't seem to think how I can incorporate the things that go through my head when I'm solving them by hand into code... But I will soon, I promise

oceanebelle, we don't have some predetermined puzzles that we are going to use, when marking time comes along we'll find some and test the entries with the puzzles we choose.

monkey, get working

[tr333]

if i could do this in Haskell it would be infinitely easier than vb/c#.

[eyeRmonkey]

Ohh, darn!
I want a monkey!
Please, can't the monkey play???

Here's some more you can try!
http://www.vbforums.com/showpost.php...5&postcount=79

Build a list of all the values a cell could be.
Then, for each revealed cell, delete all of that cells could be's, then place in it its must be.

Then, for every cell in that mustbe's row, delete that must be from each of those cells,
Ditto per column,
Ditto for the actual 3x3 parent SQUARE.

Then, look for pairs of identical COULD BE numbers, per row, column, or SQUARE

If you find 2 cells with 2 COULD BE's, and they are the same COULD BE's, then those values cannot be anywhere else in the group your checking. Delete those values everywhere else in the group that they're in.

Look at each cell whose COULD BE count > 1.
For each value, check and see if that COULD_BE value is anywhere else in the group you are checking.
If it's not, then that cell MUST BE that number.

{Group = Row, Column, 3x3 SQUARE}



with just those three rules, you'll find you'll be able to solve some of the puzzles, AND it'll get you started thinking up more rules to include in your solver.


-Lou

I don't get that part. I did the other 2 parts though and thats working well (on the MOST simpe puzzels with only a few squares missing).

Could someone explain that part to me?

[Something Else]

uhmm Lou, solution set meaning there can be many solutions to a sudoku puzzle? I was pretty sure that it has only one solution.. well that's what I deduced from solving some puzzles.

Sorry.
I'm referring to the filenames.
and "set" is in relation to the solution AND the puzzle are each a set of numbers.

And Yes. I endeaver to submit ony puzzles with one and only one solution.

No one has yet reported I've done otherwise.


-Lou

[Something Else]

I don't get that part. I did the other 2 parts though and thats working well (on the MOST simpe puzzels with only a few squares missing).

Could someone explain that part to me?

Certainly!

Lets start at the beginning.
Without knowing what ANY cell is, each cell can be 9 values.

I also refer to that as each cell could be 9 values.

Or... each cell has 9 COULD_BE's.

Now, lets say you KNOW the value of 1 cell, thru the initial settings of a puzzle, or by progressive elimination.

THEN, for every row, column, or SQUARE {3x3}, that value is removed from each of its groups, thus you are eliminating 1 COULD_BE from that cells row, column, and SQUARE, wherever that value exists.

SO... Your cells all eventually decrease in the number of possibilities that they COULD_BE, from their initial nine, to something lower.

Eventually, {hopefully}, you will have cells that might be, or COULD_BE, 2 and only 2 values. Therefore, I just say, they have 2 COULD_BE's.

So,
lets say you have a row where 2 cells COULD_BE 1 or 5, simultaneously.
For some reason, other cells in that row still have marked 2 or 5 as possible candidates, along with other numbers. Since 2 cells, well, MUST_BE a 2 or a 5, then the numbers 2 and 5 MUST BE ELIMINATED from every other cell in that row.

Ditto same thing, except columns for rows, ditto same thing, except 3x3 SQUARES for rows.


-Lou

OOPS!
I just saw that you've highlighted 2 rules, not one.

Ok.

Lets say, after successive elimination by established rules, in your group, you've got 9 cells. each cell COULD_BE some set of numbers, 1 thru 9. After inspecting each cell, you might notice, one cell COULD_BE 1,2,3, or 4.

Comparing that cell with all the other cells in its group, you might notice that no other cell has "1" for a could_be. Guess Where the 1 must be!

Thats right!

[eyeRmonkey]

Thanks for the help so far Lou. I understand all the rules you posted and am workin on ways to apply them.

[manavo11]

Just to inform you that there were some additions (features) in the rules of the contest. Check here : http://www.vbforums.com/showthread.php?t=351477

Sorry for the inconvenience...