468,241 Members | 1,555 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,241 developers. It's quick & easy.

Looking for really hard sudoku puzzles

jkmyoung
2,057 Expert 2GB
Does anyone have some super, super hard Sudoku puzzles?

Back in February this year, I had enough time to finally program a Sudoku solver in Java. Right now, I'm looking for solvable puzzles, but ones that my program cannot solve. However, most hard puzzles in the newspapers are solved within 2-3 cycles so far.

The ones I've found on google which are said to be hard, get solved in 3 cycles.

Any help would be very much appreciated!
========================================
The program works on the possible values for each cell.
1. Determine the possible values in each cell.
2. Check rows. If there is any value in which only 1 empty cell can take that value, set empty cell to that value.
3. Columns.
4. Nonets, (3X3 Squares.)
5. Indiviual cells.
Dec 17 '08 #1
62 10855
Nepomuk
3,112 Expert 2GB
Well, I have some on my mobile which that solver might not be able to solve, so here are a few:
Expand|Select|Wrap|Line Numbers
  1. |xx1|xxx|xxx|
  2. |x2x|345|xxx|
  3. |xxx|xxx|267|
  4.  
  5. |x4x|x6x|xxx|
  6. |87x|xxx|x51|
  7. |xxx|x1x|x9x|
  8.  
  9. |563|xxx|xxx|
  10. |xxx|927|xxx|
  11. |xxx|xxx|8xx|
  12.  
Expand|Select|Wrap|Line Numbers
  1. |x1x|x2x|3xx|
  2. |x2x|4xx|xxx|
  3. |x3x|5xx|6xx|
  4.  
  5. |3xx|x7x|xx1|
  6. |8xx|xxx|xx9|
  7. |4xx|x6x|xx5|
  8.  
  9. |xx9|xx1|x8x|
  10. |xxx|xx2|x5x|
  11. |xx7|x3x|x4x|
  12.  
Expand|Select|Wrap|Line Numbers
  1. |xxx|x1x|xx2|
  2. |3xx|4xx|x5x|
  3. |6xx|7xx|x8x|
  4.  
  5. |xx1|x5x|9xx|
  6. |xx4|xxx|2xx|
  7. |xx5|x6x|7xx|
  8.  
  9. |x5x|xx8|xx6|
  10. |x7x|xx2|xx3|
  11. |9xx|x4x|xxx|
  12.  
("x" being an empty field) Hope that helps.

Greetings,
Nepomuk
Dec 17 '08 #2
JosAH
11,448 Expert 8TB
Thanks for those puzzles; I just checked: my old solver solves them all instantaneously. (see that old article about Sudoku).

kind regards,

Jos

ps. solving took 14, 2 and 9 ms respectively but that includes the class loading etc. Those are highly inaccurate timings.
Dec 17 '08 #3
jkmyoung
2,057 Expert 2GB
Managed to find a bug in the program thanks to your inputs. After running those 3 problems through again, I got.
1. Solved. 5 cycles.
2. Not enough data, or unsolvable puzzle.
3. Not enough data, or unsolvable puzzle.

Will have to look up ways to refine the algorithm, so that it can solve the last 2.
Dec 17 '08 #4
JosAH
11,448 Expert 8TB
@jkmyoung: can you tell a bit about your algorithm? The solver I wrote just uses a brute force search and a bit of local cleverness to quickly determine whether or not a value in a cell is possible. Basically it can't go any faster than it goes without any 'intelligence'.

kind regards,

Jos

ps. what's a 'cycle' in your algorithm?
Dec 17 '08 #5
jkmyoung
2,057 Expert 2GB
Each cell has an integer associated with it, representing the possible combinations for that square. Each cell uses 10 bits.
1<<0 Lowest order bit, determines if the value is finalized.
1<<1 bit determines if 1 is possible,
1<<2 bit determines if 2 is possible,
etc..

We also have 3 X 9 integers for the rows, cols, and nonets for the numbers that are already set.

