Keskustelu: Ohjelmointikysymykset: C++: Numeroshakki

Eli ongelmani on menettely tapa... Ja samanlaista menettyly tapaa tarvitsen(?) numero shakkia ratkaistessani. Tämä on parempi tapa havainnollistaa ongelmaa. Numero shakki on monelle varmaan tuttu mutta kerrataan

Numero shakin säännöt:
10*10 ruudukko. Se pitää täyttää niin täyteen numeroilla kuin saa. (1,2,3...) Mutta numerot pitää "latoa" seuraavasti:
Aloitetaan vasemmasta ylänurkasta. Seuraava numero pitää laittaa kaksi ruutua yli "pääilmansuuntiin" ja yksi ruutu yli "sivuilmansuuntiin".

Tähän malliin...

1 x x 2 x x 3 x x x
x x x x x x x x x x
x x x x x x x x 4 x
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x 5 x
x x x x x x x x x x
x x x x x x 6 x x x
x x x x x x x x x x
x x x x x x x x x x

Ohjelman toiminta ideana ois että ohjelma täyttää ruudukkoa tarkastaen että ruutu ei ole jo varattu. Tätä myöten täyttäs ruudukon parhaansa mukaan numeroilla. Kunnes jää juumiin, eli ei enää "laillisia" siirtoja jäljellä. Tähän asti kyllä osaisin tehdä.

Mutta miten saada ohjelma kokeileen eri vaihtoehtoja järjestelmällisesti? Eli periaatteessa kokeilisi vaikka kaikki vaihtoehdot kun saa tarpeeksi aikaa. Tässä vaiheessa mietin myös tuota "ohjausta" se ei voi olla vain että

"laitetaan numero ylös jos voi, jos ei voi laitetaan ylös oikealle jos ei voi...."

Eli neuvoa aloittelijalle. Kiitos

Oikea ongelma takana on kurssi tarjottin. Johon verrattuna sudokun täyttö on helppoa ja rentouttavaa.

PS. ei tässä tuonkaan kanssa helpolla pääse ku pitää syöttää kurssitarjotin digitaaliseen muotoon :(

Tässä on yksinkertainen ohjelma, joka sijoittaa numeroita ruudukkoon.

#include <stdio.h>

// tämä taulukko sisältää ruudukon (0 = tyhjä)
int ruudukko[10][10] = {0};
// paras löydetty tulos
int paras = 0;

// tulostaa ruudukon sisällön ennätystapauksessa
void tulos(void) {
    int i, j;
    printf("Löytyi %i numeron ruudukko.\n", paras);
    printf("+--+--+--+--+--+--+--+--+--+--+\n");
    for (i = 0; i < 10; i++) {
        for (j = 0; j < 10; j++) {
            if (ruudukko[j][i] == 0) {
                printf("|  ");
            } else {
                printf("|%2i", ruudukko[j][i]);
            }
        }
        printf("|\n+--+--+--+--+--+--+--+--+--+--+\n");
    }
    printf("\n\n");
}

// merkitsee numeron ruudukkoon ja siirtyy seuraavaan numeroon
void siirto(int x, int y, int numero) {
    // jos koordinaatit ruudukon ulkopuolella, pois
    if (x < 0 || y < 0 || x >= 10 || y >= 10) return;
    // jos ruudukon kohta on jo varattu, pois
    if (ruudukko[x][y] != 0) return;
    // merkitään numero ruudukkoon
    ruudukko[x][y] = numero;
    // tarkistetaan ennätystulos
    if (numero > paras) {
        paras = numero;
        tulos();
    }
    // yritetään merkitä seuraava numero kaikkiin suuntiin
    siirto(x + 2, y, numero + 1);
    siirto(x - 2, y, numero + 1);
    siirto(x, y + 2, numero + 1);
    siirto(x, y - 2, numero + 1);
    siirto(x + 1, y + 1, numero + 1);
    siirto(x + 1, y - 1, numero + 1);
    siirto(x - 1, y + 1, numero + 1);
    siirto(x - 1, y - 1, numero + 1);
    // poistetaan numero ruudukosta
    ruudukko[x][y] = 0;
}

int main(void) {
    // aloituskohta (0, 0), numero 1
    siirto(0, 0, 1);
    return 0;
}

Ohjelman toiminta perustuu rekursiiviseen siirto-funktioon, joka merkitsee numeron ruudukkoon ja kutsuu itseään. Tällä tavalla varmistetaan, että jokainen numeroiden järjestys käydään läpi vain kerran. Jokaisen siirron jälkeen yritetään lisätä seuraavaa numeroa kaikkiin mahdollisiin suuntiin. Mutta ruudukoita voi laatia niin monella tavalla, että tämän ohjelman suoritus ei pääty käytännössä koskaan. Ohjelma kuitenkin tulostaa näytölle aina parhaan löytämänsä ruudukon.

Tällainen ratkaisu sopii yleisesti sellaisiin tehtäviin, joissa pitää koettaa sijoittaa jotain ruudukkoon. Tosin tämä on yleensä vain ohjelman raakaversio, ja riittävän nopean ohjelman tekemiseksi muodostettavien järjestysten määrää pitää jotenkin rajoittaa. Parasta ratkaisua etsittäessä tällainen parannus olisi arvio, jonka perusteella voidaan jo varhain tietää, että tietty alkuvaiheessa oleva numeroiden järjestys ei johda ennätystä parempaan tulokseen.

Jos jokin kohta ohjelman toiminnassa ei selviä yllä olevan perusteella, kysy toki.

Kiitos tuosta. Tutkin perusteellisemmin tuota heti kun kerkeän... On ollut vähän seurantalkoot ja koulu työt viemässä aikaa.

Tottahan on että 100 kertoma on ISO. Vaikka vaihtoehtoja on vain murto-osa siitä niin johan niitä silti jää... Kurssitarjotin sisältää 32-33 "numeroa"... Tosin konetta voi avittaa laittamalla sellaiset "must" kurssit paikalleen.

Minäkin olen tehnyt kerran ohjelman lukion kurssien valintaan. Se perustui juuri tuohon samaan tekniikkaan. Kurssit onneksi sulkivat pois toisiaan niin tehokkaasti, että mahdollisten järjestysten määrä liikkui sadoissa tuhansissa.