九宮格元素遍歷問題解決方法

『壹』 將1到9填在九宮格內 怎麼樣使橫行都是偶數

首先滿足條件的九宮格填充方法並不存在。

因為九宮格填充要求每行、每列兩個對角線上的三數之和都等於15，如果任意一橫行都是偶數，那麼所在行的數字和必不可能等於奇數。

那麼遍歷所有九宮格填充方法，只能得到4種解，同樣找不到符合條件的解。

1、此解是九宮格解，確不滿足題目條件

(1)九宮格元素遍歷問題解決方法擴展閱讀：

九宮格排列是數學里的三階幻方。幻方是一種將數字安排在正方形格子中，使每行、列和對角線上的數字和都相等的方法。

幻方又包括：完全幻方、乘幻方、高次幻方等。

完全幻方，指一個幻方行、列、主對角線及泛對角線各數之和均相等 [1] 。

乘幻方，指一個幻方行列、對角線各數乘積相等。

高次幻方，n階幻方是由前n^2（n的2次方）個自然數組成的一個n階方陣，其各行、各列及兩條對角線所含的n個數的和相等。

『貳』 「樣式遍歷」，公考圖形推理當中經常用到這個詞彙，但是不太理解，求高人指點迷津。

送你一句華圖老師對樣式遍歷的概述：

樣式遍歷：不改變樣式的種類，只改變樣式的順序。

樣式遍歷多出現在於九宮格里，先看樣式遍歷再看加減同異。

最後附贈兩道例題

『叄』 2017年聯考：圖形推理九宮格出題形式技巧點撥

按以往的考請看，聯考中圖形推理考查規律推理與重構推理兩大類，規律推理包括：數量類規律、樣式類規律、位置類規律等，出題形式比較靈活，有一條式、兩段式、九宮格、分組分類。一般在九宮格的出題形式下，題目較難，考查規律的方式也較多。因此在這種出題形式下，應該引起大家的重視。而我們觀察九宮格可以從以下幾種形式去觀察。

1.九宮格橫行規律。在這種出題形式下，解題方法為：尋找第一行的規律，用第二行驗證規律，在第三行應用規律。例如：

【例1】從所給四個選項中，選擇最合適的一個填入問號處，使之呈現一定的規律性：

【答案】B

【解析】圖形組成相似，我們可以考慮樣式類規律，樣式類包括遍歷和運算，而此題的規律為米字型兩端疊加求中間，選B。

『肆』 九宮格數獨游戲最簡單最實用的解法

基本解法分為兩類思路：

1. 排除法

   就是利用1~9的數字在每一行、每一列、每一個九宮格都只能出現一次的規則進行解題的方法。基礎摒除法可以分為行摒除、列摒除、九宮格摒除。
   

2. 唯一法

   當某行已填數字的宮格達到8個，那麼該行剩餘宮格能填的數字就只剩下那個還沒出現過的數字了，成為行唯一解。
   

『伍』 九宮格怎麼破解!

1.聯除法.
在並排的三個九宮格中的兩排尋找相同數字,再利用九宮格得出另一排中該數字位置,該方法適用於中高級數獨.
2.巡格法
找出在每個九宮格中出現頻率較高的數字,得出該數字在其餘九宮格內位置,該方法應用於方法一之後.
3.排它法
這個方法是解決問題的關鍵,易被常人所忽略.在各行列或九宮格中觀察,若有個位置其它數字都不能填,就填餘下的數字
4.待定法
此方法不常用卻很有效.暫時確定某個數字在某個區域,再利用其來進行排除
5.行列法
此方法用於收官階段,利用先從行列突破來提高解題效率.
6.假設法
作為一名高手,我不提倡這種方法.即在某個位置隨機的填上一個數字,再進行推演,並有可能最終產生矛盾而否定結論.
7.頻率法
這種方法相比於上一種方法更能提高效率.在某一行列或九宮格列舉出所有情況,再選擇某位置中出現頻率高的數字

『陸』 九宮格拼圖·求此問題解法~~思路~代碼都可~~就是關於其還原演算法的·急~在線等~多謝哈

http://www.cublog.cn/u/8780/showart.php?id=163291

