Cube Solver

Pemecah Kubus Rubik

Demo Video: https://www.youtube.com/watch?v=A6JyElruhwE

Demo: http://d4m4s74.pythonanywhere.com/

Keterangan:

Proyek Akhir Saya untuk CS50 adalah Pemecah Kubus Rubik "Metode Manusia".
Artinya Kubus Rubik yang dimasukkan diselesaikan menggunakan metode yang bisa digunakan manusia (CFOP), dengan langkah-langkah yang jelas: Cross, F2L, OLL dan PLL.
Produk akhir terdiri dari aplikasi shell, perpustakaan C untuk digunakan dalam proyek lain, dan antarmuka web yang ditulis dalam Flask, HTML, CSS dan Javascript.

Saya memutuskan untuk membuat pemecah Kubus Rubik karena saya telah membuat pemecah Sudoku sebelumnya di C++, dan kubus tersebut merupakan sebuah kemajuan.
Alih-alih bidang 2d, saya memiliki bidang semi-3d, dengan tepi dan sudut.
Karena pemecah AI telah selesai, dan saya tidak cukup yakin dengan kemampuan menulis AI saya, saya memutuskan untuk membuat program memecahkan kubus seperti yang saya lakukan:
Silang, F2L, OLL dan PLL

Cara menggunakan

Pemecah

Linux

Unduh bin/solver yang dapat dieksekusi atau buat dari sumber menggunakan make solver

OS X

Unduh atau kloning file dari repositori ini dan buat menggunakan make solver

jendela

Unduh atau kloning file menggunakan repositori ini dan kompilasi semua file .c di src kecuali solver_library

Semua

Jalankan solver dengan salah satu perintah berikut:

 ./solver "Algorithm"
./solver [Up] [Front] [Right] [Back] [Left] [Down]

