piccola sfida

[Strat]

Come sanno bene gli appassionati di programmazione ( amatoriali o professionisti che siano) la cosa più stimolante e trovare la soluzione di problemi più o meno complessi, a prescindere dal linguaggio che si usa per la codifica, che alla fine è la parte "banale".

Penso di aver trovato un giochetto stimolante, magari la soluzione è una c*****a e io non ci sono arrivato, ma non credo.

Sto seguendo un corso di elettrotecnica, la odio, devo pure passarmi il tempo!!!

Il gioco è questo: si ha a disposizione un matrice 10x10, quindi 100 caselle e si deve riempire con i numeri da uno a cento seguendo le seguenti regole:
- si piazza l'1 in una pos a scelta
per gli altri numeri si seguono 2 semplici regole:
- spostamenti verticale e orrizzontale saltando 2 caselle
-spostamento obliquo saltando 1 casella.
Es.: __________________
|_1_|___|__|_ 2_|
|___|_4_|__|____|
|___|___|__|____|
|___|___|__|_3__|
|___|___|__|____|
...ho messo l'1 nella casella(1,1) ho saltato due caselle verso destra e messo il 2, poi due caselle verticalmente e messo il 3 e una casella obliquamente e messo il 4, e così via...

Preciso che non mi è mai riuscito, ma mi hanno assicurato che si può fare!
Fatto stà che la soluzione in qualche modo la vorrei vedere!

Scartato subito il caso di scrivere direttamnte un algoritomo che si basi su un certo ragionamento, altrimenti lo avrei risolto anche sulla carta, ho pensato di passare attraverso un algoritmo di BRUTE FORCING che vi desrivo sommariamente:

Si piazza a caso l'1
Dipendentemente dalla posizione del numero si sceglie a caso la pos in cui mettere il numero successivom se non è occupata bene, altrimenti se ne sceglie un'altra, e così via tendo memoria delle pos occupate e finchè non è stato inserito il numero 100.

Ma.... Quanto ci metterà?

Vi chiedo di aiutarmi soprattutto perchè è un anno che non scrivo una riga di codice ( non mi ricordo la sintassi!)

Ciao e grazie!!!

[misterx]

dai a2000 è pane per i tuoi.....denti ?

onestamente non ho capito come distribuisci i numeri nella matrice

[Strat]

L'unica cosa da sapere è che orrizzontalmente e verticalmente si saltano 2 caselle e obliquamente 1, naturalmente la matrice non si può intendere appaoggiato su una sfera, quindi i bordi sono MURI!

[a2000]

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	x
x	x	x	50	x	|	x	51	x	x	x
x	x	x	x	26	|	75	x	x	x	x
----------------------------------------------------------------------------------------------
x	x	x	x	100	|	1	9	20	2	12
x	x	x	76	x	|	15	25	5	16	22
x	x	x	x	x	|	7	18	13	8	19
x	x	x	x	x	|	4	10	21	3	11
x	x	x	x	x	|	14	24	6	17	23

[a2000]

gli altri tre quadranti si completano analogamente al 4° quadrante (in basso a destra).

[recoil]

Originariamente inviato da Strat
Vi chiedo di aiutarmi soprattutto perchè è un anno che non scrivo una riga di codice ( non mi ricordo la sintassi!)

scusa ma prima dici che è bello perché non dipende dal linguaggio e poi dici che non ti ricordi la sintassi...
tu invia la soluzione in uno pseudo linguaggio e poi te la traduciamo

[cionci]

Originariamente inviato da a2000
gli altri tre quadranti si completano analogamente al 4° quadrante (in basso a destra).

Ma c'è un algoritmo per il rimpimento ?

[a2000]

Originariamente inviato da Strat
...

Scartato subito il caso di scrivere direttamnte un algoritomo che si basi su un certo ragionamento, altrimenti lo avrei risolto anche sulla carta, ho pensato di passare attraverso un algoritmo di BRUTE FORCING che vi desrivo sommariamente:

Si piazza a caso l'1
Dipendentemente dalla posizione del numero si sceglie a caso la pos in cui mettere il numero successivom se non è occupata bene, altrimenti se ne sceglie un'altra, e così via tendo memoria delle pos occupate e finchè non è stato inserito il numero 100.

Ma.... Quanto ci metterà?

....

tutti i giochi su campo intero (carte, scacchi, ecc.) possono essere rappresentati con un grafo di stato e risolti solitamente con due approcci principali:
combinatorio
strategico


Soluzione combinatoria
si determina la soluzione in base a una analisi più o meno semplice (simmetria, teoremi) del problema.