在一個3×3的九宮中有1－8這8個數及一個空格隨機的擺放在其中的格子里，如圖1－1所示。現在要求實現這個問題：將其調整為如圖1－1右圖所示的形式。調整的規則是：每次只能將與空格（上、下、或左、右）相鄰的一個數字平移到空格中。試編程實現這一問題的求解。

（圖1－1）

二、題目分析：
這是人工智慧中的經典難題之一，問題是在3×3方格棋盤中，放8格數，剩下的沒有放到的為空，每次移動只能是和相鄰的空格交換數。程序自動產生問題的初始狀態，通過一系列交換動作將其轉換成目標排列（如下圖1－2到圖1－3的轉換）。

（圖1－2） （圖1－3）

該問題中，程序產生的隨機排列轉換成目標共有兩種可能，而且這兩種不可能同時成立，也就是奇數排列和偶數排列。可以把一個隨機排列的數組從左到右從上到下用一個一維數組表示，如上圖1－2我們就可以表示成｛8，7，1，5，2，6，3，4，0｝其中0代表空格。
在這個數組中我們首先計算它能夠重排列出來的結果，公式就是：

∑（F（X））＝Y，其中F（X）

是一個數前面比這個數小的數的個數,Y為奇數和偶數時各有一種解法。（八數碼問題是否有解的判定 ）

上面的數組可以解出它的結果。
F（8）＝0；
F（7）＝0；
F（1）＝0；
F（5）＝1；
F（2）＝1；
F（6）＝3；
F（3）＝2；
F（4）＝3；
Y＝0＋0＋0＋1＋1＋3＋2＋3＝10

Y＝10是偶數，所以其重排列就是如圖1－3的結果，如果加起來的結果是奇數重排的結果就是如圖1－1最右邊的排法。

三、演算法分析
求解方法就是交換空格（0）位置，直至到達目標位置為止。圖形表示就是：

（圖3－1）

要想得到最優的就需要使用廣度優先搜索，九宮的所以排列有9！種，也就是362880種排法，數據量是非常大的，使用廣度搜索，需要記住每一個結點的排列形式，要是用數組記錄的話會佔用很多的內存，可以把數據進行適當的壓縮。使用DWORD形式保存，壓縮形式是每個數字用3位表示，這樣就是3×9＝27個位元組，由於8的二進製表示形式1000，不能用3位表示，使用了一個小技巧就是將8表示為000，然後用多出來的5個字表示8所在的位置，就可以用DWORD表示了。用移位和或操作將數據逐個移入，比乘法速度要快點。定義了幾個結果來存儲遍歷到了結果和搜索完成後保存最優路徑。
類結構如下：

class CNineGird
{
public:
struct PlaceList
{
DWORD Place;
PlaceList* Left;
PlaceList* Right;
};
struct Scanbuf
{
DWORD Place;
int ScanID;
};
struct PathList
{
unsigned char Path[9];
};

private:
PlaceList *m_pPlaceList;
Scanbuf *m_pScanbuf;
RECT m_rResetButton;
RECT m_rAutoButton;

public:
int m_iPathsize;
clock_t m_iTime;
UINT m_iStepCount;
unsigned char m_iTargetChess[9];
unsigned char m_iChess[9];
HWND m_hClientWin;
PathList *m_pPathList;
bool m_bAutoRun;

private:
inline bool AddTree(DWORD place , PlaceList*& parent);
void FreeTree(PlaceList*& parent);
inline void ArrayToDword(unsigned char *array , DWORD & data);
inline void DwordToArray(DWORD data , unsigned char *array);
inline bool MoveChess(unsigned char *array , int way);
bool EstimateUncoil(unsigned char *array);
void GetPath(UINT depth);

public:
void MoveChess(int way);
bool ComputeFeel();
void ActiveShaw(HWND hView);
void DrawGird(HDC hDC , RECT clientrect);
void DrawChess(HDC hDC , RECT clientrect);
void Reset();
void OnButton(POINT pnt , HWND hView);

public:
CNineGird();
~CNineGird();
};

計算隨機隨機數組使用了vector模板用random_shuffle（，）函數來打亂數組數據，並計算目標結果是什麼。代碼：