After the numbers are loaded, we loop through the following process.
Main loop:
Side Loop1: Check rows.
Examine the 9 numbers in the current row. If there are any values such that only 1 cell can have them, and they aren't set yet, then set them. If there is no possible cell for a value, throw an error.

Side Loop2: Check cols,
Side Loop3: Check nonets,
Side Loop4: Check each individual cell.
If a cell has only one possible value and isn't set yet, then mark it as set.

End Main loop

A 'cycle' is one iteration through the main loop.
Dec 19 '08 #6
JosAH
11,448 Expert 8TB
I don't understand how your algorithm 'starts up'. Suppose there's an empty Sudoku puzzle: every row/column/sub-square/cell can store one of nine values so none is assigned in your cycle ...

kind regards,

Jos
Dec 20 '08 #7
jkmyoung
2,057 Expert 2GB
Ah sorry, didn't think it made a difference.

Loading:
The program only reads in 81 digits, from 0-9. 0 is an empty space, 1-9 are set numbers. It ignores all other input. It determines if there are any duplicate numbers in any row/column/nonet, and if so throws an "InvalidInput" error.

Running:
If no changes are made within a single cycle, then the program returns:
Not enough data, or unsolvable puzzle.

Side Loop4: Check each individual cell. If there is no possible value for a cell, the program throws an error stating something like "No possible value for cell (x,y)"

===============
So if you have an empty puzzle, no changes will be made in a cycle.
- Program returns "Not enough data, or unsolvable puzzle."

===============
If you have an impossible puzzle like
Expand|Select|Wrap|Line Numbers
  1. -23------
  2. 456------
  3. 789------
  4. ---------
  5. ---------
  6. ---------
  7. ---------
  8. ---------
  9. 1--------
  10.  
The puzzle will return:
"No possible value for cell (1,1)"
Dec 22 '08 #8
JosAH
11,448 Expert 8TB
@jkmyoung
Ah, ok; so your algorithm completes a partially filled board if only one solution is possible, i.e. it doesn't find any or all possible solutions given a partial solution, right?

kind regards,

Jos
Dec 22 '08 #9
jkmyoung
2,057 Expert 2GB
Yes. Have thought about it, but haven't figured out a way beyond brute force, so haven't implemented it yet.
Dec 23 '08 #10
ashitpro
542 Expert 512MB
I'd implemented this long ago...
It worked with algorythm strategy what we call as backtracking...Or may be you can say brute force...
It used to solved even empty sudoku
Dec 31 '08 #11
JosAH
11,448 Expert 8TB
@ashitpro
That's what he was talking about: how to find anything more clever than just a brute force algorithm. I once tried it by using ILP (Integer Linear Programming) but it failed miserably: although the solver found a solution it was much slower than my simple brute force approach (see an article about it in the Java howtos section).

kind regards,

Jos
Dec 31 '08 #12
r035198x
13,262 8TB
I'm interested in the ILP approach. Did you find out why it is slower?
Jan 2 '09 #13
JosAH
11,448 Expert 8TB
@r035198x
I used the binary version, i.e. Xijv == 1 if square at i,j == v. You need 9x9 constraints to model the puzzle and you need 9x9x9 binary variables. I think that the search space is a bit bigger than just enumerating the feasable possibilites. Since the entire puzzle is a feasability problem the linear relaxation (simplex or interior point) doesn't buy you much.

kind regards,

Jos
Jan 3 '09 #14
NeoPa
32,053 Expert Mod 16PB
I have an Excel spreadsheet that handles solving and allowing user entry (with checking and optional assistance). It implements some of the techniques I use when solving, but is otherwise brute-force / iterative.

I moved on to Killers a while back, but even displaying them in Excel was more than I wanted to get into as a simple diversion.

If anyone gets bored with the Deadly Killers (reference The Times) then try restricting yourself only to writing the solutions from the top-left cell and proceeding in a clockwise spiral (Making notes is clearly not allowed).
Jan 5 '09 #15
JosAH
11,448 Expert 8TB
@NeoPa
I didn't know Excel has an ILP solver; cute. Can it solve sudokus? A pure ILP doesn't need any brute force at the surface, i.e. the branch and bound strategy handles that below the surface but even my cplex solver takes a few seconds to come up with a solution. My brute force silly solver in the Java articles section is much, much faster.

