Sudoku

[seth]

gudn tach!

bevor der thread im archiv verschwindet, moechte ich noch sagen, dass ich mich am samstag ein bissl mit der thematik auseinandergesetzt habe und dabei mit erstaunen etwas festgestellt habe, was vielleicht auch andere erstaunen koennte, aber ihnen wahrscheinlich eher einfach woscht-egal sein wird.

eine frage bei sudoku ist ja die nach einer gescheiten datenstuktur, um moeglichst geschickt die verschiedenen bedingungen (fuer zeilen, spalten, subquadrate) ueberpruefen zu koennen.

ich legte mal den naiven ansatz zugrunde, das feld in einem 2d-array (9x9) zu speichern, wobei die erste komponente die zeile und die zweite die spalte repraesentieren sollte, also z.b.

(0,0) (0,1) (0,2) ... (0,8)
(1,0) (1,1) (1,2) ... (1,8)
  .                     .
  .                     .
  .                     .
(8,0) (8,1) (8,2) ... (8,8)

eine umrechnung in eine (lexikografische 1d-)liste stellt kein problem dar. was jedoch macht man mit den subquadraten?

da gaebe es nun sehr viele moeglichkeiten, die einem spontan einfallen koennten, z.b. nach dem gleichen muster wie oben ein 4d-array (zeile, spalte, subzeile, subspalte) oder ein 3d-array (zeile, spalte, #subquadrat (lexikografisch nummeriert)) oder eben einfach ein 2d-array mit verschachtelter lexikografischer anordnung (#subquadrat, #subelement). letzteres waere also

(0,0) (0,1) (0,2) | (1,0) ... (2,2)
(0,3) (0,4) (0,5) | (1,3) ... (2,5)
(0,6) (0,7) (0,8) | (1,6) ... (2,8)
------------------+----------------
(3,0) (3,1) (3,2) | (4,0) ... (5,2)
  .               .             .
  .               .             .
  .               .             .
(6,6) (6,7) (6,8) | (7,6) ... (8,8)

so, und die umrechnung?

ha, und das ist das mich zunaechst verblueffende:

die abbildung

[latex]f:[0,\ldots,8]^2\to[0,\ldots,8]^2, \left({x \atop y}\right)\mapsto f\left({x \atop y}\right)=\left({3\cdot x/3+y/3\atop 3\cdot x%3+y%3}\right)[/latex],
wobei / die ganzzahlige division ist und % der modulo-operator,
die vom ersten beispiel (zeilen-spalten-koordinaten) ins letzte (subquadrat, subelement) umrechnet, ist selbstinvers, d.h. man nimmt dieselbe formel um die koordinaten in die entgegensetzte richtung zu transformieren, oder kurz: f(f(x,y))=(x,y). wer haette das gedacht?
freut sich jemand mit mir? kommen jetzt so kommentare wie "ach, das haett' ich dir auch gleich sagen koennen!" oder "ei, das sieht man doch!"? oder hatte ich doch eher mit meiner woscht-egal-vermutung recht? ich denke ja letzteres. mir egal. ich find's toll.

prost
seth