void CNineGird::Reset()
{
if(m_bAutoRun) return;
vector vs;
int i;
for (i = 1 ; i < 9 ; i ++)
vs.push_back(i);
vs.push_back(0);
random_shuffle(vs.begin(), vs.end());
random_shuffle(vs.begin(), vs.end());
for ( i = 0 ; i < 9 ; i ++)
{
m_iChess[i] = vs[i];
}

if (!EstimateUncoil(m_iChess))
{
unsigned char array[9] = {1,2,3,8,0,4,7,6,5};
memcpy(m_iTargetChess , array , 9);
}
else
{
unsigned char array[9] = {1,2,3,4,5,6,7,8,0};
memcpy(m_iTargetChess , array , 9);
}

m_iStepCount = 0;
}

數據壓縮函數實現：

inline void CNineGird::ArrayToDword(unsigned char *array , DWORD& data)
{
unsigned char night = 0;
for ( int i = 0 ; i < 9 ; i ++)
{
if (array[i] == 8)
{
night = (unsigned char)i;
break;
}
}

array[night] = 0;
data = 0;
data = (DWORD)((DWORD)array[0] << 29 | (DWORD)array[1] << 26 |
(DWORD)array[2] << 23 | (DWORD)array[3] << 20 |
(DWORD)array[4] << 17 | (DWORD)array[5] << 14 |
(DWORD)array[6] << 11 | (DWORD)array[7] << 8 |
(DWORD)array[8] << 5 | night);

array[night] = 8;
}

解壓縮時跟壓縮正好相反，解壓代碼：

inline void CNineGird::DwordToArray(DWORD data , unsigned char *array)
{
unsigned char chtem;
for ( int i = 0 ; i < 9 ; i ++)
{
chtem = (unsigned char)(data >> (32 - (i + 1) * 3) & 0x00000007);
array[i] = chtem;
}
chtem = (unsigned char)(data & 0x0000001F);
array[chtem] = 8;
}

由於可擴展的數據量非常的大，加上在保存的時候使用的是DWORD類型，將每一步數據都記錄在一個排序二叉樹中，按從小到大從左到有的排列，搜索的時候跟每次搜索將近萬次的形式比較快幾乎是N次方倍，把幾個在循環中用到的函數聲明為內聯函數，並在插入的時候同時搜索插入的數據會不會在樹中有重復來加快總體速度。二叉樹插入代碼：

inline bool CNineGird::AddTree(DWORD place , PlaceList*& parent)
{
if (parent == NULL)
{
parent = new PlaceList();
parent->Left = parent->Right = NULL;
parent->Place = place;
return true;
}
if (parent->Place == place)
return false;

if (parent->Place > place)
{
return AddTree(place , parent->Right);
}
return AddTree(place , parent->Left);
}

計算結果是奇數排列還是偶數排列的代碼：

bool CNineGird::EstimateUncoil(unsigned char *array)
{
int sun = 0;
for ( int i = 0 ; i < 8 ; i ++)
{
for ( int j = 0 ; j < 9 ; j ++)
{
if (array[j] != 0)
{
if (array[j] == i +1 )
break;
if (array[j] < i + 1)
sun++;
}
}
}
if (sun % 2 == 0)
return true;
else
return false;
}

移動到空格位的代碼比較簡單，只要計算是否會移動到框外面就可以了，並在移動的時候順便計算一下是不是已經是目標結果，這是用來給用戶手工移動是給與提示用的，代碼：

inline bool CNineGird::MoveChess(unsigned char *array , int way)
{
int zero , chang;
bool moveok = false;
for ( zero = 0 ; zero < 9 ; zero ++)
{
if (array[zero] == 0)
break;
}
POINT pnt;
pnt.x = zero % 3;
pnt.y = int(zero / 3);
switch(way)
{
case 0 : //up
if (pnt.y + 1 < 3)
{
chang = (pnt.y + 1) * 3 + pnt.x ;
array[zero] = array[chang];
array[chang] = 0;
moveok = true;
}
break;
case 1 : //down
if (pnt.y - 1 > -1)
{
chang = (pnt.y - 1) * 3 + pnt.x ;
array[zero] = array[chang];
array[chang] = 0;
moveok = true;
}
break;
case 2 : //left
if (pnt.x + 1 < 3)
{
chang = pnt.y * 3 + pnt.x + 1;
array[zero] = array[chang];
array[chang] = 0;
moveok = true;
}
break;
case 3 : //right
if (pnt.x - 1 > -1)
{
chang = pnt.y * 3 + pnt.x - 1;
array[zero] = array[chang];
array[chang] = 0;
moveok = true;
}
break;
}
if (moveok && !m_bAutoRun)
{
m_iStepCount ++ ;

DWORD temp1 ,temp2;
ArrayToDword(array , temp1);
ArrayToDword(m_iTargetChess , temp2);
if (temp1 == temp2)
{
MessageBox(NULL , "你真聰明這么快就搞定了!" , "^_^" , 0);
}
}
return moveok;
}