kind regards,

Jos

edit. I happen to have a 2007 version of excel and it explicitly mentions a sudoku solver in its help files; here it is. I tried it; it is pure crap.
Jan 5 '09 #16
NeoPa
32,053 Expert Mod 16PB
I make no claims to an ILP solution Jos. My education didn't get that far if I remember accurately enough. I always loved Maths, but missed out on university due to various complications at the time.

I was able to code in a solver of sorts into Excel using VBA. In truth, it was never meant as a solver per se. Rather it was a teacher and something to provide the puzzles (for my children). It offered some assistance, but I'm not even sure now if it could necessarily solve all solvable puzzles, though I think it did. I must dig it up. I stopped using it a while back when I got into the (for me more interesting) Killer puzzles.

PS. Just checked and "No". It doesn't handle all - just the basic slog of the simple checks. I guess that means the intelligent checks never got as far as implementation (:embarrassment:).
Jan 5 '09 #17
JosAH
11,448 Expert 8TB
@NeoPa
No need to be ashamed; my solver doesn't make any 'intelligent' decisions either; it just tries them all and it tries to do that as efficient as possible. The recursion in it is just an artifact: basically speaking it runs as follows: if the solving succeeded this far try to solve the rest of it otherwise crawl back and try another possibiliy.

IMHO there's not much intelligence in the sudoku puzzle to apply or I am just too stupid too see it ;-) The ILP approach has just too much overhead in every step to make it fast. The math in it isn't much more than 101 either. OTOH I haven't seen any 'killer' puzzles either; a brute force approach can solve the difficult puzzles just as easy if not easier ...

kind regards,

Jos
Jan 5 '09 #18
NeoPa
32,053 Expert Mod 16PB
I didn't even get that far Jos. The (Excel) interface is able to handle the display layout for Killers, but only with great difficulty. Realising that I would need to insert extra, ultra-thin columns and rows, and that these would further complicate the workings out of what's where, I decided not to invest the time ;)
Jan 5 '09 #19
jkmyoung
2,057 Expert 2GB
Took a look at the excel method. Didn't know Excel had an iterative method.

Looking back at my notes, the one thing I failed to code was as such:

Given n cells in any row, column, or nonet, if there are n values which are not possible any of the 9-n other cells of the group of 9, eliminate all of the 9-n other possibilities for each of the original n cells.

Am uncertain how to code this.
1. How do I find these n-cells? OR
2. How do I find these n-values?
(efficiently, of course).

Will probably code in pairs, and/or if I can figure it out, triplets in a line/nonet.

Does anyone know of any better rules that they've used in their own solvers?
Jan 5 '09 #20
NeoPa
32,053 Expert Mod 16PB
That's pretty well how I do it JKM. Let me see if I can specify that more clearly in English.

Given n cells, where the only possible values for any (all) of those n cells make up a group of only n values, none of those values is available to any other cell in the section (line, column or nonet).

EG. You have a row of nine cells with the following values (possibilities) :
A=3; B=5; C=8; D=4 or 7; E=9; F=4 or 2; G=1; H=6; I=4 or 7
As both D & I have the possibilities of 4 or 7, then neither 4 nor 7 is available to any other cell. ==> F=2.

The more basic and obvious rules are that a value is not available to any other cell once it has been used within that section.

Slightly less obvious is that if a cell is the only one within any section that has a particular value available to it, regardless of how many other values are still available to it, that cell has the value of that particular value.
Jan 6 '09 #21
NeoPa
32,053 Expert Mod 16PB
@jkmyoung
Frankly I don't follow this statement at all :S What is "the Excel method" (What are you referring to when you say it)?

Anyway, in case it helps I'll attach what I have. As I say, it was never principally for solving the puzzles, it was more as an application to use to see and interface to them. I should also point out that it was developed a while ago so, while I'm happy to field any questions, I may not know the answers.

