| View previous topic :: View next topic |
| Author |
Message |
Proginoskes
Guest
|
 Posted: Mon Oct 06, 2008 9:51 pm Post subject: Complexity of Hidato? |
 |
|
I stumbled across a new Sudoku-like puzzle called Hidato. A Hidato
puzzle is a subgraph of a grid with n squares where some numbers
filled in; your goal is to fill in the rest of the puzzle so that k is
adjacent to k+1 for all k ("adjacent" means vertically, horizontally,
or diagonally).
Amazingly, no one seems to have discovered whether this is an NP-
complete problem. (I.e., determine whether there is a solution.) It is
clearly in NP, and has a nice graph theory formulation (the numbers i
and j must be connected by a path of length exactly
j - i - 1). If the graph (which determines adjacency) is allowed to be
any graph, then the problem is NP-complete, because it reduces to the
Hamiltonian Path problem.
But what if the underlying graph is a subgraph of the "king>s graph"?
That>s the key point.
Having worked on problems in Gyora Benedek>s book, it seems that there
is a small number of key ideas (parity, "don>t cut off the chain",
etc) involved in solving the problems, but I>ve only gotten to the
intermediate section. Also, knowing that there is a solution is
somewhat biased.
--- Christopher Heckman |
|
| |
|
 Back to top |
