數字拼盤2(利用逆數對找到並輸出可解版面)

#include <conio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
#include <windows.h>
using namespace std;
vector<string> bign{"０","１","２","３","４","５","６","７","８","９"};  //用來輸出的全形數字，因為空白格 □是全形，這樣格子才不會歪掉
const int length = 4; //使用者可以透過更改邊長來玩到不一樣大小的數字拼盤
int map[length*length + 1]={0};  //一開始10格都設為0 ，但是捨棄第0格，只用map[1]~map[9]九宮格
int p;//目前位置
int k;//目前按鍵
int s;//目前移動數

void draw(){
    //system("cls");  //cls means clear screen
    cout << "steps:" << s << endl;
    for(int i = 1 ; i <= (length * length) ; i++ ){
        //cout << "de";
        if( map[i] == 0 ){
            cout << "□" << " ";
        }
        else if( map[i] >=1 && map[i] <=9 ){
            cout << bign[ map[i] ] << " ";
        }
        else{
            cout << map[i] << " ";
        }
        if( i % length == 0 ){
            cout << endl;
        }
    }
}

void init(){
    int i , j ;
    for( i = 1 ; i <= ((length*length) -1) ; i++ ){
        map[i] = i;
    }
    map[i] = 0;

    while(1){
        for( i = 1 ; i <= (length*length -1) ; i ++ ){
            int x = rand()%(length*length -1)+1;
            int y = map[x];
            map[x] = map[i];
            map[i] = y;
        }

        //第二題 逆數對之運算
        int a = 0;
        for( i = 1 ; i <= (length*length -2) ; i++ ){
            for( j = i + 1 ; j <= (length*length -1) ; j ++ ){
                if( map[i] > map[j] ){
                    a++;
                }
            }
        }
        if( a % 2 == 0 ){
            break;
        }
        cout << "no solution , try next\n";
        draw();
    }
    p = length*length;
    s = 0;
}



int main(){
    init();
    draw();
    /*while(1){
        if( kbhit() ){
            k = _getch();
            if(k == 'q'){
                break;
             }
            else if( k == 'e'){
                if( p < (length*length -length) ){
                    int x = p + length ;
                    int y = map[x];
                    map[x] = map[p];
                    map[p] = y;
                    p = x;
                }
            }
            else if( k == 'd'){
                if( p > length ){
                    int x = p - length ;
                    int y = map[x];
                    map[x] = map[p];
                    map[p] = y;
                    p = x;
                }
            }
            else if( k == 's'){
                if( p % length != 0 ){
                    int x = p + 1 ;
                    int y = map[x];
                    map[x] = map[p];
                    map[p] = y;
                    p = x;
                }
            }
            else if( k == 'f'){
                if( p % length != 1 ){
                    int x = p - 1 ;
                    int y = map[x];
                    map[x] = map[p];
                    map[p] = y;
                    p = x;
                }
            }
            if( k == 'e' || k == 'd' || k == 's' || k == 'f' ){
                s++;
            }
            bool finished = true;
            for( int i = 1 ; i <= (length*length -1) ; i++ ){
                if( map[i] != i ){
                    finished = false;
                    break;
                }
            }
            if( finished ){
                cout<<"you win!\n";
                draw();
                break;
            }
            draw();
         }
     }*/
    return 0;
}