同じ色で同じ色を使わずに、r x rフィールドをn個の異なる色でペイントする方法

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とcol％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が存在します。