Guest
|
| Posted: Tue Oct 07, 2008 4:22 am Post subject: Re: Complexity of Hidato? |
|
|
In article <bed242b3-6bf9-409e-b111-adca558e7aa8@b30g2000prf.googlegroups.com>,
Proginoskes <CCHeckman@gmail.com> wrote:
[quote]I stumbled across a new Sudoku-like puzzle called Hidato.
[...]
Amazingly, no one seems to have discovered whether this is an NP-
complete problem.
[/quote]
Yes, this is a nice question. It>s not so "amazing" that nobody has settled
this question, because NP-completeness results---especially of "recreational"
problems---are a dime a dozen, and so there is not much prestige associated
with producing one. However, it>s still an interesting question.
If I were to attack this, I would start with the following paper.
Alon Itai, Christos H. Papadimitriou, and Jayme Luiz Szwarcfiter,
Hamilton paths in grid graphs, SIAM J. Comput. 11 (1982), 676-686.
They show that it is NP-complete to determine whether a graph has a
Hamiltonian path, even if we restrict to graphs that are a finite subset
of the infinite chessboard (only horizontal and vertical adjacencies are
allowed, not diagonal ones). There is a decent chance that tinkering
with their construction will settle the Hidato question.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences |
|
| |
|
| Back to top |
Proginoskes
Guest
|
| Posted: Tue Oct 07, 2008 7:22 am Post subject: Re: Complexity of Hidato? |
|
|
On Oct 6, 4:22 pm, tc...@lsa.umich.edu wrote:
[quote]In article <bed242b3-6bf9-409e-b111-adca558e7...@b30g2000prf.googlegroups..com>,
Proginoskes <CCHeck...@gmail.com> wrote:
I stumbled across a new Sudoku-like puzzle called Hidato.
[...]
Amazingly, no one seems to have discovered whether this is an NP-
complete problem.
Yes, this is a nice question. It>s not so "amazing" that nobody has settled
this question, because NP-completeness results---especially of "recreational"
problems---are a dime a dozen, and so there is not much prestige associated
with producing one. However, it>s still an interesting question.
[/quote]
Actually, I included "amazingly", because usually when I find a neat
problem like this to work on, I find out that someone has beaten me to
it and solved it! Maybe Hidato is new enough that this hasn>t happened
yet.
[quote]If I were to attack this, I would start with the following paper.
Alon Itai, Christos H. Papadimitriou, and Jayme Luiz Szwarcfiter,
Hamilton paths in grid graphs, SIAM J. Comput. 11 (1982), 676-686.
They show that it is NP-complete to determine whether a graph has a
Hamiltonian path, even if we restrict to graphs that are a finite subset
of the infinite chessboard (only horizontal and vertical adjacencies are
allowed, not diagonal ones). There is a decent chance that tinkering
with their construction will settle the Hidato question.
[/quote]
I read through this paper quickly, and they seem to rely heavily on
the grid graph being bipartite. None of the papers which reference
this one seem to have generalized the result in "the right way", so it
may take a fair amount of work.
--- Christopher Heckman |
|
| |
|
| Back to top |
GJ Woeginger
Guest
|
| Posted: Tue Oct 07, 2008 7:56 am Post subject: Re: Complexity of Hidato? |
|
|
In comp.theory Proginoskes <CCHeckman@gmail.com> wrote:
# On Oct 6, 4:22??pm, tc...@lsa.umich.edu wrote:
#
# > If I were to attack this, I would start with the following paper.
# >
# > ?? Alon Itai, Christos H. Papadimitriou, and Jayme Luiz Szwarcfiter,
# > ?? Hamilton paths in grid graphs, SIAM J. Comput. 11 (1982), 676-686.
# >
# > They show that it is NP-complete to determine whether a graph has a
# > Hamiltonian path, even if we restrict to graphs that are a finite subset
# > of the infinite chessboard (only horizontal and vertical adjacencies are
# > allowed, not diagonal ones). ??There is a decent chance that tinkering
# > with their construction will settle the Hidato question.
#
# I read through this paper quickly, and they seem to rely heavily on
# the grid graph being bipartite. None of the papers which reference
# this one seem to have generalized the result in "the right way", so it
# may take a fair amount of work.
#
# --- Christopher Heckman
It is actually not so difficult:
The Itai-Papadimitriou-Szwarcfiter result settles the case of grid graphs.
Adjacency of points is with respect to the L_1-metric (Manhattan-metric).
The unit-ball of the L_1-metric is a square, tilted by 45 degree.
Hidato deals with grids.
Adjacency of points is with respect to the L_infinity-metric.
The unit-ball of the L_infinity-metric is a square (not tilted).
Take the Itai-Papadimitriou-Szwarcfiter construction.
Rotate it by 45 degree.
Blow it up by a factor of sqrt(2).
You get NP-hardness of Hidato.
--Gerhard
___________________________________________________________
Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/ |
|
| |
|
| Back to top |
Proginoskes
Guest
|
| Posted: Tue Oct 07, 2008 10:35 pm Post subject: Re: Complexity of Hidato? |
|
|
On Oct 7, 1:18 am, gwo...@figipc70.tu-graz.ac.at (GJ Woeginger) wrote:
[quote]In comp.theory Proginoskes <CCHeck...@gmail.com> wrote:
# On Oct 6, 4:22??pm, tc...@lsa.umich.edu wrote:
#
# > If I were to attack this, I would start with the following paper.
#
# > ?? Alon Itai, Christos H. Papadimitriou, and Jayme Luiz Szwarcfiter,
# > ?? Hamilton paths in grid graphs, SIAM J. Comput. 11 (1982), 676-686.
#
# > They show that it is NP-complete to determine whether a graph has a
# > Hamiltonian path, even if we restrict to graphs that are a finite subset
# > of the infinite chessboard (only horizontal and vertical adjacencies are
# > allowed, not diagonal ones). ??There is a decent chance that tinkering
# > with their construction will settle the Hidato question.
#
# I read through this paper quickly, and they seem to rely heavily on
# the grid graph being bipartite. None of the papers which reference
# this one seem to have generalized the result in "the right way", so it
# may take a fair amount of work.
#
# --- Christopher Heckman
It is actually not so difficult:
The Itai-Papadimitriou-Szwarcfiter result settles the case of grid graphs.
Adjacency of points is with respect to the L_1-metric (Manhattan-metric).
The unit-ball of the L_1-metric is a square, tilted by 45 degree.
Hidato deals with grids.
Adjacency of points is with respect to the L_infinity-metric.
The unit-ball of the L_infinity-metric is a square (not tilted).
Take the Itai-Papadimitriou-Szwarcfiter construction.
Rotate it by 45 degree.
Blow it up by a factor of sqrt(2).
You get NP-hardness of Hidato.
[/quote]
Yes, of course; the factor of sqrt(2) makes the graph induced.
Since Benedek>s book mostly consists of rectangular grids, the next
natural question is to ask about those graphs. (The construction above
doesn>t apply there.) In their paper, I-P-S also give a linear-time
algorithm to determine whether there is a Hamiltonian path in a
rectangular grid graph, which may be of some use.
--- Christopher Heckman |
|
| |
|
| Back to top |
|