nel caso in eseme:
100 arbitrario, perchè non 10, 50 o 1000
forse problema a celle legate
simmetria
frazionamento in celle secondo assi di simmetria
numerazione simmetrica crescente e decrescente
soluzione trovata


Soluzione con regole di strategia
la soluzione si determina passo passo secondo regole di strategia che massimizzano una "funzione di merito" che tiene conto di tutte le possibilità per n passi successivi.
per esempio:
ad ogni passo scelgo la cella che ha il minor grado d'entrata
posso ibridare la strategia con un criterio di simmetria decidendo di numerare alternativamente in senso crescente e decrescente.

la ricerca di soluzioni con regole di strategia è semplice da implementare ma non "vede" oltre gli n passi analizzati dall'algoritmo e trova soluzioni connesse a quella iniziale.

[a2000]

Originariamente inviato da cionci
Ma c'è un algoritmo per il rimpimento ?

stabilita la cella iniziale e finale, riempimento simmetrico a numerazione alternata.

è un'algoritmo semplice ma della razza di quelli difficili (combinatori).

gli algoritmi più facilmente adottati (p.es. negli scacchi) sono di tipo strategico con massimizzazione di una funzione obiettivo.
soluzione a cui probabilmente accennava Strat e che si può fare anche in questo caso.

Un problema con analogie è quello della riduzione dei sistemi per il totocalcio.

[a2000]

Originariamente inviato da Strat
...
Sto seguendo un corso di elettrotecnica, la odio, devo pure passarmi il tempo!!!
....

ma come !?

elettrotecnica è bellissima!
deduttiva e pulita: da quattro equazioni si ricava tutto.

[Strat]

x a2000

grazie mille, anchio avevo provato con delle simmetrie, ma arrivavo sempre a 98. Complimenti!

xrecoil

io accennavo ad un algoritmo di forza bruta, che credo chiunque sia in grado di scrivere, semplicemente per avere una soluz da studiare in modo da scrivere poi un codice ragionato, è questa la cosa tosta! Mi hai frainteso!

Ciao a tutti!

[NA01]

è da quasi 2 anni che lo faccio nelle ore di italiano e latino (ovviamente a mano) e mi è riuscito solo 3 volte!
non avevo mai pensato di farlo fare a un pc, appena trovo il tempo provo!

ciao

[alderighi]

l'algoritmo sembra semplice, ditemi se ho capito bene, questo giochetto non funziona tutte le volte, vero? basta mettere un ciclo while che lo ripete finchè casualmente l'uno non viene messo nella posizione giusta a random e il giochetto funziona. magari impieghera qualche secondo ma dovrebbe funzionare.

[a2000]

tel chì !
per esempio questo è generato in automatico con un algoritmo di 30 righe

1	54	41	2	55	42	23	30	43	22
62	18	15	63	19	14	83	20	13	84
40	3	60	57	99	29	56	100	28	31
16	53	67	17	82	68	24	81	44	21
61	58	94	64	59	93	86	32	12	85
39	4	79	69	98	80	70	97	27	34
75	52	66	76	91	65	25	92	45	8
49	72	95	50	71	96	87	33	11	88
38	5	78	37	6	77	36	7	26	35
74	51	48	73	90	47	10	89	46	9

[a2000]

la regola di scelta è quella suddetta del minimo grado di uscita.

[a2000]

ah, dimenticavo, VBA-Excel rulez !!

[a2000]

e questa è un'altra

74	51	48	73	98	47	6	97	46	5
38	1	78	37	2	77	36	3	26	35
49	72	95	50	71	96	87	33	7	88
75	52	66	76	99	65	25	100	45	4
39	16	79	69	90	80	70	89	27	34
61	58	94	64	59	93	86	32	8	85
12	53	67	17	82	68	24	81	44	21
40	15	60	57	91	29	56	92	28	31
62	18	11	63	19	10	83	20	9	84
13	54	41	14	55	42	23	30	43	22

[a2000]

un'altra ancora:

15	54	41	14	55	42	23	30	43	22
62	18	1	63	19	2	83	20	3	84
40	13	60	57	99	29	56	100	28	31
16	53	67	17	82	68	24	81	44	21
61	58	94	64	59	93	86	32	4	85
39	12	79	69	98	80	70	97	27	34
75	52	66	76	91	65	25	92	45	8
49	72	95	50	71	96	87	33	5	88
38	11	78	37	10	77	36	9	26	35
74	51	48	73	90	47	6	89	46	7

[a2000]

voletelamacchinetta?

[NA01]

ma usi un algoritmo random o ha un criterio?
niente vba e exel, non ne sò niente, senza contare che sul pc non li ho nemmeno (slack rulez! )
ciao