PS. I'm not suggesting anyone should be interested in my version, simply that it's there to look at should you feel you may want to. It was always a personal project so please excuse any untidiness in the code (and, of course you're free to use it as it was intended - simply to allow you to solve sudoku puzzles on screen. It does provide an interface for adding new puzzles if that helps).

PS. It seems I must lose some of the current stored puzzles to fit the size limit. Give me a short while.
Jan 6 '09 #22
NeoPa
32,053 Expert Mod 16PB
@NeoPa
Sorry. It seems that a claimed ZIP file attachment size of 50 MB is not supported (by about 49.999 MB).

Staff can hit me up on IM of course (or email or whatever) where I can get it transferred without fuss.
Jan 6 '09 #23
jkmyoung
2,057 Expert 2GB
I was referring to the Excel Sudoku solver link posted by Jos.

I think the example works if you note not only that "both D & I have the possibilities of 4 or 7" but also "both D & I ONLY have the possibilities of 4 or 7"

Another example to clear what I said up earlier.
a = 1,2,3,4,5,6,7,8,
b = 1,2,3,4,5,6,7,9
c = 1,2,3,4,5,6,8,9
d = 1,2,3,4,5,7,8,9
e = 1,2,3,6,7,8,9
f = 1,2,3,5,6,7,8,9
g = 2,3
h = 1,3
i = 1,2

g-i are limited to 1-3, and do not have 4-9. So, cells a-f are limited to 4-9. Remove 1-3 from a-f.

a = 4,5,6,7,8
b = 4,5,6,7,9
c = 4,5,6,8,9
d = 4,5,7,8,9
e = 6,7,8,9
f = 5,6,7,8,9
g = 2,3
h = 1,3
i = 1,2
Jan 6 '09 #24
NeoPa
32,053 Expert Mod 16PB
@jkmyoung
Ah yes of course. Makes perfect sense.
@jkmyoung
I think if you read my second paragraph you'll find that is covered.
@NeoPa
I've edited the quote here (and the original) in case that helps to make it clearer (the bolded n), but it's essentially the same (I also changed "none ARE" to the more correct "none IS").

Your example though, is a better illustration of the point we were both making. Well expressed.
Jan 6 '09 #25
NeoPa
32,053 Expert Mod 16PB
The logic to test for this is not trivial, even for the human brain, but I suspect that the brain has many advantages in a problem of this kind over a computer.

Mathematicians may find shortcut ways to cancel out some of the work of this, but the tests for determining this, as far as I can see easily at this point, would have to include some of the following logic.
  1. Start with a single section (Row; Column or Nonet).
  2. Get to a position where each element (cell) has a list of possible values left to it (as in your example).
  3. This must be done in memory (tables / arrays should be used). Excell cells are probably too clumsy to work fast enough. Many events get triggered every time a cell is updated. For proper programming, ignore this line.
  4. Start with a depth level (DLvl) of 2. This means that pairs of cells are being checked first time through the loop. The depth level only needs to go to 4. Once you are checking more than half of the available cells you can only find a result if there is also a result for the remaining cells. Clearly this should already have been found as they must, of necessity, have a depth of 9-DLvl ==> must be less than DLvl when DLvl > 9/2.
  5. Start from a. If/when a is fully exhausted proceed onto b through h in similar manner.
  6. Starting from the current letter +1 (b for the first iteration, then c etc) check each grouping (pairs to start with then groups of 3 & 4) and find each unique possible value for the grouping.
  7. Check each possible grouping (for whatever the current DLvl is) available. For pairs the sequence would be - ab; ac; ad; ...; bc; bd; be; ...; cd; ce; ...; hi. Threes are more complicated and fours even more so, but if you start from one end (a) and proceed only towards the other, all situation can be covered. Threes would start - abc; abd; ...; acd; ace; ...; bcd; bce; ...; bde; bdf; ...ghi.
  8. If, at any time, the number of unique values found for a grouping exceeds 8, then abort the test on that particular grouping. To illustrate take an example of DLvl=4 and testing the first grouping (abcd). If a has 9 possible values then abort the grouping. If ab together have 9 then again, abort. The same for abc.
  9. If however, the number of unique values found matches (there should never be less unless an earlier process has failed) DLvl, then all those unique values may be removed from all cells within the section except for those within the current grouping.
Hopefully, that is a workable outline of how to process this algorithm in a logical way. The numbers of tests here will actually be quite large and may even strain a modern computer. I don't know.
Jan 6 '09 #26
jkmyoung
2,057 Expert 2GB
maximum
pairs: 36
triplets: 84
quadruplets: 126

There's probably a way to test the triplets from pairs, quadruplets from pairs or triplets, to avoid repeating work.

I'm trying to figure out if the reverse is as easily doable also. Swap cells and values in your previous statement and you get the following:
Given n values, where the only possible cells for any (all) of those n values make up a group of only n cells, none of those cells is available to any other value in the section (line, column or nonet).
eg, a-g can take any values but 8 or 9. 8 or 9 is therefore restricted to h-i regardless of h and i's earlier possibilities, eg even if they were unrestricted.
The algorithm seems to be slightly different here.

Due to the current layout of my program, the reverse method does not seem as reasonable (in terms of computation time). Will have to have a go at it this week and see what happens.

Will definitely program the 54 triplets sharing a row/nonet or col/nonet, and hope for results.
Jan 6 '09 #27
NeoPa
32,053 Expert Mod 16PB
@jkmyoung
Possibly less mindless crunching than I anticipated then. This is a good thing :)
@jkmyoung
I started from this point, but it's a ba***rd to express in clear English. The order of processing would need to be different (build triplets only on valid pairs and quads only on valid triplets etc. Doable, but I'm guessing a bit more complicated in the design.
@jkmyoung
Perfectly reasonable, but doesn't this just leave you at your starting point (unless you're not considering starting from the same position I am). You already know which values are possible in each individual cell. There doesn't appear to be any further restriction (info) from this.
@jkmyoung
I was considering treating each section (Row; Column or Nonet) separately. Cross referencing separate sections doesn't accrue any benefit that I can perceive (and adds an order of magnitude of complexity). Maybe I'm simply not following you clearly enough.
Jan 7 '09 #28
jkmyoung
2,057 Expert 2GB
The cross-referencing was to take advantage of particular computations that I was already using in my solving algorithm. Actually, why don't I just post it? This tries to determine if there is any number which can only fit within one cell in the row:
Expand|Select|Wrap|Line Numbers
  1.         int parityRow = C[row][0]^C[row][1]^C[row][2]^C[row][3]^C[row][4]^
  2.                         C[row][5]^C[row][6]^C[row][7]^C[row][8];
  3.         int t1or      = C[row][0]|C[row][1]|C[row][2];
  4.         int t2or      = C[row][3]|C[row][4]|C[row][5];
  5.         int t3or      = C[row][6]|C[row][7]|C[row][8];
  6.         int t1and     = C[row][0]&C[row][1]&C[row][2];
  7.         int t2and     = C[row][3]&C[row][4]&C[row][5];
  8.         int t3and     = C[row][6]&C[row][7]&C[row][8];
  9.         int share     = (t1or & t2or) | (t1or & t3or) | (t2or & t3or);
  10.  
  11.         long solveRow  = parityRow & (~share) & (~t1and) & (~t2and) & (~t3and) 
  12.             & solve & (~Row[row]);
  13.  
