Dtjytyk

apt-get update is failing in debian

Teaching indefinite integrals that require special-casing

Have I saved too much for retirement so far?

Is HostGator storing my password in plaintext?

Everything Bob says is false. How does he get people to trust him?

At which point does a character regain all their Hit Dice?

(Bedrock Edition) Loading more than six chunks at once

Why "be dealt cards" rather than "be dealing cards"?

What does this 7 mean above the f flat

Is there any reason not to eat food that's been dropped on the surface of the moon?

How can I use the arrow sign in my bash prompt?

How to be diplomatic in refusing to write code that breaches the privacy of our users

Curses work by shouting - How to avoid collateral damage?

Dot above capital letter not centred

Products and sum of cubes in Fibonacci

Is the destination of a commercial flight important for the pilot?

What would happen if the UK refused to take part in EU Parliamentary elections?

Was the picture area of a CRT a parallelogram (instead of a true rectangle)?

Can criminal fraud exist without damages?

Is there a good way to store credentials outside of a password manager?

What't the meaning of this extra silence?

What are the ramifications of creating a homebrew world without an Astral Plane?

What to do with wrong results in talks?

Is there a problem with hiding "forgot password" until it's needed?

If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, 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)$ timeCan Euclidean TSP be exactly solved in time better than (sym)metric TSP?How to find partition set of a Partition Problem using its decision problemHow can we design an efficient warehouse management program?Finding vertices of a maximum clique in polynomial timeIs this an instance of a well-known problem?Is any sudoku solver an SAT solver?Applying a permutation on a sequence with multiplicationSolve this integer program (problem: Travelling salesman problem)

21

5

$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 reductions traveling-salesman sudoku

share|cite|improve this question

edited Mar 16 at 15:45

Rodrigo de Azevedo

704615

asked Mar 15 at 7:53

Chakrapani N RaoChakrapani N Rao

11418

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  This paper claims to give a constructive reduction from Sudoku to Hamiltonian cycle problem: sciencedirect.com/science/article/pii/S097286001630038X
  $endgroup$
  – C. Windolf
  Mar 15 at 20:24
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @C.Windolf The question is asking for the other direction. (Indeed, there's a deleted answer that made the same mistake and cited the same paper.)
  $endgroup$
  – David Richerby
  Mar 15 at 20:25
  

  
  
  
  

add a comment | 

21

5

$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 reductions traveling-salesman sudoku

share|cite|improve this question

edited Mar 16 at 15:45

Rodrigo de Azevedo

704615

asked Mar 15 at 7:53

Chakrapani N RaoChakrapani N Rao

11418

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  This paper claims to give a constructive reduction from Sudoku to Hamiltonian cycle problem: sciencedirect.com/science/article/pii/S097286001630038X
  $endgroup$
  – C. Windolf
  Mar 15 at 20:24
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @C.Windolf The question is asking for the other direction. (Indeed, there's a deleted answer that made the same mistake and cited the same paper.)
  $endgroup$
  – David Richerby
  Mar 15 at 20:25
  

  
  
  
  

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 reductions traveling-salesman sudoku

share|cite|improve this question

edited Mar 16 at 15:45

Rodrigo de Azevedo

704615

asked Mar 15 at 7:53

Chakrapani N RaoChakrapani N Rao

11418

$endgroup$

share|cite|improve this question

edited Mar 16 at 15:45

Rodrigo de Azevedo

704615

asked Mar 15 at 7:53

Chakrapani N RaoChakrapani N Rao

11418

share|cite|improve this question

edited Mar 16 at 15:45

Rodrigo de Azevedo

704615

asked Mar 15 at 7:53

Chakrapani N RaoChakrapani N Rao

11418

edited Mar 16 at 15:45

Rodrigo de Azevedo

704615

edited Mar 16 at 15:45

Rodrigo de Azevedo

704615

asked Mar 15 at 7:53

Chakrapani N RaoChakrapani N Rao

11418

asked Mar 15 at 7:53

Chakrapani N RaoChakrapani N Rao

11418

2 Answers
2

active

oldest

votes

31

$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, and ran in polynomial time, 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 Mar 17 at 15:53

answered Mar 15 at 8:19

D.W.♦D.W.

102k12129293

$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
  Mar 15 at 8:22
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $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.♦
  Mar 15 at 8:25
  

  
  
  
  


• 
  
  
  

  
  8
  

  
  
  
  
  
  

  
  $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
  Mar 15 at 17:43
  

  
  
  
  


• 
  
  
  

  
  8
  

  
  
  
  
  
  

  
  $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
  Mar 15 at 18:32
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  @SolomonUcko, well, no, not necessarily. The questions asks: if we have a Sudoku solver, can we use it to solve TSP? The answer is yes, we can. I explain how. This will give you a way to solve TSP about as fast as the Sudoku solver will solve Sudoku. If the Sudoku solver runs in polynomial time, this will give you a way to solve TSP in polynomial time. If the Sudoku solver runs in subexponential time, this will give you a way to solve TSP in subexponential time. And so on.
  $endgroup$
  – D.W.♦
  Mar 17 at 5:11
  
  
  

  
  
  
  

 | 
show 5 more comments

24

$begingroup$

It is indeed possible to use a general Sudoku solver to solve instances of TSP, and if this solver takes polynomial time then the whole process will as well (in complexity terminology, there is a polynomial-time reduction from TSP to Sudoku). This is because Sudoku is NP-complete and TSP is in NP. But as is usually the case in this area, looking at the details of the reduction isn't particularly illuminating. If you want, you can piece it together by using the simple reduction from Latin square completion to Sudoku here, the reduction from triangulating uniform tripartite graphs to Latin square completion here, the reduction from 3SAT to triangulation here, and a formulation of TSP as a 3SAT problem. However, if you want to understand the idea behind reducing from Sudoku to TSP I think you would be better off studying Cook's theorem (showing that SAT is NP-complete) and a couple of simple reductions from 3SAT (e.g. to 3-dimensional matching) and being satisfied in the knowledge that the TSP-Sudoku reduction is just the same kind of thing but longer and more fiddly.

share|cite|improve this answer

answered Mar 15 at 20:22

rlmsrlms

34114

$endgroup$

add a 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
});


}
});

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-the-travelling-salesman-problem-tsp-if-so%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

