search

sfuhrm / sudoku

A very fast Java Sudoku library implementation along with a command line client
GNU Lesser General Public License v3.0
19 stars 8 forks source link

Sudoku size could be variable to solve for example 4x4 or 16x16 sudokus #5

Closed sfuhrm closed 1 year ago

sfuhrm commented 1 year ago

It would also be nice if the size could be variable to solve for example 4x4 or 16x16 sudokus...

Originally posted by @Lemkinator in https://github.com/sfuhrm/sudoku/issues/4#issuecomment-1290967108

sfuhrm commented 1 year ago

I've implemented variable sudoku sizes. Unfortunately 16x16 and 25x25 are really not working with the algorithm used here.

See: https://github.com/sfuhrm/sudoku/releases/tag/sudoku-parent-4.0.0

Lemkinator commented 1 year ago

image

is that an copy paste error?

Lemkinator commented 1 year ago

What does "the algorithm is really slow" mean, are there any numbers?

sfuhrm commented 1 year ago

Yes, you've found a C&P error in S25X25, thanks! This is fixed in 16ffe3798c42377b27090b74d567eaac00eb12c1

What does "the algorithm is really slow" mean, are there any numbers?

Creating full matrices is still quick, creating riddles isn't (text output doesn't make sense):

$ java -jar sudoku-client/target/sudoku-client-4.0.1-SNAPSHOT-jar-with-dependencies.jar -s S16X16 -e Full -t
16135261381297101141415
11871415141636529101213
91541237105131114162168
13261091112148154137165
81016971211121331461554
13131585261041297161114
51214641591317161182310
47211141016358156129131
14135166815411191210372
29101163712614131545811
12111571325101638414619
36841141197102513121516
71411251631412108151396
15413109671451113168212
61612131148159217514103
10598121314215166311147
Took total of 18ms
Each iteration took 18ms
$ java -jar sudoku-client/target/sudoku-client-4.0.1-SNAPSHOT-jar-with-dependencies.jar -s S16X16 -e Riddle -t
...

I never got a riddle of a 16x16 or 25x25 run. I think the backtracking approach is not suitable for that since the runtime can grow exponentially with the dimension growth of the game.

Lemkinator commented 1 year ago

yep, but there is not really a performant alternative to backtracking, is there? this app has 16x16 Sudokus and i wonder how they did... maybe just downloading pre-made sudokus/riddles?

sfuhrm commented 1 year ago

@Lemkinator I have the suspect that the problem is the non deterministic loop in https://github.com/sfuhrm/sudoku/blob/master/sudoku/src/main/java/de/sfuhrm/sudoku/Creator.java#L320 The proper way would be to do a backtracking search using a difficulty range as suggested in the articles mentioned above. A 'riddle has exactly one single solution' is expensive to calculate. I did not yet have time to check it.