在進行廣度搜索時候，將父結點所在的數組索引記錄在子結點中了，所以得到目標排列的時候，只要從子結點逆向搜索就可以得到最優搜索路徑了。用變數m_iPathsize來記錄總步數，具體函數代碼：

void CNineGird::GetPath(UINT depth)
{
int now = 0 , maxpos = 100 ;
UINT parentid;
if (m_pPathList != NULL)
{
delete[] m_pPathList;
}
m_pPathList = new PathList[maxpos];
parentid = m_pScanbuf[depth].ScanID;

DwordToArray(m_pScanbuf[depth].Place , m_pPathList[++now].Path);

while(parentid != -1)
{
if (now == maxpos)
{
maxpos += 10;
PathList * temlist = new PathList[maxpos];
memcpy(temlist , m_pPathList , sizeof(PathList) * (maxpos - 10));
delete[] m_pPathList;
m_pPathList = temlist;
}
DwordToArray(m_pScanbuf[parentid].Place , m_pPathList[++now].Path);
parentid = m_pScanbuf[parentid].ScanID;
}
m_iPathsize = now;
}

動態排列的演示函數最簡單了，為了讓主窗體有及時刷新的機會，啟動了一個線程在需要主窗體刷新的時候，用Slee（UINT）函數來暫停一下線程就可以了。代碼：

unsigned __stdcall MoveChessThread(LPVOID pParam)
{
CNineGird * pGird = (CNineGird *)pParam;
RECT rect;
pGird->m_iStepCount = 0;
::GetClientRect(pGird->m_hClientWin , &rect);
for ( int i = pGird->m_iPathsize ; i > 0 ; i --)
{
memcpy(pGird->m_iChess , pGird->m_pPathList[i].Path , 9);
pGird->m_iStepCount ++;
InvalidateRect( pGird->m_hClientWin , &rect , false);
Sleep(300);
}
char msg[100];
sprintf(msg , "^_^ ! 搞定了!\r\n計算步驟用時%d毫秒" , pGird->m_iTime);
MessageBox(NULL , msg , "~_~" , 0);
pGird->m_bAutoRun = false;
return 0L;
}

最後介紹一下搜索函數的原理，首先得到源數組，將其轉換成DWORD型，與目標比較，如果相同完成，不同就交換一下數據和空格位置，加入二叉樹，搜索下一個結果，直到沒有步可走了，在搜索剛剛搜索到的位置的子位置，這樣直到找到目標結果為止，函數：

bool CNineGird::ComputeFeel()
{
unsigned char *array = m_iChess;
UINT i;
const int MAXSIZE = 362880;
unsigned char temparray[9];

DWORD target , fountain , parent , parentID = 0 , child = 1;
ArrayToDword(m_iTargetChess , target);
ArrayToDword(array , fountain);
if (fountain == target)
{
return false;
}
if (m_pScanbuf != NULL)
{
delete[] m_pScanbuf;
}
m_pScanbuf = new Scanbuf[MAXSIZE];
AddTree(fountain ,m_pPlaceList);
m_pScanbuf[ 0 ].Place = fountain;
m_pScanbuf[ 0 ].ScanID = -1;
clock_t tim = clock();
while(parentID < MAXSIZE && child < MAXSIZE)
{
parent = m_pScanbuf[parentID].Place;
for ( i = 0 ; i < 4 ; i ++) // 0 :UP , 1:Down ,2:Left,3:Right
{
DwordToArray(parent , temparray);
if (MoveChess(temparray,i)) //是否移動成功
{
ArrayToDword(temparray , fountain);
if (AddTree(fountain, m_pPlaceList)) //加入搜索數
{
m_pScanbuf[ child ].Place = fountain;
m_pScanbuf[ child ].ScanID = parentID;
if (fountain == target) //是否找到結果
{
m_iTime = clock() - tim;
GetPath(child);//計算路徑
FreeTree(m_pPlaceList);
delete[] m_pScanbuf;
m_pScanbuf = NULL;
return true;
}
child ++;
}
}
} // for i
parentID++;
}
m_iTime = clock() - tim;

FreeTree(m_pPlaceList);
delete[] m_pScanbuf;
m_pScanbuf = NULL;
return false;
}

