Cube Solver

루빅스 큐브 솔버

비디오 데모: https://www.youtube.com/watch?v=A6JyElruhwE

데모: http://d4m4s74.pythonanywhere.com/

설명:

CS50에 대한 나의 마지막 프로젝트는 "인간 방식"의 루빅스 큐브 솔버입니다.
이는 입력된 루빅스 큐브가 Cross, F2L, OLL 및 PLL의 명확한 단계를 통해 인간이 사용할 수 있는 방법(CFOP)을 사용하여 해결된다는 것을 의미합니다.
최종 제품은 쉘 애플리케이션, 다른 프로젝트에서 사용하기 위한 C 라이브러리, Flask, HTML, CSS 및 Javascript로 작성된 웹 인터페이스로 구성됩니다.

이전에 C++로 스도쿠 해결사를 만들었고 큐브가 한 단계 더 발전했기 때문에 루빅스 큐브 해결사를 만들기로 결정했습니다.
2D 평면 대신 가장자리와 모서리가 있는 반 3D 평면이 있습니다.
AI 해결사가 완료되었고 AI 쓰기 능력에 대해 확신이 없기 때문에 프로그램이 내가 하는 방식으로 큐브를 해결하도록 결정했습니다.
크로스, F2L, OLL 및 PLL

사용방법

솔버

리눅스

bin/solver 실행 파일을 다운로드하거나 make solver 사용하여 소스에서 빌드하세요.

OS X

이 저장소에서 파일을 다운로드하거나 복제하고 make solver 사용하여 빌드하세요.

윈도우

이 저장소를 사용하여 파일을 다운로드하거나 복제하고 Solver_library를 제외한 src의 모든 .c 파일을 컴파일하십시오.

모두

다음 명령 중 하나를 사용하여 솔버를 실행합니다.

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

알고리즘을 스크램블 알고리즘(예: U R2 FBR B2 R U2 L B2 RU' D' R2 FR' L B2 U2 F2 ) 또는 해당 면의 색상이 있는 면(예: wbwowrwgw gwgogrgyg rwrgrbryr bwbrbobyb owobogoyo ygyoyryby )으로 대체합니다.
가능한 색상은 Green, Red, Blue, Orange, White, Yellow의 첫 번째 문자입니다.
olls.txt 및 plls.txt 파일이 바이너리와 동일한 폴더에 없으면 -o 및 -p 또는 -d 옵션을 사용하여 파일을 가리킵니다.

 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"

큐브 이미지 없이 텍스트만 인쇄하려면 -t 옵션을 추가하세요.

웹 인터페이스

리눅스:

이 저장소에서 파일을 다운로드하거나 복제하세요.
pip를 사용하여 Flask와 Numpy를 설치합니다.

 python3 -m pip -r requirements.txt

flask run 명령을 사용하거나 python3 app.py 사용하여 웹 서버를 실행합니다.
솔버를 사용하려면 https://127.0.0.1:5000/으로 이동하세요.

OS X:

이 저장소에서 파일을 다운로드하거나 복제하세요.
bin/libcubesolver.so의 Linux 버전을 수동으로 제거하거나 make clean 사용하여 제거하고 make library 사용하여 다시 컴파일하십시오.
pip를 사용하여 Flask와 Numpy를 설치합니다.

 python3 -m pip -r requirements.txt

flask run 명령을 사용하거나 python3 app.py 사용하여 웹 서버를 실행합니다.
솔버를 사용하려면 https://127.0.0.1:5000/으로 이동하세요.

윈도우:

이 저장소에서 파일을 다운로드하거나 복제하세요. bin/libcubesolver.so의 Linux 버전을 수동으로 제거합니다.
Solver.c를 제외한 src의 모든 .c 파일을 bin/libcubesolver.so로 컴파일합니다. 또는 다른 이름을 사용하는 경우 이를 반영하도록 app.py의 19행을 변경하세요.
pip를 사용하여 Flask와 Numpy를 설치합니다.

 python3 -m pip -r requirements.txt

flask run 명령을 사용하거나 python3 app.py 사용하여 웹 서버를 실행합니다.
솔버를 사용하려면 https://127.0.0.1:5000/으로 이동하세요.

솔버 라이브러리

C 또는 C++와 함께 사용하기 위해 설치

Solver.c를 제외한 src의 모든 파일을 libcubesolver.so, libcubesolver.dylib 또는 libcubesolver.dll로 컴파일하고 PC의 라이브러리가 저장되는 곳에 저장합니다.
Linux에서는 make library 사용할 수 있습니다.
libcubesolver.h를 src에서 PC의 헤더가 저장된 위치(예: /usr/include/)로 복사합니다.

C 또는 C++에서의 사용법

-lcubesolver 로 연결하거나 마치 .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 );