Explanation:
The or's: find the possibilities in each of the triplets.
The and's: find the numbers which can be placed in any square of the triplet.
share: Find the numbers which can only be in more than one of the triplets.
parityRow: find parity of row.

If the number is set in share, then there's clearly more than one possibility.
If not, then the number is only in one triplet.
Break it down to the 3 cases:
possible in 3 cells. Then it appears in one of the ands.
possible in 2 cells. Then parity is even.
possible in 1 cells. Parity is odd.

So we can find all numbers which are possible in 1 cell this way.

Coded in the check for the 27 triplets for the rows, and the reverse cases (eg check the other 6 cells), but it has given me nothing so far. OH! Just realized that I forgot to call the new functions in the Column and Nonet methods. Will implement it and see what happens.
Jan 15 '09 #29
NeoPa
32,053 Expert Mod 16PB
What type of value do you have in the elements of C (presumably a 9 x 9 array)?

Haven't done c for a while, are :
Expand|Select|Wrap|Line Numbers
  1. ^ ==> EOR
  2. & ==> AND
  3. | ==> OR
Jan 15 '09 #30
jkmyoung
2,057 Expert 2GB
^ ==> XOR
Others are right. With the modifications, have been able to solve puzzle 3.
3 iterations of previous code + 5 iterations of added code.

