Sudoku-Generierung

[Gunnar Bittersmann]

Hello out there!

Ich bin's lediglich zufrieden, dass sowas oder sowas reibungslos funktioniert.

Nein, damit kannst du kaum zufrieden sein.

Zumindest dein Algorithmus in http://www.mah-jongg.ch/sudoku zur Erstellung eines Sudoku ist fehlerhaft; er gibt ungültige Sudokus aus. Ich erhielt bspw. dieses (evil):

  
╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗  
║   │ 3 │ 5 ║   │   │   ║   │   │   ║  
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  
║   │ 6 │   ║   │ 5 │   ║   │ 1 │ 2 ║  
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  
║   │   │   ║   │   │ 9 ║   │   │ 3 ║  
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣  
║   │   │ 7 ║   │ 3 │   ║   │   │   ║  
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  
║   │ 9 │   ║ 1 │   │ 8 ║   │ 6 │   ║  
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  
║   │   │   ║   │ 7 │   ║ 3 │   │   ║  
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣  
║ 7 │   │   ║ 5 │   │   ║   │   │   ║  
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  
║ 9 │ 5 │   ║   │ 1 │   ║   │ 8 │   ║  
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  
║   │   │   ║   │   │   ║ 5 │ 4 │   ║  
╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝  

Das wird von diser Belegung erfüllt:

  
╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗  
║ 2 │ 3 │ 5 ║ 6 │ 8 │ 1 ║ 9 │ 7 │ 4 ║  
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  
║ 4 │ 6 │ 9 ║ 7 │ 5 │ 3 ║ 8 │ 1 │ 2 ║  
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  
║ 1 │ 7 │ 8 ║ 2 │ 4 │ 9 ║ 6 │ 5 │ 3 ║  
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣  
║ 6 │ 4 │ 7 ║ 9 │ 3 │ 5 ║ 1 │ 2 │ 8 ║  
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  
║ 5 │ 9 │ 3 ║ 1 │ 2 │ 8 ║ 4 │ 6 │ 7 ║  
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  
║ 8 │ 1 │ 2 ║ 4 │ 7 │ 6 ║ 3 │ 9 │ 5 ║  
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣  
║ 7 │ 8 │ 1 ║ 5 │ 6 │ 4 ║ 2 │ 3 │ 9 ║  
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  
║ 9 │ 5 │ 4 ║ 3 │ 1 │ 2 ║ 7 │ 8 │ 6 ║  
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  
║ 3 │ 2 │ 6 ║ 8 │ 9 │ 7 ║ 5 │ 4 │ 1 ║  
╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝  

Aber auch von dieser:

  
╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗  
║ 2 │ 3 │ 5 ║ 6 │ 8 │ 1 ║ 9 │ 7 │ 4 ║  
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  
║ 4 │ 6 │ 9 ║ 7 │ 5 │ 3 ║ 8 │ 1 │ 2 ║  
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  
║ 1 │ 7 │ 8 ║ 2 │ 4 │ 9 ║ 6 │ 5 │ 3 ║  
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣  
║ 8 │ 4 │ 7 ║ 9 │ 3 │ 6 ║ 1 │ 2 │ 5 ║  
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  
║ 5 │ 9 │ 3 ║ 1 │ 2 │ 8 ║ 4 │ 6 │ 7 ║  
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  
║ 6 │ 1 │ 2 ║ 4 │ 7 │ 5 ║ 3 │ 9 │ 8 ║  
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣  
║ 7 │ 8 │ 1 ║ 5 │ 6 │ 4 ║ 2 │ 3 │ 9 ║  
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  
║ 9 │ 5 │ 4 ║ 3 │ 1 │ 2 ║ 7 │ 8 │ 6 ║  
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  
║ 3 │ 2 │ 6 ║ 8 │ 9 │ 7 ║ 5 │ 4 │ 1 ║  
╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝  

Und auch von dieser:

  
╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗  
║ 2 │ 3 │ 5 ║ 6 │ 8 │ 1 ║ 9 │ 7 │ 4 ║  
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  
║ 4 │ 6 │ 9 ║ 7 │ 5 │ 3 ║ 8 │ 1 │ 2 ║  
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  
║ 8 │ 7 │ 1 ║ 2 │ 4 │ 9 ║ 6 │ 5 │ 3 ║  
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣  
║ 6 │ 4 │ 7 ║ 9 │ 3 │ 5 ║ 1 │ 2 │ 8 ║  
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  
║ 5 │ 9 │ 3 ║ 1 │ 2 │ 8 ║ 4 │ 6 │ 7 ║  
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  
║ 1 │ 8 │ 2 ║ 4 │ 7 │ 6 ║ 3 │ 9 │ 5 ║  
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣  
║ 7 │ 1 │ 8 ║ 5 │ 6 │ 4 ║ 2 │ 3 │ 9 ║  
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  
║ 9 │ 5 │ 4 ║ 3 │ 1 │ 2 ║ 7 │ 8 │ 6 ║  
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢  
║ 3 │ 2 │ 6 ║ 8 │ 9 │ 7 ║ 5 │ 4 │ 1 ║  
╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝  

Möglich, dass es weitere gibt.

Ein Sudoku muss aber _eindeutig_ lösbar sein!

See ya up the road,
Gunnar