重要函數的介紹結束;下面是程序的運行結果和運算結果：

『柒』 圖形推理遍歷是什麼意思

是行測判斷推理題中的重要考察題型，其中有個知識點叫作遍歷。

圖形推理的出題形式常見的有：一條式，兩段式和九宮格。一條式常見的觀察方式：是從左向右觀察，問號處選擇一個與所給圖形規律一致的圖形。

兩段式的觀察口訣是：第一段找規律，第二段應用規律。即觀察第一段圖形出現的規律，第二段結合前兩個圖形，最大限度地運用第一段的規律選擇問號處圖形;九宮格觀察的方式：比較多樣，常見的有橫向、縱向和米字型、S型等。橫(縱)向規律最為常見，即第一行找規律，第二行驗證規律，第三行應用規律。

圖形推理規律類考分為位置、樣式、屬性、數量、功能五大類。下面分類別為小夥伴們介紹下各個考點的識別特徵和考查方式。

圖形組成不同，但屬性上呈現一致性時可以考慮屬性類。屬性類規律可分為對稱性、曲直性和封閉性。對稱性是屬性類的考查重點。當題干圖形比較規整時，可以考慮對稱性，包括軸對稱和中心對稱。軸對稱圖形還可以進一步考查對稱軸的數量、方向變化、圖形中小元素的對稱軸之間的位置變化、對稱軸是否經過圖形中的線/點等。

考查曲直性的圖形其曲線和直線特徵明顯，但線條數量不一定明顯，可能存在不好界定數量的線條，曲直性常與靜態位置相結合考查。封閉性考查的頻率不高，一般如果選項中出現一個圖形的封閉性與其他三個明顯不同時，可以考慮封閉性。

『捌』 數獨（九宮格）解題技巧

樓上的那是最小的九宮格的技巧，數獨最少是9個九宮格，根本不適用的。 . 每個人的習慣不一樣，每個人的思維方法，慣性也不一樣，根據自己的長處選擇最好的辦法才是真正的技巧。 . 1.聯除法. 在並排的三個九宮格中的兩排尋找相同數字,再利用九宮格得出另一排中該數字位置,該方法適用於中高級數獨. 2.巡格法 找出在每個九宮格中出現頻率較高的數字,得出該數字在其餘九宮格內位置,該方法應用於方法一之後. 3.排它法 這個方法是解決問題的關鍵,易被常人所忽略.在各行列或九宮格中觀察,若有個位置其它數字都不能填,就填餘下的數字 4.待定法 此方法不常用卻很有效.暫時確定某個數字在某個區域,再利用其來進行排除 5.行列法 此方法用於收官階段,利用先從行列突破來提高解題效率. 6.假設法 作為一名高手,我不提倡這種方法.即在某個位置隨機的填上一個數字,再進行推演,並有可能最終產生矛盾而否定結論. 7.頻率法 這種方法相比於上一種方法更能提高效率.在某一行列或九宮格列舉出所有情況,再選擇某位置中出現頻率高的數字 8.候選數法使用候選數法解數獨題目需先建立候選數列表，根據各種條件，逐步安全的清除每個宮格候選數的不可能取值的候選數，從而達到解題的目的。 使用候選數法一般能解比較復雜的數獨題目，但是候選數法的使用沒有直觀法那麼直接，需要先建立一個候選數列表的准備過程，所以實際使用時可以先利用直觀法進行解題，到無法用直觀法解題時再使用候選數法解題。 候選數法解題的過程就是逐漸排除不合適的候選數的過程，所以在進行候選數刪除的時候一定要小心，確定安全地刪除不合適的候選數，否則，很多時候只有重新做題了。有了計算機軟體的幫助，使得候選數表的維護變得輕鬆起來。 數獨直觀法解題技巧主要有：唯一候選數法、隱性唯一候選數法、區塊刪減法、數對刪減法、隱性數對刪減法、三鏈數刪減法、隱性三鏈數刪減法、矩形頂點刪減法、三鏈列刪減法、關鍵數刪減法、關連數刪減法。

