# 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.. – Travis Wells May 11 at 1:27

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.