# NP hardness of unique Puzzle Generation

## 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

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?

• 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.. May 11 '19 at 1:27

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).

• Comments are not for extended discussion; this conversation has been moved to chat.
– D.W.
May 11 '19 at 2:17