Решение Nonograms (Picross)
Вы просто ищете join, в пандах мы используем pd.merge для этого, например:
df3 = pd.merge(df1, df2, on='Category')
ID Category Value1 Value2 Value 1 Average Value 2 Average
0 111 1 5 7 4 5
1 112 1 3 8 4 5
2 113 2 6 9 6 7
3 114 3 2 6 9 2
Официальная документация pandas о слиянии:
https://pandas.pydata.org/pandas-docs/stable/reference/api/pandas.DataFrame.merge.html
Вот хорошее объяснение объединений: Панды слияния 101
5 ответов
I don't have enough time right now to flesh out a solution, but this is how I would tackle it.
"function1" determine the possible combinations for a row or column given the constraints of the numbers on the top or side, and the squares that are already filled out and those that have been emptied.
"function2" take the output from function1 and logically and all the results together - the spots with ones could be filled in.
"function3" take the output from function1 and logically or all the results together - the spots with zeros could be emptied.
keep applying function2 and function3 to all the rows and collumns until no more boxes are emptied or filled in. If the puzzle is solved then, you are done.
If the puzzle is not solved, then take a row or column that has the fewest possibilities and apply the first possibility. Then apply function2 and function3 to the new board. If it leads to a contradiction (0 possibilities for a row or column) then un-apply the possibility and try a different one. Keep recursing like this until a solution is found.
Determining whether a Nonogram solution exists/is unique is NP-hard. See http://en.wikipedia.org/wiki/Nonogram#cite_note-0
This seems like a pretty obvious case for depth first search with backtracking, as with the "n queens" problem. The sort of cute part is that as well as placing rows/columns, you can shift the blocks.
Okay, here's an outline.
Start with an empty board, place the first row
Now, with that board, place a second row, check it against the column constraints. If it passes, recursively try the next row against that state; if it doesn't pass, then try the next possible placement of that row.
If at any time you run out of possible placements of a row that satisfy the constraints, then the puzzle has no solution. Otherwise, when you run out of rowns, you've solved the problem.
It's convenient that these rows can be treated as binary numbers, so there is a natural ordering to the possibilities.
Вместо того, чтобы пытаться разместить «первую» строку, она существенно сократит ваш поиск, если вы попытаетесь получить информацию из «наиболее ограниченной» строки или столбца, который может иметь несколько принудительных ценности. Быстрое указание - сложить все значения в строке / столбце и добавить #_of_values - 1, а затем найти строку / столбец с наибольшим таким значением (или наименьшей разницей между этим значением и количеством строк или столбцов, если строки и столбцы различаются). Таким образом, если у вас есть головоломка 25x25, и одна из строк «5 1 1 6 1 1 3», эта строка имеет значение 24, что означает, что она очень ограничена - относительное положение всех, кроме одного из пустых квадратов в этом ряду известен, и последний пустой квадрат может находиться в любом из 8 различных относительных положений. Таким образом, для каждой группы заполненных квадратов, Есть только две возможности: дополнительный пустой квадрат слева от этой группы, или дополнительный пустой квадрат справа от этой группы. Так, например, пять из заполненных квадратов в этой группе из 6 уже известны.
Если у вас есть некоторые принудительные значения в одном направлении, это дополнительно ограничивает любую из групп в другом направлении, которые пересекаются с известной информацией. Таким образом, лучший подход, вероятно, будет работать взад-вперед между столбцами и строками, когда станет известно больше информации, и именно в этом случае вам нужно решить ее вручную.
это дополнительно ограничивает любую из групп в другом направлении, которое пересекается с известной информацией. Таким образом, лучший подход, вероятно, будет работать взад-вперед между столбцами и строками, когда станет известно больше информации, и именно в этом случае вам нужно решить ее вручную. это дополнительно ограничивает любую из групп в другом направлении, которое пересекается с известной информацией. Таким образом, лучший подход, вероятно, будет работать взад-вперед между столбцами и строками, когда станет известно больше информации, и именно в этом случае вам нужно решить ее вручную.Настоящая проблема в том, сможет ли кто-нибудь придумать алгоритм, который решит указанную головоломку быстрее, чем человек? Это легко сделать для относительно простых головоломок, таких как справочная, но если головоломка вырастет, большинство алгоритмов здесь быстро замедлятся. Вот загадка, которую я пытался решить. Проблема в том, что, например, 4-я строка имеет 2220075 возможных комбинаций, которые я считаю. Если алгоритм Чарли временно принимает неправильную строку для строки 3, он перебирает все эти комбинации для строки 4. И это не говоря уже о случае, когда алгоритм противоречит сам себе в строке 35 из-за ошибки, сделанной в строке 2.
Мой алгоритм был похож на алгоритм Джона. Он не смог работать в режиме x86 на моем 64-битном рабочем столе. Когда я переключил его в 64-битный режим и позволил ему работать на ночь, утром мой компьютер был совершенно непригоден для использования. В процессе резервировалось 8 гигабайт памяти (8 гигабайт физической памяти на рабочем столе), и компьютер не отвечал из-за безумной подкачки. И он даже не решил все возможные ряды. Не говоря уже о том, что он даже не коснулся возможных комбинаций столбцов.
List<List<int>> rows =
new List<List<int>>()
{
new List<int> { 8,29,4 },
new List<int> { 6,4,25,4,3 },
new List<int> { 5,3,2,3,9,4,2,1,3 },
new List<int> { 4,2,2,2,2,1,2,2 },
new List<int> { 4,1,1,9,10,2,2,1 },
new List<int> { 3,2,6,5,5,1,1 },
new List<int> { 3,1,5,5,1,1 },
new List<int> { 3,1,4,4,1,1 },
new List<int> { 3,1,4,4,1,1 },
new List<int> { 3,1,3,3,1,1 },
new List<int> { 3,1,3,6,2 },
new List<int> { 3,1,2,3,2,4,2 },
new List<int> { 4,3,1,8,7,1,2,3 },
new List<int> { 4,2,1,12,11,1,2,4 },
new List<int> { 5,1,2,7,2,2,6,1,1,4 },
new List<int> { 4,1,1,1,6,2,2,6,1,2,1,3 },
new List<int> { 4,1,1,2,4,3,4,3,1,1,1,1,3 },
new List<int> { 4,1,1,2,1,4,1,2,3,2,1,2,2 },
new List<int> { 3,1,1,1,2,5,6,1,1,1,3,2 },
new List<int> { 3,2,1,1,2,1,5,4,4,2,1,2,1,2 },
new List<int> { 3,2,2,1,1,4,2,2,3,1,1,2,1,1,2 },
new List<int> { 3,1,3,2,1,1,4,1,5,3,2,1,3,1,2 },
new List<int> { 3,1,2,1,2,1,3,7,4,1,4,2,2 },
new List<int> { 2,1,4,1,1,1,2,6,2,2,2,3,2,1 },
new List<int> { 2,2,4,1,2,1,2,5,2,1,1,3,2,1 },
new List<int> { 2,2,1,4,1,1,3,3,2,1,4,4,1 },
new List<int> { 2,3,3,2,1,3,3,7,4,1 },
new List<int> { 2,3,2,4,5,8,1,2,1 },
new List<int> { 1,1,3,11,6,7,1,3,1 },
new List<int> { 1,1,2,2,13,10,2,3,2 },
new List<int> { 1,2,3,1,6,1,1,7,1,5,2 },
new List<int> { 1,1,3,2,6,1,1,1,1,4,1,4,2 },
new List<int> { 1,1,6,7,2,4,2,5,6,1 },
new List<int> { 1,1,2,3,1,4,2,2,11,2,1 },
new List<int> { 1,1,1,1,2,1,5,10,1,1,1 },
new List<int> { 1,1,1,1,4,7,4,10,1,1,1 },
new List<int> { 1,2,1,1,28,1,1,3 },
new List<int> { 1,2,1,2,27,2,1,3 },
new List<int> { 1,1,1,1,26,1,1,1,1 },
new List<int> { 2,3,1,28,2,1,2,1 }
};
List<List<int>> cols =
new List<List<int>>()
{
new List<int> { 40 },
new List<int> { 28,1 },
new List<int> { 23,8 },
new List<int> { 5,6,7,4 },
new List<int> { 3,6,1,9,3,1 },
new List<int> { 2,3,2,5,4,2,2 },
new List<int> { 1,2,4,1,2,5,2 },
new List<int> { 1,1,4,9,2,3,2 },
new List<int> { 2,4,2,6,1,4,3 },
new List<int> { 1,4,1,3,4,1,6 },
new List<int> { 1,4,3,2,3,5,5 },
new List<int> { 2,4,1,2,3,4,1,3 },
new List<int> { 1,2,3,4,2,2,4,4,1 },
new List<int> { 1,1,2,3,2,1,4,2,4 },
new List<int> { 2,3,5,3,3,5,4 },
new List<int> { 3,1,6,1,2,5,5 },
new List<int> { 3,2,6,2,15 },
new List<int> { 3,1,8,2,13 },
new List<int> { 2,2,4,5,15 },
new List<int> { 2,2,2,2,22 },
new List<int> { 2,1,1,1,12,6 },
new List<int> { 2,1,10,4,5 },
new List<int> { 3,1,3,1,2,4 },
new List<int> { 3,1,1,4,3,1,4 },
new List<int> { 3,2,2,3,2,2,5 },
new List<int> { 3,1,1,5,1,1,5 },
new List<int> { 3,1,1,5,1,1,5 },
new List<int> { 3,1,1,5,1,1,5 },
new List<int> { 3,2,5,2,1,1,4 },
new List<int> { 3,1,1,3,2,2,4 },
new List<int> { 3,1,6,4,5 },
new List<int> { 2,2,12,2,6 },
new List<int> { 2,2,1,1,22 },
new List<int> { 2,1,2,2,5,15 },
new List<int> { 3,1,4,3,2,14 },
new List<int> { 3,1,7,2,1,13 },
new List<int> { 3,2,6,1,1,6,8 },
new List<int> { 3,2,5,2,2,4,7 },
new List<int> { 2,1,2,4,1,1,1,4,1,4,2 },
new List<int> { 1,1,4,4,3,1,4,5,1 },
new List<int> { 1,1,5,1,1,2,1,2,2,3,2 },
new List<int> { 1,5,2,2,1,5,5,3 },
new List<int> { 1,6,2,1,4,2,6,1 },
new List<int> { 1,6,2,6,5,2 },
new List<int> { 1,5,3,1,9,2 },
new List<int> { 2,2,4,2,6,3 },
new List<int> { 1,2,2,2,9,2,1 },
new List<int> { 3,5,5,8,4 },
new List<int> { 4,13,9 },
new List<int> { 27,2 }
};
Авторские права принадлежат Гильдии информационных технологий Тампере / Kaisapais / Финской пивоварне.