Yhyjyk

Parent theme necessary?

Define, (actually define) the "stability" and "energy" of a compound

Co-worker team leader wants to inject his friend's awful software into our development. What should I say to our common boss?

My Graph Theory Students

Are all passive ability checks floors for active ability checks?

AG's and indictments

Equilateral triangle on a concentric circle

Are the common programs (for example: "ls", "cat") in Linux and BSD come from the same source code?

Time travel from stationary position?

How to simplify this time periods definition interface?

If I can solve Sudoku can I solve Travelling Salesman Problem(TSP)? If yes, how?

How do anti-virus programs start at Windows boot?

Is it possible to learn piano technique from the book alone?

Identifying the interval from A♭ to D♯

Do I need life insurance if I can cover my own funeral costs?

How to prevent Firefox and Chrome from opening ports in the firewall?

How to terminate ping <dest> &

What's the meaning of “spike” in the context of “adrenaline spike”?

Is this ununderstandable character part of the conflict?

How can I track script which gives me "command not found" right after the login?

Professor being mistaken for a grad student

Official degrees of earth’s rotation per day

Brexit - No Deal Rejection

What should tie a collection of short-stories together?

If I can solve Sudoku can I solve Travelling Salesman Problem(TSP)? If yes, how?

When can a greedy algorithm solve the coin change problem?Finding the subset of $S$ that sums up to $k$ using a black box in $O(n)$ timeHow to find partition set of a Partition Problem using its decision problemHow can we design an efficient warehouse management program?A Black Box AlgorithmFinding vertices of a maximum clique in polynomial timeIs this an instance of a well-known problem?Polytime algorithm for SUBSET-SUM assuming P=NPHow can I use prefix sum of an array to solve this problem?Applying a permutation on a sequence with multiplication

5

2

$begingroup$

Let us say there is a program such that if you give a partially filled Sudoku of any size it gives you corresponding completed Sudoku.

Can you treat this program as a black box and use this to solve TSP? I mean is there a way to represent TSP problem as partially filled Sudoku, so that if I give you the answer of that Sudoku, you can tell the solution for TSP in polynomial time?

If yes, how? how do you represent TSP as a partially filled Sudoku and interpret corresponding filled Sudoku for the result.

algorithms np-complete

share|cite|improve this question

edited 47 mins ago

Chakrapani N Rao

asked 11 hours ago

Chakrapani N RaoChakrapani N Rao

317

New contributor

Chakrapani N Rao is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Nowhere on this page (in the question or either answer or comments) is "TSP" defined. Especially since this question is now on the Hot Network Questions list, a definition for outsiders would be a very nice addition.
  $endgroup$
  – Wildcard
  58 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Wildcard done.
  $endgroup$
  – Chakrapani N Rao
  46 mins ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Wildcard Within computer science, it's so widely understood that TSP means "travelling salesman problem" that asking somebody to expand the abbreviation it is a bit like asking them to define "PC" on Super User. Sure, adding the definition doesn't hurt, but somebody who doesn't know the definition probably isn't going to get anything out of the question, anyway.
  $endgroup$
  – David Richerby
  30 mins ago
  

  
  
  
  

add a comment | 

5

2

$begingroup$

Let us say there is a program such that if you give a partially filled Sudoku of any size it gives you corresponding completed Sudoku.

Can you treat this program as a black box and use this to solve TSP? I mean is there a way to represent TSP problem as partially filled Sudoku, so that if I give you the answer of that Sudoku, you can tell the solution for TSP in polynomial time?

If yes, how? how do you represent TSP as a partially filled Sudoku and interpret corresponding filled Sudoku for the result.

algorithms np-complete

share|cite|improve this question

edited 47 mins ago

Chakrapani N Rao

asked 11 hours ago

Chakrapani N RaoChakrapani N Rao

317

New contributor

Chakrapani N Rao is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Nowhere on this page (in the question or either answer or comments) is "TSP" defined. Especially since this question is now on the Hot Network Questions list, a definition for outsiders would be a very nice addition.
  $endgroup$
  – Wildcard
  58 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Wildcard done.
  $endgroup$
  – Chakrapani N Rao
  46 mins ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Wildcard Within computer science, it's so widely understood that TSP means "travelling salesman problem" that asking somebody to expand the abbreviation it is a bit like asking them to define "PC" on Super User. Sure, adding the definition doesn't hurt, but somebody who doesn't know the definition probably isn't going to get anything out of the question, anyway.
  $endgroup$
  – David Richerby
  30 mins ago
  

  
  
  
  

