Jump to content
BrainDen.com - Brain Teasers
  • 0

Prove that you solved sudoku


harey
 Share

Question

11 answers to this question

Recommended Posts

  • 0

one approach 

compute a CRC or checksum, etc. and publish it. When someone does find the solution, they use the same algorithm and arrive at the same checksum, and thus see that you must have found the solution before them. But the published value of the checksum will not give any hints about any details of the solution.

Link to comment
Share on other sites

  • 0

@Jason

Not bad, we might come to the solution this way in 2-3 steps. (Just YOU solved the sudoku, so YOU enter the answer).

Hint: Be a little more specific about the program. How should I write the program that you cannot fool it by entering  shifted 1 2 3 4 5 6 7 8 9 for every line/column?

Edited by harey
Link to comment
Share on other sites

  • 0

Rephrasing my addition to Jasen's answer in response to Harey's hint:

Jasen has solved a difficult Sudoku problem, and is bragging to Harey.
Harey has a dilemma: ( a ) How can he believe Jasen? ( b ) Harey wants to attack the problem himself, but doesn't want to know Jasen's solution

Solution:
Jasen's twin brother writes a program that takes two inputs:
( i ) a sudoku problem (mostly blanks, a few numbers)
( ii ) a proposed solution (all cells filled)
this program verifies that every row contains one each of the digits 1-9, every column contains one each of 1-9, and every block of 9 contains one each of 1-9 AND cells match the non-blank cells of input 1 
The final view shows only VALID or INVALID

Harey enters the sudoku problem as input 1, then moves away from the keyboard/monitor
Jasen enters the proposed solution as input 2, presses NEXT
Harey  comes to the monitor and reads the final view

Link to comment
Share on other sites

  • 0

@CaptainEd  Good work.... But why so complicated? No need for a third person.

<spoiler>

1) The solver secretly creates a matrix with the complete solution. Known numbers are preceded by a star.

2) The challenger writes a program that takes as input this matrix. The program displays numbers preceded by a star and blanks for numbers not preceded by a star and makes the necessary checks. (If the solver fears the program would display everything, it can be tested on another grid.)

3) The solver wipes the harddisk (optional).

</spoiler>

Almost there. Just the computerized solution does not have the beauty of the manual solution - as I said, it is an intermediate step. How can it be done without a computer? All you need: scissors, paper, pencil.

Edited by harey
Link to comment
Share on other sites

  • 0

it seems to me what you really need is an encryption method that can be reversed if necessary but would take longer to reverse than to solve the sudoku yourself and get the same encryption.  what do you think of this idea? it may not even require a computer, depending on how difficult the encryption method is. 

Link to comment
Share on other sites

  • 0

after a week long journey abroad, now I'm active again.

@phil1882: The solution does not require a computer. I do not see well encrypting decrypting by hand.

 All you need: scissors, paper, pencil.

After thinking again, and using the clue harrey give us (scisors, pen, and paper),

Yes it is possible to prove it without computer, but it takes many steps.

1. You write your solution on a answering paper.
2. Put it with back side up on the floor, and ask your friend (who need prove) to numbering it. Better numbering it like (horz, vert) format
3. Cut it to smaller peaces, every squere (with a number) 1 peace.
4. Rearrange it with back side up, then turn over/show the numbers in question in the right place. (means you are not cheating)
5. now take all the squares in first row, suffle it, turn then over secreatly, and show them to your friend, that all number from 1 to 9 are there.
back to step 4 and do the same with other rows (vert and horz). and other 3x3 squares.

Link to comment
Share on other sites

  • 0

@Jasen I think you got it, but SO confusing.

1) Insert the solution on small pieces of paper into the original grid, numbers down. (You better use a non-transparent paper.)
2) For each row/column/square I ask, collect your papers and show them to me in ascending order: (With the original numbers, 1-9 will be used exactly once.)
3) Put your pieces of paper back.

Edited by harey
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...