PROPOZICIJE STUDENTSKOG INFORMATIČKOG NATJECANJA

sin(2007).open

"Sudoku"

.natjecanje

Studentsko informatičko natjecanje (SIN) programersko je natjecanje putem Interneta u organizaciji Udruge darovitih informatičara Rijeke (DIR). Ove se godine održava po osmi put.

Nastavak "OPEN" označava mogućnost sudjelovanja SVIH zainteresiranih, uključujući osnovce, srednjoškolce i studente iz čitave Republike Hrvatske, bez obzira na članstvo u Udruzi.

Natjecatelji se nisu dužni prethodno prijaviti. Ne postoji ni kotizacija. Dovoljno je upoznati se sa ovim propozicijama i predati rješenje u roku.

Natjecanje je otvoreno od 10. studenoga do 30. studenoga 2007. godine. U tom periodu moguće je predati rješenja. Rješenja predana nakon isteka navedenog perioda neće se uzimati u obzir.

.zadatak

Zar je već prošla još jedna godina? Već ste se zaželjeli rješavati zadatak? Da vidimo što nam je ove godine Rotkvica pripremila...

.uvod

Sudoku ili učestalo sudoko (na japanskom znači jedan broj) je igra koja potječe iz Japana i igra se već 1000 godina. To je vrsta slagalice čije je rješavanje temeljeno na logici. Sastoji se od jednog velikog kvadratnog polja, podijeljeno na 81 manjih kvadratića. Nadalje, unutar velikog kvadrata, označeno je 9 odjeljaka velikih 3x3 polja. Postoje različite težine te igre, a koristi se za zabavu ili testiranje inteligencije.

Primjer jednog sudoku zadatka

Cilj igre je ispuniti sva polja brojevima od 1 do 9, s time da se svaki broj smije pojaviti točno 9 puta. Problematika je u tome što se jedan broj smije pojaviti samo jednom u svakom retku, svakom stupcu i svakom odjeljku od 3x3 polja. Na početku igre, otkriveni su određeni brojevi, a onaj koji rješava mora otkriti gdje se nalaze svi ostali brojevi i kako su raspoređeni. Svaki sudoko ima samo jedno rješenje. Zato se mora paziti sa se greška ne načini na početku rješavanja. Jedini način rješavanja sudoku-a je metoda eliminacije, a tu se koristimo svojstvom da se jedan broj smije pojaviti samo jednom u svakom stupcu, retku i bloku. Rješavanje postaje lakše što se veći broj brojeva otkrije.

Rješenje gornjeg zadatka

.problem

Nakon beskonačno mnogo uspješno riješenih slagalica, Rotkvica je odlučila malo zakomplicirati si (vam) stvari i hoće rješavati "NxN sudoku", po istim pravilima kao i za 3x3, ali s tom razlikom da ploča sada ima ukupno N4 polja koja se popunjavaju sa brojevima od 1 do N2, a analogno sa 3x3 sudoku-om, ima NxN odjeljaka sa NxN polja i svaki broj se pojavljuje točno NxN puta. No, kako je takve zadatke vrlo teško pronaći, Rotkvica želi da vi prethodno provjerite da li je navedeni zadani sudoku uopće ispravan, i ako je, ispišite "RJEŠENJE JE JEDINSTVENO" zajedno sa tim rješenjem. Ako sudoku nije ispravno zadan jer nije moguće dobiti rješenje koje će zadovoljavati gornje uvjete ispišite poruku "RJEŠENJE NIJE MOGUĆE". Ako pak postoji rješenje koje će zadovoljavati uvjete, ali nije jedinstveno, onda ispišite poruku "RJEŠENJE NIJE JEDINSTVENO" i bilo koje od rješenja koje će zadovoljavati postavljeni uvjet.

.ulazni podaci

