1
  • A sudoku net is defined here.

A sudoku net is defined as 'pseudo-solvable' if we can deduce at least two valid 'not unique' solutions.

  • friendly sudoku is defined here

What is the sudoku net with the minimum possible blocks in such a way that this sudoku net is pseudo-solvable with at least one friendly sudoku?

Challenge 2

Find a sudoku net $N$ with visible set $V_N$ such that for any sudoku $S_1$, there is another $S_2\ne S_1$ where $V_N(S_1) = V_N(S_2)$ and $|V_N|$ is maximal.

Bonus question: (it is worth 50pts) is there any condition of pattern arrangements inside blanks which makes a sudoku unsolvable using previous result as work-domain?

bobble
  • 10,245
  • 4
  • 32
  • 80
Abr001am
  • 1,004
  • 8
  • 27
  • Can you clarify the order of quantifiers? (Something like: FIND a net such that FOR ALL solved sudokus, if you place the net over the sudoku, then THERE EXISTS at least two solutions to the resulting puzzle) – Lopsy Apr 24 '15 at 16:24
  • @Lopsy in fact its not for all arrangements , there is specific oredering which would work it out – Abr001am Apr 24 '15 at 16:29
  • @Lopsy in that case such sudoko can be with 80 blocks so trivial for a question dont you think ? – Abr001am Apr 24 '15 at 16:40
  • @Lopsy does it look pleasant or encouraging now ? – Abr001am Apr 24 '15 at 16:57
  • 2
    Honestly I'm still not 100% sure what you mean, and I wouldn't want to work on a question like this one only to be told that I solved the wrong puzzle. Is your first question equivalent to "What's the smallest possible number of cells you can change to get from one solved Sudoku to a different solved Sudoku?" – Lopsy Apr 24 '15 at 17:11
  • For the second question, first we take the random sudoku, then build a net on it ), or do we have to build a net that works for any random sudoku? – leoll2 Apr 24 '15 at 17:21
  • the second net is laid above a solved sudoko – Abr001am Apr 24 '15 at 17:22
  • Yes, but can we look at the sudoku before building the net (I mean, to build a specific net for each kind of sudoku, as they aren't all the same)? – leoll2 Apr 24 '15 at 17:24
  • @leoll2 if you want to divide and rule all cases , im not advicing that as a solution , otherwise the solved-sudoko can be whatever still solved one when you put the net at the top. – Abr001am Apr 24 '15 at 17:48
  • @Ian MacDonald seems that your recent edit contradicts leoll2 's answer – Abr001am Apr 24 '15 at 21:54
  • @Agawa001 if that's how you feel, then maybe his answer is wrong. His answer to the question that I edited is "it depends on the sudoku", which is not answering an interesting question at all. – Ian MacDonald Apr 24 '15 at 21:56
  • @IanMacDonald so i think i did just answer my own question without paying attention :/ , exept if someone would do better (not the condition part) – Abr001am Apr 24 '15 at 22:13

2 Answers2

3

MINIMUM BLOCKED BOXES:

$4$

O O A | O O O | C O O
O O O | O O O | O O O
O O B | O O O | D O O
-------------------------------
O O O | O O O | O O O
O O O | O O O | O O O
O O O | O O O | O O O
-------------------------------
O O O | O O O | O O O
O O O | O O O | O O O
O O O | O O O | O O O

Where A,B,C,D are equal in pairs (the O are given numbers).
Suppose that both the top-left and the top-right squares are missing the numbers 5 and 7. If you swap A with B, and C with D the sudoku will be still valid. This means that if you have clues about all cells except A,B,C,D there are 2 different valid solutions to the sudoku, which means UNSOLVABLE.

Given a random solved sudoku, what's the minimal net that makes it pseudo-solvable?
The answer is: it depends on the sudoku! Some particular sudoku need a net with just $4$ blocks, like the one showed in the picture, while other require up to $18$ blocks to become pseudo-solvable (put the blocks on all $1$ and $2$). Example of the latter configuration is here:

enter image description here

If you want a net that works for any sudoku, independently from the grid, just put the blocks on the first and second row. Anyway, this would still require $18$ blocks, not better than my previous solution.

When is a sudoku pseudo-solvable?

When you don't have information about $4$ cells, arranged on a rectangular shape, such that $2$ of them belong to a quadrant, while the other $2$ belong to another quadrant (as shown in the above picture); also, the cells on the opposite vertices of the rectangle should contain the same values!

Let's say these values are $a$ and $b$ and the pattern is the same described in the above picture. The first row says the A and C must contain $a$ and $b$, but doesn't say in which order. Same for the third row, third column, seventh column, top-left box, top-right box. This means, there are $2$ valid solutions for this sudoku.

When is a sudoku NOT pseudo-solvable?

This means solvable or impossible! A Sudoku is impossible when it has internal contradictions (like two $7$ in the same row). When the sudoku isn't impossible (aka possible), it can be either solvable (admits 1 solution) or pseudo-solvable (admits 2+ solutions). How to tell them? First of all, given a grid, fill as many cells as possible using deductions. Now, if you have 4 unknown cells arranged in a rectangular pattern (see above for the other conditions), then the sudoku is pseudo-solvable!

Community
  • 1
leoll2
  • 12,590
  • 3
  • 39
  • 83
  • this is correct for the first question . – Abr001am Apr 24 '15 at 16:55
  • @Agawa001 Added answer for the second, thinking about the bonus. – leoll2 Apr 24 '15 at 17:02
  • i changed the content btw , but your first intervention is still valid – Abr001am Apr 24 '15 at 17:03
  • leoll2 refering to your latest edit , do you mean the shortest chain ? – Abr001am Apr 24 '15 at 18:11
  • @Agawa001 my last edit is the answer to the 2nd question, I provided the minimum number of blocks in a net that transforms a solved sudoku into a pseudo-solvable one! – leoll2 Apr 24 '15 at 18:32
  • i know , but we can never know where is that chain ? henceforth you should case-separate your solution , which is very very hard and tiring – Abr001am Apr 24 '15 at 18:37
  • @Agawa001 I've just posted an example configuration where you'll never find the "rectangular pattern", so you can't make it pseudo-solvable with just 4 blocks. So far, the best way I found to make it pseudo-solvable is adding 18 blocks. – leoll2 Apr 24 '15 at 18:54
  • it depends on the shortest chain of the worst case grid... so are you saying that you did just discovered a grid with 36 maximal chains !? – Abr001am Apr 24 '15 at 19:04
0

my answer for the second question may be :

# # # | # # # | # # #

# # # | # # # | # # #

____ | ____ | ____

____ | ____ | ____

____ | ____ | ____

____ | ____ | ____

____ | ____ | ____

____ | ____ | ____

____ | ____ | ____

18 blocks

bonus question :

any logical relation isnt known yet but sure ... it would have something to do with graph-theory

Abr001am
  • 1,004
  • 8
  • 27