add a comment | 

$begingroup$

Let us say there is a program such that if you give a partially filled Sudoku of any size it gives you corresponding completed Sudoku.

Can you treat this program as a black box and use this to solve TSP? I mean is there a way to represent TSP problem as partially filled Sudoku, so that if I give you the answer of that Sudoku, you can tell the solution for TSP in polynomial time?

If yes, how? how do you represent TSP as a partially filled Sudoku and interpret corresponding filled Sudoku for the result.

algorithms np-complete

share|cite|improve this question

edited 47 mins ago

Chakrapani N Rao

asked 11 hours ago

Chakrapani N RaoChakrapani N Rao

317

New contributor

Chakrapani N Rao is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|cite|improve this question

edited 47 mins ago

Chakrapani N Rao

asked 11 hours ago

Chakrapani N RaoChakrapani N Rao

317

New contributor

Chakrapani N Rao is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|cite|improve this question

edited 47 mins ago

Chakrapani N Rao

asked 11 hours ago

Chakrapani N RaoChakrapani N Rao

317

New contributor

Chakrapani N Rao is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 11 hours ago

Chakrapani N RaoChakrapani N Rao

317

New contributor

Chakrapani N Rao is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 11 hours ago

Chakrapani N RaoChakrapani N Rao

317

1 Answer
1

active

oldest

votes

10

$begingroup$

For 9x9 Sudoku, no. It is finite so can be solved in $O(1)$ time.

But if you had a solver for $n^2 times n^2$ Sudoku, that worked for all $n$ and all possible partial boards, then yes, that could be used to solve TSP in polynomial time, as completing a $n^2 times n^2$ Sudoku is NP-complete.

The proof of NP-completeness works by reducing from some NP-complete problem R to Sudoku; then because R is NP-complete, you can reduce from TSP to R (that follows from the definition of NP-completeness); and chaining those reductions gives you a way to use the Sudoku solver to solve TSP.

share|cite|improve this answer

edited 10 hours ago

answered 10 hours ago

D.W.♦D.W.

101k12124289

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Could you please explain how? Yes lets assume I have general sudoku solver which acts as a black box. So how can you use it? How do you represent TSP as a partially filled Sudoku
  $endgroup$
  – Chakrapani N Rao
  10 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @ChakrapaniNRao, see updated answer. Yes, I understand it is a black box. To work out the details, find the proof of NP-completeness for Sudoku and understand how the reduction works.
  $endgroup$
  – D.W.♦
  10 hours ago
  

  
  
  
  


• 
  
  
  

  
  4
  

  
  
  
  
  
  

  
  $begingroup$
  @ChakrapaniNRao It doesn't answer the question completely but the full answer would be ridiculously long, be full of intricate details and wouldn't give you any more enlightenment than the sketch here. It's possible that a reduction of some NP-complete problem to $n^2times n^2$ sudoku might be interesting but, unless the proof that sudoku is NP-complete was actually by reduction from TSP (unlikely), the answer is still going to end "and then chain those two reductions together".
  $endgroup$
  – David Richerby
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  OK, so we do not have a working solution for the above question then?
  $endgroup$
  – Chakrapani N Rao
  48 mins ago
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  @ChakrapaniNRao You are asking how to solve problem X using a black box for problem Y. That is literally asking for a reduction. That's what "reduction" means. And, as this answer explains, the answer to your yes/no question is yes.
  $endgroup$
  – David Richerby
  40 mins ago
  

  
  
  
  

 | 
show 1 more comment

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

Chakrapani N Rao is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105618%2fif-i-can-solve-sudoku-can-i-solve-travelling-salesman-problemtsp-if-yes-how%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

10

$begingroup$

For 9x9 Sudoku, no. It is finite so can be solved in $O(1)$ time.

But if you had a solver for $n^2 times n^2$ Sudoku, that worked for all $n$ and all possible partial boards, then yes, that could be used to solve TSP in polynomial time, as completing a $n^2 times n^2$ Sudoku is NP-complete.

The proof of NP-completeness works by reducing from some NP-complete problem R to Sudoku; then because R is NP-complete, you can reduce from TSP to R (that follows from the definition of NP-completeness); and chaining those reductions gives you a way to use the Sudoku solver to solve TSP.

share|cite|improve this answer

edited 10 hours ago

answered 10 hours ago

D.W.♦D.W.