파이썬과의 사용법

각 함수의 기능을 보려면 C 버전을 참조하세요.
Python에서는 malloc된 메모리를 해제하기가 ​​어렵기 때문에 "안전한" 버전의 해결 함수를 사용하고 사용 후에는 free_strings()를 사용하세요.

 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 ()

구조

CS50에서는 모든 파일의 기능과 그 내용에 대해 설명해달라고 합니다. 따라서 이 추가 정보는 내 파일 3개를 제외한 모든 파일보다 깁니다.

 ├── app.py  
├── 빈  
│ ├── libcubesolver.so  
│ └── 솔버  
├── 데이터  
│ ├── 오류.txt  
│ ├── olls.csv  
│ ├── 패턴.csv  
│ └── plls.csv  
├── 메이크파일  
├── 읽어보세요.md  
├── 요구사항.txt  
├── src  
│ ├── cross.c  
│ ├── 크로스.h  
│ ├── 큐브.c  
│ ├── 큐브.h  
│ ├── Cubesolver.h  
│ ├── f2l.c  
│ ├── f2l.h  
│ ├── lastlayer.c  
│ ├── lastlayer.h  
│ ├── 솔버.c  
│ ├──solver_library.c    
│ ├── utils.c  
│ └── utils.h  
├── 테스트  
│ ├── Randomtests.c  
│ └── 무작위 테스트   
├── 정적  
│ ├── 큐브.css  
│ ├── 큐브.js  
│ ├── Cubeinterface.js  
│ ├── favicon.ico  
│ ├── next.png  
│ ├── 일시정지.png  
│ ├── play.png  
│ └── prev.png  
├── 템플릿  
│ ├── 큐브.html  
│ └── 솔버.html  

소스

큐브.c와 큐브.h

Cube.c와 Cube.h에는 메모리에서 루빅스 큐브를 제어하는 ​​모든 코드가 포함되어 있습니다.

메모리에 있는 루빅스 큐브는 6 x 9 2D 배열입니다. 외부 배열에는 전면, 오른쪽, 후면, 왼쪽, 위, 아래의 6개 면이 포함되어 있습니다.
위아래 면이 항상 똑같기 때문에 이 순서를 선택했습니다. 그래서 하드코딩할 수 있지만 면끼리만 맞으면 됩니다. 이는 모듈러스와 결합된 간단한 플러스 또는 마이너스를 사용하여 테스트를 변환하고 모든 측면으로 이동할 수 있음을 의미합니다. 0부터 5까지의 숫자로 저장되는 색상도 마찬가지입니다. 0은 전면 색상, 1은 오른쪽 색상입니다.
나는 먼저 내가 사용하는 색상 순서를 선택했습니다. 앞쪽은 빨간색, 위쪽은 노란색, 오른쪽은 녹색입니다. 그러나 나중에 Python 코드와 인터페이스를 작성할 때 앞쪽은 "공식" 녹색, 위쪽은 흰색으로 전환하여 아래쪽이 흰색이 되도록 사용자가 입력한 큐브를 회전할 필요가 없습니다.

color_cube()

먼저 color_cube() 함수를 만들었습니다. 6개의 스트링을 사용하여 원하는 패턴을 큐브에 적용합니다.
간단한 char 수학을 사용하여 char '0', '1' 등을 int로 변경하고 주어진 배열에 저장합니다.
나는 이것을 하나의 라이너로 한 번 또는 두 번만 사용하여 한 줄에 해결된 큐브를 설정합니다. 왜냐하면 사용자 입력을 컴퓨터가 이해하는 것으로 변환할 때 먼저 문자열로 변환하는 대신 int를 개별적으로 입력하는 것이 나을 수 있기 때문입니다.

print_cube()

Print_cube()는 제공된 큐브를 터미널에 출력합니다. 이는 디버깅할 때와 터미널 애플리케이션에 많이 사용됩니다. 나는 폭발한 루빅스 큐브 모양으로 0부터 5까지의 숫자만 출력하는 것부터 시작했습니다.

    444
    444
    444

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

    555
    555
    555

