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?