cubeSolver

Risolutore sperimentale del cubo di Rubik in C++20, per cubi 3×3 e 4×4. Il programma cerca, per forza bruta su sequenze casuali, combinazioni di mosse "interessanti" (ad esempio sequenze che lasciano quasi tutte le caselle a posto), utili come mattoni per algoritmi di risoluzione.

Struttura del repository

cube/
├── cubeSolver/          Applicazione console (solution + progetto principale)
│   ├── cubeSolver.sln   Solution Visual Studio (include anche CubeTest)
│   ├── Face3.h/.cpp     Faccia 3×3 bit-packed (uint32_t, 3 bit per casella)
│   ├── Face4.h/.cpp     Faccia 4×4 bit-packed (uint64_t, 3 bit per casella)
│   ├── Face.h           Alias Face<N> -> Face3 / Face4
│   ├── Move.h/.cpp      Codifica delle mosse e dispatcher Moves<N>
│   ├── Cube.h/.cpp      Il cubo generico Cube<N>
│   ├── CombinationFinder.h/.cpp  Ricerca di combinazioni per forza bruta
│   └── main.cpp         Entry point
├── CubeTest/            Test unitari (VS CppUnitTestFramework)
└── tools/
    └── cube-viewer.html Visualizzatore grafico delle combinazioni (apribile nel browser)

Convenzione dei sorgenti: gli header contengono solo le interfacce, le implementazioni stanno nei .cpp. Le classi template (Cube<N>, Moves<N>, CombinationFinder<N>) sono istanziate esplicitamente per N=3 e N=4 in fondo al rispettivo .cpp.

Architettura

Facce bit-packed

Ogni casella occupa 3 bit (6 colori, valori 0–5). Un'intera faccia sta quindi in un singolo intero:

• Face3: 9 caselle × 3 bit = 27 bit → uint32_t
• Face4: 16 caselle × 3 bit = 48 bit → uint64_t

Le operazioni (rotazioni della faccia, inversione di colonna, isDone) lavorano direttamente sui bit. Face<N> (in Face.h) mappa la dimensione sull'implementazione giusta, quindi il resto del codice è generico rispetto a N.

Il cubo

Cube<N> mantiene 6 facce e una faceMap che associa i codici faccia alle posizioni:

    4          U
  3 0 1 2    L F R B
    5          D

I colori iniziali coincidono con gli indici di faccia (F=0, R=1, B=2, L=3, U=4, D=5).

Le mosse

Notazione testuale accettata da do_command:

Comando	Effetto
R:n / L:n	Ruota la riga n verso destra / sinistra
U:n / D:n	Ruota la colonna n verso l'alto / il basso
GR GL GU GD	Ruota l'intero cubo (right/left/up/down)

Codifica compatta (move_t, in Move.h): (op << 4) | riga, con op 0=R 1=L 2=U 3=D 4=GR 5=GL 6=GU 7=GD.

normalize() riporta il cubo all'orientamento standard con rotazioni globali, così due stati che differiscono solo per l'orientamento risultano uguali.

CombinationFinder

CombinationFinder<N> genera sequenze casuali di mosse (escludendo le rotazioni globali e le mosse della prima riga) e le valuta:

• find(nMoves, mask): cerca una sequenza che rispetti una maschera di caselle da preservare
• findDiff(nMoves, nDiff): cerca (all'infinito, stampandole) sequenze che lasciano al più nDiff pezzi (cubie) fuori posto, nessuno sulla faccia U — un pezzo con più sticker sbagliati conta una volta sola. Stampa solo le combinazioni uniche: due risultati che muovono i pezzi allo stesso modo ma su facce diverse (cioè identici a meno di una delle 48 simmetrie del cubo, rotazioni e riflessioni) contano come la stessa combinazione (canonicalSignature). Le sequenze stampate sono scremate delle mosse inutili (simplifySequence): mosse su righe diverse — o colonne diverse — commutano, quindi nei tratti consecutivi sullo stesso asse i quarti di giro di ogni riga/colonna si sommano modulo 4 (mossa + inversa, doppia + doppia, X² Y X², X Y X⁻¹… spariscono)

Compilazione

Requisiti: Visual Studio con toolchain C++ (MSVC, C++20).

Visual Studio: aprire cubeSolver/cubeSolver.sln e compilare (configurazione consigliata: x64).

Visual Studio Code: aprire la cartella cubeSolver/; sono già configurate le task di build (Ctrl+Shift+B, usa MSBuild) e il debug (F5) in .vscode/.

Riga di comando (da Developer PowerShell):

msbuild cubeSolver\cubeSolver.sln /p:Configuration=Debug /p:Platform=x64

L'eseguibile finisce in cubeSolver\x64\Debug\cubeSolver.exe.

Test

I test unitari (progetto CubeTest, 10 test su Cube<4>) si eseguono dal Test Explorer di Visual Studio, oppure:

vstest.console.exe cubeSolver\x64\Debug\CubeTest.dll /Platform:x64

Visualizzatore grafico

tools/cube-viewer.html è una pagina autosufficiente (nessuna dipendenza, basta aprirla con doppio clic nel browser) che mostra graficamente il risultato di una combinazione:

1. Scegli la dimensione del cubo (3×3 o 4×4)
2. Incolla la sequenza — codici numerici come li stampa findDiff (es. 49 17 33 33) oppure comandi testuali (D:1 L:1 GR) — e premi Applica
3. La pagina mostra lo sviluppo a croce del cubo con gli sticker fuori posto marcati, il conteggio dei pezzi mossi (identico a countDiff) e uno slider per ripercorrere la sequenza mossa per mossa

Il motore JavaScript della pagina è un port fedele di Cube.cpp (verificato contro l'output del motore C++); se si modifica la logica delle mosse in C++, va aggiornato anche lì.

Estendere a nuove dimensioni (es. 5×5)

1. Implementare Face5 (Face5.h/Face5.cpp) — servono più di 64 bit: 25 caselle × 3 bit = 75 bit
2. Aggiungere la specializzazione FaceOf<5> in Face.h
3. Aggiungere template class ...<5>; in fondo a Cube.cpp, Move.cpp e CombinationFinder.cpp

Se si dimentica un'istanziazione, il linker segnala il simbolo mancante.