The New Sudoku Players' Forum

[Guest]

Hi Animator,

What do you mean "only logic" and no "guessing"? I take it you mean a non-iterative algorithm. Put another way, are you looking for an "equation" in each blank cell which yields the correct number (where every other cell would be an independent variable)? If so, there's no hope.

Incidentally my simple effort finds problems and provides a simple way to adjust the difficulty of each problem. I can easily generate "fiendish" quality puzzles in under a second.

There's no puzzle which can not be instantly solved with my algorithm - which is trivial - do you have any puzzle to offer?

[Animator]

Basiclly, the solver should solve it the same way a human should...

As in, for a program it is simple to create a recursive solutions in which you simply try to fill in the numbers, as in, first you start filling in the number 1 in a cell, and see if you can complete it, if you can't you change 1 into a 2 and so on.

But ofcourse that's not logic, that's guessing...

A consequence of that is that if there is more then one solution then you are unable to find any of those... (since it requires you to guess to fill in one cell)
The main idea is to program it so it can reconsize the pattern. For example, it detects that the only possibilty for the number 2 in row 5 for example is r5c6.

[Guest]

Hi Animator,

I do not think your explanation is logical. If you want a program to solve a puzzle "in the same way a human should" you need first to define what the "should" actually is. If you had said "a human would" then you will get a very unreliable, slow solver! Try programming a computer to play chess the same way as a human should/would - not a chance. In any case, I think you'll find a human very much "guesses", e.g. "If I put a 4 in this square, what are the consequences for allocating a number in another square?" That's a guess.

There is no way on earth you will come up with a (complete) set of non-iterative rules to apply on each square in order to get the solution. You may come up with a sufficient number to solve some problems, but this is intrinsically arbitrary since you will never know when you have the complete set of rules to solve every problem. i.e. there is no mathematical rigour to this process whatsoever - you will not be able to prove success (though I suspect that it may well be possible to prove that it is impossible).

I guess it's fine that people in this forum have fun trying so long as they realise that there is no point at which they will know that they have succeeded! That's why I wouldn't try!

On the point of multiple solutions, clearly the iterative approach identifies these with ease. If the forum want to "solve the way a human should", there's no reason to extend the (impossible!) challenge to have the rules deliver a SET of numbers - however, the sets would have to be correlated with all solutions sets on the other 80 squares. So still there need be no guessing - the problem just got harder. But since the single-solution problem is impossible to solve anyway, impossible squared is still impossible!

[Animator]

In any case, I think you'll find a human very much "guesses", e.g. "If I put a 4 in this square, what are the consequences for allocating a number in another square?" That's a guess.

Not really, I would look where can a 4 go, I wouldn't try filling in one randomly and see where it takes me.

What follows are some grids in which you can fill in a number using only logic.

Assume this small (incomplete) grid, for the first three boxes:

* * * | * * 4 | * * *
* * * | * * * | 4 * *
1 2 * | * * * | * * *

In this situation there is only one valid place for the 4 in box 1, so no need to guess at all. That is a logic conclusion based on the rules: a column, row, box has to have all numbers from 1 to 9.


Some other patterns:

* * * | * * * | * * *
* * * | * * * | * * *
* * * | 3 5 6 | 7 8 9
-----------------------
1 * * | * * * | * * *
2 * * | * * * | * * *

Based on that you can fill in the 4 in box1: row 3 needs the number 1, 2 and 4. But r3c1 cannot be 1 or 2 so it has to be 4. Logic conclusion, not a guess.


Another one:

6 5 * | * 2 * | * * 7
* * 1 | * * * | 9 * *
8 9 * | * * * | * * 1
------------------------
* * * | * * * | 8 * *

Missing numbers for row 1: 1, 3, 4, 8, 9

In this example you fill in the 8 without a problem, without needing to do a single guess. Possibilites:
r1c3: 3, 4
r1c4: 1, 3, 4, 8, 9
r1c6: 1, 3, 4, 8, 9
r1c7: 3, 4
r1c8: 3, 4, 8

From this you learn that there are two cells that have two identical values, this means that you can remove them as candidates from all other cells, and allow you to fill in the 8 in r1c8

That is what I mean by logic and that is how most people here solve the puzzle, by looking at the possibilites, not by trial and error (which is guessing). (Note though, these are not all the possible patterns, there are more, it are juist some examples!)


A human solves the puzzle by reconsing the patterns, and all puzzles created by the Pappocom software are solvable using this technique.

And that's what all the fuzz about... making a program that reconise the patterns. It is easy enough to write a program that tries every possiblities.

[Guest]

Thanks, Automator - very clearly put. But I would disagree with your implied differentiation between guessing and logic. In each of your examples, you are simply demonstrating the rules of the game.

Take your simplest example:

Where do you start? Do you ask:
I wish to place a four in the first box?
I wish to complete R3C3 of the first box?
I wish to plant a valid number in any cell in the first box?

How did you know that R3C3 is the only place to put your 4? I bet you said:
I can't put it in R1.
I can't put it in R2.
It has to go in R3 and there's only one spot to put it there.

How did you know that you could not put your 4 in R1? You knew because you tried it and it broke a rule! Although it did not feel like it, that's the unavoidable step you take - you "guess" to put it in R1 and find it does not work.

Put another way, you deduced that 4 could not go in R1 and R2. But to deduce that you must have toyed with the idea!

