Skip to main content
deleted 7 characters in body
Source Link
The T
  • 321
  • 2
  • 11

Introduction

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] 1 and Here-2 and Grid generation and Grid generation written in Python

SAT Instance Used

I have taken this SAT instance from this linked pdf on page 3 and reduced to a 3-SAT instance.

(x1 ∨ x2 ∨ ¬x4) ∧ (x2 ∨ ¬x3) ∧ x5

SAT reduced into 3-SAT

(x1 ∨ x2 ∨ ¬x4) ∧ (x2 ∨ ¬x3 ∨ x1)

Here are the definitions for the variables.

shift(L) = the circular shifts

x1 = shift(L) to generate valid n^2 x n^2 grid and puzzle

x2 = shift(L) to generate another valid n^2 x n^2 grid and puzzle

¬x4 = valid grids and puzzles not following shift(L)

¬x3 = another valid grid and its puzzle not following shift(L)

Explanation of the purpose of the 3-SAT instance

When x1 and x2 are true (shift(L) grids and puzzles)

Then the output is True (shift(L) puzzles/grid)

When x1 and/or x2 is not shift(L)... false.

While the negated form is basically a "not false"

Therefore the output is false because no two puzzles are made from shift(L)

Question

Did I prove correctly that my puzzles are NP-hard assuming that that the language used to generate these grids never have missing instances?

Introduction

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] 1 and Here-2 and Grid generation and Grid generation written in Python

SAT Instance Used

I have taken this SAT instance from this linked pdf on page 3 and reduced to a 3-SAT instance.

(x1 ∨ x2 ∨ ¬x4) ∧ (x2 ∨ ¬x3) ∧ x5

SAT reduced into 3-SAT

(x1 ∨ x2 ∨ ¬x4) ∧ (x2 ∨ ¬x3 ∨ x1)

Here are the definitions for the variables.

shift(L) = the circular shifts

x1 = shift(L) to generate valid n^2 x n^2 grid and puzzle

x2 = shift(L) to generate another valid n^2 x n^2 grid and puzzle

¬x4 = valid grids and puzzles not following shift(L)

¬x3 = another valid grid and its puzzle not following shift(L)

Explanation of the purpose of the 3-SAT instance

When x1 and x2 are true (shift(L) grids and puzzles)

Then the output is True (shift(L) puzzles/grid)

When x1 and/or x2 is not shift(L)... false.

While the negated form is basically a "not false"

Therefore the output is false because no two puzzles are made from shift(L)

Question

Did I prove correctly that my puzzles are NP-hard assuming that that the language used to generate these grids never have missing instances?

Introduction

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] 1 and Here-2 and Grid generation and Grid generation written in Python

SAT Instance Used

I have taken this SAT instance from this linked pdf on page 3 and reduced to a 3-SAT instance.

(x1 ∨ x2 ∨ ¬x4) ∧ (x2 ∨ ¬x3) ∧ x5

SAT reduced into 3-SAT

(x1 ∨ x2 ∨ ¬x4) ∧ (x2 ∨ ¬x3 ∨ x1)

Here are the definitions for the variables.

shift(L) = the circular shifts

x1 = shift(L) to generate valid n^2 x n^2 grid and puzzle

x2 = shift(L) to generate another valid n^2 x n^2 grid and puzzle

¬x4 = valid grids and puzzles not following shift(L)

¬x3 = another valid grid and its puzzle not following shift(L)

Explanation of the purpose of the 3-SAT instance

When x1 and x2 are true (shift(L) grids and puzzles)

Then the output is True (shift(L) puzzles/grid)

When x1 and/or x2 is not shift(L)... false.

While the negated form is basically a "not false"

Therefore the output is false because no two puzzles are made from shift(L)

Question

Did I prove correctly that my puzzles are NP-hard assuming that the language used to generate these grids never have missing instances?

Source Link
The T
  • 321
  • 2
  • 11

Proving NP hardness in Puzzle with SAT reduction

Introduction

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] 1 and Here-2 and Grid generation and Grid generation written in Python

SAT Instance Used

I have taken this SAT instance from this linked pdf on page 3 and reduced to a 3-SAT instance.

(x1 ∨ x2 ∨ ¬x4) ∧ (x2 ∨ ¬x3) ∧ x5

SAT reduced into 3-SAT

(x1 ∨ x2 ∨ ¬x4) ∧ (x2 ∨ ¬x3 ∨ x1)

Here are the definitions for the variables.

shift(L) = the circular shifts

x1 = shift(L) to generate valid n^2 x n^2 grid and puzzle

x2 = shift(L) to generate another valid n^2 x n^2 grid and puzzle

¬x4 = valid grids and puzzles not following shift(L)

¬x3 = another valid grid and its puzzle not following shift(L)

Explanation of the purpose of the 3-SAT instance

When x1 and x2 are true (shift(L) grids and puzzles)

Then the output is True (shift(L) puzzles/grid)

When x1 and/or x2 is not shift(L)... false.

While the negated form is basically a "not false"

Therefore the output is false because no two puzzles are made from shift(L)

Question

Did I prove correctly that my puzzles are NP-hard assuming that that the language used to generate these grids never have missing instances?