0
$\begingroup$

Introduction

For those who did not read my prior question, I have created an algorithm that generates n^2 x n^2 Sudoku Grids. Out of those grids I remove elements to give only one solution. The algorithm follows an infinite language based on circular matrix shift of elements. It does so in such a way that allows valid grids to be formed. Explained Here-1, Here-2, Here-3 and algorithm in python

Decision Problem

Before reading make sure the links are read first.

Given an n^2 x n^2 grid G does there exist a mapping of a puzzle that will allow only one solution?

Here I test to see if my problem is in NP

g = grid

p = mapped puzzle

The certificate (g, p) is accepted by the checker

run backtracker....

print "analyzing puzzle to check possible solutions"

       if p == one solution

       print "valid shift-L puzzle"
else:
       print "false"

Proof that Puzzle completion is NP-Complete

It is already proven by Colborn with a reduction from a NP-complete problem known as Triangle Partition of tripartite graphs. Explained here

Question

With a pre-existing proof that latin square completion is NP-complete, is it safe for me to firmly say my puzzle generation (or puzzles) is at least NP-hard?

$\endgroup$
  • $\begingroup$ Its kinda like Minesweeper, when I create puzzles with only one solution. Just an intuitive concept that I believe is true. Reducing Minesweeper to puzzle generation would be interesting... hmm.. $\endgroup$ – Travis Wells May 11 at 1:27
3
$\begingroup$

Your problem is in NP.
Generalized Sudoku is NP-Complete, but your mapper is in P. Check whether given grid is generated by mapper runs in $\mathcal O(n^2)$ time.
Your mapper is not NP-Complete and your decision problem is not NP-hard.

On the other hand decision version of Sudoku is NP-hard.

The main problem is that you have not provided anything about checking uniqeness of solution, but since your mapper resolves only one solution from family of solutions it can't decide it.

If you insist on proving NP-hardness please provide valid reduction (hint, it will not run in polytime, so answer is no).

$\endgroup$
  • 1
    $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – D.W. May 11 at 2:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.