如何使用n種不同顏色在同一行上使用相同顏色繪製r x r字段，使用DP

Question

我想問如何用DP解決此問題。

問題是：「製作一個程序，計算用不同顏色繪製r x r字段的多少種方法，而不在同一行和列中使用相同的顏色。

我試圖用回溯來解決它，但花了很多時間。 還有BFS，它花費了大量的內存。 （而且速度並不快。） 有人告訴我用算法DLX解決它，但我認爲會有一個更簡單的解決方案。

請問DP能解決嗎？ 10個10色的區域應在1〜2秒內填充。請幫忙！

Answer 1

我不知道用DP一個解決方案，但他們的是，這將需要一次遍歷矩陣無需任何額外的空間，併爲O（n^2）複雜（我認爲也將是在案件的另一種方法使用DP）。

從單元格（0,0）開始用顏色paint_no繪製它，然後將行和列增加1，但請記住佔用行％n和列％n，因爲某些點行或列可能大於'n 」。

解決方案的工作，因爲當你永遠都畫有彩色的下一個框將下一行和下一列在其它框畫等一個盒子。

starting_cell_row=0; 
starting_cell_col=0; 
count=0; 
for(paint_no, 1, n) 
{ 
    count=0; 
    row=starting_cell_row; 
    col=starting_cell_col; 
    while(count<n) 
    { 
     matrix[row][col]=paint_no; 
     row=(row+1)%n; 
     col=(col+1)%n; 
     count++; 
    } 
    starting_cell_col++; 
} 

Answer 2

它是尋找拉丁方 https://en.wikipedia.org/wiki/Latin_square

任務還沒有一個通用的解決方案的數量的一個衆所周知的任務。

但計算髮現所有排列存在一個Jacobson and Matthews' algorithm。