31

$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, and ran in polynomial time, 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 Mar 17 at 15:53

answered Mar 15 at 8:19

D.W.♦D.W.

102k12129293

$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
  Mar 15 at 8:22
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $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.♦
  Mar 15 at 8:25
  

  
  
  
  


• 
  
  
  

  
  8
  

  
  
  
  
  
  

  
  $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
  Mar 15 at 17:43
  

  
  
  
  


• 
  
  
  

  
  8
  

  
  
  
  
  
  

  
  $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
  Mar 15 at 18:32
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  @SolomonUcko, well, no, not necessarily. The questions asks: if we have a Sudoku solver, can we use it to solve TSP? The answer is yes, we can. I explain how. This will give you a way to solve TSP about as fast as the Sudoku solver will solve Sudoku. If the Sudoku solver runs in polynomial time, this will give you a way to solve TSP in polynomial time. If the Sudoku solver runs in subexponential time, this will give you a way to solve TSP in subexponential time. And so on.
  $endgroup$
  – D.W.♦
  Mar 17 at 5:11
  
  
  

  
  
  
  

 | 
show 5 more comments

31

$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, and ran in polynomial time, 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 Mar 17 at 15:53

answered Mar 15 at 8:19

D.W.♦D.W.

102k12129293

$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
  Mar 15 at 8:22
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $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.♦
  Mar 15 at 8:25
  

  
  
  
  


• 
  
  
  

  
  8
  

  
  
  
  
  
  

  
  $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
  Mar 15 at 17:43
  

  
  
  
  


• 
  
  
  

  
  8
  

  
  
  
  
  
  

  
  $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
  Mar 15 at 18:32
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  @SolomonUcko, well, no, not necessarily. The questions asks: if we have a Sudoku solver, can we use it to solve TSP? The answer is yes, we can. I explain how. This will give you a way to solve TSP about as fast as the Sudoku solver will solve Sudoku. If the Sudoku solver runs in polynomial time, this will give you a way to solve TSP in polynomial time. If the Sudoku solver runs in subexponential time, this will give you a way to solve TSP in subexponential time. And so on.
  $endgroup$
  – D.W.♦
  Mar 17 at 5:11
  
  
  

  
  
  
  

 | 
