To avoid backtracking, I’ve generated an algorithm with some research into a polynomial time algorithm.

*Overall, I’m looking for constructive-criticism, improvement, recommendations, etc.*

I’ve found out that if I control all parameters in the creation of a Sudoku puzzle I can generate the puzzle from a solution in quadratic time.

**Here’s the summary of the entire description of the algorithm. Before you get into your reading.**

Step 1 Follow the grid and puzzle generation method(mentioned at the end of the question).

Step 2 Enter for input l to generate a solution before generating the puzzle [8,5,9,6,1,2,4,3,7]

Step 3. Now generate the puzzle Example- Take the output of the complete grid and compare to the world’s hardest sudoku puzzle and arrange the elements in some algorthim(paper or computer) to match the below.

—

`n = 0 l = input('Enter the first solved box to get a correct solution') note when script asks for input you must write it like this [1,2,3,4,5,6,7,8,9] indices = [] for i in xrange(1, 1+len(l)): indices.append(n % i) n //= i indices.reverse() perm = l for index in indices: perm.append(l.pop(index)) print(perm) `

2nd part of algorthim not yet implemented in the script

To convert the result(which is an horizantal solution) into human readable format follow this method.

You take the first three rows from the output

`[1,2,3,4,5,6,7,8,9] [1,2,3,4,5,6,7,8,9] [1,2,3,4,5,6,7,8,9] `

and do this…. Line them up one by one side by side in this order and I’m seemingly always getting correct grids!!

*Yeah, I know this isn’t in right order but just to show illustration*

[1,2,3]

[4,5,6]

[7,8,9]

–

[1,2,3]

[4,5,6]

[7,8,9]

–

[1,2,3]

[4,5,6]

[7,8,9]

Here’s an actual output of a solution in horizontal format.

`[9, 6, 1, 2, 4, 3, 7, 8, 5] [6, 1, 2, 4, 3, 7, 8, 5, 9] [1, 2, 4, 3, 7, 8, 5, 9, 6] [2, 4, 3, 7, 8, 5, 9, 6, 1] [4, 3, 7, 8, 5, 9, 6, 1, 2] [3, 7, 8, 5, 9, 6, 1, 2, 4] [7, 8, 5, 9, 6, 1, 2, 4, 3] [8, 5, 9, 6, 1, 2, 4, 3, 7] [5, 9, 6, 1, 2, 4, 3, 7, 8] `

Following the aforementioned method.

You get a correct Sudoku grid. (The checker says its correct every time I’ve ran it) I’ve taken out some elements to see if there’s a puzzle with 1 solution and behold.

`[9 6 1][2 4 3][7 8 5] [2 4 3][7 8 5][9 6 1] [7 8 5][9 6 1][2 4 3] [6 1 2][4 3 7][8 5 9] [4 3 7][8 5 9][6 1 2] [8 5 9][6 1 2][4 3 7] [1 2 4][3 7 8][5 9 6] [3 7 8][5 9 6][1 2 4] [5 9 6][1 2 4][3 7 8] `

Pseudo-code

Python2.7

`>>>World-s hardest Sudoku puzzle converted in vertical format 800000000003600000070090200050007000000045700000100030001000068008500010090000400 Manipulating your generated grid to match index by index of hardest puzzle. (This is making sure there should only be 1 solution) 961243785612437859124378596243785961437859612378596124785961243859612437596124378 Poof!! string manipulation done in linear time. 900000000002400000020070500040005000000059600000500020005000043009600030090000300 `

(warning manual typos will happen if done by hand)

Converting into correct format with one solution only(supposedly)

— Solve this. Warning I’ve probably got typos.

`900 040 050 000 005 000 000 000 430 002 000 096 400 000 000 000 059 300 020 005 900 070 000 003 500 200 000 `

Since, I’ve made sure that the grids are always correct. I took a screenshot of Sudoku checker. Generating Complete Grids. Even the puzzles are seemingly always generated correctly in quadratic time.

Not enough testing has confirmed if every puzzle generated from this algorithm is correct, *but every grid has been correct so far if you actually follow the method correctly.*

http://www.birot.hu/sudoku.php