لغز: اللغز المربع
https://stackoverflow.com/questions/767912
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
آخر يومين، امتنعت نفسي من دراسات الماجستير وتركز على هذا اللغز (على ما يبدو بسيطا):
هناك هذه الشبكة 10 * 10 التي تشكل مربع من 100 مكان متاح للذهاب. الهدف هو البدء من زاوية واجتياز جميع الأماكن فيما يتعلق ببعض "قواعد اجتياز" بسيطة والوصول إلى رقم 100 (أو 99 إذا كنت مبرمجا وابدأ مع 0 بدلا من ذلك :)
قواعد العبور هي:
1. اثنين من المساحات قفز على طول المحور الرأسي والأفقي
2. قفزة مساحة واحدة على طول الأقطار
3. يمكنك زيارة كل مربع مرة واحدة فقط
لتصور أفضل، إليك مثال صحي ترافيرس (حتى الخطوة الثامنة):
مثال Traverse http://img525.imageshack.us/img525/280/squarepuzle.png.
يدويا، لقد كنت أعمل على هذا اللغز من الملل. لسنوات، حاولت حلها باليد من وقت لآخر، لكنني لم أذهب إلى ما بعد 96. تبدو سهلة؟ جرب نفسك وانظر لنفسك :)
وبالتالي، من أجل حل المشكلة، قمت بتطوير برنامج قصير (حوالي 100 خط كود) في Python. أنا مبتدئ في هذه اللغة أردت أن أرى ما يمكنني القيام به.
يطبق البرنامج ببساطة محاولة حلول شاملة وأحلام الأخطاء. وبعبارة أخرى: البحث العمق الضابط الأول.
ينشأ سؤالي من هنا في: البرنامج، للأسف لا يمكن حل المشكلة لأن مساحة الدولة كبيرة جدا بحيث لا ينتهي البحث أبدا عن حلا. يمكن أن ترتفع إلى رقم 98 (ويطبع ذلك) دون صعوبة كبيرة، ومع ذلك ليس حل كامل.
يطبع البرنامج أيضا طول شجرة البحث التي تغطيها حتى الآن. في بضع دقائق، قالت قائمة Traverse، عن العنصر 65 مغطى حتى النهاية، لمسار واحد فقط. يتناقص هذا الرقم في فترات زمنية متزايدة بشكل كبير. لقد قمت بتشغيل الرمز لبعض الوقت ولم أستطع تجاوز 50 حاجزا والآن أنا مقتنع.
يبدو أن هذا النهج البسيط لن يكون كافيا إلا إذا قمت بتشغيله من أي وقت مضى. لذلك، كيف يمكنني تحسين التعليمات البرمجية ليكون أسرع وأكثر كفاءة حتى يأتي مع الحلول؟
في الأساس، أنا أتطلع لرؤية الأفكار حول كيفية:
- التقاط واستغلال المعرفة المجال محددة لهذه المشكلة
تطبيق تقنيات البرمجة / الحيل للتغلب على الإرهاق
.. وأخيرا تدرك في حل كبير.
شكرا مقدما.
مراجعة
بفضل ديف WebB لملق المشكلة في المجال الذي ينتمي إليه:
هذا يشبه إلى حد كبير مشكلة جولة الفارس التي تتعلق بتحريك فارس حول لوحة الشطرنج دون إعادة النظر في نفس المربع. في الأساس هي نفس المشكلة ولكن مع "قواعد اجتياز" مختلفة.
المحلول 3
في النهاية، لقد توصلت إلى رمز Python المعدل للتغلب على المشكلة. لقد تون الرمز لبضع ساعات وقد وجد بالفعل نصف مليون حلول في بضع ساعات.
لا تزال المجموعة الكاملة من الحلول تتطلب بحث شامل إجمالي، أي السماح للبرنامج بتشغيله حتى ينتهي من جميع المجموعات. ومع ذلك، يمكن أن يتم تخفيض حل "A" الشرعي إلى "الوقت الخطي".
أولا، أشياء تعلمتها:
بفضل إجابة ديف ويب و إجابة ammoq. وبعد المشكلة هي في الواقع امتداد لمشكلة مسار هاميلتون، كما أنها صلبة NP. لا يوجد حل "سهل" لتبدأ به. هناك لغز مشهور من جولة نايت التي هي ببساطة نفس المشكلة مع حجم مختلف من اللوحة / الشبكة وقواعد اجتياز مختلفة. هناك العديد من الأشياء قلت وفعلت لتوضيح المشكلة والمنهجيات والخوارزميات قد تم ابتكارها.
بفضل جو إجابة. وبعد يمكن التعامل مع المشكلة في إحساس من الأسفل ويمكن تقليلها إلى مشاكل قابلة للحل. يمكن توصيل المشكلات الفرعية التي تم حلها في فكرة نقطة الخروج (نقطة الخروج يمكن توصيلها بموجب نقطة الدخول الأخرى) بحيث يمكن حل المشكلة الرئيسية كدستور بمشاكل النطاق الأصغر. هذا النهج سليم وعملية ولكن غير كاملة، رغم ذلك. لا يمكن ضمان العثور على إجابة إذا كان موجودا.
عند البحث الضابط الرائع، فيما يلي النقاط الرئيسية التي قمت بتطويرها على الكود:
خوارزمية Warnsdorff.: هذه الخوارزمية هي النقطة الرئيسية للوصول إلى عدد مفيد من الحلول بطريقة سريعة. ينص ببساطة على أنه، يجب عليك اختيار نقلك المقبل إلى مكان "الأقل الوصول إليها" وملء قائمة "الذهاب" الخاصة بك مع ترتيب تصاعدي أو تسوية. أقل مكان يمكن الوصول إليه يعني المكان بأقل عدد ممكن من التحركات التالية.
أدناه هو pseudocode (من ويكيبيديا):
بعض التعاريف:
- يمكن الوصول إلى الوظيفة Q من موقع P إذا كان P يمكن أن ينتقل إلى Q بواسطة تحريك فارس واحد، و Q لم تتم زيارةه بعد.
- إمكانية الوصول إلى الموقف ف هو عدد المواقف التي يمكن الوصول إليها من P.
خوارزمية:
قم بتعيين P ليكون موضعا أوليا عشوائيا على اللوحة يمثل اللوحة في P مع رقم الخطوة "1" لكل رقم خطوة من 2 إلى عدد المربعات الموجودة على اللوحة، دعونا مجموعة من المواقف التي يمكن الوصول إليها من موضع الإدخال قم بتعيين P ليكون الموقف من خلال الحد الأدنى من إمكانية الوصول إلى الحد الأدنى من اللوحة في P مع إرجاع رقم الحركة الحالي، سيتم وضع علامة على كل مربعة مع رقم الحركة الذي تمت زيارته.
- التحقق من الجزر: لقد أثبتت استغلال نطيف معرفة المجال هنا أنها مفيدة. إذا كانت خطوة (ما لم تكن الأخيرة) تسبب أي من جيرانها لتصبح جزيرة، أي لا يمكن الوصول إليها من قبل أي شيء آخر، ثم لم يعد هذا الفرع محققته. يوفر قدر كبير من الوقت (25٪ تقريبا) جنبا إلى جنب مع خوارزمية Warnsdorff.
وهنا رمز بلدي في بيثون يحل اللغز (إلى درجة مقبولة بالنظر إلى أن المشكلة صعبة NP). الرمز سهل الفهم لأنني أعتبر نفسي في مستوى المبتدئين في بيثون. التعليقات واضحة في شرح التنفيذ. يمكن عرض الحلول على شبكة بسيطة من قبل واجهة المستخدم الرسومية الأساسية (إرشادات في التعليمات البرمجية).
# Solve square puzzle
import operator
class Node:
# Here is how the squares are defined
def __init__(self, ID, base):
self.posx = ID % base
self.posy = ID / base
self.base = base
def isValidNode(self, posx, posy):
return (0<=posx<self.base and 0<=posy<self.base)
def getNeighbors(self):
neighbors = []
if self.isValidNode(self.posx + 3, self.posy): neighbors.append(self.posx + 3 + self.posy*self.base)
if self.isValidNode(self.posx + 2, self.posy + 2): neighbors.append(self.posx + 2 + (self.posy+2)*self.base)
if self.isValidNode(self.posx, self.posy + 3): neighbors.append(self.posx + (self.posy+3)*self.base)
if self.isValidNode(self.posx - 2, self.posy + 2): neighbors.append(self.posx - 2 + (self.posy+2)*self.base)
if self.isValidNode(self.posx - 3, self.posy): neighbors.append(self.posx - 3 + self.posy*self.base)
if self.isValidNode(self.posx - 2, self.posy - 2): neighbors.append(self.posx - 2 + (self.posy-2)*self.base)
if self.isValidNode(self.posx, self.posy - 3): neighbors.append(self.posx + (self.posy-3)*self.base)
if self.isValidNode(self.posx + 2, self.posy - 2): neighbors.append(self.posx + 2 + (self.posy-2)*self.base)
return neighbors
# the nodes go like this:
# 0 => bottom left
# (base-1) => bottom right
# base*(base-1) => top left
# base**2 -1 => top right
def solve(start_nodeID, base):
all_nodes = []
#Traverse list is the list to keep track of which moves are made (the id numbers of nodes in a list)
traverse_list = [start_nodeID]
for i in range(0, base**2): all_nodes.append(Node(i, base))
togo = dict()
#Togo is a dictionary with (nodeID:[list of neighbors]) tuples
togo[start_nodeID] = all_nodes[start_nodeID].getNeighbors()
solution_count = 0
while(True):
# The search is exhausted
if not traverse_list:
print "Somehow, the search tree is exhausted and you have reached the divine salvation."
print "Number of solutions:" + str(solution_count)
break
# Get the next node to hop
try:
current_node_ID = togo[traverse_list[-1]].pop(0)
except IndexError:
del togo[traverse_list.pop()]
continue
# end condition check
traverse_list.append(current_node_ID)
if(len(traverse_list) == base**2):
#OMG, a solution is found
#print traverse_list
solution_count += 1
#Print solution count at a steady rate
if(solution_count%100 == 0):
print solution_count
# The solution list can be returned (to visualize the solution in a simple GUI)
#return traverse_list
# get valid neighbors
valid_neighbor_IDs = []
candidate_neighbor_IDs = all_nodes[current_node_ID].getNeighbors()
valid_neighbor_IDs = filter(lambda id: not id in traverse_list, candidate_neighbor_IDs)
# if no valid neighbors, take a step back
if not valid_neighbor_IDs:
traverse_list.pop()
continue
# if there exists a neighbor which is accessible only through the current node (island)
# and it is not the last one to go, the situation is not promising; so just eliminate that
stuck_check = True
if len(traverse_list) != base**2-1 and any(not filter(lambda id: not id in traverse_list, all_nodes[n].getNeighbors()) for n in valid_neighbor_IDs): stuck_check = False
# if stuck
if not stuck_check:
traverse_list.pop()
continue
# sort the neighbors according to accessibility (the least accessible first)
neighbors_ncount = []
for neighbor in valid_neighbor_IDs:
candidate_nn = all_nodes[neighbor].getNeighbors()
valid_nn = [id for id in candidate_nn if not id in traverse_list]
neighbors_ncount.append(len(valid_nn))
n_dic = dict(zip(valid_neighbor_IDs, neighbors_ncount))
sorted_ndic = sorted(n_dic.items(), key=operator.itemgetter(1))
sorted_valid_neighbor_IDs = []
for (node, ncount) in sorted_ndic: sorted_valid_neighbor_IDs.append(node)
# if current node does have valid neighbors, add them to the front of togo list
# in a sorted way
togo[current_node_ID] = sorted_valid_neighbor_IDs
# To display a solution simply
def drawGUI(size, solution):
# GUI Code (If you can call it a GUI, though)
import Tkinter
root = Tkinter.Tk()
canvas = Tkinter.Canvas(root, width=size*20, height=size*20)
#canvas.create_rectangle(0, 0, size*20, size*20)
canvas.pack()
for x in range(0, size*20, 20):
canvas.create_line(x, 0, x, size*20)
canvas.create_line(0, x, size*20, x)
cnt = 1
for el in solution:
canvas.create_text((el % size)*20 + 4,(el / size)*20 + 4,text=str(cnt), anchor=Tkinter.NW)
cnt += 1
root.mainloop()
print('Start of run')
# it is the moment
solve(0, 10)
#Optional, to draw a returned solution
#drawGUI(10, solve(0, 10))
raw_input('End of Run...')
شكرا لجميع الجميع يشاركون معرفتهم وأفكارهم.
نصائح أخرى
هذا يشبه جدا جولة نايت المشكلة التي تتعلق تحريك فارس حول لوحة الشطرنج دون إعادة النظر في نفس المربع. في الأساس هي نفس المشكلة ولكن مع "قواعد اجتياز" مختلفة.
التحسين الرئيسي الذي أتذكره من معالجة جولة الفرسان بشكل متكرر يتطلب التحركات التالية في ترتيب متزايد لعدد التحركات المتاحة على مربع الوجهة. هذا يشجع البحث على المحاولة والتحرك بشكل كبير في منطقة واحدة وملء ذلك بدلا من التكبير في جميع أنحاء المجلس وترك مربعات الجزيرة الصغيرة التي لا يمكن زيارةها أبدا. (هذا هو خوارزمية Warnsdorff..)
تأكد أيضا من أنك رأيت التماثل حيث يمكنك ذلك. على سبيل المثال، عند أبسط مستوى X و Y من مربع البداية تحتاج فقط إلى الحصول على ما يصل إلى 5 نظرا لأن (10،10) هو نفسه (1،1) مع المستنقع.
قررت أن ننظر إلى المشكلة ومعرفة ما إذا كان بإمكاني كسرها في حلول 5 × 5 مع إنهاء محلول قفزة واحدة من زاوية أخرى.
الافتراض الأول كان ذلك 5x5 قابل للحل. إنه وبسرعة.
لذلك ركضت حل (0،5) ونظرت إلى النتائج. ووجهت شبكة رقمية 10x10 في Excel مع شبكة رقمية 5x5 للترجمة. ثم بحثت للتو النتائج عن #] (الخلايا المنتهية) التي ستكون قفزة بعيدا عن بداية 5x5 القادمة. (السابقين. للمربع الأول، بحثت عن "13].)
كمرجع:
10 x 10 grid 5 x 5 grid
0 1 2 3 4 | 5 6 7 8 9 0 1 2 3 4
10 11 12 13 14 | 15 16 17 18 19 5 6 7 8 9
20 21 22 23 24 | 25 26 27 28 29 10 11 12 13 14
30 31 32 33 34 | 35 36 37 38 39 15 16 17 18 19
40 41 42 43 44 | 45 46 47 48 49 20 21 22 23 24
---------------+---------------
50 51 52 53 54 | 55 56 57 58 59
60 61 62 63 64 | 65 66 67 68 69
70 71 72 73 74 | 75 76 77 78 79
80 81 82 83 84 | 85 86 87 88 89
90 91 92 93 94 | 95 96 97 98 99
إليك حل ممكن:
المربع الأول: [0، 15، 7، 19، 16، 1، 4، 12، 20، 23، 8، 5، 17، 2، 10، 22، 14، 11، 3، 18، 6، 9، 24، 24، 24، 24، 24، 24، 24، 21، 13] يضعها قفزة قطرية تصل إلى 5 (في 10x10) في الزاوية الأولى من 5 × 5 القادمة.
المربع الثاني: [0، 12، 24، 21، 6، 9، 17، 2، 14، 22، 7، 15، 18، 3، 11، 23، 20، 5، 8، 16، 19، 4، 1، 1، 1، 1، 13، 10] يضعها مع المربع الأخير من 25 في 10x10، وهو ما يقفزان بعيدا عن 55.
المربع الثالث: [0، 12، 24، 21، 6، 9، 17، 5، 20، 23، 8، 16، 19، 4، 1، 13، 10، 2، 14، 11، 3، 18، 15، 7، 22] يضعها مع المربع الأخير من 97 في 10x10، وهو ما يقفزان بعيدا عن 94.
يمكن أن يكون المربع الرابع أي حل صالح، لأن نقطة النهاية لا يهم. ومع ذلك، فإن تعيين الحل من 5x5 إلى 10x10 أصعب، حيث بدأ المربع في الزاوية المعاكسة. بدلا من الترجمة، ران حل (24،5) واختار عشوائيا: [24، 9، 6، 21، 13، 10، 2، 17، 5، 20، 23، 8، 16، 1، 4، 12، 0، 15، 18، 3، 11، 14، 22، 7، 19
يجب أن يكون هذا ممكنا جميعا القيام به برمجيا، والآن بعد أن تعرف حلول 5x5 سارية المفعول بنقاط النهاية التحركات القانونية إلى الزاوية 5x5 التالية. عدد حلول 5 × 5 كانت 552، مما يعني تخزين الحلول لمزيد من الحسابات وإعادة الدعم سهلة للغاية.
ما لم أكن هذا خطأ، إلا أن هذا يمنحك حلا واحدا ممكنا (يعرف عن حلول 5 × 5 كواحد من أربعة على التوالي):
def trans5(i, col5, row5):
if i < 5: return 5 * col5 + 50 * row5 + i
if i < 10: return 5 + 5 * col5 + 50 * row5 + i
if i < 15: return 10 + 5 * col5 + 50 * row5 + i
if i < 20: return 15 + 5 * col5 + 50 * row5 + i
if i < 25: return 20 + 5 * col5 + 50 * row5 + i
>>> [trans5(i, 0, 0) for i in one] + [trans5(i, 1, 0) for i in two] + [trans5(i, 0, 1) for i in three] + [trans5(i, 1, 1) for i in four]
[0, 30, 12, 34, 31, 1, 4, 22, 40, 43, 13, 10, 32, 2, 20, 42, 24, 21, 3, 33, 11, 14, 44, 41, 23, 5, 27, 49, 46, 16, 19, 37, 7, 29, 47, 17, 35, 38, 8, 26, 48, 45, 15, 18, 36, 39, 9, 6, 28, 25, 50, 72, 94, 91, 61, 64, 82, 60, 90, 93, 63, 81, 84, 54, 51, 73, 70, 52, 74, 71, 53, 83, 80, 62, 92, 99, 69, 66, 96, 78, 75, 57, 87, 65, 95, 98, 68, 86, 56, 59, 77, 55, 85, 88, 58, 76, 79, 97, 67, 89]
يمكن أن تحقق بعض واحد المزدوج المنهجية؟ أعتقد أن هذا حل صالح وطريقة كسر المشكلة.
هذا هو مجرد مثال على http://en.wikipedia.org/wiki/hamilton_path. مشكلة. ويكيبيديا الألمانية يدعي أنها NP-Hard.
يمكن أن يتم تحسين التحسين من أجل التحقق من الجزر (أي المساحات غير الزائدة دون جيران صالحين.) والخروج من العبس حتى يتم القضاء على الجزيرة. سيحدث هذا بالقرب من الجانب "الرخيص" من شجرة معينة اجتياز. أعتقد أن السؤال هو إذا كان الحد يستحق المصاريف.
أردت أن أرى ما إذا كان بإمكاني كتابة برنامج من شأنه أن يأتي بكل الحلول الممكنة.
#! /usr/bin/env perl
use Modern::Perl;
{
package Grid;
use Scalar::Util qw'reftype';
sub new{
my($class,$width,$height) = @_;
$width ||= 10;
$height ||= $width;
my $self = bless [], $class;
for( my $x = 0; $x < $width; $x++ ){
for( my $y = 0; $y < $height; $y++ ){
$self->[$x][$y] = undef;
}
}
for( my $x = 0; $x < $width; $x++ ){
for( my $y = 0; $y < $height; $y++ ){
$self->[$x][$y] = Grid::Elem->new($self,$x,$y);;
}
}
return $self;
}
sub elem{
my($self,$x,$y) = @_;
no warnings 'uninitialized';
if( @_ == 2 and reftype($x) eq 'ARRAY' ){
($x,$y) = (@$x);
}
die "Attempted to use undefined var" unless defined $x and defined $y;
my $return = $self->[$x][$y];
die unless $return;
return $return;
}
sub done{
my($self) = @_;
for my $col (@$self){
for my $item (@$col){
return 0 unless $item->visit(undef);
}
}
return 1;
}
sub reset{
my($self) = @_;
for my $col (@$self){
for my $item (@$col){
$item->reset;
}
}
}
sub width{
my($self) = @_;
return scalar @$self;
}
sub height{
my($self) = @_;
return scalar @{$self->[0]};
}
}{
package Grid::Elem;
use Scalar::Util 'weaken';
use overload qw(
"" stringify
eq equal
== equal
);
my %dir = (
# x, y
n => [ 0, 2],
s => [ 0,-2],
e => [ 2, 0],
w => [-2, 0],
ne => [ 1, 1],
nw => [-1, 1],
se => [ 1,-1],
sw => [-1,-1],
);
sub new{
my($class,$parent,$x,$y) = @_;
weaken $parent;
my $self = bless {
parent => $parent,
pos => [$x,$y]
}, $class;
$self->_init_possible;
return $self;
}
sub _init_possible{
my($self) = @_;
my $parent = $self->parent;
my $width = $parent->width;
my $height = $parent->height;
my($x,$y) = $self->pos;
my @return;
for my $dir ( keys %dir ){
my($xd,$yd) = @{$dir{$dir}};
my $x = $x + $xd;
my $y = $y + $yd;
next if $y < 0 or $height <= $y;
next if $x < 0 or $width <= $x;
push @return, $dir;
$self->{$dir} = [$x,$y];
}
return @return if wantarray;
return \@return;
}
sub list_possible{
my($self) = @_;
return unless defined wantarray;
# only return keys which are
my @return = grep {
$dir{$_} and defined $self->{$_}
} keys %$self;
return @return if wantarray;
return \@return;
}
sub parent{
my($self) = @_;
return $self->{parent};
}
sub pos{
my($self) = @_;
my @pos = @{$self->{pos}};
return @pos if wantarray;
return \@pos;
}
sub visit{
my($self,$v) = @_;
my $return = $self->{visit} || 0;
$v = 1 if @_ == 1;
$self->{visit} = $v?1:0 if defined $v;
return $return;
}
sub all_neighbors{
my($self) = @_;
return $self->neighbor( $self->list_possible );
}
sub neighbor{
my($self,@n) = @_;
return unless defined wantarray;
return unless @n;
@n = map { exists $dir{$_} ? $_ : undef } @n;
my $parent = $self->parent;
my @return = map {
$parent->elem($self->{$_}) if defined $_
} @n;
if( @n == 1){
my($return) = @return;
#die unless defined $return;
return $return;
}
return @return if wantarray;
return \@return;
}
BEGIN{
for my $dir ( qw'n ne e se s sw w nw' ){
no strict 'refs';
*$dir = sub{
my($self) = @_;
my($return) = $self->neighbor($dir);
die unless $return;
return $return;
}
}
}
sub stringify{
my($self) = @_;
my($x,$y) = $self->pos;
return "($x,$y)";
}
sub equal{
my($l,$r) = @_;
"$l" eq "$r";
}
sub reset{
my($self) = @_;
delete $self->{visit};
return $self;
}
}
# Main code block
{
my $grid = Grid->new();
my $start = $grid->elem(0,0);
my $dest = $grid->elem(-1,-1);
my @all = solve($start,$dest);
#say @$_ for @all;
say STDERR scalar @all;
}
sub solve{
my($current,$dest,$return,@stack) = @_;
$return = [] unless $return;
my %visit;
$visit{$_} = 1 for @stack;
die if $visit{$current};
push @stack, $current->stringify;
if( $dest == $current ){
say @stack;
push @$return, [@stack];
}
my @possible = $current->all_neighbors;
@possible = grep{
! $visit{$_}
} @possible;
for my $next ( @possible ){
solve($next,$dest,$return,@stack);
}
return @$return if wantarray;
return $return;
}
جاء هذا البرنامج بأكثر من 100000 حلول ممكنة قبل إنهاءه. أرسلت STDOUT إلى ملف، وكان أكثر من 200 ميغابايت.
يمكنك حساب عدد الحلول بالضبط مع خوارزمية البرمجة الديناميكية الخطية.