Am still stuck on puzzle 2. Final output:
Expand|Select|Wrap|Line Numbers
  1. 51--263--
  2. 7264-35-8
  3. 93-5-76--
  4. 395278461
  5. 86--54--9
  6. 47--698-5
  7. -59-41-83
  8. -43--2-5-
  9. -87-35-4-
  10.  
Am going to post a miscellaneous question for solving this sudoku.
Jan 16 '09 #31
NeoPa
32,053 Expert Mod 16PB
What? You think EOR is just a donkey noise (I can't say "ass" as our US cousins may find it too amusing) :D EOR ==> XOR ==> eXclusive OR. Just a notation difference ;)

Reminder: Can you let me know what type of data is held in the array C[][] (at an element level if possible).
Jan 16 '09 #32
jkmyoung
2,057 Expert 2GB
Each cell has an integer associated with it, representing the possible combinations for that square. Each cell uses 10 bits.
1<<0 Lowest order bit, determines if the value is finalized.
1<<1 bit determines if 1 is possible,
1<<2 bit determines if 2 is possible,
etc..
Jan 16 '09 #33
NeoPa
32,053 Expert Mod 16PB
Thanks :)

I realised while going through the three puzzles that Nepo posted, that I had got the fundamental algorithm a little wrong in my post #26. In point #4 it says :
@NeoPa
This is only true if you also check for items that occur only in a limited number of cells. If X items occur only in X cells (of the section), then they can be considered to exclude any other potential answers for any cells within that group.

Consider the following column section of data where the possibilities worked out so far are :
Expand|Select|Wrap|Line Numbers
  1. 1 - 2;4;5;6;7;8;9
  2. 2 - all
  3. 3 - 2;4;5;6;7;8;9
  4. 4 - 2;4;5;6;7;8;9
  5. 5 - 2;4;5;6;7;8;9
  6. 6 - 2;4;5;6;7;8;9
  7. 7 - all
  8. 8 - 2;4;5;6;7;8;9
  9. 9 - 2;4;5;6;7;8;9
In this case it is clear that only entries 2 & 7 may contain the values 1 & 3. Only 2 possible cells with those 2 values. Thus neither can possibly contain any other value.
Expand|Select|Wrap|Line Numbers
  1. 2 - 1;3
  2. 7 - 1;3
Jan 18 '09 #34
JosAH
11,448 Expert 8TB
@NeoPa
Congrats; you've tried to find a Gomory cut. The problem is that those cuts in the search space aren't 'deep', i.e. the cut doesn't just leave one unique optimal solution to the problem. You always have to back track in the search space unless you find something ingenious; let me know then ;-)

kind regards,

Jos
Jan 18 '09 #35
NeoPa
32,053 Expert Mod 16PB
And without even knowing it :D

I did appreciate that I wasn't necessarily finding unique results with this particular process, but simply refining the process of elimination outlined earlier, which should ultimately lead to a unique solution, if there is one.

If I happen to fall over a mathematical theorem while I'm doing that, then all the better. Shows I'm maybe not too far off in my thinking.
Jan 19 '09 #36
JosAH
11,448 Expert 8TB
@NeoPa
Yup, but your phrase "if there is one" tells it all: a partially filled Sudoku matrix may not have one single solution, i.e. more than one completion of the puzzle can be available, leading to all the solutions of that particular puzzle. If that is the case you do have to back track and see where your initial assumption(s) failed or succeeded. For an example see a completely empty Sudoku matrix. There definitely is a solution, but which one to select?

kind regards,