Mengganti algoritma dengan algoritma scramble (misalnya U R2 FBR B2 R U2 L B2 RU' D' R2 FR' L B2 U2 F2 ) atau wajah dengan warna pada wajah tersebut (misalnya wbwowrwgw gwgogrgyg rwrgrbryr bwbrbobyb owobogoyo ygyoyryby ).
Warna yang mungkin adalah karakter pertama Hijau, Merah, Biru, Oranye, Putih dan Kuning.
Jika file olls.txt dan plls.txt tidak berada dalam folder yang sama dengan biner, gunakan opsi -o dan -p, atau -d untuk menunjuk ke file

 bin/solver -d data/ "U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2"
bin/solver -o data/olls.csv -p data/plls.csv "U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2"

Tambahkan opsi -t untuk hanya mencetak teks tanpa gambar kubus.

Antarmuka web

Linux:

Unduh atau kloning file dari repositori ini.
Instal Flask dan Numpy menggunakan pip.

 python3 -m pip -r requirements.txt

Gunakan perintah flask run , atau python3 app.py untuk menjalankan server web.
Buka https://127.0.0.1:5000/ untuk menggunakan pemecah.

OS X:

Unduh atau kloning file dari repositori ini.
Hapus bin/libcubesolver.so versi Linux secara manual atau gunakan make clean dan kompilasi ulang menggunakan make library .
Instal Flask dan Numpy menggunakan pip:

 python3 -m pip -r requirements.txt

Gunakan perintah flask run , atau python3 app.py untuk menjalankan server web.
Buka https://127.0.0.1:5000/ untuk menggunakan pemecah.

jendela:

Unduh atau kloning file dari repositori ini. Hapus bin/libcubesolver.so versi Linux secara manual.
Kompilasi semua file .c di src kecuali solver.c ke bin/libcubesolver.so. Atau jika menggunakan nama yang berbeda, ubah baris 19 di app.py untuk mencerminkan hal itu.
Instal Flask dan Numpy menggunakan pip:

 python3 -m pip -r requirements.txt

Gunakan perintah flask run , atau python3 app.py untuk menjalankan server web.
Buka https://127.0.0.1:5000/ untuk menggunakan pemecah.

Perpustakaan Pemecah

Instal untuk digunakan dengan C atau C++

Kompilasi semua file di src kecuali solver.c ke libcubesolver.so, libcubesolver.dylib atau libcubesolver.dll dan simpan di mana pun perpustakaan disimpan di komputer Anda.
Di Linux Anda dapat menggunakan make library
Salin libcubesolver.h dari src ke mana pun header disimpan di komputer Anda (mis. /usr/include/)

Penggunaan dengan C atau C++

Tautkan dengan -lcubesolver atau cukup kompilasi ke dalam aplikasi seolah-olah itu file .o

 #include 
#include 
//Use either setup, or both load_olls and load_plls.
//Load all OLLs and PLLs into memory. Path is the folder where the olls.csv and plls.csv file are located.
//Returns indicating for succes or failure.
setup ( path );
//Loads the OLLs from a CSV file. Returns bool indicating success or failure.
load_olls ( filename );
//Loads the PLLs from a CSV file. Returns bool indicating success or failure.
load_plls ( filename );
//Create an array to hold the cube. 6 faces, 9 squares per face.
//The faces in order are Front, Right, Back, Left, Up and Down.
//The "Colors" are saved as the numbers 0 to 5.
int cube [ 6 ][ 9 ];
//Add the "colors" of the cube to the array as 9 character strings containing numbers 0 to 5.
color_cube ( cube , front , right , back , left , up , down );
//Run a multiple move algorithm on the cube, using standard cube notation. (Useful for scrambling)
run_algorithm ( cube , "Algorithm" );
/*
A function that prints the sides of the cube in an exploded fashion. Uses colors when in linux or OS X
Uses Green for 0, Red for 1, Blue for 2, Orange for 3, White for 4, Yellow for 5
    WWW
    WWW
    WWW

OOO GGG RRR BBB
OOO GGG RRR BBB
OOO GGG RRR BBB

    YYY
    YYY
    YYY
*/
print_cube ( cube );
//Validate the colors on the cube for impossible cubies. This does not check if the scramble is solvable.
//Returns bool.
if (! validate ( cube ))
{
    return "Invalid color combinaton" ;
}
//returns pointer to string containing all algorithms used to solve the cube, separated by newlines,
//and the names of the steps. (eg. Cross, F2L, OLL: Sune, PLL: Y perm)
//Modifies the array to its solved position
char * solution = solve ( cube );
// Returns:
/*
Cross
(R D' F D)
(y) (R D' F D)
(y) (R D' F D)
(y) (R D' F D)

F2L
(y) R U R' U R U' R') (d' L U L')
(y2) (L' U' L) (y') (U' F' U F) (R' F R F')
(d2 R' U2 R2 U R2 U R)
(y) (U R U R' U2) (d R' U2 R) (U' R B' R' B)

OLL: Kite
(y2) (R U R' U') R' F R2 U R' U' F'

PLL: G perm c
(y2) L' R' U2 L R (y) L U' R U2 L' U R'
*/

//Generates a cube from an algorithm and returns pointer to its solution, or an error if unsolvable.
char * solution2 = solve_scramble ( "scramble" );
//Solves the (yellow) cross.
//Returns a pointer to a string containing the solve algorithm, with each solved edge separated by newlines.
//May also return an error if unsolvable.
//Modifies the cube array to have a solved cross.
char * cross = solve_cross ( cube );
//Solves the first two layers of the cube assuming a solved cross.
//Returns a string containing the solve algorithm, with each solved pair separated by newlines.
//Modifies the cube array to solve its f2l.
//Returns null if the cube is unsolvable.
char * f2l = solve_f2l ( cube );
//Looks up the right OLL algorithm and runs it, assuming a solved F2L.
//Returns the name of the OLL, and the algorithm, separated by a newline.
//Returns null if the cube is unsolvable.
char * oll = solve_oll ( cube );
//Looks up the right PLL algorithm and runs it, assuming a solved OLL.
//Returns the name of the PLL, and the algorithm, separated by a newline.
//Returns null if the cube is unsolvable.
char * pll = solve_pll ( cube );

Penggunaan dengan python

Lihat versi C untuk melihat fungsi masing-masing.
Karena sulit untuk mengosongkan memori malloced dengan python, gunakan versi fungsi penyelesaian yang "aman" dan gunakan free_strings() setelah digunakan.

 import numpy
import ctypes
# Most functions will need a c 2d int array. Let's give it a name so it's easy to use.
array_2d_int = numpy . ctypeslib . ndpointer (
    dtype = ctypes . c_int , ndim = 2 , flags = 'CONTIGUOUS' )
# First load the solver library using ctypes CDLL.
solver = ctypes . CDLL ( "/path/to/libcubesolver.so" )
# Then we set up all functions we might want to use.
# Setup, load_olls and load_plls require a string.
solver . setup . argtypes = [ ctypes . c_char_p ]
solver . load_olls . argtypes = [ ctypes . c_char_p ]
solver . load_olls . argtypes = [ ctypes . c_char_p ]
# Run_algorithm requires a 2d array for the cube, and a string.
solver . run_algorithm . argtypes = [ array_2d_int , ctypes . c_char_p ]
# All other functions require just the 2d array.
solver . print_cube . argtypes = [ array_2d_int ]
solver . validate . argtypes = [ array_2d_int ]
solver . solve_safe . argtypes = [ array_2d_int ]
solver . solve_cross_safe . argtypes = [ array_2d_int ]
solver . solve_f2l_safe . argtypes = [ array_2d_int ]
solver . solve_oll_safe . argtypes = [ array_2d_int ]
solver . solve_pll_safe . argtypes = [ array_2d_int ]
# For functions that return something other than an int (or bool) we also need to set the response type.
solver . solve_safe . restype = ctypes . c_char_p
solver . solve_cross_safe . restype = ctypes . c_char_p
solver . solve_f2l_safe . restype = ctypes . c_char_p
solver . solve_oll_safe . restype = ctypes . c_char_p
solver . solve_pll_safe . restype = ctypes . c_char_p
# Load the olls and plls csvs. in my case they're in the data folder.
# Use .encode('utf-8') to convert the python string to a c string.
solver . setup ( "data" . encode ( 'utf-8' ))
# Set up a cube. The inner lists, in order, are Front, Right, Back, Left, Up and Down.
# By default 0 = green, 1 = red, 2 = blue, 3 = orange, 4 = white, 5 = yellow.
solvedcube = [[ 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ],
              [ 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ],
              [ 2 , 2 , 2 , 2 , 2 , 2 , 2 , 2 , 2 ],
              [ 3 , 3 , 3 , 3 , 3 , 3 , 3 , 3 , 3 ],
              [ 4 , 4 , 4 , 4 , 4 , 4 , 4 , 4 , 4 ],
              [ 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 ]]
# Turn it into a C 2d array.
cube = numpy . array ( solvedcube ). astype ( ctypes . c_int )
# Run a scramble on the array. Use .encode('utf-8') to change the python string to a c string.
solver . run_algorithm (
    cube , "U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2" . encode ( 'utf-8' ))
# Print the cube to the shell.
solver . print_cube ( cube )
# Validate the color comibinations on the cube.
if not validate ( cube ):
    return "Invalid color combinaton"
# Solve the cube using solver.solve.
# Note: running the function also modifies the cube array.
solution = solver . solve_safe ( cube ). decode ( "utf-8" )
# Returns:
"""
Cross
(R D' F D)
(y) (R D' F D)
(y) (R D' F D)
(y) (R D' F D)

F2L
(y) R U R' U R U' R') (d' L U L')
(y2) (L' U' L) (y') (U' F' U F) (R' F R F')
(d2 R' U2 R2 U R2 U R)
(y) (U R U R' U2) (d R' U2 R) (U' R B' R' B)

OLL: Kite
(y2) (R U R' U') R' F R2 U R' U' F'

PLL: G perm c
(y2) L' R' U2 L R (y) L U' R U2 L' U R'
"""
# Or returns an error if the cube is unsolvable.

# You can also do the steps separately.
# solve the cross.
cross = solver . solve_cross_safe ( cube ). decode ( "utf-8" )
# returns
'''
(R D' F D)
(y) (R D' F D)
(y) (R D' F D)
(y) (R D' F D)
'''
# solve the F2L.
f2l = solver . solve_f2l_safe ( cube ). decode ( "utf-8" )
# returns
'''
(y) R U R' U R U' R') (d' L U L')
(y2) (L' U' L) (y') (U' F' U F) (R' F R F')
(d2 R' U2 R2 U R2 U R)
(y) (U R U R' U2) (d R' U2 R) (U' R B' R' B)
'''
# solve the OLL.
oll = solver . solve_oll_safe ( cube ). decode ( "utf-8" )
# returns
'''
Kite
(y2) (R U R' U') R' F R2 U R' U' F'
'''
# solve the PLL.
pll = solver . solve_pll_safe ( cube ). decode ( "utf-8" )
# returns
'''
G perm c
(y2) L' R' U2 L R (y) L U' R U2 L' U R'
'''
# If a step is already solved, the functions return an empty string.
# With an unsolvable cube, these functions return NULL, which causes an
# AttributeError when trying to decode. You may want to verify before decoding. (or use try)

# Clean up the memory for the solution strings.
solver . free_strings ()
# Finally clean up the loaded OLLs or PLLs to prevent memory leaks
solver . cleanup_last_layer ()

Struktur

CS50 ingin saya menjelaskan fungsi setiap file dan apa isinya. Jadi readme ini lebih panjang dari semua kecuali 3 file saya.

 ├── aplikasi.py  
├── bin  
│ ├── libcubesolver.so  
│ └── pemecah  
├── data  
│ ├── kesalahan.txt  
│ ├── olls.csv  
│ ├── pola.csv  
│ └── tolong.csv  
├── makefile  
├── README.md  
├── persyaratan.txt  
├── src  
│ ├── lintas.c  
│ ├── lintas.h  
│ ├── kubus.c  
│ ├── kubus.h  
│ ├── cubesolver.h  
│ ├── f2l.c  
│ ├── f2l.h  
│ ├── lapisan terakhir.c  
│ ├── lapisan terakhir.h  
│ ├── pemecah.c  
│ ├── solver_library.c    
│ ├── utils.c  
│ └── utils.h  
├── tes  
│ ├── tes acak.c  
│ └── tes acak   
├── statis  
│ ├── kubus.css  
│ ├── kubus.js  
│ ├── cubeinterface.js  
│ ├── favicon.ico  
│ ├── selanjutnya.png  
│ ├── jeda.png  
│ ├── mainkan.png  
│ └── sebelumnya.png  
├── templat  
│ ├── kubus.html  
│ └── solver.html  

src

kubus.c dan kubus.h

Cube.c dan cube.h berisi semua kode yang mengontrol kubus rubik di memori.

Kubus rubik, dalam memori, adalah larik 2d berukuran 6 kali 9. Array luar berisi enam sisi: Depan, Kanan, Belakang, Kiri, Atas dan Bawah.
Saya memilih urutan ini karena permukaan atas dan bawah selalu sama, jadi saya dapat melakukan hardcode pada keduanya, namun sisi-sisinya hanya perlu benar dalam kaitannya satu sama lain. Ini berarti saya dapat menggunakan plus atau minus sederhana, dikombinasikan dengan modulus untuk menerjemahkan tes dan berpindah ke setiap sisi. Hal yang sama berlaku untuk warna, yang disimpan sebagai angka 0 sampai 5, 0 adalah warna depan, 1 adalah warna kanan, dan seterusnya.
Saya pertama kali memilih urutan warna yang saya gunakan: Merah di depan, kuning di atas, hijau di kanan. Namun kemudian ketika menulis kode python dan antarmuka saya beralih ke warna hijau "Resmi" di depan, putih di atas sehingga saya tidak perlu memutar kubus yang dimasukkan oleh pengguna menjadi putih di bawah.

warna_kubus()

Pertama saya membuat fungsi color_cube(). Ini menerapkan pola pilihan Anda pada kubus menggunakan 6 senar.
Ia menggunakan matematika char sederhana untuk mengubah char '0', '1', dll. menjadi int dan menyimpannya dalam array yang diberikan.
Saya hanya menggunakan ini sekali atau dua kali sebagai satu liner untuk menyiapkan kubus yang diselesaikan dalam satu baris, karena ketika menerjemahkan input pengguna ke sesuatu yang dipahami komputer, Anda sebaiknya memasukkan int satu per satu daripada menerjemahkannya terlebih dahulu ke string.

cetak_kubus()

Print_cube() mengeluarkan kubus yang disediakan ke terminal. Ini banyak digunakan saat debugging, dan untuk aplikasi terminal. Saya mulai dengan mengeluarkan angka 0 hingga 5 saja dalam bentuk kubus rubik yang meledak.

    444
    444
    444

333 000 111 222
333 000 111 222
333 000 111 222

    555
    555
    555

Karena akan membuat lebih banyak baris kode untuk mengotomatiskannya, saya cukup menggunakan 9 pernyataan cetak yang masing-masing berisi hingga 12 variabel.
Kemudian saya mengetahui bahwa saya dapat menambahkan kode shell seperti e[42m untuk memberi warna latar belakang pada angka-angka ini. Menambahkannya memberi saya 28 variabel per cetakan.
Akhirnya saya berpikir untuk memasukkan huruf atau angka untuk warna ke dalam array yang menyimpan kode shell, mengembalikannya ke 12. Sayangnya Windows tidak mendukung jenis kode shell ini, jadi saya harus tetap menggunakan angka saja, dan surat-surat selanjutnya.

pindahkan_kubus()

Move_cube() adalah fungsi pertama untuk mengubah kubus. Ini adalah fungsi rekursif yang melakukan perpindahan yang diminta sebanyak yang diminta. Ada 9 kemungkinan gerakan, bernomor 0 hingga 8. Default depan, kanan, belakang, dll. Tetapi juga lapisan tengah, khatulistiwa, dan berdiri. Menggunakan fungsi pembantu yang saya tulis di utils.c disebut Siklus Saya mengganti nilai setiap kotak di setiap sisi sesuai dengan gerakan searah jarum jam, ulangi jika perlu.

jalankan_algoritma()

Karena perpindahan biasanya tidak terjadi dengan sendirinya, selanjutnya saya menulis run_algorithm(). Fungsi ini menggunakan move_cube() untuk menjalankan algoritma pada kubus yang disediakan dalam notasi kubus standar. Ini memberi saya kemampuan untuk melakukan beberapa gerakan sekaligus (atau secara berurutan), dan melakukan gerakan yang berpengaruh pada 2 atau bahkan 3 lapisan seperti x, y, dan z.

mengesahkan()

Terakhir, validasi(). Saya menambahkan fungsi ini saat menulis antarmuka Python karena Anda tidak boleh mempercayai pengguna Anda untuk tidak memasukkan hal-hal aneh.
Fungsi ini tidak memeriksa apakah kubus rubik dapat dipecahkan. Ia memeriksa apakah warnanya benar. Misalnya, satu cubie tidak boleh memiliki stiker putih dan kuning sekaligus. Dan searah jarum jam dimungkinkan untuk memiliki stiker hijau, putih dan merah dalam urutan itu, tetapi tidak sebaliknya.
Untuk melakukan ini, saya menyalin sebagian gagasan array terkunci di Tideman, menggunakan array boolean 2d untuk sudut, dan array boolean 3d untuk tepinya untuk melihat apakah kombinasi 2 atau 3 warna dimungkinkan. Kode ini mengalami beberapa iterasi. Pertama-tama periksa setiap tepi dan sudut secara terpisah, dan kemudian gunakan beberapa loop for.

cross.c dan cross.h

Cross.c berisi semua kode yang diperlukan untuk menyelesaikan persilangan kubus. Karena saya menggunakan "Metode Manusia" (CFOP) untuk menyelesaikan kubus, saya terpaksa menggunakan pohon keputusan yang besar.
Saya menulis ulang hampir seluruh file ini pada menit-menit terakhir sehingga tidak harus menyelaraskan tepinya di setiap langkah.

temukanZero()

Menemukan lokasi tepi kuning-hijau pada lapisan bawah, atau jika belum ada. Hal ini memudahkan untuk menyelaraskan tepi lainnya dalam langkah yang lebih sedikit karena tepi tersebut dapat disejajarkan ke "nol relatif" dan bukan ke nol sebenarnya.

crossCase1() hingga 6

6 kasus ini adalah setiap cara sebuah tepi dapat diorientasikan, Menunjuk ke bawah, menunjuk ke atas, menunjuk ke luar pada lapisan atas dan bawah, menunjuk ke kiri dan menunjuk ke kanan pada lapisan E.
Fungsinya pada dasarnya memindai wajah dalam urutan 0 hingga 3 untuk mencari bagian yang termasuk dalam salib, memutarnya ke tempatnya, dan menyimpan gerakan dalam array char menggunakan fungsi pembantu yang saya sebut append().

pecahkan_silang()

Solve_cross pertama-tama mengarahkan kubus sehingga warna kuning turun. Kemudian ia melakukan 6 kasus silang secara berurutan. Jika seseorang mengembalikan sesuatu selain null maka kembali ke kasus pertama.
Setelah keempat sisi diselesaikan, fungsi mengembalikan algoritma. Jika semua kasus diuji tanpa hasil, atau setelah 4 loop, fungsi akan mengembalikan NULL.

f2l.c dan f2l.h

Idenya sama dengan cross.c, hanya saja jauh lebih besar. 3600 baris kode untuk menyelesaikan semua kasus.

f2lCase1() hingga 11

11 kasus ini terdiri dari segala cara untuk mengorientasikan sudut, dan beberapa kombinasi sudut dan tepi.
Untuk menghemat waktu dan garis, sebagian besar fungsi tidak sepenuhnya menyelesaikan kombinasi sudut/tepi, namun membawanya ke keadaan terpendek yang diketahui dan memanggil fungsi yang benar.
Angka 1 sampai 11 adalah urutan penulisannya, tidak selalu urutan penulisannya.

pecahkan_f2l()

Solve_f2l pertama-tama memverifikasi bahwa persilangan telah diselesaikan. Jika tidak, ia mengembalikan nol.
Setelah itu solve_f2l menelusuri kasus-kasus dalam urutan algoritma rata-rata terpendek hingga terpanjang, kembali ke 1 setelah suatu fungsi mengembalikan suatu algoritma. Jika semua kasus diuji tanpa keberhasilan, atau setelah 4 loop, fungsinya mengembalikan NULL.

lapisan terakhir.c dan lapisan terakhir.h

File yang paling saya banggakan. Tidak ada putaran raksasa, tidak ada pohon keputusan. Hanya matematika cerdas dan tabel pencarian.

struct oll, dan pll

Oll dan pll adalah dua struct yang dimaksudkan untuk menyimpan OLL dan PLL. Mereka menyimpan nama, pola yang saya gunakan untuk mengenalinya, dan algoritma untuk menyelesaikannya.
Pada malam tanpa tidur saya menyadari bahwa saya dapat mengenali PLL hanya dengan menggunakan warna lingkar luar, dan OLL hanya dengan 12 boolean yang berarti kuning, atau bukan kuning.

load_olls() dan load_plls()

Load_olls() dan load_plls() memuat nama, pola, dan algoritme dari file CSV. Ini mengalami beberapa pengulangan.
Saya pertama kali memulai dengan getline() untuk mendapatkan setiap baris file CSV, dan membagi string menjadi 24, karakter dan 36 karakter, mengisi nama dengan spasi.
Ini tidak bagus jadi saya mulai mencari koma dan memisahkannya di sana.
Akhirnya seseorang di perselisihan mengarahkan saya ke sscanf() memungkinkan saya dengan mudah dan rapi membagi setiap string.
Saya juga beralih ke fgets() untuk membuat saluran lebih kompatibel.
Baris yang dimulai dengan # ditolak karena merupakan komentar. Garis yang polanya tidak murni numerik dikenali menggunakan fungsi pembantu yang disebut isNumber() atau isBinary() dan ditolak, dan saat menulis bagian ini saya menambahkan tes untuk melihat apakah nama, pola, dan algoritme memiliki panjang yang tepat untuk berhenti membaca dan menulis di luar batas.
Dalam ruang array olls dan plls untuk nama dan algoritma dibuat menggunakan malloc dan informasinya disalin menggunakan strncpy. Polanya diubah menjadi array 12 int atau boolean.

temukan_oll() dan temukan_pll()

Find_pll() adalah kebanggaan dan kegembiraan saya. Itu adalah algoritma pertama yang saya tulis untuk menyelesaikan kubus (sebelum salib dan f2l), dan itu datang kepada saya dalam mimpi. Sebuah cara untuk memeriksa pola oll untuk kombinasi warna apa pun dengan beberapa perhitungan sederhana. Saya benar-benar bangun dan menulis int case[12] containing the outer ring. if (front[0] == (front[1]-(case[0]-case[1])%4)) . Keesokan harinya saya menyederhanakannya menjadi (faces[0][0] == (faces[0][1] - (plls[i].pattern[0] - plls[i].pattern[1])) % 4) (kali 12). Kemudian (faces[j][0] - faces[j][1]) % 4 == (plls[i].pattern[0] - plls[i].pattern[1]) % 4 dan akhirnya setelah banyak iterasi Saya berakhir dengan mod((cube[(j + i / 3) % 4][i % 3] + dif[j]), 4) memungkinkan saya untuk menyandikan pola lapisan atas kubus menggunakan 12 int array, untuk memudahkan perbandingan dengan semua nilai yang diketahui.
Saya bisa saja menyandikan polanya sebagai int 4 byte, tetapi saya memutuskan untuk tidak melakukannya karena menurut saya lebih baik membuat polanya mudah dipahami daripada menyimpan 44 byte (total 3408 kb untuk pola)
Terakhir, fungsi mengembalikan pair_int_int yang berisi orientasi lapisan, dan OLL atau PLL yang benar. Atau dua angka negatif jika tidak ditemukan apa pun.

solve_oll() dan solve_pll()

Fungsi solve_oll() dan solve_pll() relatif sederhana. Mereka memanggil find_oll atau pll untuk mendapatkan indeks dan orientasi yang tepat (jumlah y gerakan). Kemudian fungsinya memutar kubus menggunakan gerakan y, menjalankan algoritma OLL atau PLL yang tepat, dan dalam kasus solve_pll() memutar lapisan U untuk akhirnya menyelesaikan kubus. Fungsi mengembalikan algoritma yang digunakan untuk menyelesaikan kubus dalam notasi kubus standar.

pembersihan_lapisan_terakhir()

Membebaskan memori yang digunakan untuk menyimpan semua OLL dan PLL.

utils.c dan utils.h

Beberapa fungsi untuk membuat hidup saya sedikit lebih mudah.

mod()

Karena % normal tidak berfungsi dengan angka negatif, ini adalah "versi saya sendiri" yang berfungsi. Dengan khusus terima kasih kepada perselisihan cs50.

make_pair_int_int()

Untuk beberapa fungsi saya ingin mengembalikan lebih dari satu variabel. Yang ini didasarkan pada pasangan C++ dan make_pair(). Itu membuat struct dengan dua int: pertama dan kedua. Dalam hal ini digunakan untuk mengembalikan nomor oll/pll dan gerakan U atau y sebelumnya.

siklus()

Sebuah fungsi yang memutar 4 angka. Pada dasarnya merupakan langkah maju dari swap. Digunakan di cube.c untuk memutar tepi dan sudut gerakan kubus. Ada salinan langkah itu di cube.js

menambahkan()

Fungsi yang menambahkan string ke string lain, mengalokasikan ulang jika perlu. Digunakan di mana saja di aplikasi ini.

isNumber() dan isBinary()

Memeriksa apakah string hanya berisi angka, atau hanya nol dan satu. Saat ini hanya digunakan untuk memuat OLL dan PLL.

solver_library.c dan cubesolver.h

Saya pertama kali menulis solver.c sebagai antarmuka untuk pemecah kubus saya, tetapi dengan cepat memutuskan bahwa saya menginginkan UI grafis, yang belum siap saya lakukan di C murni.
Itu sebabnya saya mulai membuat cubesolver saya menjadi perpustakaan untuk digunakan dengan apa pun yang saya inginkan.

menyelesaikan()

Gabungkan semuanya untuk memecahkan kubus. Dibutuhkan sebuah kubus dan memvalidasinya. Kemudian upaya untuk memecahkan salib. Jika gagal, ia mengembalikan kesalahan, jika tidak, ia akan menyimpan hasilnya. Kemudian menyelesaikan persilangan atau mengembalikan kesalahan. Ini kemudian memecahkan OLL (atau pengembalian) dan PLL. Akhirnya ia mengembalikan string yang berisi solusi lengkap.

pecahkan_perebutan()

Antarmuka untuk penyelesaian. Menghasilkan kubus dari perebutan yang dimasukkan dan meneruskannya ke solve()

pengaturan()

Hanya untuk membuat hidup semua orang sedikit lebih mudah. Mengambil jalur, dan memuat olls dan plls dari jalur itu. Mengembalikan nilai benar jika berhasil, membersihkan dirinya sendiri, dan mengembalikan nilai salah jika tidak.

toko_string_pointer()

Karena sulit untuk mengosongkan memori dari Python, saya memutuskan untuk melakukannya dari C. Saya memiliki versi "Aman" dari setiap fungsi yang mungkin ingin Anda gunakan dari luar C. Ini menyimpan pointer yang dihasilkan yang perlu dibebaskan ke array global untuk membebaskan semuanya sekaligus.

string_bebas()

Bebaskan semua string yang disimpan

solve_safe(), solve_scramble_safe(), solve_cross_safe(), solve_f2l_safe(), solve_oll_safe() dan solve_pll_safe()

Beberapa fungsi mengembalikan string, yang pada akhirnya harus dibebaskan. Fungsi-fungsi ini menyimpan pointer ke string ini untuk dihapus nanti.

pemecah.c

Untuk pengujian, dan mereka yang lebih baik menggunakan keyboard dibandingkan dengan mouse, antarmuka terminal.
Itu mengalami beberapa kali penulisan ulang, akhirnya ditulis ulang saat menulis readme ini untuk bekerja dengan solver_library alih-alih sendiri.

utama()

Ia melakukan segalanya! Ini memuat OLL dan PLL berdasarkan input default atau pengguna. Kemudian menghasilkan kubus berdasarkan baris perintah atau input pengguna, dan akhirnya menyelesaikan kubus tersebut langkah demi langkah, mencetak kubus tersebut sepanjang prosesnya.

dapatkanDir()

Mendapatkan direktori dari jalur file tertentu (mis. argv[0]). Ditulis untuk bekerja dengan OS berbasis Windows dan Unix.

warna_huruf_ke_angka()

Mengubah huruf berwarna menjadi int yang sesuai. Di python saya hanya menggunakan kamus. Jauh lebih mudah.

warna_wajah_dari_input()

Tanyakan kepada pengguna sembilan warna wajah kubus rubik, dan letakkan di atas kubus.

warna_kubus_interaktif()

Antarmuka interaktif langkah demi langkah untuk memasukkan warna ke dalam kubus.

teks bantuan()

Mencetak tes bantuan.

penggunaan()

Mencetak penggunaannya.

tes

tes acak.c

Aplikasi singkat sederhana untuk pengujian bug. Menghasilkan banyak pengacakan dan menyelesaikannya. Mencetak perebutan pertama yang gagal dan berhenti.
Saya menggunakan ini untuk menemukan satu kesalahan ketik. Segala sesuatu yang lain saya lakukan secara manual.

periksa Terpecahkan ()

Menggunakan memcmp untuk membandingkan kubus yang dimuntahkan oleh algoritma penyelesaian dengan salah satu dari 4 kubus yang diselesaikan (satu per orientasi).
Memperdagangkan sedikit memori untuk kecepatan.

menghasilkan_scramble()

Menghasilkan pengacakan acak untuk kubus rubik. Dengan buruk. Tidak melindungi terhadap gerakan ganda dan gerakan mundur. Namun alangkah baiknya jika perebutannya cukup lama.

utama()

Memuat OLL dan PLL dari input pengguna. Memecahkan kubus sebanyak yang diinginkan pengguna, hingga gagal.

data

olls.csv

Berisi daftar 58 kasus OLL (termasuk yang terpecahkan) untuk digunakan dengan perpustakaan C saya
Algoritma dari ingatan saya sendiri, dan dari https://www.speedsolving.com/wiki/index.php/OLL

tolong.csv

Berisi daftar semua 22 kasus PLL (termasuk yang diselesaikan) untuk digunakan dengan perpustakaan C saya
Algoritma dari ingatan saya sendiri, dan dari https://www.speedsolving.com/wiki/index.php/PLL

pola.csv

Berisi beberapa pola untuk mengacak kubus dengan cara yang cantik. Sebagian besar digunakan untuk menguji javascript saya, tetapi merupakan fitur yang bagus untuk pengguna.

error.txt

Mudah-mudahan tidak mengandung apa pun, tetapi dimaksudkan untuk menyimpan segala kesalahan dalam menyelesaikan kubus.

./

app.py

Jembatan antara kode C dan javascript saya. Itu memuat perpustakaan C, dan menginisialisasi fungsi yang saya butuhkan dengan argtypes dan jika perlu mengetik ulang. Menggunakan numpy untuk mengonversi dari tipe python ke ctypes.

dekomposisi()

Sebuah fungsi yang saya "pinjam" dari stackoverflow. Dibutuhkan aliran input dan output setiap baris hingga #

langkah-langkah()

Pemecah sebenarnya. Dibutuhkan kubus acak dan menyelesaikannya langkah demi langkah, mengembalikan langkah-langkah tersebut sebagai array kamus (berisi array dengan algoritma). Jika ada pengecualian, ia menyimpan pola di data/errors.txt

antarmuka pemecah()

Hanya digunakan untuk pengujian. Mengambil algoritma pengacakan dari GET, menyelesaikannya menggunakan getsteps() dan meneruskannya ke templat pemecah.

pemecahJSON()

Mengambil pola dan mengacak dari GET atau POST, menyelesaikannya menggunakan getsteps dan mengembalikannya sebagai JSON.

validatorJSON()

Mengambil pola dari GET atau POST dan menyelesaikan kubus, tidak peduli dengan solusi sebenarnya, tetapi memeriksa apakah dan di mana solusi tersebut gagal. Mengembalikan 0 untuk keberhasilan atau nomor kesalahan.

kubus()

Menampilkan templat cube.html: UI sebenarnya. Meskipun demikian, ia juga mengambil pola dari data/patterns.csv untuk diberikan ke templat, menggunakan dictreader dan decomment untuk menghapus komentar saya.

favicon()

Melewati favicon ke browser untuk simbol kubus yang bagus.

pembersihan()

Membebaskan semua memori dari kode C saya: PLL dan string. Terdaftar menggunakan atexit untuk dijalankan saat keluar

makefile

Semua perintah untuk mengkompilasi kode C saya di Linux atau OS X. Meskipun perpustakaan saya dapat digunakan sebagai perpustakaan, saya memutuskan untuk menggunakan semua file untuk dikompilasi sehingga saya hanya dapat memberikan satu file yang dapat dieksekusi.

persyaratan.txt

Berisi dua perpustakaan yang saya gunakan yang perlu diinstal secara terpisah. Hanya labu dan numpy. Tidak ada yang istimewa.

templat

solver.html

Meminta perebutan, meneruskannya ke app.py untuk menyelesaikan dan mencetak solusinya. Hanya digunakan untuk pengujian cepat.

kubus.html

Berisi banyak div kosong untuk diisi dengan kode javascript saya, dan dibentuk oleh css. Berisi 3 gambar untuk kontrol pemutaran, formulir untuk memasukkan pengacakan, dan penjelasan singkat.
Akhirnya memuat javascript karena tidak ada artinya tanpa dom. Tidak terlalu cantik, tapi sangat fungsional.

statis

Kecuali src berisi kode paling aktual. Beberapa CSS untuk membuat semuanya terlihat dapat digunakan, dan javascript untuk membuatnya benar-benar dapat digunakan. Dan beberapa gambar untuk diklik.

kubus.css

Mengubah tautan div acak menjadi sesuatu yang dapat Anda lihat.
Menggunakan grid CSS secara default, dan lebih sedikit cara default.
Saya menggunakan wadah luar untuk menempatkan kontrol di sebelah kiri, animasi pemecah di kanan atas, dan solusi di kanan bawah.
Dengan menggunakan pemosisian absolut, saya menempatkan kontrol pemutaran dan alg saat ini di atas animasi.
Segala sesuatu yang lain cukup default kecuali colorpicker. Jika Anda melihat kode html Anda hanya melihat sebuah div berisi 6 div, masing-masing berisi 9 div. Dengan menggunakan grid saya membentuk 6 div "wajah" agar terlihat seperti kubus yang tidak dilipat, setiap wajah berisi grid 9 kotak. Hal ini memungkinkan saya membuat variabel ukuran sementara bentuknya tetap sama, tanpa perlu menggunakan gambar.
Saya juga menghabiskan satu atau 2 minggu untuk membuat tampilan seluler, karena ukuran teksnya sepertinya bervariasi. Saya menghubungi perselisihan, facebook, dan bahkan stackoverflow. Akhirnya saya menemukan baris html di stackoverflow: yang menyelesaikan semuanya dalam satu baris.

kubus.js

Membawa algoritma saya ke pengguna. Berdasarkan three.js
Ini adalah pertama kalinya saya benar-benar menulis javascript. Kelihatannya tidak cantik, mungkin melanggar semua aturan, tapi berhasil.

Saya menulis ulang file ini beberapa kali. Iteratif pertama, sebelum saya mulai mengunggah ke github, lalu fungsional, dan akhirnya semacam berorientasi objek
Pertama saya mendeklarasikan semua variabel yang perlu digunakan oleh lebih dari satu fungsi: Bahan dan geometri untuk objek three.js, array untuk menyimpan objek, sumbu rotasi, dan banyak lagi.
Ada juga kamus raksasa yang berisi variabel-variabel yang diperlukan untuk setiap pergerakan kubus legal: Kubik yang akan diputar atau ditukar, sumbu dan derajat rotasi, dan apa yang harus ditampilkan. Ini semua bisa muat dalam 72 baris, tetapi style50 menginginkan satu variabel per baris, menjadikannya 649 baris.

konstruktor()

Mengambil adegan dan menyimpan referensi, menghasilkan kubus, garis luar dan bidang dalam satu lingkaran, mengatur posisi kubus dan garis luar dalam satu lingkaran, dan bidang secara manual.

siklus_rotasi()

Fungsi pembantu. Siklus rotasi 4 kubus a > b > c > d > a menggunakan temp cubie.

swap_rotations()

Fungsi pembantu. Menukar rotasi 2 kubus menggunakan temp cubie.

setel ulang_kubus()

Setel ulang kubus ke posisi defaultnya dan setel ulang div solusi. Ini memerlukan lebih banyak langkah daripada yang Anda kira. Pertama kita perlu mengatur ulang semua animasi, selesaikan. Atur ulang semua gerakan masa depan dan masa lalu, dan terakhir atur ulang rotasi kubus.

sedang_bergerak()

Mengembalikan nilai benar atau salah bergantung pada apakah kubus bergerak.

lakukan_pindah()

Menyiapkan animasi untuk pergerakan pada kubus.
Fungsi ini awalnya terdiri dari 160 baris pernyataan if/else, tetapi kemudian saya menulis ulang untuk mendapatkan kubus dan perpindahan dari kamus raksasa. Ini membuat fungsi ini dan fungsi selanjutnya lebih mudah dibaca, sehingga jika saya menulis versi 4x4 atau 5x5 saya hanya perlu mengganti kamus.

selesai_bergerak()

Menyelesaikan animasi, dan benar-benar menggerakkan (memutar) kubus.
Karena kubus tidak benar-benar bergerak, ide dasarnya adalah menyalin rotasi kubus yang pada kubus nyata akan berpindah ke tempatnya, dan kemudian memutar semuanya.
Fungsi ini awalnya merupakan 375 baris monstrositas dari pernyataan if/else berikutnya. Itu kemudian ditulis ulang agar berfungsi dengan kamus gerakan.

langkah_berikutnya()

Melakukan langkah berikutnya dalam daftar langkah, atau algoritma berikutnya dalam daftar langkah, dan menampilkan algoritma saat ini di layar.

sebelumnya_pindah()

Apakah langkah sebelumnya dalam daftar langkahnya terbalik, atau algoritma sebelumnya dalam daftar langkah

terapkan_pola()

Menerapkan warna dari pemilih warna (atau susunan wajah sebenarnya) ke kubus dengan memutar setiap kubus. Berisi beberapa fungsinya sendiri Setiap cubie memiliki lini tersendiri dengan pengubah manual. Bagi saya itu terlalu acak untuk diotomatisasi. Tetapi jika Anda ingin mencobanya, jadilah tamu saya.

warna_berlawanan()

Mengubah warna hijau menjadi biru, merah menjadi oranye, putih menjadi kuning, dan sebaliknya. Sekarang saya memikirkannya, ini bisa saja sebuah dict, tetapi satu baris matematika dan 3 if juga bisa digunakan.

terapkan_warna()

Memutar kubus berdasarkan warna depan dan kiri, atau warna atas. Pada dasarnya banyak pernyataan if dengan gerakan hardcode, tapi itu sudah cukup di sini.

jalankan_alg()