[Community Puzzle] Sudoku Solver

Puzzles
#21

Use a list instead, it should be faster.

#23

That creates a new string for the whole line at each modification.
You should instead convert lines into lists of integers:

sudoku = [list(map(int, input())) for _ in range(9)]

Then each modification would be done in a much simpler and more efficient way: sudoku[i][j] = n.

1 Like
#24

hello,

is it possible to solve the last example (ā€œworldā€™s hardest sudokuā€) without resorting to backtracking?

#25

Thanks, solved it for me too !

#26

I try to solve it in Java but my solution takes too long time.

What is faster for set or get element of the grid ? Use an array of String[9][9] or use a (long) String and functions using String ?

#27

Why not int[][]?

But you time out not because of using int or string, it is mainly due to your algorithm being too slow.

#28

Thanks for tips : I have changed String[][] for int [][]
But Youā€™re right : Time out is already there !

#29

Fun fact about backtracking here (at least according to my experience when testing):
If you loop through the cells from up to bottom and then from left to right, the last test case is way longer to solve!

:arrow_right::arrow_right::arrow_right: This order took less than 2 seconds.

:arrow_down:.
:arrow_down: This order took more than 80 seconds!
:arrow_down:.
(And I found the same solution in both cases, obviously.)

For what I know, it could be your problem @MixWit (if you havenā€™t solved it since your last post).

2 Likes
#30

My code passed all ā€œvisibleā€ tests fine (it also pass hard pazzle 4x4 solver).
BUT it fail to pass hidden test num. 3
I reversed order of allowed signs from:

//POSSIBLE = []string{1, 2, 3, 4, 5, 6, 7, 8, 9}
// to
POSSIBLE = []string{9, 8, 7, 6, 5, 4, 3, 2, 1}

And ALL test are passed 100%.
Conclution:
hidden #3 (Intermediate/Hard) test HAVE more than one proper solution.

#31

There is just one solution. Not sure why you passed with that change in your code, maybe the order of evaluation leads to a difference in the time required to find a solution. As references https://forum.codingame.com/t/community-puzzle-sudoku-solver/111428/5 observes that the first empty cells tend to be 9 8 7, and https://forum.codingame.com/t/community-puzzle-sudoku-solver/111428/29 finds a significant time difference between different order of checking.

#32

Hi,
Can anybody help me with this?
I canā€™t understand whats happening with my list I build from the input. In my understanding these both snippets of code should produce the same grid, but they donā€™t. In the second example, the first line is just repeated over and over again, and I really canā€™t understand why.

Can anybody tell me what Iā€™m missing?

grid = list()
for y in range(9):
    grid.append(list())
    line = input()
    for x in range(9):
        grid[y].append(int(line[x]))

grid = [[0]*9]*9
for y in range(9):
    line = input()
    for x in range(9):
        grid[y][x] = int(line[x])
#33

[[0]*9]*9

This creates a single list object ([0,0,0,0,0,0,0,0,0]) and then creates another list object containing 9 references to the first list. You need to find a way to create 9 different lists for the first step instead:

[[0]*9 for _ in range(9)]

Is how Iā€™d generally do it, the other option would be to do something similar to your first example but put

grid.append([0] * 9)

instead of appending an empty list.

1 Like
#34

Thanks a lot!
I think this wrong understanding takes a lot of my time also in other situations. I really need to get used to how python handles objects and pointers ^^

#35

WITH RANGE (1 to 9) it takes
WORLD HARDEST SODUKO SOLVED IN = 0.365807 Seconds
++++SOLUTION AFTER 49 559 iteration++++

With RANGE [1,2,7,5,3,6,4,9,8] it takes
0.0497223 Seconds (10 times faster)

++++SOLUTION AFTER 5882 iteration++++
8 1 2 | 7 5 3 | 6 4 9
9 4 3 | 6 8 2 | 1 7 5
6 7 5 | 4 9 1 | 2 8 3
-------------------------
1 5 4 | 2 3 7 | 8 9 6
3 6 9 | 8 4 5 | 7 2 1
2 8 7 | 1 6 9 | 5 3 4
-------------------------
5 2 1 | 9 7 4 | 3 6 8
4 3 8 | 5 2 6 | 9 1 7
7 9 6 | 3 1 8 | 4 5 2

####BEFORE SOLUTION:######

8 0 0 | 0 0 0 | 0 0 0
0 0 3 | 6 0 0 | 0 0 0
0 7 0 | 0 9 0 | 2 0 0
-------------------------
0 5 0 | 0 0 7 | 0 0 0
0 0 0 | 0 4 5 | 7 0 0
0 0 0 | 1 0 0 | 0 3 0
-------------------------
0 0 1 | 0 0 0 | 0 6 8
0 0 8 | 5 0 0 | 0 1 0
0 9 0 | 0 0 0 | 4 0 0

#36

A special ordering of search sequence -

  1. is the same ordering generally applicable to all / most sudoku starting status to give faster solution?
  2. what is the logic behind the special ordering? Can we deduce this ordering by an algorithm or have to discover it by bruteforce trials?
#37

Compare between RANGE [1,2,7,5,3,6,4,9,8] and 1 2 | 7 5 3 | 6 4 9 ā€¦

#38

Iā€™m using a backtracking algorithm coded in Python. It doesnā€™t work with the intermediate/hard test (edit: except if I reverse the order of the list of possible digits for each uncovered pointā€¦ which is quiet strange !!!), but it works with the world hardest Sudoku test. In this last case, the recursive function is called 191.505 times, and the solution takes aroundā€¦ 3 minutes to appear !.. (edit: with reversed list of possible digitsā€¦ time is now more than 20 minutes (Iā€™ve stopped the program before it ends) !!!). I canā€™t see how to improve optimization. Note that Iā€™m using object-oriented programming, it might be the problem, what do you think ? :confused:

#39

The concept used in Knuthā€™s Algorithm X may help. Exploration is done in the order of the number of possibilities. For example, the cell with the least choices is explored first, as it has a higher possibility of being correct and cutting down the backtracking tree more.

Perhaps this may also help you: https://norvig.com/sudoku.html

2 Likes
#40

Yes, I tried to order the points (or ā€œcellsā€), starting from those which have the fewest number of possible digits, but then my program didnā€™t stop even after 20 minutesā€¦ I think this is due to the fact that there wonā€™t be an early stop condition, because you donā€™t fill the cells in lines, but in a ā€œrandomlyā€ way.

Thank you for the link, Iā€™m going to read it carefully.

#41

Algorithm X is a bit overkill here.
I pass 100% in Python with a basic backtracking that fills the grid row by row.
What helps saving time:

  • donā€™t use OOP,
  • early break when you find a solution (you can use a global flag or use exit() after printing the solution),
  • donā€™t check if a state has already been encountered, it cannot happen,
  • do the changes in place, never copy the entire grid
  • when you check if a digit is valid, donā€™t check the whole grid, only the column/row/subgrid of the cell you put the digit in.
1 Like