Jos
Jan 19 '09 #37
NeoPa
32,053 Expert Mod 16PB
I would only be looking to see what must be, rather then any random solution.

If there are multiple solutions I would list in each cell the possible values allowed for that cell (For display purposes I leave it blank if all values are possible).

In practice, I would only be interested in a puzzle with a single correct solution anyway, but the code I have works (to the extent that it DOES work) regardless of how many potential solutions there are.
Jan 19 '09 #38
JosAH
11,448 Expert 8TB
@NeoPa
Ok, but realize there's an essential difference between trying to find one single solution (if there is only one) given a partial solution and searching for any or all solutions given any partial solution.

Just because solutions aren't 'quantified', i.e. no cost factor is given to a solution and we can't say solution A is better than solution B those Gomory cuts aren't much help either: those cuts try to minimize the solution space given a cost function of every point in that space.

Maybe solving an 'N-tower' problem N times could be of help here but then again we need that back tracking stuff again.

kind regards,

Jos
Jan 19 '09 #39
NeoPa
32,053 Expert Mod 16PB
Not having followed the full explanation of the Gomory Cuts, and perceiving how you seem to be referring to it, I suspect that what I have is possibly not one of them at all.

I am looking to find the values that must be in cells, or a list of possible values if the information is not available to determine which individual value it should be.

Every iteration of the algorithm (process) has the potential for allowing other aspects of the process to yield more information still, as the result of one iteration is the starting data for the next.

I'm not aware of any sudoku puzzle (with a unique solution) that does not eventually yield up the solution on following the processes listed. Admittedly, as my software doesn't apply the whole algorithm as listed, I've often applied these steps manually (should that be cranially?), but the algorithm is the same in either case.

Where multiple solutions are possible, I've never even looked for a way to itemise the various possible solutions. I don't see that as part of this question, though I'm sure that would be possible with a little work if someone had the interest.
Jan 19 '09 #40
JosAH
11,448 Expert 8TB
@NeoPa
Well, read my article in the Java Howtos section: that brute force solver finds solution(s) given a partial solution no matter whether or not more than one (or zero) solutions are possible.

Those Gomory cuts are algebraic cuts, e.g. if x != 1 all it can do is add two more constraints: x >= 2 and x <= 0 which doesn't help much because you already knew that and now you're stuck with two sub problems.

kind regards,

Jos
Jan 19 '09 #41
NeoPa
32,053 Expert Mod 16PB
@JosAH
From post #34 however, you'll see a before and after image that are clearly different. Whether this is a Gomory Cut I couldn't tell you, but it certainly leads to progress towards a solution.

How you use this (to provide multiple solutions or a statement of what can be determined) is surely irrelevant. I don't see how the eventual results (IE. How this information is later used) has any bearing on the matter. It either progresses the understanding of the problem or it doesn't. I'm pretty sure what I was suggesting does (It's fundamental to how I solve the puzzles myself when I do).
Jan 19 '09 #42
JosAH
11,448 Expert 8TB
All I was saying is this:

Expand|Select|Wrap|Line Numbers
  1.         Puzzle #1:
  2. +-------+-------+-------+
  3. | 5   4 | 8 2 6 | 3 9 7 | 
  4. | 7 2 6 | 4 9 3 | 5   8 | 
  5. | 9 3 8 | 5   7 | 6 2 4 | 
  6. +-------+-------+-------+
  7. | 3 9 5 | 2 7 8 | 4 6   | 
  8. | 8 6   | 3 5 4 | 2 7 9 | 
  9. | 4 7 2 |   6 9 | 8 3 5 | 
  10. +-------+-------+-------+
  11. | 2 5 9 | 6 4   | 7 8 3 | 
  12. |   4 3 | 7 8 2 | 9 5 6 | 
  13. | 6 8 7 | 9 3 5 |   4 2 | 
  14. +-------+-------+-------+
  15.  
  16.         Puzzle #2:
  17. +-------+-------+-------+
  18. |       |       |       | 
  19. |       |       |       | 
  20. |       |       |       | 
  21. +-------+-------+-------+
  22. |       |       |       | 
  23. |       |       |       | 
  24. |       |       |       | 
  25. +-------+-------+-------+
  26. |       |       |       | 
  27. |       |       |       | 
  28. |       |       |       | 
  29. +-------+-------+-------+
  30.  