이를 자동화하려면 더 많은 코드 줄이 필요하기 때문에 각각 최대 12개의 변수를 포함하는 9개의 인쇄 문을 사용합니다.
나중에 나는 e[42m 과 같은 쉘 코드를 추가하여 이 숫자에 배경색을 부여할 수 있다는 것을 알게 되었습니다. 이를 추가하면 인쇄당 28개의 변수가 제공됩니다.
마지막으로 쉘 코드가 들어 있는 배열에 색상에 대한 문자나 숫자를 넣어서 다시 12로 가져오는 방법을 생각했습니다. 안타깝게도 Windows에서는 이러한 유형의 쉘 코드를 지원하지 않기 때문에 숫자만 계속 사용해야 했습니다. 나중에 편지.

move_cube()

Move_cube()는 실제로 큐브를 변경하는 첫 번째 함수입니다. 이는 요청된 횟수만큼 요청된 이동을 수행하는 재귀 함수입니다. 0부터 8까지 번호가 매겨진 9개의 가능한 이동이 있습니다. 기본 앞, 오른쪽, 뒤 등. 그러나 중간, 적도 및 서 레이어도 있습니다. Cycle이라는 utils.c에 작성한 도우미 함수를 사용하여 시계 방향 이동에 해당하는 각 면의 각 사각형 값을 전환하고 필요한 경우 반복합니다.

run_algorithm()

이동은 대개 저절로 발생하지 않기 때문에 다음으로 run_algorithm()을 작성했습니다. 이 함수는 move_cube()를 사용하여 표준 큐브 표기법으로 제공된 큐브에서 알고리즘을 실행합니다. 이를 통해 한 번에(또는 실제로는 순서대로) 여러 동작을 수행할 수 있고 x, y 및 z와 같은 2개 또는 심지어 3개의 레이어에 영향을 미치는 동작을 수행할 수 있습니다.

검증()

마지막으로 유효성을 검사()합니다. 사용자가 이상한 것을 입력하지 않는다고 믿어서는 안 되기 때문에 Python 인터페이스를 작성하는 동안 이 함수를 추가했습니다.
이 함수는 루빅스 큐브를 풀 수 있는지 여부를 확인하지 않습니다. 색상이 올바른지 확인합니다. 예를 들어 큐비 하나에 흰색 스티커와 노란색 스티커를 모두 가질 수는 없습니다. 시계 방향으로 녹색, 흰색, 빨간색 스티커를 순서대로 배치하는 것이 가능하지만 그 반대 방향은 불가능합니다.
이를 위해 Tideman의 잠긴 배열 아이디어를 부분적으로 복사하여 모서리에 2D 부울 배열을 사용하고 가장자리에 3D 부울 배열을 사용하여 2~3가지 색상의 조합이 가능한지 확인했습니다. 이 코드는 여러 번 반복되었습니다. 먼저 각 가장자리와 모서리를 개별적으로 확인하고 나중에 몇 개의 for 루프를 사용합니다.

cross.c와 cross.h

Cross.c에는 큐브의 십자가를 푸는 데 필요한 모든 코드가 포함되어 있습니다. 큐브를 풀기 위해 "인간적 방법"(CFOP)을 사용하기 때문에 거대한 의사 결정 트리를 사용해야 하는 경우도 있습니다.
나는 마지막 순간에 이 파일 전체를 거의 다시 작성했기 때문에 모든 단계에서 가장자리를 정렬할 필요가 없습니다.

findZero()

아래쪽 레이어에서 황록색 가장자리가 있는 위치를 찾습니다. 아직 가장자리가 없는 경우 있을 것입니다. 이렇게 하면 실제 0 대신 "상대 0"에 정렬할 수 있으므로 더 적은 단계로 다른 가장자리를 정렬하는 것이 더 쉬워집니다.

crossCase1()부터 6까지

이 6가지 경우는 가장자리의 방향을 지정할 수 있는 모든 방식입니다. 아래를 가리키고, 위쪽을 가리키고, 위쪽 및 아래쪽 레이어에서 가리키고, E 레이어에서 왼쪽을 가리키고 오른쪽을 가리킵니다.
이 함수는 기본적으로 0부터 3까지의 순서로 면을 스캔하여 십자가에 속한 조각을 찾고, 제자리에 회전시킨 다음, 제가append()라고 부르는 도우미 함수를 사용하여 char 배열에 움직임을 저장합니다.

solv_cross()

Solve_cross는 먼저 노란색이 아래로 향하도록 큐브의 방향을 지정합니다. 그런 다음 6개의 교차 사례를 순서대로 수행합니다. null이 아닌 다른 것을 반환하면 첫 번째 경우로 돌아갑니다.
4개의 모서리가 모두 해결되면 함수는 알고리즘을 반환합니다. 모든 사례가 성공하지 않고 테스트되거나 4번의 루프 이후에 테스트되면 함수는 NULL을 반환합니다.

f2l.c 및 f2l.h

훨씬 더 크다는 점을 제외하면 cross.c와 동일한 아이디어입니다. 모든 사건을 해결하기 위한 3600줄의 코드.

f2lCase1()부터 11까지

이 11가지 사례는 모서리의 방향을 지정할 수 있는 모든 방법과 모서리와 가장자리의 일부 조합으로 구성됩니다.
시간과 라인을 절약하기 위해 대부분의 함수는 모서리/모서리 조합을 완전히 해결하지 못하지만 알려진 가장 짧은 상태로 가져와 올바른 함수를 호출합니다.
1부터 11까지의 숫자는 쓰여진 순서이며 항상 실행되는 순서는 아닙니다.

solv_f2l()

Solve_f2l은 먼저 십자가가 해결되었는지 확인합니다. 그렇지 않으면 null을 반환합니다.
그 후,solve_f2l은 가장 짧은 평균 알고리즘부터 가장 긴 알고리즘 순으로 사례를 거치며, 함수가 알고리즘을 반환하면 1로 돌아갑니다. 모든 사례가 성공하지 않고 테스트되거나 4번의 루프 이후에 테스트되면 함수는 NULL을 반환합니다.

lastlayer.c 및 lastlayer.h

내가 가장 자랑스러워하는 파일. 거대한 루프도 없고 의사결정 트리도 없습니다. 스마트한 수학 및 조회 테이블만 있으면 됩니다.

구조체 oll 및 pll

Oll과 pll은 OLL과 PLL을 저장하기 위한 두 개의 구조체입니다. 이름, 인식하는 데 사용하는 패턴, 문제를 해결하는 알고리즘이 저장됩니다.
잠 못 이루는 밤에 나는 외부 링의 색상만 사용하여 PLL을 인식할 수 있다는 것을 알았고 OLL은 노란색 또는 노란색이 아님을 의미하는 12개의 부울만으로 인식할 수 있었습니다.

load_olls() 및 load_plls()

Load_olls() 및 load_plls()는 CSV 파일에서 이름, 패턴 및 알고리즘을 로드합니다. 이것은 몇 가지 반복을 거쳤습니다.
먼저 getline()으로 시작하여 CSV 파일의 각 줄을 가져오고 문자열을 24자, 36자로 나누고 이름을 공백으로 채웠습니다.
이건 예쁘지 않아서 쉼표를 찾아 거기에서 내용을 나누기 시작했습니다.
마침내 디스코드의 누군가가 나에게 각 문자열을 쉽고 깔끔하게 분할할 수 있도록 sscanf()를 지시했습니다.
또한 라인의 상호 호환성을 높이기 위해 fgets()로 전환했습니다.
#으로 시작하는 줄은 주석이므로 거부됩니다. 패턴이 순전히 숫자가 아닌 줄은 isNumber() 또는 isBinary()라는 도우미 함수를 사용하여 인식되고 거부됩니다. 이 섹션을 작성하는 동안 이름, 패턴 및 알고리즘의 길이가 올바른지 확인하는 테스트를 추가했습니다. 범위를 벗어난 읽기 및 쓰기를 중지합니다.
olls 및 plls 배열에서 이름과 알고리즘을 위한 공간은 malloc을 사용하여 생성되고 정보는 strncpy를 사용하여 복사됩니다. 패턴은 12개의 정수 또는 부울 배열로 변환됩니다.

find_oll() 및 find_pll()

Find_pll()은 나의 자부심이자 기쁨입니다. 그것은 (십자가와 f2l 이전에) 큐브를 풀기 위해 제가 작성한 첫 번째 알고리즘이었는데, 꿈에서 떠올랐습니다. 몇 가지 간단한 수학으로 색상 조합에 대한 올 패턴을 확인하는 방법입니다. 나는 말 그대로 잠에서 깨어나 int case[12] containing the outer ring. if (front[0] == (front[1]-(case[0]-case[1])%4)) . 다음날 나는 그것을 (faces[0][0] == (faces[0][1] - (plls[i].pattern[0] - plls[i].pattern[1])) % 4) 로 단순화했습니다. (faces[0][0] == (faces[0][1] - (plls[i].pattern[0] - plls[i].pattern[1])) % 4) (12회). 그런 다음 (faces[j][0] - faces[j][1]) % 4 == (plls[i].pattern[0] - plls[i].pattern[1]) % 4 그리고 마지막으로 많은 반복 후에 나는 mod((cube[(j + i / 3) % 4][i % 3] + dif[j]), 4) 를 사용하여 큐브의 최상위 레이어 패턴을 인코딩할 수 있게 되었습니다. 알려진 모든 값과 쉽게 비교할 수 있는 12 int 배열.
패턴을 4바이트 int로 인코딩할 수도 있었지만 44바이트(패턴의 경우 총 3408kb)를 저장하는 것보다 패턴을 이해하기 쉽게 만드는 것이 더 낫다고 생각했기 때문에 인코딩하지 않기로 결정했습니다.
마지막으로 함수는 레이어의 방향과 올바른 OLL 또는 PLL을 포함하는 pair_int_int를 반환합니다. 또는 아무것도 발견되지 않으면 두 개의 음수입니다.

solv_oll() 및solv_pll()

solv_oll() 및solv_pll() 함수는 비교적 간단합니다. 올바른 인덱스와 방향(y 이동량)을 얻기 위해 find_oll 또는 pll을 호출합니다. 그런 다음 함수는 y 이동을 사용하여 큐브를 회전하고 올바른 OLL 또는 PLL 알고리즘을 실행하며,solve_pll()의 경우 U 레이어를 회전하여 최종적으로 큐브를 해결합니다. 함수는 표준 큐브 표기법으로 큐브를 푸는 데 사용되는 알고리즘을 반환합니다.

cleanup_last_layer()

모든 OLL 및 PLL을 저장하는 데 사용된 메모리를 해제합니다.

utils.c 및 utils.h

내 삶을 좀 더 쉽게 만들어주는 몇 가지 기능.

모드()

일반 %는 음수에서는 작동하지 않기 때문에 이것이 작동하는 "내 자신의 버전"입니다. cs50 discord에 특별히 감사드립니다.

make_pair_int_int()

일부 함수의 경우 둘 이상의 변수를 반환하고 싶습니다. 이것은 C++ 쌍 및 make_pair()를 기반으로 합니다. 첫 번째와 두 번째라는 두 개의 정수가 있는 구조체를 만듭니다. 이 경우 oll/pll 번호와 이전 U 또는 y 이동을 반환하는 데 사용됩니다.

주기()

4개의 숫자를 순환하는 함수입니다. 기본적으로 스왑보다 한 단계 더 발전했습니다. Cube.c에서 큐브 이동을 위한 가장자리와 모서리를 순환하는 데 사용됩니다. Cube.js에 해당 움직임의 복사본이 있습니다.

추가()

문자열을 다른 문자열에 추가하고 필요한 경우 재할당하는 함수입니다. 이 응용 프로그램의 모든 곳에서 사용됩니다.

isNumber() 및 isBinary()

문자열에 숫자만 포함되어 있는지, 아니면 0과 1만 포함되어 있는지 확인합니다. 현재는 OLL 및 PLL 로드에만 사용됩니다.

solver_library.c 및 Cubesolver.h

나는 처음에 큐브 솔버의 인터페이스로solver.c를 작성했지만 곧 그래픽 UI를 원하기로 결정했습니다. 순수 C에서는 이를 수행할 준비가 되어 있지 않습니다.
그래서 나는 내가 원하는 모든 것에 사용할 수 있도록 내 Cubesolvers를 라이브러리로 만들기 시작했습니다.

해결하다()

큐브를 해결하기 위해 모든 것을 하나로 묶습니다. 큐브를 가져와서 유효성을 검사합니다. 그런 다음 십자가를 해결하려고 시도합니다. 실패하면 오류를 반환하고, 그렇지 않으면 출력을 저장합니다. 그런 다음 십자형을 풀거나 오류를 반환합니다. 그런 다음 OLL(또는 반환)과 PLL을 해결합니다. 마지막으로 전체 솔루션이 포함된 문자열을 반환합니다.

해결_스크램블()

해결을 위한 인터페이스입니다. 입력된 스크램블에서 큐브를 생성하고 이를solv()에 전달합니다.

설정()

모든 사람의 삶을 조금 더 쉽게 만들기 위해서입니다. 경로를 선택하고 해당 경로에서 ol과 pll을 로드합니다. 작동하면 true를 반환하고, 자체적으로 정리하고, 그렇지 않으면 false를 반환합니다.

store_string_pointer()

Python에서 메모리를 해제하는 것은 어렵기 때문에 C에서 수행하기로 결정했습니다. C 외부에서 사용하려는 모든 함수의 "안전한" 버전이 있습니다. 이러한 버전은 전역 배열로 해제해야 하는 생성된 포인터를 저장합니다. 한 번에 해방시키기 위해.

free_strings()

저장된 모든 트링을 해제하세요.

solv_safe(),solv_scramble_safe(),solv_cross_safe(),solv_f2l_safe(),solv_oll_safe() 및solv_pll_safe()

여러 함수는 결국 해제해야 하는 문자열을 반환합니다. 이러한 함수는 나중에 삭제할 수 있도록 이러한 문자열에 대한 포인터를 저장합니다.

솔버.c

테스트를 위해 터미널 인터페이스인 마우스보다 키보드를 사용하는 것이 더 나은 사용자를 위한 것입니다.
여러 번 재작성되었으며, 이 Readme를 작성하는 동안 자체적으로가 아닌solver_library와 함께 작동하도록 최종적으로 재작성되었습니다.

기본()

그것은 모든 것을 다합니다! 기본 또는 사용자 입력을 기반으로 OLL 및 PLL을 로드합니다. 그런 다음 명령줄이나 사용자 입력을 기반으로 큐브를 생성하고 마지막으로 단계별로 큐브를 해결하여 큐브를 인쇄합니다.

getDir()

지정된 파일 경로(예: argv[0])에서 디렉터리를 가져옵니다. Windows 및 Unix 기반 OS 모두에서 작동하도록 작성되었습니다.

color_letter_to_number()

색상 문자를 해당 int로 변경합니다. 파이썬에서는 방금 사전을 사용했습니다. 훨씬 더 쉽습니다.

color_face_from_input()

사용자에게 루빅스 큐브 면의 9가지 색상을 묻고 이를 큐브 위에 올려 놓습니다.

color_cube_interactive()

큐브에 색상을 입력하기 위한 단계별 대화형 인터페이스입니다.

도움말 텍스트()

도움말 테스트를 인쇄합니다.

용법()

사용량을 인쇄합니다.

시험

무작위테스트.c

버그 테스트를 위한 간단하고 짧은 애플리케이션입니다. 많은 스크램블을 생성하고 해결합니다. 실패하고 중지되는 첫 번째 스크램블을 인쇄합니다.
나는 이것을 하나의 오타를 찾는 데 사용했습니다. 그 밖의 모든 작업은 내가 수동으로 수행했습니다.

해결됨()

memcmp를 사용하여 해결 알고리즘에 의해 생성된 큐브를 4개의 해결된 큐브(방향당 하나씩) 중 하나와 비교합니다.
속도를 위해 약간의 메모리를 교환합니다.

생성_스크램블()

루빅스 큐브에 대한 무작위 스크램블을 생성합니다. 심하게. 이중 이동 및 역방향 이동으로부터 보호하지 않습니다. 하지만 스크램블이 충분히 길면 충분합니다.

기본()

사용자 입력에서 OLL 및 PLL을 로드합니다. 실패할 때까지 사용자가 원하는 만큼 큐브를 해결합니다.

데이터

olls.csv

내 C 라이브러리와 함께 사용할 수 있는 모든 58개 OLL 사례(해결된 사례 포함) 목록이 포함되어 있습니다.
내 기억과 https://www.speedsolving.com/wiki/index.php/OLL의 알고리즘

plls.csv

내 C 라이브러리와 함께 사용할 수 있는 모든 22개 PLL 사례(해결된 사례 포함) 목록이 포함되어 있습니다.
내 기억과 https://www.speedsolving.com/wiki/index.php/PLL의 알고리즘

패턴.csv

큐브를 예쁜 방식으로 뒤섞기 위한 몇 가지 패턴이 포함되어 있습니다. 주로 내 자바스크립트를 테스트하는 데 사용되지만 사용자에게는 좋은 기능입니다.

오류.txt

아무것도 포함되어 있지 않기를 바라지만 큐브를 풀 때 발생하는 모든 오류를 저장하기 위한 것입니다.

./

app.py

내 C 코드와 자바스크립트 사이의 다리입니다. C 라이브러리를 로드하고 필요한 기능을 argtypes로 초기화하고 필요한 경우 다시 유형을 지정합니다. numpy를 사용하여 Python 유형을 ctypes로 변환합니다.

분해()

stackoverflow에서 "빌린" 함수입니다. 입력 스트림을 받아 최대 #까지 모든 라인을 출력합니다.

getstep()

실제 해결사. 스크램블된 큐브를 가져와 단계별로 해결하고 단계를 사전 배열(알고리즘이 포함된 배열 포함)로 반환합니다. 예외가 발생하면 data/errors.txt에 패턴을 저장합니다.

솔버인터페이스()

테스트용으로만 사용됩니다. GET에서 스크램블 알고리즘을 가져와서 getsteps()를 사용하여 해결하고 이를 솔버 템플릿에 전달합니다.

솔버JSON()

GET 또는 POST에서 패턴 및 스크램블을 가져와 getsteps를 사용하여 해결하고 JSON으로 반환합니다.

유효성 검사기JSON()

GET 또는 POST에서 패턴을 가져와 실제 솔루션에 신경 쓰지 않고 실패 여부와 위치를 확인하면서 큐브를 해결합니다. 성공하면 0을 반환하거나 오류 번호를 반환합니다.

입방체()

실제 UI인 Cube.html 템플릿을 표시합니다. 그렇게 하는 동안 data/patterns.csv의 패턴을 템플릿에 제공하고 dictreader 및 decomment를 사용하여 내 주석을 제거합니다.

파비콘()

멋진 큐브 기호를 위해 파비콘을 브라우저에 전달합니다.

대청소()

내 C 코드(PLL 및 문자열)에서 모든 메모리를 해제합니다. 종료 시 실행하기 위해 atexit를 사용하여 등록됨

메이크파일

Linux 또는 OS X에서 내 C 코드를 컴파일하기 위한 모든 명령. 내 라이브러리가 라이브러리로 사용될 수 있음에도 불구하고 나는 하나의 실행 파일만 제공할 수 있도록 모든 파일을 사용하여 컴파일하기로 결정했습니다.

요구사항.txt

별도로 설치해야 하는 두 개의 라이브러리가 포함되어 있습니다. 그냥 플라스크와 numpy. 특별한 것은 없습니다.

템플릿

솔버.html

스크램블을 요청하고 이를 app.py에 전달하여 해결하고 솔루션을 인쇄합니다. 빠른 테스트에만 사용됩니다.

큐브.html

내 자바스크립트 코드로 채워지고 CSS로 모양이 지정된 빈 div가 많이 포함되어 있습니다. 재생 제어를 위한 3개의 이미지, 스크램블 입력 양식 및 간단한 설명이 포함되어 있습니다.
DOM 없이는 아무 것도 아니기 때문에 마지막으로 자바스크립트를 로드합니다. 그다지 예쁘지는 않지만 매우 기능적입니다.

공전

src를 제외하면 가장 실제적인 코드가 포함되어 있습니다. 모든 것을 사용할 수 있게 만드는 일부 CSS와 실제로 사용할 수 있도록 만드는 자바스크립트입니다. 그리고 클릭할 이미지도 있습니다.

큐브.css

임의의 div 링크를 볼 수 있는 것으로 변경합니다.
CSS 그리드를 기본 방식과 덜 기본 방식으로 사용합니다.
저는 외부 컨테이너를 사용하여 왼쪽에 컨트롤을 배치하고, 솔버 애니메이션은 오른쪽 위에, 솔루션은 오른쪽 아래에 배치했습니다.
절대 위치 지정을 사용하여 애니메이션 위에 재생 컨트롤과 현재 정보를 배치했습니다.
색상 선택기를 제외한 다른 모든 것은 기본입니다. HTML 코드를 보면 각각 9개의 div를 포함하는 6개의 div가 포함된 div가 표시됩니다. 그리드를 사용하여 6개의 "얼굴" div를 펼쳐진 큐브처럼 보이게 만들었습니다. 각 면에는 9개의 정사각형 그리드가 포함되어 있습니다. 이를 통해 이미지를 사용할 필요 없이 모양은 동일하게 유지하면서 크기를 가변적으로 만들 수 있습니다.
모바일 뷰도 만드는데 1~2주 정도 걸렸는데, 텍스트 크기가 가변적인 것 같았거든요. 디스코드, 페이스북, 심지어 스택오버플로우에도 연락했어요. 마지막으로 stackoverflow에서 html 줄을 발견했습니다. 이 줄은 모든 것을 한 줄로 해결했습니다.

큐브.js

내 알고리즘을 사용자에게 제공합니다. three.js 기반
실제로 자바스크립트를 작성하는 것은 이번이 처음입니다. 보기에는 좋지 않고 아마도 모든 규칙을 어길 수도 있지만 작동합니다.

이 파일을 여러 번 다시 썼습니다. 첫 번째 반복은 github에 업로드를 시작하기 전이었고, 그 다음에는 기능적이었고 마지막으로 일종의 객체 지향이었습니다.
먼저 하나 이상의 함수에서 사용해야 하는 모든 변수를 선언합니다. three.js 객체의 재질과 형상, 객체를 저장할 배열, 회전 축 등입니다.
또한 모든 합법적인 큐브 이동에 필요한 변수, 즉 순환하거나 교체할 큐비, 회전 축 및 각도, 표시할 내용이 포함된 거대한 사전도 있습니다. 이것은 모두 72줄에 들어갈 수 있지만 style50에서는 줄당 하나의 변수를 원하므로 649줄이 됩니다.

건설자()

장면을 가져와 참조를 저장하고, 루프의 큐비, 윤곽선 및 평면을 생성하고, 루프의 큐비 및 윤곽선의 위치와 평면을 수동으로 설정합니다.

사이클_회전()

도우미 기능. 임시 큐비를 사용하여 4개의 큐비 a > b > c > d > a의 회전을 순환합니다.

교환_회전()

도우미 기능. 임시 큐비를 사용하여 2개의 큐비의 회전을 교환합니다.

재설정_큐브()

큐비를 기본 위치로 재설정하고 솔루션 div를 재설정합니다. 생각보다 더 많은 단계가 필요합니다. 먼저 모든 애니메이션을 재설정하고 완료해야 합니다. 모든 미래 및 과거 이동을 재설정하고 마지막으로 큐비의 회전을 재설정합니다.

is_moving()

큐브가 움직이는지에 따라 true 또는 false를 반환합니다.

do_move()

큐브 이동에 대한 애니메이션을 설정합니다.
이 함수는 원래 160줄의 if/else 문이었지만 나중에 거대한 사전에서 큐비와 이동을 가져오기 위해 다시 작성했습니다. 이렇게 하면 이 함수와 다음 함수를 더 쉽게 읽을 수 있고 4x4 또는 5x5 버전을 작성하는 경우 사전만 변경하면 됩니다.

마무리_이동()

애니메이션을 완료하고 실제로 큐비를 이동(회전)합니다.
큐비는 실제로 움직이지 않기 때문에 기본 아이디어는 실제 큐브에서 해당 위치로 이동하는 큐비의 회전을 복사한 다음 모든 것을 회전시키는 것입니다.
이 함수는 원래 다음 if/else 문의 375줄짜리 괴물이었습니다. 나중에 이동 사전과 함께 작동하도록 다시 작성되었습니다.

다음_이동()

이동 목록에서 다음 이동을 수행하거나 단계 목록에서 다음 알고리즘을 수행하고 현재 알고리즘을 화면에 표시합니다.

이전_이동()

이전 이동은 목록을 역방향으로 이동합니까, 아니면 단계 목록의 이전 알고리즘을 수행합니까?

적용_패턴()

각 큐비를 회전하여 색상 선택기(또는 실제로는 면 배열)의 색상을 큐브에 적용합니다. 자체 기능 중 일부가 포함되어 있습니다. 모든 큐브에는 수동 수정자가 있는 자체 라인이 있습니다. 나에게 그것은 자동화하기에는 너무 무작위적이다. 하지만 시도하고 싶다면 내 손님이 되어주세요.

반대_색상()

녹색은 파란색으로, 빨간색은 주황색으로, 흰색은 노란색으로, 그 반대 방향으로 변경됩니다. 지금 생각해보면 이것은 dict일 수도 있지만 한 줄의 수학과 3개의 ifs도 작동합니다.

apply_color()

앞면과 왼쪽 색상 또는 위쪽 색상을 기준으로 큐비를 회전합니다. 기본적으로 이동이 하드코딩된 if 문이 많이 있지만 여기서는 이것으로 충분합니다.

run_alg()