Validating a completed sudoku grid
salmo...@aol.com
or be able to suggest a different forum..
If you have a completed sudoku grid, you supposedly need to check all
9 rows, then all 9 columns, then all 9 boxes to validate that it has
been completed correctly. But it's pretty obvious that the grid can be
validated with somewhat less checking. For instance, if each of the
boxes has been checked and the first 2 rows are checked, there's no
need to check the 3rd row.
So what's the minimum amount of checking that needs to be done to show
that a completed 9x9 grid is valid?
Brian Tung
If you switch the last two numbers in the entire 81-square grid, then
all boxes check out and all rows check out, but the last two columns
won't. A transpose of that means that all boxes check out and all
columns check out, but the last two rows won't.
Not obvious in a minute of thinking whether there's always a way to
modify a working grid to get all rows and columns to check out, but not
the boxes.
--
Brian Tung <br...@aero.org>
NOTE: Below addresses changing soon...
The Astronomy Corner at http://astro.isi.edu/
Unofficial C5+ Home Page at http://astro.isi.edu/c5plus/
The PleiadAtlas Home Page at http://astro.isi.edu/pleiadatlas/
My Own Personal FAQ (SAA) at http://astro.isi.edu/reference/faq.html
Freddy Flares
news:243ac1fb-ea1b-447a...@m44g2000hsc.googlegroups.com...
Spoiler space
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
First check the boxes then add all the 9 digit numbers in each row. Total
should be 4999999995 for all correct grids and something else if the grid is
wrong. Haven't proved it though.
Could you get away without pre-checking the last box?
FF.
Freddy Flares
news:m6mdnc5n8bikEa3V...@bt.com...
> <salmo...@aol.com> wrote in message
> news:243ac1fb-ea1b-447a...@m44g2000hsc.googlegroups.com...
>> Quick question that I though someone here might know the answer to -
>> or be able to suggest a different forum..
>>
>> If you have a completed sudoku grid, you supposedly need to check all
>> 9 rows, then all 9 columns, then all 9 boxes to validate that it has
>> been completed correctly. But it's pretty obvious that the grid can be
>> validated with somewhat less checking. For instance, if each of the
>> boxes has been checked and the first 2 rows are checked, there's no
>> need to check the 3rd row.
>>
>> So what's the minimum amount of checking that needs to be done to show
>> that a completed 9x9 grid is valid?
>>
>.
>.
> First check the boxes then add all the 9 digit numbers in each row. Total
> should be 4999999995 for all correct grids and something else if the grid
> is wrong. Haven't proved it though.
>
Doesn't work, you can interchange whole boxes in a given column and the
total still checks out, oh well.
FF.
salmo...@aol.com
> modify a working grid to get all rows and columns to check out, but not
> the boxes.
First row is 1,2,3,....8, 9
Second row is 2,3,4.... 9,1
...
Ninth Row is 9,1,2,.....7,8 8
Brian Tung
Not sure what this is supposed to represent, but the question is how to
permute the 81-square grid in such a way that all rows and columns still
work, but the boxes no longer do. Does the above represent such a
permutation?
salmo...@aol.com
> > Second row is 2,3,4.... 9,1
> > ...
> > Ninth Row is 9,1,2,.....7,8 8
>
> Not sure what this is supposed to represent, but the question is how to
> permute the 81-square grid in such a way that all rows and columns still
> work, but the boxes no longer do. Does the above represent such a
> permutation?
Yes - the rows and columns work, the boxes don't.
Barbara Bailey
7fb162...@b64g2000hsa.googlegroups.com:
The rows and columns don't work either, if the last row is really what
what's up there: 9,1,2, ... 7,8,8. Some number between 2 and 7 is missing
in row 9, and that row contains two 8's. Column 8 also contains two 8's
--the one in row 1 and the one in row 9.
However, I think that any valid sudoku could be permuted into one with
both the rows and columns working but not the boxes. I just don't know
how to explain it clearly.
Here's a valid grid:
365 874 921
189 632 475
724 951 836
492 765 183
631 248 759
857 193 642
913 587 264
248 316 597
576 429 318
Transpose two rows which encompass six boxes and which have four or fewer
number in common in paired boxes. In this case, row 1 and row 4 will
work. That produces this grid:
492 765 183 <<<this was row 4 originally.
189 632 475
724 951 836
365 874 921 <<<this was row 1 originally.
631 248 759
857 193 642
913 587 264
248 316 597
576 429 318
The rows haven't changed internally -- they all still work.
The columns haven't changed internally -- they also all still work.
However, the top six boxes are all faulty now; box #1 has dupes of 2, 4,
and 9; box #2 of 5 and 6; #3 of 3 and 8; #4 of 3, 5, and 6; #5 of 4 and
8; and #6 dupes 2 and 9
jonnie303
I check my sudoku differently. I look at all the 1s, and check that
they're all in different boxes and that no two of them lie on the same
column or row. Then I repeat the procedure for the 2s, 3s, and so on.
It seems very quick.
-------------
jonnie303
sevenoaks, uk
Tim Woodall
Barbara Bailey <rabr...@yayhu.comm> wrote:
>
> However, I think that any valid sudoku could be permuted into one with
> both the rows and columns working but not the boxes. I just don't know
> how to explain it clearly.
>
> Here's a valid grid:
>
> 365 874 921
> 189 632 475
> 724 951 836
>
> 492 765 183
> 631 248 759
> 857 193 642
>
> 913 587 264
> 248 316 597
> 576 429 318
>
> Transpose two rows which encompass six boxes and which have four or fewer
> number in common in paired boxes. In this case, row 1 and row 4 will
> work. That produces this grid:
>
You can do better than that and only corrupt four boxes. Anywhere you've
got a
A B
B A
Pattern in four boxes you can swap the A and B. E.g. below I've swapped
the 9s and 8s in the fifth and ninth row.
> 365 874 921
> 189 632 475
> 724 951 836
>
> 492 765 183
> 631 249 758 <<< 9 and 8 exchanged
> 857 193 642
>
> 913 587 264
> 248 316 597
> 576 428 319 <<< 9 and 8 exchanged
>
Not certain if you can improve on that but I suspect not.
Tim.
--
God said, "div D = rho, div B = 0, curl E = - @B/@t, curl H = J + @D/@t,"
and there was light.
remys...@yahoo.com
> So what's the minimum amount of checking that needs to be done to show
> that a completed 9x9 grid is valid?
When I do sudoku by spreadsheet, I sum the rows and columns and the
3x3 squares. All sums must be 45. I'm sure there's an exception, but
it reduces the possibility of having used duplicate numbers by
mistake, and I've never had a problem with it.
Barbara Bailey
news:slrng33uf8....@dirac.home.woodall.me.uk:
That *is* more elegant. Is it as likely to be possible, though? What's
the probability of having an
AB
BA
square somewhere on the board? I'm not sure how to figure that.
I was looking for something that was likely to occur in any valid grid,
and there are 27 possible permutations of two rows and 27 of columns
regardless of the way the numbers are arranged.
Robby Goetschalckx
Recently we had a seminar about this by Bart Demoen at out university.
Of the 27 'big rules' (rows, columns, boxes), you only need to check 21
- if you choose them correctly.
Bart can surely give you all the details you wanted and more ...
cheers,
robby
Abigail
Robby Goetschalckx (ro...@cs.kuleuven.ac.be) wrote on VCCCLXXVII
September MCMXCIII in <URL:news:4833FD40...@cs.kuleuven.ac.be>:
++ salmo...@aol.com wrote:
++ > Quick question that I though someone here might know the answer to -
++ > or be able to suggest a different forum..
++ >
++ > If you have a completed sudoku grid, you supposedly need to check all
++ > 9 rows, then all 9 columns, then all 9 boxes to validate that it has
++ > been completed correctly. But it's pretty obvious that the grid can be
++ > validated with somewhat less checking. For instance, if each of the
++ > boxes has been checked and the first 2 rows are checked, there's no
++ > need to check the 3rd row.
++ >
++ > So what's the minimum amount of checking that needs to be done to show
++ > that a completed 9x9 grid is valid?
++
++ Recently we had a seminar about this by Bart Demoen at out university.
++ Of the 27 'big rules' (rows, columns, boxes), you only need to check 21
++ - if you choose them correctly.
All you need is a single regular expression.
Abigail
Freddy Flares
news:slrng382cq....@alexandra.abigail.be...
What's your point?
Bart Demoen
Let's number box rules as
B1 B2 B3
B4 B5 B6
B7 B8 B9
row rules as R1 ... R9 and
column rules as C1 ... C9
Then (for instance) it is enough to check
B1 B3 B7 B9 C1 ... C9 R1 R2 R3 R4 R6 R7 R8 R9
(this misses B2 B4 B5 B6 B8 and R5)
or
B1 ... B9 R2 R3 R5 R6 R8 R9 C2 C3 C5 C6 C8 C9
(this misses R1 R4 R7 C1 C4 C7)
There are 38 more essentially different such sets of 21 rules that are equivalent
to the whole set of 27 rules - all other sets can be obtained by applying
the usual spatial symmetries.
No set of 20 (box column row) rules is equivalent to the 27 rules, so in general
you can't check less than 21.
Does this answer your question ?
My interest in this came from redundant constraints in CSP's - I basically know
very little about Sudoku: my apologies if my terminology is bad.
We proved the above partly by a computer program, partly by hand proving some
lemmas - we had no idea whether this was known before (and we still don't
know: if you have pointers, please tell me).
[We = me and Maria Garcia de la Banda]
Cheers
Bart Demoen
salmo...@aol.com
> (this misses R1 R4 R7 C1 C4 C7)
> No set of 20 (box column row) rules is equivalent to the 27 rules, so in general
> you can't check less than 21.
>
> Does this answer your question ?
Yes, thanks. The one above is what I use. Nice to hear it can't be
bested. But also kinda sad, as it's "simple". Be cool if it could be
bested.
Aslam Siddiqui
I'm not sure I understand the question. May be it's directed to the real
serious and compulsive solvers who use timers. Me, I do it for mental
stimulation and entertainment only. Every single time I write in a
number I check it immediately against the column, row and the box.
By the way, if you are solving the puzzle alone in your den, what does
the time mean? All puzzles are different, the assigned degree of
difficulty is arbitrary. The timers are useful only when several people
are doing the same puzzle at the same time (or comparing with a buddy at
a later time).
aslam
S.C.Sprong
>salmo...@aol.com wrote:
>> So what's the minimum amount of checking that needs to be done to show
>> that a completed 9x9 grid is valid?
>I'm not sure I understand the question. May be it's directed to the real
>serious and compulsive solvers who use timers.
The question is not for the OCD's but for the mathematicians:
"There is redundancy observed in checking all rows and columns to verify
the correctness of a Sudoku solution. Can this redundancy be removed and if
so, is there a theoretical required minimum of checks for all possible
Sudoku grids of size n?"
I think it's nice that there's already a solution available.
scs
Anthony Buckland
"S.C.Sprong" <scsp...@gmail.com> wrote in message
news:6aftt4F...@mid.individual.net...
Take a valid n=9 solution. Pick on any 2 by 2 square crossing
the line or column boundary (but not both) between
3 by 3 squares. Interchange the columns and rows
which intersect to form the 2 by 2 square. Every column
and row is still ok, but now two 3 by 3 squares are invalid
(in general -- there are a few cases in which validity remains).
This implies that there are solutions requiring checking all
rows, all columns and eight 3 by 3 squares. The minimum
number of checks is 26 out of 27, for n = 9.
S.C.Sprong
>> the correctness of a Sudoku solution. Can this redundancy be removed and
>> if so, is there a theoretical required minimum of checks for all possible
>> Sudoku grids of size n?"
>rows, all columns and eight 3 by 3 squares. The minimum
>number of checks is 26 out of 27, for n = 9.
Check Bart Demoen's posting dd May 21nd; he claims a minimum of 21 for
n = 9.
scs
Bart Demoen
> Take a valid n=9 solution. Pick on any 2 by 2 square crossing
> the line or column boundary (but not both) between
> 3 by 3 squares. Interchange the columns and rows
> which intersect to form the 2 by 2 square. Every column
> and row is still ok, but now two 3 by 3 squares are invalid
> (in general -- there are a few cases in which validity remains).
> This implies that there are solutions requiring checking all
> rows, all columns and eight 3 by 3 squares. The minimum
> number of checks is 26 out of 27, for n = 9.
>
>
I am not sure I understand what you meant. Would interchanging
col3 with col4 and at the same time interchanging row1 with row2
comply with your description ? Or could you give an example ?
It is true that one can fill a puzzle such that
exactly two rules (out of the 27) are violated; what our result about 21
says is this: checking 21 is enough to decide whether your puzzle violates
any rule or not; of course, the result does not say that ANY selection of
21 will do that job - which is what you seem to want to show (and once more,
you are right).
Cheers
Bart Demoen
bart....@gmail.com
> Quick question that I though someone here might know the answer to -
> or be able to suggest a different forum..
it still worth telling this newsgroup that
a paper describing the redundant (large) constraints in Sudoku has
been accepted by "Theory and Practice of Logic Programming"; see
http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=8729246&fulltextType=RA&fileId=S1471068412000361
There is also a version at http://arxiv.org/abs/1207.5926
The title of the paper is "Redundant Sudoku Rules"
Cheers
Bart Demoen and Maria Garcia de la Banda
Curlytop
space-time continuum:
> The title of the paper is "Redundant Sudoku Rules"
solution?
--
ξ: ) Proud to be curly
Interchange the alphabetic letter groups to reply
James Dow Allen
> Just wondering - is it possible for a Sudoku to have more than one valid
> solution?
solution.
If that constraint is removed, starting grids may have multiple
solutions;
in particular, the empty grid has 6,670,903,752,021,072,936,960
solutions.
> --
> ξ: ) Proud to be curly
ภูมิใจที่ได้เป็นหยิก
Robin Halligan
bart....@gmail.com set the following eddies spiralling through the
space-time continuum:
> The title of the paper is "Redundant Sudoku Rules"
>Just wondering - is it possible for a Sudoku to have more than one valid
>solution?
http://www.youtube.com/watch?v=MlyTq-xVkQE