For puzzle #1 your method can find a (the) solution very quickly but it'll fail miserably for puzzle #2. Both are Sudoku puzzles though; the difference is that puzzle #1 has one and only one solution while puzzle #2 has many solutions. In order to solve all Sudokus you have to deal with two different problems.

kind regards,

Jos
Jan 20 '09 #43
jkmyoung
2,057 Expert 2GB
From post #2, puzzles 1 and 3 have definite solutions. puzzle 2 has multiple solutions.

Using the 54 triplets which share a nonet and either a row or column has solved puzzle #3 and limited the solutions of #2.
====
With above post (#43) perhaps a more interesting task is to determine if a given puzzle has multiple solutions?
Jan 20 '09 #44
JosAH
11,448 Expert 8TB
@jkmyoung
Maybe you like this link and a specialization of it then.

kind regards,

Jos
Jan 20 '09 #45
NeoPa
32,053 Expert Mod 16PB
@jkmyoung
I'd be interested to see your multiple solutions to #2.

I found only the one. I may have slipped up of course, but found only one valid solution.
Grid #2
Expand|Select|Wrap|Line Numbers
  1. |x1x|x2x|3xx|       |514|826|397|
  2. |x2x|4xx|xxx|       |726|493|518|
  3. |x3x|5xx|6xx|       |938|517|624|
  4.  
  5. |3xx|x7x|xx1|       |395|278|461|
  6. |8xx|xxx|xx9|       |861|354|279|
  7. |4xx|x6x|xx5|       |472|169|835|
  8.  
  9. |xx9|xx1|x8x|       |259|641|783|
  10. |xxx|xx2|x5x|       |143|782|956|
  11. |xx7|x3x|x4x|       |687|935|142|
Jan 20 '09 #46
JosAH
11,448 Expert 8TB
@NeoPa
According to my stupid brute force solver there's only one solution.

kind regards,

Jos
Jan 21 '09 #47
jkmyoung
2,057 Expert 2GB
I get 2 more solutions corresponding to the following:
Expand|Select|Wrap|Line Numbers
  1. +-------+-------+-------+  
  2. | 5 1 8 | 9 2 6 | 3 7 4 |  
  3. | 7 2 6 | 4 1 3 | 5 9 8 |  
  4. | 9 3 4 | 5 8 7 | 6 1 2 |  
  5. +-------+-------+-------+  
  6. | 3 9 5 | 2 7 8 | 4 6 1 |  
  7. | 8 6 - | - 5 4 | 7 - 9 |  
  8. | 4 7 - | - 6 9 | 8 - 5 |  
  9. +-------+-------+-------+  
  10. | 6 5 9 | 7 4 1 | 2 8 3 |  
  11. | 1 4 3 | 8 9 2 | 1 5 7 |  
  12. | 2 8 7 | 6 3 5 | 9 4 6 |  
  13. +-------+-------+-------+ 
  14.  
Relied on another online sudoku solver to find it, so hopefully it validates.
Jan 21 '09 #48
JosAH
11,448 Expert 8TB
@jkmyoung

That is an infeasible partial solution:

8,7: 1
9,9: 6

kind regards,

Jos
Jan 21 '09 #49
NeoPa
32,053 Expert Mod 16PB
@jkmyoung
That's why I was after a solution. So that I could check it out :S
Jan 21 '09 #50

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

5 posts views Thread by sub1ime_uk | last post: by
5 posts views Thread by Stewart Gordon | last post: by
12 posts views Thread by kalinga1234 | last post: by
4 posts views Thread by hashimtk | last post: by
10 posts views Thread by doubleac | last post: by
38 posts views Thread by Boon | last post: by
3 posts views Thread by Ri0o | last post: by
1 post views Thread by 361162 | last post: by
reply views Thread by NPC403 | last post: by
reply views Thread by kermitthefrogpy | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.