Mixing
4x4 Chromatic Sudoku Graph
$begingroup$
I was unsatisfied with existing Sudoku graphs online and my goal was to show the structure in a manner in which the regions are explicit.
Nodes which share an edge cannot have be same color. Shaded areas connote nodes in the same region; thick edges are intra-regional connections and thin edges are extra-regional connections.
Two questions:
Are there any errors?
Does this constitute a proof that there are only two unique, reduced forms of 4x4 Sudoku?
- If not, what additional steps do I need to take?
graph-theory proof-writing sudoku
asked Jan 30 at 17:27
DukeZhouDukeZhou
272316
$endgroup$
|
show 1 more comment
$begingroup$
I was unsatisfied with existing Sudoku graphs online and my goal was to show the structure in a manner in which the regions are explicit.
Nodes which share an edge cannot have be same color. Shaded areas connote nodes in the same region; thick edges are intra-regional connections and thin edges are extra-regional connections.
Two questions:
Are there any errors?
Does this constitute a proof that there are only two unique, reduced forms of 4x4 Sudoku?
- If not, what additional steps do I need to take?
graph-theory proof-writing sudoku
asked Jan 30 at 17:27
DukeZhouDukeZhou
272316
$endgroup$
$begingroup$
What does "Nodes which share an edge must be unique" mean? There are definitely more than two nodes that share an edge. And what do the colors represent?
$endgroup$
– Misha Lavrov
Jan 30 at 17:32
$begingroup$
The colors are the 4 elements of a 4x4 Sudoku. "Nodes which share an edge" means any two nodes which share an edge (connection) must be unique--essentially, the edges are the constraints.
$endgroup$
– DukeZhou
Jan 30 at 17:34
$begingroup$
You mean they must have different colors? "Unique" does not tell me that.
$endgroup$
– Misha Lavrov
Jan 30 at 17:35
$begingroup$
(Apologies if this is an inappropriate question--if so I will delete. :)
$endgroup$
– DukeZhou
Jan 30 at 17:35
$begingroup$
@MishaLavrov I see. How can I word that more clearly?
$endgroup$
– DukeZhou
Jan 30 at 17:36
|
show 1 more comment
$begingroup$
I was unsatisfied with existing Sudoku graphs online and my goal was to show the structure in a manner in which the regions are explicit.
Nodes which share an edge cannot have be same color. Shaded areas connote nodes in the same region; thick edges are intra-regional connections and thin edges are extra-regional connections.
Two questions:
Are there any errors?
Does this constitute a proof that there are only two unique, reduced forms of 4x4 Sudoku?
- If not, what additional steps do I need to take?
graph-theory proof-writing sudoku
asked Jan 30 at 17:27
DukeZhouDukeZhou
272316
$endgroup$
I was unsatisfied with existing Sudoku graphs online and my goal was to show the structure in a manner in which the regions are explicit.
Nodes which share an edge cannot have be same color. Shaded areas connote nodes in the same region; thick edges are intra-regional connections and thin edges are extra-regional connections.
Two questions:
Are there any errors?
Does this constitute a proof that there are only two unique, reduced forms of 4x4 Sudoku?
- If not, what additional steps do I need to take?
graph-theory proof-writing sudoku
graph-theory proof-writing sudoku
asked Jan 30 at 17:27
DukeZhouDukeZhou
272316
asked Jan 30 at 17:27
DukeZhouDukeZhou
272316
edited Jan 31 at 18:21
DukeZhou
asked Jan 30 at 17:27
DukeZhouDukeZhou
272316
asked Jan 30 at 17:27
DukeZhouDukeZhou
272316
asked Jan 30 at 17:27
DukeZhouDukeZhou
272316
272316
$begingroup$
What does "Nodes which share an edge must be unique" mean? There are definitely more than two nodes that share an edge. And what do the colors represent?
$endgroup$
– Misha Lavrov
Jan 30 at 17:32
$begingroup$
The colors are the 4 elements of a 4x4 Sudoku. "Nodes which share an edge" means any two nodes which share an edge (connection) must be unique--essentially, the edges are the constraints.
$endgroup$
– DukeZhou
Jan 30 at 17:34
$begingroup$
You mean they must have different colors? "Unique" does not tell me that.
$endgroup$
– Misha Lavrov
Jan 30 at 17:35
$begingroup$
(Apologies if this is an inappropriate question--if so I will delete. :)
$endgroup$
– DukeZhou
Jan 30 at 17:35
$begingroup$
@MishaLavrov I see. How can I word that more clearly?
$endgroup$
– DukeZhou
Jan 30 at 17:36
|
show 1 more comment
$begingroup$
What does "Nodes which share an edge must be unique" mean? There are definitely more than two nodes that share an edge. And what do the colors represent?
$endgroup$
– Misha Lavrov
Jan 30 at 17:32
$begingroup$
The colors are the 4 elements of a 4x4 Sudoku. "Nodes which share an edge" means any two nodes which share an edge (connection) must be unique--essentially, the edges are the constraints.
$endgroup$
– DukeZhou
Jan 30 at 17:34
$begingroup$
You mean they must have different colors? "Unique" does not tell me that.
$endgroup$
– Misha Lavrov
Jan 30 at 17:35
$begingroup$
(Apologies if this is an inappropriate question--if so I will delete. :)
$endgroup$
– DukeZhou
Jan 30 at 17:35
$begingroup$
@MishaLavrov I see. How can I word that more clearly?
$endgroup$
– DukeZhou
Jan 30 at 17:36
$begingroup$
What does "Nodes which share an edge must be unique" mean? There are definitely more than two nodes that share an edge. And what do the colors represent?
$endgroup$
– Misha Lavrov
Jan 30 at 17:32
$begingroup$
What does "Nodes which share an edge must be unique" mean? There are definitely more than two nodes that share an edge. And what do the colors represent?
$endgroup$
– Misha Lavrov
Jan 30 at 17:32
$begingroup$
The colors are the 4 elements of a 4x4 Sudoku. "Nodes which share an edge" means any two nodes which share an edge (connection) must be unique--essentially, the edges are the constraints.
$endgroup$
– DukeZhou
Jan 30 at 17:34
$begingroup$
The colors are the 4 elements of a 4x4 Sudoku. "Nodes which share an edge" means any two nodes which share an edge (connection) must be unique--essentially, the edges are the constraints.
$endgroup$
– DukeZhou
Jan 30 at 17:34
$begingroup$
You mean they must have different colors? "Unique" does not tell me that.
$endgroup$
– Misha Lavrov
Jan 30 at 17:35
$begingroup$
You mean they must have different colors? "Unique" does not tell me that.
$endgroup$
– Misha Lavrov
Jan 30 at 17:35
$begingroup$
(Apologies if this is an inappropriate question--if so I will delete. :)
$endgroup$
– DukeZhou
Jan 30 at 17:35
$begingroup$
(Apologies if this is an inappropriate question--if so I will delete. :)
$endgroup$
– DukeZhou
Jan 30 at 17:35
$begingroup$
@MishaLavrov I see. How can I word that more clearly?
$endgroup$
– DukeZhou
Jan 30 at 17:36
$begingroup$
@MishaLavrov I see. How can I word that more clearly?
$endgroup$
– DukeZhou
Jan 30 at 17:36
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
The graph looks correct - but drawing the two graphs does not, in itself, constitute a proof that these are the only two possibilities.
Presumably you want to say that there are only two forms of Sudoku up to symmetry. In this case, you want to start out by being clear up to which forms of symmetry you allow. I can think of the following:
- Permuting the colors (that is, the labels 1,2,3,4 in the grid);
- Swapping the first two rows or columns;
- Swapping the last two rows or columns;
- Swapping two $2times 4$ or $4 times 2$ halves of the grid.
If you want to represent the Sudoku by a graph, you want to understand what effect these have on the graphs. If it's true that there are two types, you might want to find a "canonical representative" of each type: for example, you might want to begin by fixing a particular coloring of one shaded region (though I don't think this addresses all the symmetries; you might be able to fix the coloring of a few more nodes).
Then you can make an argument that the coloring can only be completed in (2?) ways.
answered Jan 30 at 17:56
Misha LavrovMisha Lavrov
48.4k757107
$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: "69"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3093831%2f4x4-chromatic-sudoku-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The graph looks correct - but drawing the two graphs does not, in itself, constitute a proof that these are the only two possibilities.
Presumably you want to say that there are only two forms of Sudoku up to symmetry. In this case, you want to start out by being clear up to which forms of symmetry you allow. I can think of the following:
- Permuting the colors (that is, the labels 1,2,3,4 in the grid);
- Swapping the first two rows or columns;
- Swapping the last two rows or columns;
- Swapping two $2times 4$ or $4 times 2$ halves of the grid.
If you want to represent the Sudoku by a graph, you want to understand what effect these have on the graphs. If it's true that there are two types, you might want to find a "canonical representative" of each type: for example, you might want to begin by fixing a particular coloring of one shaded region (though I don't think this addresses all the symmetries; you might be able to fix the coloring of a few more nodes).
Then you can make an argument that the coloring can only be completed in (2?) ways.
answered Jan 30 at 17:56
Misha LavrovMisha Lavrov
48.4k757107
$endgroup$
add a comment |
$begingroup$
The graph looks correct - but drawing the two graphs does not, in itself, constitute a proof that these are the only two possibilities.
Presumably you want to say that there are only two forms of Sudoku up to symmetry. In this case, you want to start out by being clear up to which forms of symmetry you allow. I can think of the following:
- Permuting the colors (that is, the labels 1,2,3,4 in the grid);
- Swapping the first two rows or columns;
- Swapping the last two rows or columns;
- Swapping two $2times 4$ or $4 times 2$ halves of the grid.
If you want to represent the Sudoku by a graph, you want to understand what effect these have on the graphs. If it's true that there are two types, you might want to find a "canonical representative" of each type: for example, you might want to begin by fixing a particular coloring of one shaded region (though I don't think this addresses all the symmetries; you might be able to fix the coloring of a few more nodes).
Then you can make an argument that the coloring can only be completed in (2?) ways.
answered Jan 30 at 17:56
Misha LavrovMisha Lavrov
48.4k757107
$endgroup$
add a comment |
$begingroup$
The graph looks correct - but drawing the two graphs does not, in itself, constitute a proof that these are the only two possibilities.
Presumably you want to say that there are only two forms of Sudoku up to symmetry. In this case, you want to start out by being clear up to which forms of symmetry you allow. I can think of the following:
- Permuting the colors (that is, the labels 1,2,3,4 in the grid);
- Swapping the first two rows or columns;
- Swapping the last two rows or columns;
- Swapping two $2times 4$ or $4 times 2$ halves of the grid.
If you want to represent the Sudoku by a graph, you want to understand what effect these have on the graphs. If it's true that there are two types, you might want to find a "canonical representative" of each type: for example, you might want to begin by fixing a particular coloring of one shaded region (though I don't think this addresses all the symmetries; you might be able to fix the coloring of a few more nodes).
Then you can make an argument that the coloring can only be completed in (2?) ways.
answered Jan 30 at 17:56
Misha LavrovMisha Lavrov
48.4k757107
$endgroup$
The graph looks correct - but drawing the two graphs does not, in itself, constitute a proof that these are the only two possibilities.
Presumably you want to say that there are only two forms of Sudoku up to symmetry. In this case, you want to start out by being clear up to which forms of symmetry you allow. I can think of the following:
- Permuting the colors (that is, the labels 1,2,3,4 in the grid);
- Swapping the first two rows or columns;
- Swapping the last two rows or columns;
- Swapping two $2times 4$ or $4 times 2$ halves of the grid.
If you want to represent the Sudoku by a graph, you want to understand what effect these have on the graphs. If it's true that there are two types, you might want to find a "canonical representative" of each type: for example, you might want to begin by fixing a particular coloring of one shaded region (though I don't think this addresses all the symmetries; you might be able to fix the coloring of a few more nodes).
Then you can make an argument that the coloring can only be completed in (2?) ways.
answered Jan 30 at 17:56
Misha LavrovMisha Lavrov
48.4k757107
answered Jan 30 at 17:56
Misha LavrovMisha Lavrov
48.4k757107
answered Jan 30 at 17:56
Misha LavrovMisha Lavrov
48.4k757107
answered Jan 30 at 17:56
Misha LavrovMisha Lavrov
48.4k757107
48.4k757107
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3093831%2f4x4-chromatic-sudoku-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
What does "Nodes which share an edge must be unique" mean? There are definitely more than two nodes that share an edge. And what do the colors represent?
$endgroup$
– Misha Lavrov
Jan 30 at 17:32
$begingroup$
The colors are the 4 elements of a 4x4 Sudoku. "Nodes which share an edge" means any two nodes which share an edge (connection) must be unique--essentially, the edges are the constraints.
$endgroup$
– DukeZhou
Jan 30 at 17:34
$begingroup$
You mean they must have different colors? "Unique" does not tell me that.
$endgroup$
– Misha Lavrov
Jan 30 at 17:35
$begingroup$
(Apologies if this is an inappropriate question--if so I will delete. :)
$endgroup$
– DukeZhou
Jan 30 at 17:35
$begingroup$
@MishaLavrov I see. How can I word that more clearly?
$endgroup$
– DukeZhou
Jan 30 at 17:36