show 5 more comments

$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, and ran in polynomial time, 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 Mar 17 at 15:53

answered Mar 15 at 8:19

D.W.♦D.W.

102k12129293

$endgroup$

share|cite|improve this answer

edited Mar 17 at 15:53

answered Mar 15 at 8:19

D.W.♦D.W.

102k12129293

answered Mar 15 at 8:19

D.W.♦D.W.

102k12129293

answered Mar 15 at 8:19

D.W.♦D.W.

102k12129293

24

$begingroup$

It is indeed possible to use a general Sudoku solver to solve instances of TSP, and if this solver takes polynomial time then the whole process will as well (in complexity terminology, there is a polynomial-time reduction from TSP to Sudoku). This is because Sudoku is NP-complete and TSP is in NP. But as is usually the case in this area, looking at the details of the reduction isn't particularly illuminating. If you want, you can piece it together by using the simple reduction from Latin square completion to Sudoku here, the reduction from triangulating uniform tripartite graphs to Latin square completion here, the reduction from 3SAT to triangulation here, and a formulation of TSP as a 3SAT problem. However, if you want to understand the idea behind reducing from Sudoku to TSP I think you would be better off studying Cook's theorem (showing that SAT is NP-complete) and a couple of simple reductions from 3SAT (e.g. to 3-dimensional matching) and being satisfied in the knowledge that the TSP-Sudoku reduction is just the same kind of thing but longer and more fiddly.

share|cite|improve this answer

answered Mar 15 at 20:22

rlmsrlms

34114

$endgroup$

add a comment | 

24

$begingroup$

It is indeed possible to use a general Sudoku solver to solve instances of TSP, and if this solver takes polynomial time then the whole process will as well (in complexity terminology, there is a polynomial-time reduction from TSP to Sudoku). This is because Sudoku is NP-complete and TSP is in NP. But as is usually the case in this area, looking at the details of the reduction isn't particularly illuminating. If you want, you can piece it together by using the simple reduction from Latin square completion to Sudoku here, the reduction from triangulating uniform tripartite graphs to Latin square completion here, the reduction from 3SAT to triangulation here, and a formulation of TSP as a 3SAT problem. However, if you want to understand the idea behind reducing from Sudoku to TSP I think you would be better off studying Cook's theorem (showing that SAT is NP-complete) and a couple of simple reductions from 3SAT (e.g. to 3-dimensional matching) and being satisfied in the knowledge that the TSP-Sudoku reduction is just the same kind of thing but longer and more fiddly.

share|cite|improve this answer

answered Mar 15 at 20:22

rlmsrlms

34114

$endgroup$

add a comment | 

$begingroup$

It is indeed possible to use a general Sudoku solver to solve instances of TSP, and if this solver takes polynomial time then the whole process will as well (in complexity terminology, there is a polynomial-time reduction from TSP to Sudoku). This is because Sudoku is NP-complete and TSP is in NP. But as is usually the case in this area, looking at the details of the reduction isn't particularly illuminating. If you want, you can piece it together by using the simple reduction from Latin square completion to Sudoku here, the reduction from triangulating uniform tripartite graphs to Latin square completion here, the reduction from 3SAT to triangulation here, and a formulation of TSP as a 3SAT problem. However, if you want to understand the idea behind reducing from Sudoku to TSP I think you would be better off studying Cook's theorem (showing that SAT is NP-complete) and a couple of simple reductions from 3SAT (e.g. to 3-dimensional matching) and being satisfied in the knowledge that the TSP-Sudoku reduction is just the same kind of thing but longer and more fiddly.

share|cite|improve this answer

answered Mar 15 at 20:22

rlmsrlms

34114

$endgroup$

share|cite|improve this answer

answered Mar 15 at 20:22

rlmsrlms

34114

answered Mar 15 at 20:22

rlmsrlms

34114

answered Mar 15 at 20:22

rlmsrlms

34114