『玖』 數獨（九宮格）的規律是什麼

規律：每一行、每一列、每一個粗線宮（3*3）內的數字均含1-9，不重復。

玩家需要根據9×9盤面上的已知數字，推理出所有剩餘空格的數字，並滿足每一行、每一列、每一個粗線宮（3*3）內的數字均含1-9，不重復。

九宮格游戲規則，1至9九個數字，橫豎都有3個格，思考怎麼使每行、每列兩個對角線上的三數之和都等於15。這個游戲不僅僅考驗人的數字推理能力，也同時考驗了人的思維邏輯能力。

「重排九宮」有兩種玩法：

第一種是在在3×3方格盤上，是把1至8八個小木塊隨意擺放，每一空格其周圍的數字可移至空格。玩者要將小木塊按12345678的順序重新排好，以最少的移動次數拼出結果者為勝。

第二種玩法如九宮格算術游戲玩法，推動木格中8個數字排列，橫豎都有3個格，使每行、每列兩個對角線上的三數之和都等於15。在計算的同時，還必須思考怎麼把數字方塊推動到相對應的位置上，這個游戲不僅僅考驗人的數字推理能力，也同時考驗了人的思維邏輯能力。

以上內容參考：網路-九宮格

『拾』 九格拼圖該怎麼解決

你是想拼成這個樣子吧：
1 2 3
4 5 6
7 8 0
如果按照九宮格拼圖的規則，這是不可能的。
將九宮格拉成一行數，只考慮1-8八個數，你的圖逆序數為3，是奇排列； 答案逆序數為0，是偶排列。九宮格的移動規則不會改變排列的奇偶性，故此題無解。這個證明需要一點數學知識，可以參考以下資料：
-------------------------------------------------

假設圖中的a是3*3數字拼圖標準的結果，則對於圖b的狀態是不可能變換成a的。證明起來需要用到高等代數里逆序數的概念，具體的說是用到了一個簡單的定理。
定義：在一個1,2,...,n的排列中，如果一對數的前後位置與大小順序相反，即前面的數大於後面的數，那麼它們就稱為一個逆序。一個排列中逆序的總數就稱為這個排列的逆序數。逆序數為偶數的排列稱為偶排列；逆序數為奇數的排列稱為奇排列。如2431中，21，43，41，31是逆序，逆序數是4，為偶排列。——這是北大《高等代數》上的定義。
定理：交換一個排列中的兩個數，則排列的奇偶性發生改變。（證明見任何一本《高等代數》）
我們將空格看成數字9（數字9對應空位），按正常順序看a圖，9個數字排列是123456789，其逆序數是0，是偶排列；b圖是123456879，逆序數是1，是奇排列。我們知道，我們能夠移動空塊相鄰的塊，這里的移動相當於一種特殊的對換（相鄰對換），例如：對於b圖，移動6就相當於9和6互換（9向上移動了），移動7就相當於9和7互換（9向左移動了）。現在假設從b圖經過一系列的平移變到了a圖，則空格塊9必然移動（對換）了偶數次（向左一次必然要再向右一次回來，向上一次必然要向下再回來，最終才能夠回到右下角的位置），根據上面的定理最終變成的排列必然是仍然是奇排列（和b相同），然而a圖是偶排列，因而產生矛盾，因此b圖不可能通過平移變成最終的a圖。
（文中圖片請參看【參考文獻】中的鏈接。）
-------------------------------------------------

註：我還用迭代A*程序算了一下，遍歷了39步之內所有拼法，沒有解。這也印證了理論證明的結果。

【 參考文獻】
網路：不可還原的拼圖，http://ke..com/view/2879180.htm。