101k12124289

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Could you please explain how? Yes lets assume I have general sudoku solver which acts as a black box. So how can you use it? How do you represent TSP as a partially filled Sudoku
  $endgroup$
  – Chakrapani N Rao
  10 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @ChakrapaniNRao, see updated answer. Yes, I understand it is a black box. To work out the details, find the proof of NP-completeness for Sudoku and understand how the reduction works.
  $endgroup$
  – D.W.♦
  10 hours ago
  

  
  
  
  


• 
  
  
  

  
  4
  

  
  
  
  
  
  

  
  $begingroup$
  @ChakrapaniNRao It doesn't answer the question completely but the full answer would be ridiculously long, be full of intricate details and wouldn't give you any more enlightenment than the sketch here. It's possible that a reduction of some NP-complete problem to $n^2times n^2$ sudoku might be interesting but, unless the proof that sudoku is NP-complete was actually by reduction from TSP (unlikely), the answer is still going to end "and then chain those two reductions together".
  $endgroup$
  – David Richerby
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  OK, so we do not have a working solution for the above question then?
  $endgroup$
  – Chakrapani N Rao
  48 mins ago
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  @ChakrapaniNRao You are asking how to solve problem X using a black box for problem Y. That is literally asking for a reduction. That's what "reduction" means. And, as this answer explains, the answer to your yes/no question is yes.
  $endgroup$
  – David Richerby
  40 mins ago
  

  
  
  
  

 | 
show 1 more comment

10

$begingroup$

For 9x9 Sudoku, no. It is finite so can be solved in $O(1)$ time.

But if you had a solver for $n^2 times n^2$ Sudoku, that worked for all $n$ and all possible partial boards, then yes, that could be used to solve TSP in polynomial time, as completing a $n^2 times n^2$ Sudoku is NP-complete.

The proof of NP-completeness works by reducing from some NP-complete problem R to Sudoku; then because R is NP-complete, you can reduce from TSP to R (that follows from the definition of NP-completeness); and chaining those reductions gives you a way to use the Sudoku solver to solve TSP.

share|cite|improve this answer

edited 10 hours ago

answered 10 hours ago

D.W.♦D.W.

101k12124289

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Could you please explain how? Yes lets assume I have general sudoku solver which acts as a black box. So how can you use it? How do you represent TSP as a partially filled Sudoku
  $endgroup$
  – Chakrapani N Rao
  10 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @ChakrapaniNRao, see updated answer. Yes, I understand it is a black box. To work out the details, find the proof of NP-completeness for Sudoku and understand how the reduction works.
  $endgroup$
  – D.W.♦
  10 hours ago
  

  
  
  
  


• 
  
  
  

  
  4
  

  
  
  
  
  
  

  
  $begingroup$
  @ChakrapaniNRao It doesn't answer the question completely but the full answer would be ridiculously long, be full of intricate details and wouldn't give you any more enlightenment than the sketch here. It's possible that a reduction of some NP-complete problem to $n^2times n^2$ sudoku might be interesting but, unless the proof that sudoku is NP-complete was actually by reduction from TSP (unlikely), the answer is still going to end "and then chain those two reductions together".
  $endgroup$
  – David Richerby
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  OK, so we do not have a working solution for the above question then?
  $endgroup$
  – Chakrapani N Rao
  48 mins ago
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  @ChakrapaniNRao You are asking how to solve problem X using a black box for problem Y. That is literally asking for a reduction. That's what "reduction" means. And, as this answer explains, the answer to your yes/no question is yes.
  $endgroup$
  – David Richerby
  40 mins ago
  

  
  
  
  

 | 
show 1 more comment

$begingroup$

For 9x9 Sudoku, no. It is finite so can be solved in $O(1)$ time.

But if you had a solver for $n^2 times n^2$ Sudoku, that worked for all $n$ and all possible partial boards, then yes, that could be used to solve TSP in polynomial time, as completing a $n^2 times n^2$ Sudoku is NP-complete.

The proof of NP-completeness works by reducing from some NP-complete problem R to Sudoku; then because R is NP-complete, you can reduce from TSP to R (that follows from the definition of NP-completeness); and chaining those reductions gives you a way to use the Sudoku solver to solve TSP.

share|cite|improve this answer

edited 10 hours ago

answered 10 hours ago

D.W.♦D.W.

101k12124289

$endgroup$

share|cite|improve this answer

edited 10 hours ago

answered 10 hours ago

D.W.♦D.W.

101k12124289

answered 10 hours ago

D.W.♦D.W.

101k12124289

answered 10 hours ago

D.W.♦D.W.

101k12124289