So even with your "logic" you are making implicit trials. Indeed, every placement of a number is essentially a trial or test that the placement meets the rules.

So to be literal about your requirement to be based on "logic", I go back to my original interpretation: That you will need to construct a non-iterative formula in each cell whose value derives the correct number. This formula has 80 variables at its disposal where each is limited to a value from 0 to 9 and some are preset as constants. Your task is to contruct that formula. Good luck!

These puzzles can be solved in only 2 ways: Iteratively or Formulaicly.

You can make the iterative one as "human" as you think, but at the end of the day, it's just a more complicated version of the pure iterative trial version.

In many programs to play games you do, ofcourse, build more than the "pure" (or brute-force) iterative solution. You program in shortcuts, assumptions, derived rules etc etc. This is all done in persuit of speeding up the solution at the cost of accuracy. It's still "guessing", though. In the Sudoku case, however, speed is not a problem as the brute force method generally enables several hundred solutions per second to be found!

[Animator]

This seems like a useless discussion, which I'm not going to continue...

I strongly suggest you try to solve several puzzles by hand first.

[Guest]

I agree. But I have a few questions:

Does your "logic" program solve all problems?
If not, do you think it ever will?
Or will it only solve what can reasonably be expected of a human?

I understand what you are doing, but I think you are constructing "rules" which humans could apply. For ever increasing complexity of sudoku problems, you will need ever increasing complexity of rules - to the point that a human could not apply them all.

Thanks for the dialogue

[Animator]

It doesn't solve all problems since I haven't bottered with writing it yet :)

But there are others which solve quite a lot, as in beyond Swordfish (which is used only in puzzles after the 'Very hard' level, for which there isn't a generator yet (or atleast not that I'm aware of)...) But ofcourse those have a limit too (where/what that limit is is impossible for me to tell)


Solving everything ofcourse is difficult since I don't know all possible patterns, I know most of them, but I'm sure there are some more...

for example I recall a puzzle (which was not solvable by using only logic) in which I could eliminate a number as a candidate from a certain cell by appling some very easy trial and error...

Now I believe that if you can proove it via trial and error (or atleastvery basic trial and error which is limited to only one number) that you should also be possible to proove it via logic... But I haven't looked into that closely let... (to see if I can see a pattern)

[Guest]

OK, I understand. As a matter of interest, can it do something like:

*6* *** ***
**1 *** **8
*7* 8** *61

*** 2*3 7*6
*** *** 53*
*** 71* ***

4** 1** **9
5** *** ***
**3 69* *2*

?

[Animator]

Short answer: yes :)

[Guest]

That's not bad. How does the program actually work? Do you start with each square having every number as a possible entry. Then apply "rules" to eliminate numbers until you only have one possibility left in each?

So, for example, in the problem I listed, in R1C1 you have all possible numbers 1-9 but you then eliminate 6 because of the rule "6 is already present in this row"

What would you consider to be your most complex rule? Is it one such that a human could reasonably apply it in their mind?

[Animator]

I haven't started writing it yes so I'll explain how I solve them (not using a program that is).

I look for numbers that occur a lot, in this case the 1, if you look all the 1's then you will see that there is only one place for the 1 in box 2 and in box 6, it simply cannot go anywhere else. There are ofcourse two ways you can implement this is a program... that is seeing if you can fill it in r1c4, r1c5, ... or trying to learn something from the current pattern. The last will most likely be less efficient for a program but it would be more intresting IMHO.

Only eliminating numbers can slow down things... for example if there is only one candidate cell for a certain number then it will take longer to find it only by eliminating numbers... (although you can consider all other possibilities as paired and because of that remove them based on that)

The hardest one? I honestly don't know... The Pappocom software marks puzzles requiring a Swordfish (a generalised X-Wing, if you know what that is) as unfair, even though the only thing it requires is some concentration...

There are some harder ones though but I can't say I have looked at them closely...

[Guest]

Interesting. So to deduce the placement of the 1 in box 2, you must have logged in your mind that it cannot go in rows 2 and 3 and columns 4 and 5. I think that if you were to write a program on your thought processes you would have to code for this "elimination". You would have to write something like:

Set all numbers in all empty squares as a valid option
For each rule
...For each empty square
......For each number (1-9) which is currently marked as a valid option
.........If this number in this square breaks this rule
.........then mark it as an invalid possibility
......Next
...Next
Next
At this point, maybe you have only one valid choice in each square. If not, you'll need another rule....

Simple rules would be:
"If this number is already preset in this block, row or column then... it breaks the rule"
Your example of deducing the 1 into R1C6 is represented by the rule:
"If there exists another valid choice for this square which is not represented in either the preset or valid choices in any of the other squares in either my row, column or block then... it breaks the rule"

How were you going to program your thought processes? Something like this?

[Animator]

I'm not sure about that yet...

What you explained sure is an option but I would consider that the easy way...

As in, that is not how I solve the puzzles in my mind... I don't look at each cell and see what numbers are possible (or atleast not from the start). I look what clues do I have and what do they imply... programming that however might be a bit harder (and definetly less efficient)...

[Guest]

I think I know how to solve the puzzle above in a *fairly* computer friendly fashion.

for any row / column / block. If a number appears only in one 1x3 block, then remove that number from the other row / column / block that shares that 1x3 block.

eg

Y Y Y
Y Y Y
X X X 1 2 3 4 5 6

from the row above, 7 8 & 9 must appear somewhere in the X's. Therefore they cannot exist in the Y's.