U tekstualnoj datoteci "ULAZ.TXT" nalazit će se sljedeći podaci:
U prvom retku prirodan broj N, veličina našeg NxN sudoku-a, N ≤ 100.
U narednih NxN redaka nalazi se NxN cijelih brojeva, svaki broj odvojen jednim znakom razmaka, a mjesto gdje se nalazi broj 0 (nula) predstavlja trenutno prazno polje (nepoznatu vrijednost).

.izlazni podaci

Na osnovu ulaznih podataka potrebno je u tekstualnu datoteku "IZLAZ.TXT" ispisati:
U prvi redak ispišite jednu od poruka:
"RJESENJE JE JEDINSTVENO",
"RJESENJE NIJE JEDINSTVENO", ili
"RJESENJE NIJE MOGUCE" (bez navodnika).
Ako je rješenje moguće, onda u narednih NxN redaka ispišite NxN brojeva u istoj strukturi kao i kod ulaznih podataka, ali svaki broj 0 zamijenite sa odgovarajućim brojem iz intervala od 1 do NxN.

.primjeri

1. primjer

2. primjer

3. primjer

.naputak

Zadatak se treba riješiti u jednom od navedenih programskih jezika: BASIC, Pascal, C/C++, Java.

Rješenje je potrebno OBRAZLOŽITI u sklopu dokumentacije. Poželjno je, ali ne i obvezatno, priložiti dijagram toka. Postojanje i cjelovitost dokumentacije uzimat će se u obzir prilikom bodovanja.

Rješenje će se bodovati prema sljedećim kriterijima:

1. točnost rješenja (broj bodova dobivenih testiranjem)
2. brzina izvođenja programa (brže je bolje)
3. dokumentiranost (kako glavnog algoritma, uključno s dijagramom toka, tako i predanog programa u cjelosti)
4. urednost izvornog koda (čitljivost, originalnost...)

Testni primjeri imaju vremenska ograničenja. Ukoliko program ne generira rješenje u predviđenom roku, prekida se njegovo izvršenje. Tipično vremensko ograničenje po svakom testnom primjeru (odnosno, izvršavanju testnog primjera) iznosi 10 sekundi na računalu Intel Core2Duo 1.8GHz, sa 1GB radne memorije.

.predajaRješenja

Rješenje se predaje POD ŠIFROM (koju je potrebno navesti u subjectu poruke), kao dio komprimirane datoteke "SIN2007.zip" koja mora sadržavati:

1. rješenja u izvršnom (.exe) obliku (za DOS ili Windows platformu), snimljeno pod imenom "sudoku.exe".
2. izvorni kod rješenja (koji mora odgovarati izvršnoj verziji!).
3. dokumentaciju (čitljivu u Internet Exploreru)
4. "PODACI.txt" datoteku koja mora sadržavati:
4.1 ime i prezime natjecatelja
4.2 punu adresu
4.3 godinu rođenja
4.4 telefonski broj

Rješenje se predaju u privitku (attachment) isključivo e-mailom, na adresu sin@dir.hr, uz ograničenje veličine privitka na 10 MB.

Svaki natjecatelj smije poslati maksimalno jedno rješenja gornjeg problema.

.nagrade

Dodjeljuje se novčana nagrada u netto iznosu od 1.000,00 kn (slovima: tisuću kuna) prema odluci stručne komisije. Nagradu osvaja natjecatelj(i) koji na testiranju sakupi(e) najviše bodova. DIR zadržava pravo obustave dodjele nagrade ukoliko niti jedno od prispjelih rješenja ne zadovolji minimalne selekcijske kriterije.

Stručna komisija pregledat će prispjela rješenja i ocijeniti ih najkasnije do 10. prosinca 2007. godine.

Proglašenje pobjednika obavit će se putem weba i u medijima. Uručenje nagrade obavit će se u dogovoru s pobjednikom(cima).

.dodatneInformacije

Za sve dodatne informacije možete se obratiti na sin@dir.hr. I... sretno!

U Rijeci, 1. studenog 2007. godine